Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-18T08:27:16.642Z Has data issue: false hasContentIssue false
  • English
  • Français

Convergence of simulated annealing using Foster-Lyapunov criteria

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

Published online by Cambridge University Press:  14 July 2016

Christophe Andrieu ,
Laird A. Breyer  and
Arnaud Doucet
Christophe Andrieu*
Affiliation:
University of Bristol
Laird A. Breyer*
Affiliation:
Lancaster University
Arnaud Doucet*
Affiliation:
University of Melbourne
*
∗ Postal address: Department of Mathematics, Statistics Group, University of Bristol, University Walk, Bristol BS8 1TW, UK. Email address: [email protected]
∗∗ Postal address: Department of Mathematics and Statistics, Fylde College, Lancaster University, Lancaster LA1 4YF, UK.
∗∗∗ Postal address: Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Victoria 3010, Australia.
Get access Rights & Permissions [Opens in a new window]

Abstract

Simulated annealing is a popular and much studied method for maximizing functions on finite or compact spaces. For noncompact state spaces, the method is still sound, but convergence results are scarce. We show here how to prove convergence in such cases, for Markov chains satisfying suitable drift and minorization conditions.

Keywords

Simulated annealingMarkov chain Monte CarlooptimizationFoster-Lyapunovnonhomogeneous Markov chain

MSC classification

Primary: 60J27: Continuous-time Markov processes on discrete state spaces
Secondary: 65C40: Computational Markov chains
Type
Research Papers
Information
Journal of Applied Probability , Volume 38 , Issue 4 , December 2001 , pp. 975 - 994
Copyright
Copyright © by the Applied Probability Trust 2001 

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

Andrieu, C., and Doucet, A. (2000). Simulated annealing for maximum a posteriori parameter estimation of hidden Markov models. IEEE Trans. Inf. Theory 46, 994–1004.Google Scholar
Billingsley, P. (1985). Probability and Measure, 2nd edn. John Wiley, Chichester.Google Scholar
Fort, G. and Moulines, É. (2000). V-subgeometric ergodicity for a Hastings–Metropolis algorithm. Statist. Prob. Lett. 49, 401–410.Google Scholar
Fort, G., Moulines, É., and Roberts, G. O. (2001). A geometrically ergodic hybrid sampler for sub-exponential densities. Submitted.Google Scholar
Gelfand, S. B., and Mitter, S. K. (1993). Metropolis-type annealing algorithms for global optimization in R d . SIAM J. Control Optimization 31, 111–131.Google Scholar
Geman, S., and Geman, D. (1984). Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intellig. 6, 721–741.Google Scholar
Haario, A., and Saksman, E. (1991). Simulated annealing in general state space. Adv. Appl. Prob. 23, 866–893.Google Scholar
Hwang, C. (1980). Laplace's method revisited: weak convergence of probability measures. Ann. Prob. 8, 1177–1182.CrossRefGoogle Scholar
Jarner, S. F., and Hansen, E. (1998). Geometric ergodicity of Metropolis algorithms. Stoch. Process. Appl. 85, 341–361.Google Scholar
Jarner, S. F., and Roberts, G. (2001). Polynomial convergence rates of Markov chains. To appear in Ann. Appl. Prob.Google Scholar
Lindvall, T. (1992). Lectures on the Coupling Method. John Wiley, New York.Google Scholar
Locatelli, M. (2000). Simulated annealing algorithms for continuous global optimization: convergence conditions. J. Optimization Theory Appl. 104, 121–133.Google Scholar
Mengersen, K. L., and Tweedie, R. L. (1994). Rates of convergence of the Hastings and Metropolis algorithm. Ann. Statist. 24, 101–121.Google Scholar
Meyn, S. P., and Tweedie, R. L. (1993). Markov Chains and Stochastic Stability. Springer, Berlin.CrossRefGoogle Scholar
Mitra, D., Romeo, F., and Sangiovanni-Vincentelli, A. (1986). Convergence and finite-time behavior of simulated annealing. Adv. Appl. Prob. 18, 747–771.Google Scholar
Roberts, G. O., and Rosenthal, J. S. (1998). Two convergence properties of hybrid samplers. Ann. Appl. Prob. 8, 397–407.Google Scholar
Roberts, G. O., and Tweedie, R. L. (1996). Exponential convergence of Langevin diffusions and their discrete approximations. Bernoulli 2, 341–364.Google Scholar
Roberts, G. O., and Tweedie, R. L. (1996). Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms. Biometrika 83, 96–110.Google Scholar
Roberts, G. O., and Tweedie, R. L. (1999). Bounds on regeneration times and convergence rates for Markov chains. Stoch. Process. Appl. 80, 211–229.Google Scholar
Rosenthal, J. S. (1995). Minorization conditions and convergence rates for Markov chain Monte Carlo. J. Amer. Statist. Assoc. 90, 558–566.CrossRefGoogle Scholar
Tweedie, R., and Stramer, O. (1999). Langevin-type models I: diffusions with given stationary distributions, and their discretizations. Methodology Comput. Appl. Prob. 1, 283–306.Google Scholar
Tweedie, R., and Stramer, O. (1999). Langevin-type models II: self-targeting candidates for MCMC algorithms. Methodology Comput. Appl. Prob. 1, 307–328.Google Scholar
Tierney, L. (1994). Markov chains for exploring posterior distributions (with discussion). Ann. Statist. 22, 1701–1762.Google Scholar
Van Laarhoven, P. J., and Arts, E. H. L. (1987). Simulated Annealing: Theory and Applications. Reidel, Amsterdam.Google Scholar