FAST STOCHASTIC GLOBAL OPTIMIZATION

A new stochastic optimization strategy is introduced which cascades ma ny Metropolis-like procedures to sample a Boltzmann distribution at fi xed temperatures. Global optimization of an objective f(x) in a certai n class is shown to require 0 ((DELTA/T(low))2) CoMpUtational effort w here DELTA = max(x,x') (f(x) - f(c')) and T(low) is a low enough tempe rature that the Boltzmann function of f at T(low) acceptably small exc ept for optimal x. This theoretical advantage is confirmed by experime ntal results which are presented for a problem in vector quantization and for seven standard test problems in nonlinear optimization.