Applications of sharp large deviations estimates to optimal cooling schedules

 Access to full text

 Full (PDF)

1. [1] R. Azencott, Simulated Annealing, Séminaire Bourbaki, 40e année, 1987–1988, No 697, June 88. Zbl0687.60086MR992211
2. [2] O. Catoni, Grandes déviations et décroissance de la température dans les algorithmes de recuit, C. R. Acad. Sci. Paris, T. 307, Series I, 1988, pp. 535-538. Zbl0645.60035MR966258
3. [3] O. Catoni, Rough Large Deviations Estimates for Simulated Annealing. Application to Exponential Schedules, preprint, Annals Prob., March 1990 (to appear). Zbl0755.60021MR1175253
4. [4] O. Catoni, Sharp Large Deviations Estimates for Simulated Annealing Algorithms, preprint, Ann. Inst. Henri Poincaré, Prob. Stat., March 1990 (to appear). Zbl0746.60024MR1131838
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. Control and Optimization, Vol. 26, No. 6, Nov. 1988. Zbl0665.60090MR969338
7. [7] R.L. Dobrushin, Central Limit Theorems for Non-Stationary Markov Chain, 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. Geman and D. Geman, Stochastic Relaxation, Gibbs Distribution, and the Bayesian Restoration of Images, I.E.E.E. Transactions on Pattern Analysis and Machine Intelligence, Vol. 6, 1984, p. 721-741. Zbl0573.62030
10. [10] B. Gidas, Non-Stationary Markov Chains and Convergence of the Annealing Algorithms, J. Stat. Phys., Vol. 39, 1985, p. 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, J. Funct. Anal., 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 Behaviors of Simulated Annealing Process, preprint, J. Theoret. Proba. (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., 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. O. Catoni, Sharp large deviations estimates for simulated annealing algorithms
2. Olivier Catoni, Raphaël Cerf, The exit path of a Markov chain with rare transitions