Catoni, Olivier 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]. Cited in 1 ReviewCited in 32 Documents 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 Keywords:stochastic optimization; Markov chains; simulated annealing algorithms Citations:Zbl 0731.60061; Zbl 0802.60061 PDFBibTeX XMLCite \textit{O. Catoni}, Lect. Notes Math. 1709, 69--119 (1999; Zbl 0944.90053) Full Text: Numdam EuDML