×

Simulated annealing algorithms and Markov chains with rare transitions. (English) Zbl 0944.90053

Azéma, Jacques (ed.) et al., Séminaire de probabilités XXXIII. Berlin: Springer. Lect. Notes Math. 1709, 69-119 (1999).
Summary: In these notes written for a D.E.A. course at University Paris XI during the first term of 1995, we prove the essentials about stochastic optimisation algorithms based on Markov chains with rare transitions, under the weak assumption that the transition matrix obeys a large deviation principle. We present a new simplified line of proofs based on the Freidlin and Wentzell graphical approach. The case of Markov chains with a periodic behaviour at null temperature is considered. We have also included some pages about the spectral gap approach where we follow P. Diaconis and D. Stroock [Ann. Appl. Probab. 1, 36-61 (1991; Zbl 0731.60061)] and S. Ingrassia [Ann. Appl. Probab. 4, 347-389 (1994; Zbl 0802.60061)] in a more conventional way, except for the application to non reversible Metropolis algorithms (subsection 6.2.2) where we present an original result.
For the entire collection see [Zbl 0924.00016].

MSC:

90C15 Stochastic programming
90C40 Markov and semi-Markov decision processes
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: Numdam EuDML