Accueil du site > Actualité de la recherche > Actualités scientifiques




Recherchez sur ce site


Algorithme de Metropolis

2 août 2011

Une collaboration entre des mathématiciens de Stanford et du Laboratoire Jean-Alexandre Dieudonné (CNRS/Université de Nice Sophia-Antipolis) a permis d’établir une estimation précise de la vitesse de convergence d’un l’algorithme de Metropolis local pour la distribution de N boules de rayon r sans recouvrement dans un domaine de l’espace.

En 1953, Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosen- bluth, Augusta H. Teller et Edward Teller [2], ont inventé un algorithme permettant d’engendrer une distribution statistique pour un problème à N corps, grâce à la construction d’une chaîne de Markov convenable. Généralisé par K. Hastings en 1970, l’algorithme de Metropolis joue un rôle très important en mécanique statistique et en chimie physique, et est considéré comme un des fondements de la méthode de recuit simulé, une importante méthode d’optimisation dont les applications prolifèrent. Toutefois, dans la plupart des cas, aucune estimation précise de la vitesse de convergence de cet algorithme n’est connue.

Une collaboration entre des mathématiciens de Stanford et du Laboratoire Jean-Alexandre Dieudonné (CNRS/Université de Nice Sophia-Antipolis) a permis de résoudre ce problème dans le cas d’un algorithme de Metropolis local pour la distribution de N boules de rayon r sans recouvrement dans un domaine de l’espace [1].

Dans ce cas, l’algorithme consiste à tirer au hasard une des N boules, et à déplacer son centre au hasard à distance au plus d ; le mouvement est accepté si la nouvelle configuration satisfait la condition de non recouvrement. Ces mathématiciens ont réussi à analyser la théorie spectrale de cette chaîne de Markov lorsque le produit Nr reste petit. Le spectre près de 1 est discret, et lorsque la distance de déplacement élémentaire d est petite, le spectre près de 1 est bien approximé par le spectre du laplacien avec condition de Neumann dans l’espace de configuration des N boules. Enfin, à la nième étape de l’algorithme, la distance en variation totale à la mesure d’équilibre est estimée par une constante fois exp(−nd²μ), où μ est la première valeur propre non triviale du laplacien précédent.

Ce travail a permis de dégager de nouveaux problèmes géométriques pour pouvoir généraliser les résultats précédents au cas, plus intéressant pour les applications à la physique, où la densité de boules Nr2 n’est pas petite. En particulier l’étude du nombre de composantes connexes de l’espace de configuration des N boules et la structure des singularités du bord de cet espace de configuration semblent être des questions fondamentales à résoudre pour l’obtention de nouveaux résultats.

Contacts : Gilles Lebeau et Laurent Michel, Laboratoire Jean-Alexandre Dieudonné, UMR 6621

Références

- [1] P. Diaconis, G. Lebeau, L. Michel, Geometric analysis for the Metropolis algorithm on Lipschitz domains, Inventiones mathematicae, Volume 185, Number 2, pp 239-281. DOI : 10.1007/s00222-010-0303-6
- [2] N. Metropolis, and A. Rosenbluth, and M. Rosenbluth, and A. Teller, and E. Teller, Equations of state calculations by fast computing machines, J. Chem. Phys., 21, 1953, 1087–1092