Simulated annealing algorithms and Markov chains with rare transitions

Olivier Catoni

Séminaire de probabilités de Strasbourg (1999)

  • Volume: 33, page 69-119

How to cite


Catoni, Olivier. "Simulated annealing algorithms and Markov chains with rare transitions." Séminaire de probabilités de Strasbourg 33 (1999): 69-119. <>.

author = {Catoni, Olivier},
journal = {Séminaire de probabilités de Strasbourg},
keywords = {stochastic optimization; Markov chains; simulated annealing algorithms},
language = {eng},
pages = {69-119},
publisher = {Springer - Lecture Notes in Mathematics},
title = {Simulated annealing algorithms and Markov chains with rare transitions},
url = {},
volume = {33},
year = {1999},

AU - Catoni, Olivier
TI - Simulated annealing algorithms and Markov chains with rare transitions
JO - Séminaire de probabilités de Strasbourg
PY - 1999
PB - Springer - Lecture Notes in Mathematics
VL - 33
SP - 69
EP - 119
LA - eng
KW - stochastic optimization; Markov chains; simulated annealing algorithms
UR -
ER -


  1. [1] Azencott Robert (1988) Simulated Annealing, Séminaire Bourbaki 40ième année, 1987-1988697. Zbl0687.60086MR992211
  2. [2] Azencott Robert (1992) Sequential Simulated Annealing: Speed of Convergence and Acceleration Techniques, in Simulated Annealing: Parallelization Techniques, R. Azencott Ed., Wiley Interscience. Zbl0787.90071MR1188931
  3. [3] Azencott Robert (1992) A Common Large Deviations Mathematical Framework for Sequential Annealing and Parallel Annealing, in Simulated Annealing : Parallelization Techniques, R. Azencott Ed., Wiley Interscience. Zbl0787.90072MR1188932
  4. [4] Azencott Robertand Graffigne Christine (1992) Parallel Annealing by Periodically Interacting Multiple Searches: Acceleration Rates, in Simulated Annealing : Parallelization Techniques, R. Azencott Ed., Wiley Interscience. Zbl0777.90044MR1188935
  5. [5] Catoni Olivier (1991) Exponential Triangular Cooling Schedules for Simulated Annealing Algorithms: a case study, Applied Stochastic Analysis, Proceedings of a US-French Workshop, Rutgers University, April 29 - May 2, 1991, Karatzas I. and Ocone D. eds., Lecture Notes in Control and Information Sciences No 177, Springer Verlag, 1992. MR1169919
  6. [6] Catoni Olivier (1992) Rough Large Deviation Estimates for Simulated Annealing: Application to Exponential Schedules, The Annals of Probability, Vol. 20, nb. 3, pp. 1109 - 1146. Zbl0755.60021MR1175253
  7. [7] Catoni Olivier, (1998) The Energy Transformation Method for the Metropolis Algorithm Compared with Simulated Annealing. Probab. Theory Related Fields110 (1998), no. 1., pages 69-89. Zbl0897.60078MR1602040
  8. [8] Catoni Olivierand Cerf Raphael (1997) The Exit Path of a Markov Chain with Rare Transitions, ESAIM:P&S, vol 1, pp. 95-144, Zbl0869.60063
  9. [9] Catoni Olivier (1998) Solving Scheduling Problems by Simulated Annealing. SIAM J. Control Optim.36, no. 5, (electronic), pages 1539-1575. Zbl0913.60045MR1626872
  10. [10] Catoni Olivier (1996) Metropolis, Simulated Annealing and I.E.T. Algorithms: Theory and Experiments. Journal of Complexity 12, special issue on the conference Foundation of Computational Mathematics, January 5-12 1997, Rio de Janeiro, pages 595-623, December 1996. Zbl0862.68057MR1422728
  11. [11] Cot Cécileand Catoni Olivier (1998) Piecewise constant triangular cooling schedules for generalized simulated annealing algorithms. Ann. Appl. Probab.8, no. 2,, pages 375-396. Zbl1053.65500MR1624937
  12. [12] Deuschel J.D. and Mazza C. (1994) L2 convergence of time nonhomogeneous Markov processes: I. Spectral Estimates, The annals of Applied Probability, vol. 4, no. 4, 1012-1056. Zbl0819.60063MR1304771
  13. [13] Diaconis Persi and Stroock Daniel (1991) Geometric Bounds for Eigenvalues of Markov Chains, The Annals of Applied Probability, Vol. 1, No 1, 36 - 61. Zbl0731.60061MR1097463
  14. [14] Duflo M. (1996) Algorithmes Stochastiques, Mathématiques & Applications (Paris), Springer Verlag. Zbl0882.60001
  15. [15] Fill J.A. (1991) Eigenvalue bounds on the convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Applied Probab., 1. Zbl0726.60069MR1097464
  16. [16] Freidlin, M.I.and Wentzell, A.D. (1984). Random Perturbations of Dynamical Systems. Springer, New York. Zbl0522.60055MR722136
  17. [17] Geman S., Geman D., Stochastic relaxation, Gibbs distribution, and the Bayesian restoration of images, I.E.E.E. Transactions on Pattern Analysis and Machine Intelligence, 6, 721- 741, 1984. Zbl0573.62030
  18. [18] Götze F.. (1991) Rate of Convergence of Simulated Annealing Processes, preprint. MR1106283
  19. [19] Graffigne Christine (1992) Parallel Annealing by Periodically Interacting Multiple Searches: An Experimental Study, in Simulated Annealing: Parallelization Techniques, R. Azencott Ed., Wiley Interscience. Zbl0779.90069
  20. [20] Holley R. and Stroock D. (1988) Annealing via Sobolev inequalities, Comm. Math. Phys., 115:553-559. Zbl0643.60092MR933455
  21. [21] Holley, R.A., Kusuoka, S. and Stroock, D.W. (1989), Asymptotics of the spectral gap with applications to the theory of simulated annealing, Journal of functional analysis, 83, 333-347. Zbl0706.58075MR995752
  22. [22] Hwang, C.R.and Sheu, S.J. (1992) Singular perturbed Markov chains and exact behaviour of simulated annealing processes. J. Theoret. Prob., 5, 2, 223-249. Zbl0755.60047MR1157983
  23. [23] Ingrassia S. (1994) On the rate of convergence of the Metropolis algorithm and Gibbs sampler by geometric bounds, Ann. Appl. Probab.4, no.2, 347-389. Zbl0802.60061MR1272731
  24. [24] Kirchhoff G. (1847) Über die Auflösung der Gleichungen, auf welche man beider Untersuchung der linearen Verteilung galvanischer Ströme gefuhrt wird, Ann. Phys. Chem., 72, pp. 497-508.(English transl. IRE Trans. Circuit Theory CT-5 (1958) 4-7). 
  25. [25] Kirkpatrick S., Gelatt C.D. and Vecchi M.P., (1983) Optimization by simulated annealing, Science, 220, 621-680, 1983. Zbl1225.90162MR702485
  26. [26] Miclo Laurent (1991) Evolution de l'énergie libre. Application à l'étude de la convergence des algorithmes du recuit simulé. Doctoral Dissertation, Université d'Orsay, February 1991. 
  27. [27] Miclo Laurent (1996) Sur les problèmes de sortie discrets inhomogènesAnn. Appl. Probab.6, no 4, 1112-1156. Zbl0870.60062MR1422980
  28. [28] Miclo Laurent (1995) Sur les temps d'occupations des processus de Markov finis inhomogènes à basse température, submitted to Stochastics and Stochastics Reports. Zbl1002.60565MR1639780
  29. [29] Miclo Laurent (1997) Remarques sur l'hypercontractivité et l'évolution de l'entropie pour des chaines de Markov finies, Séminaire de Probabilités XXXI, Lecture Notes in Mathematics1655, Springer. Zbl0882.60065MR1478724
  30. [30] Saloff-Coste, Laurent (1997) Lectures on finite Markov chainsLectures on probability theory and statistics (Saint-Flour, 1996), 301-413, Lecture Notes in Math., 1665, Springer, Berlin. Zbl0885.60061MR1490046
  31. [31] Trouvé Alain (1993) Parallélisation massive du recuit simulé, Doctoral Dissertation, Université Paris11, January 5 1993. 
  32. [32] Trouvé Alain (1994) Cycle Decomposition and Simulated Annealing, S.I.A.M. J. Control Optim., 34(3), 1996. Zbl0852.60031MR1384962
  33. [33] Trouvé Alain (1995) Rough Large Deviation Estimates for the Optimal Convergence Speed Exponent of Generalized Simulated Annealing Algorithms, Ann. Inst. H. Poincaré, Probab. Statist., 32(2), 1996. Zbl0853.60029MR1387393

NotesEmbed ?


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.