Simulated annealing algorithms and Markov chains with rare transitions
Catoni, Olivier
Séminaire de probabilités de Strasbourg, Tome 33 (1999), p. 69-119 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{SPS_1999__33__69_0,
     author = {Catoni, Olivier},
     title = {Simulated annealing algorithms and Markov chains with rare transitions},
     journal = {S\'eminaire de probabilit\'es de Strasbourg},
     volume = {33},
     year = {1999},
     pages = {69-119},
     mrnumber = {1767994},
     zbl = {0944.90053},
     language = {en},
     url = {http://dml.mathdoc.fr/item/SPS_1999__33__69_0}
}

Catoni, Olivier. Simulated annealing algorithms and Markov chains with rare transitions. Séminaire de probabilités de Strasbourg, Tome 33 (1999) pp. 69-119. http://gdmltest.u-ga.fr/item/SPS_1999__33__69_0/

[1] Azencott Robert (1988) Simulated Annealing, Séminaire Bourbaki 40ième année, 1987-1988 697. | Numdam | MR 992211 | Zbl 0687.60086

[2] Azencott Robert (1992) Sequential Simulated Annealing: Speed of Convergence and Acceleration Techniques, in Simulated Annealing: Parallelization Techniques, R. Azencott Ed., Wiley Interscience. | MR 1188931 | Zbl 0787.90071

[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. | MR 1188932 | Zbl 0787.90072

[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. | MR 1188935 | Zbl 0777.90044

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

[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. | MR 1175253 | Zbl 0755.60021

[7] Catoni Olivier, (1998) The Energy Transformation Method for the Metropolis Algorithm Compared with Simulated Annealing. Probab. Theory Related Fields 110 (1998), no. 1., pages 69-89. | MR 1602040 | Zbl 0897.60078

[8] Catoni Olivierand Cerf Raphael (1997) The Exit Path of a Markov Chain with Rare Transitions, ESAIM:P&S, vol 1, pp. 95-144, http://www.emath.fr/Maths/Ps/ps.html. | Numdam | Zbl 0869.60063

[9] Catoni Olivier (1998) Solving Scheduling Problems by Simulated Annealing. SIAM J. Control Optim.36, no. 5, (electronic), pages 1539-1575. | MR 1626872 | Zbl 0913.60045

[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. | MR 1422728 | Zbl 0862.68057

[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. | MR 1624937 | Zbl 01319920

[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. | MR 1304771 | Zbl 0819.60063

[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. | MR 1097463 | Zbl 0731.60061

[14] Duflo M. (1996) Algorithmes Stochastiques, Mathématiques & Applications (Paris), Springer Verlag. | Zbl 0882.60001

[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. | MR 1097464 | Zbl 0726.60069

[16] Freidlin, M.I. and Wentzell, A.D. (1984). Random Perturbations of Dynamical Systems. Springer, New York. | MR 722136 | Zbl 0522.60055

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

[18] Götze F.. (1991) Rate of Convergence of Simulated Annealing Processes, preprint. | MR 1106283

[19] Graffigne Christine (1992) Parallel Annealing by Periodically Interacting Multiple Searches: An Experimental Study, in Simulated Annealing: Parallelization Techniques, R. Azencott Ed., Wiley Interscience. | Zbl 0779.90069

[20] Holley R. and Stroock D. (1988) Annealing via Sobolev inequalities, Comm. Math. Phys., 115:553-559. | MR 933455 | Zbl 0643.60092

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

[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. | MR 1157983 | Zbl 0755.60047

[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. | MR 1272731 | Zbl 0802.60061

[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] Kirkpatrick S., Gelatt C.D. and Vecchi M.P., (1983) Optimization by simulated annealing, Science, 220, 621-680, 1983. | MR 702485

[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] Miclo Laurent (1996) Sur les problèmes de sortie discrets inhomogènes Ann. Appl. Probab. 6, no 4, 1112-1156. | MR 1422980 | Zbl 0870.60062

[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. | MR 1639780 | Zbl 1002.60565

[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 Mathematics 1655, Springer. | Numdam | MR 1478724 | Zbl 0882.60065

[30] Saloff-Coste, Laurent (1997) Lectures on finite Markov chains Lectures on probability theory and statistics (Saint-Flour, 1996), 301-413, Lecture Notes in Math., 1665, Springer, Berlin. | MR 1490046 | Zbl 0885.60061

[31] Trouvé Alain (1993) Parallélisation massive du recuit simulé, Doctoral Dissertation, Université Paris 11, January 5 1993.

[32] Trouvé Alain (1994) Cycle Decomposition and Simulated Annealing, S.I.A.M. J. Control Optim., 34(3), 1996. | MR 1384962 | Zbl 0852.60031

[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. | Numdam | MR 1387393 | Zbl 0853.60029