Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T16:54:35.422Z Has data issue: false hasContentIssue false
  • English
  • Français

Simulated annealing process in general state space

Published online by Cambridge University Press:  01 July 2016

Heikki Haario  and
Eero Saksman
Heikki Haario
Affiliation:
University of Helsinki
Eero Saksman*
Affiliation:
University of Helsinki
*
∗Postal address for both authors: Department of Mathematics, University of Helsinki, Hallituskatu 15,00100 Helsinki, Finland.
Get access Rights & Permissions [Opens in a new window]

Abstract

The stochastic process corresponding to the simulated annealing optimization algorithm is generalized to the case of an arbitrary state space. Conditions for the strong and weak convergence of the process are established. In addition the relation between the size of the generating distributions and the possible rate of cooling is studied.

Keywords

GLOBAL OPTIMIZATIONNON-HOMOGENEOUS MARKOV PROCESSES
Type
Research Article
Information
Advances in Applied Probability , Volume 23 , Issue 4 , December 1991 , pp. 866 - 893
Copyright
Copyright © Applied Probability Trust 1991 

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.)

Footnotes

The work of the second author was partially supported by the Academy of Finland.

References

1. Anily, S. and Federgruen, A. (1987) Simulated annealing methods with general acceptance probabilities. J. Appl. Prob. 24, 657–667.Google Scholar
2. Billingsley, P. (1968) Convergence of Probability Measures. Wiley, New York.Google Scholar
3. Chiang, Tzuu-Shuh and Chow, Yunshyong (1988) On the convergence rate of annealing processes. SIAM J. Control Optim. 26, 1455–1470.Google Scholar
4. Doetsch, G. (1950) Handbuch der Laplace-Transformation , Band 1. Birkhäuser, Basel.Google Scholar
5. Dobrushin, R. (1956) Central limit theorems for non-stationary Markov chains II. Theory Prob. Appl. 1, 329–383.Google Scholar
6. Geman, S. and Geman, D. (1984) Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images. IEEE Proc. Pattern Anal. Mach. Intell. 6, 721–741.Google Scholar
7. Geman, S. and Hwang, C. (1986) Diffusions for global optimization. SIAM J. Control Optim. 24, 1031–1043.Google Scholar
8. Gidas, B. (1985) Non-stationary Markov chains and convergence of the annealing algorithm. J. Statist. Phys. 39, 73–131.Google Scholar
9. Hajek, B. (1988) Cooling schedules for optimal annealing. Math. Operat. Res. 13, 311–329.CrossRefGoogle Scholar
10. Hwang, C. (1980) Laplace's method revisited: weak convergence of probability measures. Ann. Prob. 8, 1177–1182.Google Scholar
11. Isaacson, O. and Madsen, R. (1976) Markov Chains: Theory and Applications. Wiley, New York.Google Scholar
12. Iosifescu, M. (1972) On two recent papers on ergodicity in non-homogeneous Markov chains. Ann. Math. Statist. 43, 1732–1736.CrossRefGoogle Scholar
13. Kushner, H. J. (1987) Asymptotic global behaviour for stochastic approximation and diffusions with slowly decreasing noise effects: global minimization via Monte Carlo. SIAM J. Appl. Math. 47, 169–185.CrossRefGoogle Scholar
14. Van Laarhoven, P. J. M. and Aarts, E. H. L. (1987) Simulated Annealing: Theory and Applications. Mathematics and Its Applications. Reidel, Dordrecht.CrossRefGoogle Scholar