Simulated annealing from continuum to discretization: a convergence analysis via the Eyring--Kramers law

Abstract

We study the convergence rate of continuous-time simulated annealing $(X_t;t\ge 0)$ and its discretization $(x_k;k=0,1,\dots )$ for approximating the global optimum of a given function $f$. We prove that the tail probability $\mathbb{P}(f(X_t)>\min f+\delta )$ (resp. $\mathbb{P}(f(x_k)>\min f+\delta )$) decays polynomial in time (resp. in cumulative step size), and provide an explicit rate as a function of the model parameters. Our argument applies the recent development on functional inequalities for the Gibbs measure at low temperatures -- the Eyring-Kramers law. In the discrete setting, we obtain a condition on the step size to ensure the convergence.

19 pages, 1 figure

References in corpus (1)

• Levy Flights, Non-local Search and Simulated Annealing