Laws of large numbers for the annealing algorithm

DOI10.1016/0304-4149(90)90009-HMaRDI QIDQ751733zbMATH OpenWikidataFDO

Authors Nina Gantert

Publication date 1990

Published in Stochastic Processes and their Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-4149(90)90009-H

zbMATH Keywords

laws of large numbers for time-inhomogeneous Markov chainssimulated annealing

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Strong limit theorems (60F15) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Review text

A convergence of the algorithm of simulated annealing is considered. First, an error in the paper of \textit{B. Gidas} [J. Stat. Phys. 39, 73-131 (1985; Zbl 0642.60049)] is pointed out. Next, well-known laws of large numbers for time-inhomogeneous Markov chains are applied. Assumptions formulated in terms of Dobrushin contraction coefficients lead to appropriate cooling constant. Namely, in the cooling scheme \(\beta (n)=\gamma \log n\) weak LLN holds for \(\gamma <\gamma_ 0\) and strong LLN holds for \(\gamma <\gamma_ 0/2\) with some given \(\gamma_ 0\).

Recommendations

• scientific article; zbMATH DE number 4052685
• Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms
• scientific article; zbMATH DE number 1759479
• Rough large deviation estimates for simulated annealing: Application to exponential schedules
• Sharp large deviations estimates for simulated annealing algorithms

Cites work

• scientific article; zbMATH DE number 3126887 (Why is no real title available?)
• scientific article; zbMATH DE number 3519671 (Why is no real title available?)
• scientific article; zbMATH DE number 3309776 (Why is no real title available?)
• Nonstationary Markov chains and convergence of the annealing algorithm
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images

Cited in

(7)

• Applications of sharp large deviations estimates to optimal cooling schedules
• On discrete inhomogeneous exit problems
• Turning a coin over instead of tossing it
• Remarks on the ergodicity of simulated annealing algorithms on a graph
• scientific article; zbMATH DE number 4052685 (Why is no real title available?)
• Annealing of Iterative Stochastic Schemes
• Stick-breaking processes, clumping, and Markov chain occupation laws

This page was built for publication: Laws of large numbers for the annealing algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751733)