FAST STOCHASTIC GLOBAL OPTIMIZATION

A new stochastic optimization strategy is introduced which cascades many Metropolis-like procedures to sample a Boltzmann distribution at fixed temperatures. Global optimization of an objective f(x) in a certain class is shown to require 0 ((DELTA/T(low))2) CoMpUtational effort where DELTA = max(x,x') (f(x) - f(c')) and T(low) is a low enough temperature that the Boltzmann function of f at T(low) acceptably small except for optimal x. This theoretical advantage is confirmed by experimental results which are presented for a problem in vector quantization and for seven standard test problems in nonlinear optimization.