Diffusions for Global Optimization
Stuart Geman, Chii-Ruey Hwang · SIAM Journal on Control and Optimization · 1986
We seek a global minimum of $U:[0,1]^n \to R$. The solution to $({d / {dt}})x_t = - \nabla U(x_t )$ will find local minima. The solution to $dx_t = - \nabla U(x_t )dt + \sqrt {2T} dw_t $, 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 $x_t $, is Gibbs with density $\pi _T (x)\alpha \exp \{ - {{U(x)} / T}\} $. This suggests setting $T = T(t) \downarrow 0$, to find the global minima of U. We give conditions on $U(x)$ and $T(t)$ such that the solution to $dx_t = - \nabla U(x_t )dt + \sqrt {2T} dw_t $ converges weakly to a distribution concentrated on the global minima of U.
Cited by 313 works. doi:10.1137/0324060
Authors
References
- Equation of State Calculations by Fast Computing Machines
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
- Elliptic Partial Differential Equations of Second Order
- Markov Processes
- MULTI-DIMENSIONAL DIFFUSION PROCESSES
- Nonstationary Markov chains and convergence of the annealing algorithm
- Global optimization and stochastic differential equations
- Laplace's Method Revisited: Weak Convergence of Probability Measures
- The Langevin Equation as a Global Minimization Algorithm