Piecewise constant triangular cooling schedules for generalized simulated annealing algorithms
Open Access
- 1 May 1998
- journal article
- Published by Institute of Mathematical Statistics in The Annals of Applied Probability
- Vol. 8 (2) , 375-396
Abstract
We investigate how to tune a generalized simulated annealing algorithm with piecewise constant cooling schedule to get an optical convergence exponent. The optimal convergence exponent of generalized simulated annealing algorithms has been computed by Catoni and Trouvé. It is reached only with triangular sequences of temperatures, meaning that different finite sequences are used, depending on the time resource available for computations (expressed by an overall number of iterations). We show first that it is possible to get close to the optimal convergence exponent uniformly over suitably bounded families of energy landscapes using a fixed number of temperature steps. Then we show that, letting the number of steps increase with the time resource, we can build a cooling schedule which is universally robust with respect to the convergence exponent: a fixed triangular sequence of temperatures gives an optimal convergence exponent for any energy landscape. Piecewise constant temperature sequences are often used in practice: in favourable cases, the use of the same temperature during a large number of iterations allows tabulating the exponential penalties appearing in the transition matrix, thus sparing a significant amount of computer time. The proofs we give rely on Freidlin and Wentzell's closed formulas for the exit time and point from subdomains of time homogeneous Markov chains.Keywords
This publication has 17 references indexed in Scilit:
- The energy transformation method for the Metropolis algorithm compared with Simulated AnnealingProbability Theory and Related Fields, 1998
- The exit path of a Markov chain with rare transitionsESAIM: Probability and Statistics, 1997
- Sur les problèmes de sortie discrets inhomogènesThe Annals of Applied Probability, 1996
- $L^2$ Convergence of Time Nonhomogeneous Markov Processes: I. Spectral EstimatesThe Annals of Applied Probability, 1994
- Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential SchedulesThe Annals of Probability, 1992
- Singular perturbed Markov chains and exact behaviors of simulated annealing processesJournal of Theoretical Probability, 1992
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- A Limit Theorem for a Class of Inhomogeneous Markov ProcessesThe Annals of Probability, 1989
- Simulated annealing via Sobolev inequalitiesCommunications in Mathematical Physics, 1988
- Optimization by Simulated AnnealingScience, 1983