Diffusion for Global Optimization in $\mathbb{R}^n $

Abstract

We seek a global minimum of $U:\mathbb{R}^n \to \mathbb{R}$. The solution to $( * )({d / {dt}})X(t) = - \nabla U(X(t))$ will find local minima. Using the idea of simulated annealing, we consider the diffusion process, $dX(t) = - \nabla U(X(t))dt + \sigma (t)dW(t)$, $X(0) = x$, where $W( \cdot )$ is the n-dimensional standard Brownian motion and $\frac{1}{2}\sigma ^2 (t)$ is the annealing rate which decreases to zero as t goes to $\infty $. Under suitable condition on $U(x)$, we prove that $X(t)$ converges weakly to a probability measure $\pi $ if for large t, $\sigma ^2 (t) = {c / {\log t}}$ with $c > c_0 $, where $c_0 $ has a simple expression involving the action function of the dynamical system $( * )$, $\pi $ concentrates on the global minima of U and is the weak limit of the Gibbs densities $\pi _t (x) \propto \exp ({{ - 2U(x)} / {\sigma ^2 (t)}})$. The above result can also be formulated as follows: consider the Fokker–Planck equation (forward equation) \[\frac{\partial }{{\partial t}}V(t,y) = \frac{1}{2}\sigma ^2 (t)\Delta V(t,y) + \nabla \cdot (V(t,y)\nabla U(y))\] with $V(0,y) = \delta _x (y)$. If $\sigma ^2 (t) = {c / {\log t}}$ for large t and $c > c_0 $, then $V(t,y) \to \pi $ weakly.