You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules
Contributor:
Catoni, Olivier
imprint:
Institute of Mathematical Statistics, 1992
Published in:The Annals of Probability
Language:
English
ISSN:
0091-1798
Origination:
Footnote:
Description:
<p>Simulated annealing algorithms are time inhomogeneous controlled Markov chains used to search for the minima of energy functions defined on finite state spaces. The control parameters, the so-called cooling schedule, control the probability that the energy should increase during one step of the algorithm. Most of the studies on simulated annealing have dealt with limit theorems, such as characterizing convergence conditions on the cooling schedule, or giving an equivalent of the law of the process for one fixed cooling schedule. In this paper we derive finite time estimates. These estimates are uniform in the cooling schedule and in the energy function. With new technical tools, we gain a new insight into the algorithm. We give a sharp upper bound for the probability that the energy is close to its minimum value. Hence we characterize the optimal convergence rate. This involves a new constant, the "difficulty" of the energy landscape. We calculate two cooling schedules for which our bound is almost reached. In one case it is reached up to a multiplicative constant for one energy function. In the other case it is reached in the sense of logarithmic equivalence uniformly in the energy function. These two schedules are both triangular: There is one different schedule for each finite simulation time. For each fixed finite time the second schedule has the currently used but previously mathematically unjustified exponential form. Finally, the title is "Rough large deviation estimates" because we have computed sharper ones (i.e., with sharp multiplicative constants) in two other papers.</p>