Diffusions for Global Optimization

Abstract

We seek a global minimum of U:(0, 1)"-. R. The solution to (d/dt)x,=-VU(xt) will find local minima. The solution to dxt =-V U(xt) dt+ dw,, where w is standard (n-dimensional) Brownian motion and the boundaries are reflecting, will concentrate near the global minima of U, at least when "temperature" T is small: the equilibrium distribution for xt is Gibbs with density 'r(x)a exp {-U(x)/T}. This suggests setting T T(t)0 to find the global minima of U. We give conditions on U(x) and T(t) such that the solution to dxt=-V U(xt)dt+x/ dw converges weakly to a distribution concentrated on the global minima of U.