About Feynman-Kac type simulated annealing

Pierre Del Moral; Laurent Miclo

ESAIM: Probability and Statistics (2006)

  • Volume: 10, page 76-140
  • ISSN: 1292-8100

Abstract

top
Let U be a function defined on a finite set E which is endowed with an irreducible Markov kernel M. The main purpose of this paper is to theoretically compare two stochastic procedures for the global minimization of U: simulated annealing and a genetic algorithm. For the latter we simplify the analysis by considering an infinite number of particles. Furthermore, we assume that the setting (E,M,U) is sufficiently symmetrical and that M does not force particles to get out of 𝒰 in bounded time, where 𝒰 is the set of global minima of U. Contrarily to simulated annealing, for all logarithmic inverse temperature evolutions, the considered genetic algorithms concentrate in large time on some particular elements of 𝒰 that we will describe. But it is more difficult for these genetic algorithms to forget their initial condition and we will quantify this property. Corresponding conjectures for more general situations will also be pointed out.

How to cite

top

Moral, Pierre Del, and Miclo, Laurent. "Dynamiques recuites de type Feynman-Kac : résultats précis et conjectures." ESAIM: Probability and Statistics 10 (2006): 76-140. <http://eudml.org/doc/249740>.

@article{Moral2006,
abstract = { Soit U une fonction définie sur un ensemble fini E muni d'un noyau markovien irréductible M. L'objectif du papier est de comparer théoriquement deux procédures stochastiques de minimisation globale de U : le recuit simulé et un algorithme génétique. Pour ceci on se placera dans la situation idéalisée d'une infinité de particules disponibles et nous ferons une hypothèse commode d'existence de suffisamment de symétries du cadre (E,M,U). On verra notamment que contrairement au recuit simulé, toute évolution logarithmique de l'inverse de la température conduit asymptotiquement à concentrer les dynamiques de Feynman-Kac recuites sur certains minima globaux de U (du moins si M ne fait pas sortir de leur ensemble en un temps presque immédiat). Par contre, ces dernières ont tendance à oublier plus difficilement leur condition initiale et on quantifiera précisément cette propriété. Enfin on présentera les conjectures correspondantes dans une situation plus générale. },
author = {Moral, Pierre Del, Miclo, Laurent},
journal = {ESAIM: Probability and Statistics},
keywords = {Optimisation stochastique; dynamique de Feynman-Kac recuite; recuit simulé généralisé; ergodicité faible; valeur et vecteur propre de Perron-Frobenius; équation de Poisson; temps de retour; probabilité invariante ou fixe; grandes déviations; mesures empiriques; basse température; couplage et inégalités stochastiques; inégalité de Sobolev logarithmique modifiée.; stochastic optimization; dynamic Feynman-Kac annealing; Perron-Frobenius eigenvalues; Perron-Frobenius eigenvectors; Poisson equation; large deviation; low temperature; stochastic coupling; stochastic inequality; Sobolev inequality; time delay; probability},
language = {fre},
month = {3},
pages = {76-140},
publisher = {EDP Sciences},
title = {Dynamiques recuites de type Feynman-Kac : résultats précis et conjectures},
url = {http://eudml.org/doc/249740},
volume = {10},
year = {2006},
}

TY - JOUR
AU - Moral, Pierre Del
AU - Miclo, Laurent
TI - Dynamiques recuites de type Feynman-Kac : résultats précis et conjectures
JO - ESAIM: Probability and Statistics
DA - 2006/3//
PB - EDP Sciences
VL - 10
SP - 76
EP - 140
AB - Soit U une fonction définie sur un ensemble fini E muni d'un noyau markovien irréductible M. L'objectif du papier est de comparer théoriquement deux procédures stochastiques de minimisation globale de U : le recuit simulé et un algorithme génétique. Pour ceci on se placera dans la situation idéalisée d'une infinité de particules disponibles et nous ferons une hypothèse commode d'existence de suffisamment de symétries du cadre (E,M,U). On verra notamment que contrairement au recuit simulé, toute évolution logarithmique de l'inverse de la température conduit asymptotiquement à concentrer les dynamiques de Feynman-Kac recuites sur certains minima globaux de U (du moins si M ne fait pas sortir de leur ensemble en un temps presque immédiat). Par contre, ces dernières ont tendance à oublier plus difficilement leur condition initiale et on quantifiera précisément cette propriété. Enfin on présentera les conjectures correspondantes dans une situation plus générale.
LA - fre
KW - Optimisation stochastique; dynamique de Feynman-Kac recuite; recuit simulé généralisé; ergodicité faible; valeur et vecteur propre de Perron-Frobenius; équation de Poisson; temps de retour; probabilité invariante ou fixe; grandes déviations; mesures empiriques; basse température; couplage et inégalités stochastiques; inégalité de Sobolev logarithmique modifiée.; stochastic optimization; dynamic Feynman-Kac annealing; Perron-Frobenius eigenvalues; Perron-Frobenius eigenvectors; Poisson equation; large deviation; low temperature; stochastic coupling; stochastic inequality; Sobolev inequality; time delay; probability
UR - http://eudml.org/doc/249740
ER -

References

top
  1. C. Ané, S. Blachère, D. Chafaï, P. Fougères, I. Gentil, F. Malrieu, C. Roberto and G. Scheffer, Sur les inégalités de Sobolev logarithmiques, Panoramas et Synthèses [Panoramas and Syntheses]. Société Mathématique de France, 10 Paris (2000). With a preface by Dominique Bakry and Michel Ledoux.  
  2. R. Bott and J.P. Mayberry, Matrices and trees, in Economic activity analysis, O. Morgenstern Ed., John Wiley and Sons, Inc., New York (1954) 391–400.  
  3. O. Catoni, Simulated annealing algorithms and Markov chains with rare transitions, in Séminaire de Probabilités, XXXIII, Lect. Notes Math.1709 (1999) 69–119.  
  4. R. Cerf, The dynamics of mutation-selection algorithms with large population sizes. Ann. Inst. H. Poincaré Probab. Statist.32 (1996) 455–508.  
  5. R. Cerf, A new genetic algorithm. Ann. Appl. Probab.6 (1996) 778–817.  
  6. D. Concordet, Estimation de la densité du recuit simulé. Ann. Inst. H. Poincaré Probab. Statist.30 (1994) 265–302.  
  7. P. Del Moral, M. Ledoux and L. Miclo, On contraction properties of Markov kernels. Probab. Theory Related Fields126 (2003) 395–420.  
  8. P. Del Moral and L. Miclo, On the convergence and applications of generalized simulated annealing. SIAM J. Control Optim.37 (1999) 1222–1250 (electronic).  
  9. P. Del Moral and L. Miclo, Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to non-linear filtering, in Séminaire de Probabilités, XXXIV, Lect. Notes Math.1729 (2000) 1–145.  
  10. P. Del Moral and L. Miclo, Annealed Feynman-Kac models. Comm. Math. Phys.235 (2003) 191–214.  
  11. P. Del Moral, Feynman-Kac formulae. Probability and its Applications (New York). Springer-Verlag, New York (2004). Genealogical and interacting particle systems with applications.  
  12. P. Del Moral and A. Guionnet, On the stability of interacting processes with applications to filtering and genetic algorithms. Ann. Inst. H. Poincaré Probab. Statist.37 (2001) 155–194.  
  13. P. Del Moral and L. Miclo, On the stability of nonlinear Feynman-Kac semigroups. Ann. Fac. Sci. Toulouse Math.11 (2002) 135–175.  
  14. Amir Dembo and Ofer Zeitouni, Large deviations techniques and applications, Applications of Mathematics (New York). Springer-Verlag, New York, second edition 38 (1998).  
  15. P.Dupuis and R.S. Ellis, A weak convergence approach to the theory of large deviations. Wiley Series in Probability and Statistics: Probability and Statistics. John Wiley & Sons Inc., New York (1997). A Wiley-Interscience Publication.  
  16. M.I. Freidlin and A.D. Wentzell, Random perturbations of dynamical systems, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, New York 260 (1984). Translated from the Russian by Joseph Szücs.  
  17. B. Hajek, Cooling schedules for optimal annealing. Math. Oper. Res.13 (1988) 311–329.  
  18. R. Holley and D. Stroock, Simulated annealing via Sobolev inequalities. Comm. Math. Phys.115 (1988) 553–569.  
  19. T. Lindvall, Lectures on the coupling method. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. John Wiley & Sons Inc., New York (1992). A Wiley-Interscience Publication.  
  20. L. Miclo, About relaxation time of finite generalized Metropolis algorithms. Ann. Appl. Probab.12 (2002) 1492–1515.  
  21. L. Miclo, Une étude des algorithmes de recuit simulé sous-admissibles. Ann. Fac. Sci. Toulouse Math.4 (1995) 819–877.  
  22. L. Miclo, Sur les problèmes de sortie discrets inhomogènes. Ann. Appl. Probab.6 (1996) 1112–1156.  
  23. L. Miclo, Sur les temps d'occupations des processus de Markov finis inhomogènes à basse température. Stoch. Stoch. Rep.63 (1998) 65–137.  
  24. L. Miclo, Une variante de l'inégalité de Cheeger pour les chaînes de Markov finies. ESAIM: Probab. Statist.2 (1998) 1–21. (electronic).  
  25. E. Seneta, Nonnegative matrices and Markov chains. Springer Series in Statistics. Springer-Verlag, New York, second edition, 1981.  
  26. W. Stannat, On the convergence of genetic algorithms – a variational approach. Probab. Theory Related Fields129 (2004) 113–132.  
  27. A. Trouvé, Cycle decompositions and simulated annealing. SIAM J. Control Optim.34 (1996) 966–986.  

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.