Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-08T15:30:29.627Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved bounds for the large-time behaviour of simulated annealing

Part of: Basic linear algebra Markov processes Probabilistic methods, simulation and stochastic differential equations

Published online by Cambridge University Press:  14 July 2016

Eric Fontenas  and
Olivier François
Eric Fontenas*
Affiliation:
LABSAD, Grenoble
Olivier François*
Affiliation:
Laboratoire TIMC, Grenoble
*
∗Postal address: LABSAD, 1251 Avenue Centrale BP 47, F38040 Grenoble Cedex, France. Email address: [email protected]
∗∗Postal address: Laboratoire TIMC, Faculté de Médecine, F38706 La Tronche Cedex, France.
Get access Rights & Permissions [Opens in a new window]

Abstract

We improve on previous finite time estimates for the simulated annealing algorithm which were obtained from a Cheeger-like approach. Our approach is based on a Poincaré inequality.

Keywords

Simulated annealinggeometric inequalities

MSC classification

Primary: 60J10: Markov chains (discrete-time Markov processes on discrete state spaces) 65C40: Computational Markov chains
Secondary: 15A42: Inequalities involving eigenvalues and eigenvectors
Type
Research Papers
Information
Journal of Applied Probability , Volume 40 , Issue 4 , September 2003 , pp. 961 - 969
Copyright
Copyright © Applied Probability Trust 2003 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aarts, E. H. L., and Korst, J. H. M. (1989). Simulated Annealing and Boltzmann Machines. John Wiley, New York.Google Scholar
Bertsimas, D., and Tsitsiklis, J. (1993). Simulated annealing. Statist. Sci. 8, 10–15.CrossRefGoogle Scholar
Catoni, O. (1999). Simulated annealing algorithms and Markov chains with rare transitions. In Séminaire de Probabilités XXXIII (Lecture Notes Math. 709), eds Azema, J., Emery, M., Ledoux, M. and Yor, M., Springer, Berlin, pp. 69-119.CrossRefGoogle Scholar
Diaconis, P., and Stroock, D. (1991). Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Prob. 1, 36–61.CrossRefGoogle Scholar
Fill, J. A. (1991). Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Prob. 1, 62–87.CrossRefGoogle Scholar
François, O. (2000). Geometric inequalities for the eigenvalues of concentrated Markov chains. J. Appl. Prob. 37, 15–28.CrossRefGoogle Scholar
Hajek, B. (1988). Cooling schedules for optimal annealing. Math. Operat. Res. 13, 311–329.CrossRefGoogle Scholar
Hastings, W. K. (1970). Monte Carlo sampling using Markov chains and their applications. Biometrika 57, 77–109.CrossRefGoogle Scholar
Ingrassia, S. (1994). On the rate of convergence of the Metropolis algorithm and the Gibbs sampler by geometric bounds. Ann. Appl. Prob. 4, 347–389.CrossRefGoogle Scholar
Kirkpatrick, S., Gelatt, C. D. Jr., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science 220, 671–680.Google ScholarPubMed
Lawler, G. F., and Sokal, A. D. (1988). Bounds on the L 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality. Trans. Amer. Math. Soc. 309, 557–580.Google Scholar
Metropolis, M. et al. (1953). Equation of state calculation by fast computing machines. J. Chem. Phys. 21, 1087–1092.CrossRefGoogle Scholar
Mihail, M. (1989). Combinatorial aspects of expanders. Doctoral Thesis, Harvard University.Google Scholar
Mitra, D., Romeo, F., and Sangiovanni-Vincentelli, A. L. (1986). Convergence and finite time behavior of simulated annealing. Adv. Appl. Prob. 18, 747–771.CrossRefGoogle Scholar
Nolte, A., and Schrader, R. (2000). A note on the finite time behavior of simulated annealing. Math. Operat. Res. 25, 476–484.CrossRefGoogle Scholar
Sinclair, A., and Jerrum, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inf. Comput. 82, 93–133.CrossRefGoogle Scholar
Van Laarhoven, P. J. M., and Aarts, E. H. L. (1987). Simulated Annealing: Theory and Applications. Reidel, Dordrecht.CrossRefGoogle Scholar