Sharp large deviations estimates for simulated annealing algorithms

 Access to full text

 Full (PDF)

1. [1] R. Azencott, Simulated Annealing, Séminaire Bourbaki, 40e année, 1987-1988, No. 697, juin 1988. Zbl0687.60086MR992211
2. [2] O. Catoni, Grandes déviations et décroissances de la température dans les algorithmes de recuit, C. R. Acad. Sci. Paris, T. 307, Series I, 1988, p. 535-538. Zbl0645.60035MR966258
3. [3] O. Catoni, Rough Large Deviations Estimates for Simulated Annealing. Application to Exponential Schedules, preprint, Ann.Prob., March 1990 (submitted). Zbl0755.60021MR1175253
4. [4] O. Catoni, Applications of Sharp Large Deviations Estimates to Optimal Cooling Schedules, preprint, Ann. l'I.H.P., March 1990 (submitted). Zbl0752.60025MR1141244
5. [5] O. Catoni, Large Deviations for Annealing, Thesis, University Paris-Sud Orsay, March 1990. 
6. [6] T.S. Chiang and Y. Chow, On the Convergence Rate of Annealing Processes, Siam J. ControlOptimization, Vol. 26, No. 6, November 1988. Zbl0665.60090MR969338
7. [7] R.L. Dobrushin, Central Limit Theorems for Non-Stationary Markov Chains, I, II (english translation) Theor. Prob. Appl., Vol. 1, 1956, pp. 65-80 and 329-383. Zbl0093.15001MR86436
8. [8] M.I. Freidlin and A.D. Wentzell, Random Perturbations of Dynamical Systems, Springer Verlag, 1984. Zbl0522.60055MR722136
9. [9] S. German and D. Geman, Stochastic Relaxation, Gibbs Distribution, and the Bayesian Restoration of images, I.E.E.E. Trans. Pattern Anal. Machine Intelligence, Vol. 6, 1984, pp. 721-741. Zbl0573.62030
10. [10] B. Gidas, Non-Stationary Markov Chains and Convergence of the Annealing Algorithms, J. Stat. Phys., Vol. 39, 1985, pp. 73-131. Zbl0642.60049
11. [11] B. Hajek, Cooling Schedules for Optimal Annealing, Math. Oper. Res., Vol. 13, 1988, pp. 311-329. Zbl0652.65050MR942621
12. [12] R.A. Holley, S. Kusuoka and D.W. Stroock, Asymptotics of the Spectral Gap with Applications to the Theory of Simulated Annealing, Journal of functional analysis, Vol. 83, 1989, pp. 333-347. Zbl0706.58075MR995752
13. [13] R. Holley and D. Stroock, Simulated Annealing via Sobolev Inequalities, Commun. Math. Phys., Vol. 115, 1988, pp. 553-569. Zbl0643.60092MR933455
14. [14] C.R. Hwang and S.J. Sheu, Large Time Behaviours of Perturbed Diffusion Markov Processes with Applications I, II et III, preprints, Institute of Mathematics, Academia Sinica, Tapei, Taiwan, 1986. 
15. [15] C.R. Hwang and S.J. Sheu, Singular Perturbed Markov Chains and Exact Behaviours of Simulated Annealing Process, preprint, J. Theor. Prob., 1988 (submitted). Zbl0755.60047MR1157983
16. [16] C.R. Hwang and S.J. Sheu, On the Weak Reversibility Condition in Simulated Annealing, preprint, Institute of Mathematics, Academia Sinica, Taipei, Taiwan, 1988. MR1045158
17. [17] M. Iosifescu and R. Theodorescu, Random Processes and Learning, Springer Verlag, 1969. Zbl0194.51101
18. [18] D.L. Isaacson and R.W. Madsen, Strongly Ergodic Behaviour for Non-Stationary Markov Processes, Ann. Prob., Vol. 1, 1973, pp. 329-335. Zbl0264.60021MR350858
19. [19] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by Simulated Annealing, Science, Vol. 220, 1983, pp. 621-680. Zbl1225.90162MR702485
20. [20] E. Seneta, Non-Negative Matrices and Markov Chains, second ed., Springer Verlag, 1981. Zbl0471.60001
21. [21] J.N. Tsitsiklis, A Survey of Large Time Asymptotics of Simulated Annealing Algorithms, in Stochastic Differential Systems, Stochastic Control Theory and Applications, W. FLEMING and P. L. LIONS Eds., I.M.A. vol. in mathematics and its applications, Vol. 10, Springer Verlag, 1988. Zbl0657.90097MR934744
22. [22] J.N. Tsitsiklis, Markov Chains with Rare Transitions and Simulated Annealing, Math. Op. Res., Vol. 14, 1989, p. 1. Zbl0664.60067MR984559

1. Olivier Catoni, Applications of sharp large deviations estimates to optimal cooling schedules
2. Laurent Miclo, Une étude des algorithmes de recuit simulé sous-admissibles
3. Olivier Catoni, Raphaël Cerf, The exit path of a Markov chain with rare transitions