Sharp large deviations estimates for simulated annealing algorithms (Q1181803)

From the author's summary freely adapted: Simulated annealing algorithms are Monte Carlo simulations of physical systems where the temperature is a decreasing function of time. The method can be used as a general purpose optimization technique to locate the minima of an arbitrary function defined on a finite but possibly very large set. It can be described as a non-stationary controlled Markov chain. The aim of this paper is to build a large deviation theory in this time-inhomogeneous discrete setting. A careful investigation of the law of the exit point and time from sets is made, based on the Venttsel'-Frejdlin decomposition of the state space into cycles. It is hoped that giving a precise description of how trajectories escape from attractors brings a qualitative contribution to the insight one may have into the behaviour of simulated annealing. The usefulness of the sharp large deviations estimates obtained is illustrated by considering the following topics: convergence to ground states, asymptotical equidistribution on ground states, thermical quasi-equilibrium, and the shape of optimal cooling schedules.