Applications of sharp large deviations estimates to optimal cooling schedules

Olivier Catoni

Annales de l'I.H.P. Probabilités et statistiques (1991)

  • Volume: 27, Issue: 4, page 463-518
  • ISSN: 0246-0203

How to cite

top

Catoni, Olivier. "Applications of sharp large deviations estimates to optimal cooling schedules." Annales de l'I.H.P. Probabilités et statistiques 27.4 (1991): 463-518. <http://eudml.org/doc/77414>.

@article{Catoni1991,
author = {Catoni, Olivier},
journal = {Annales de l'I.H.P. Probabilités et statistiques},
keywords = {large deviations; cooling systems of the critical type; annealing algorithm; Asymptotics of the law; Triangular cooling schedules; optimization problem far from the horizon},
language = {eng},
number = {4},
pages = {463-518},
publisher = {Gauthier-Villars},
title = {Applications of sharp large deviations estimates to optimal cooling schedules},
url = {http://eudml.org/doc/77414},
volume = {27},
year = {1991},
}

TY - JOUR
AU - Catoni, Olivier
TI - Applications of sharp large deviations estimates to optimal cooling schedules
JO - Annales de l'I.H.P. Probabilités et statistiques
PY - 1991
PB - Gauthier-Villars
VL - 27
IS - 4
SP - 463
EP - 518
LA - eng
KW - large deviations; cooling systems of the critical type; annealing algorithm; Asymptotics of the law; Triangular cooling schedules; optimization problem far from the horizon
UR - http://eudml.org/doc/77414
ER -

References

top
  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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.