Sharp large deviations estimates for simulated annealing algorithms
Catoni, O.
Annales de l'I.H.P. Probabilités et statistiques, Tome 27 (1991), p. 291-383 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{AIHPB_1991__27_3_291_0,
     author = {Catoni, Olivier},
     title = {Sharp large deviations estimates for simulated annealing algorithms},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     volume = {27},
     year = {1991},
     pages = {291-383},
     mrnumber = {1131838},
     zbl = {0746.60024},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIHPB_1991__27_3_291_0}
}

Catoni, O. Sharp large deviations estimates for simulated annealing algorithms. Annales de l'I.H.P. Probabilités et statistiques, Tome 27 (1991) pp. 291-383. http://gdmltest.u-ga.fr/item/AIHPB_1991__27_3_291_0/

[1] R. Azencott, Simulated Annealing, Séminaire Bourbaki, 40e année, 1987-1988, No. 697, juin 1988. | Numdam | MR 992211 | Zbl 0687.60086

[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. | MR 966258 | Zbl 0645.60035

[3] O. Catoni, Rough Large Deviations Estimates for Simulated Annealing. Application to Exponential Schedules, preprint, Ann.Prob., March 1990 (submitted). | MR 1175253 | Zbl 0755.60021

[4] O. Catoni, Applications of Sharp Large Deviations Estimates to Optimal Cooling Schedules, preprint, Ann. l'I.H.P., March 1990 (submitted). | Numdam | MR 1141244 | Zbl 0752.60025

[5] O. Catoni, Large Deviations for Annealing, Thesis, University Paris-Sud Orsay, March 1990.

[6] T.S. Chiang and Y. Chow, On the Convergence Rate of Annealing Processes, Siam J. Control Optimization, Vol. 26, No. 6, November 1988. | MR 969338 | Zbl 0665.60090

[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. | MR 86436 | Zbl 0093.15001

[8] M.I. Freidlin and A.D. Wentzell, Random Perturbations of Dynamical Systems, Springer Verlag, 1984. | MR 722136 | Zbl 0522.60055

[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. | Zbl 0573.62030

[10] B. Gidas, Non-Stationary Markov Chains and Convergence of the Annealing Algorithms, J. Stat. Phys., Vol. 39, 1985, pp. 73-131. | Zbl 0642.60049

[11] B. Hajek, Cooling Schedules for Optimal Annealing, Math. Oper. Res., Vol. 13, 1988, pp. 311-329. | MR 942621 | Zbl 0652.65050

[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. | MR 995752 | Zbl 0706.58075

[13] R. Holley and D. Stroock, Simulated Annealing via Sobolev Inequalities, Commun. Math. Phys., Vol. 115, 1988, pp. 553-569. | MR 933455 | Zbl 0643.60092

[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] C.R. Hwang and S.J. Sheu, Singular Perturbed Markov Chains and Exact Behaviours of Simulated Annealing Process, preprint, J. Theor. Prob., 1988 (submitted). | MR 1157983 | Zbl 0755.60047

[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. | MR 1045158

[17] M. Iosifescu and R. Theodorescu, Random Processes and Learning, Springer Verlag, 1969. | Zbl 0194.51101

[18] D.L. Isaacson and R.W. Madsen, Strongly Ergodic Behaviour for Non-Stationary Markov Processes, Ann. Prob., Vol. 1, 1973, pp. 329-335. | MR 350858 | Zbl 0264.60021

[19] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by Simulated Annealing, Science, Vol. 220, 1983, pp. 621-680. | MR 702485

[20] E. Seneta, Non-Negative Matrices and Markov Chains, second ed., Springer Verlag, 1981. | Zbl 0471.60001

[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. | MR 934744 | Zbl 0657.90097

[22] J.N. Tsitsiklis, Markov Chains with Rare Transitions and Simulated Annealing, Math. Op. Res., Vol. 14, 1989, p. 1. | MR 984559 | Zbl 0664.60067