Sharp large deviations estimates for simulated annealing algorithms
type: Item
instance of: scholarly article
title: Sharp large deviations estimates for simulated annealing algorithms
zbMATH Open document ID: 0746.60024
published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques
publication date: 1992-06-27T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/77409
review text: From the author's summary freely adapted: Simulated annealing algorithms are Monte Carlo simulations of physical systems where the temperature is a decreasing function of time. The method can be used as a general purpose optimization technique to locate the minima of an arbitrary function defined on a finite but possibly very large set. It can be described as a non-stationary controlled Markov chain. The aim of this paper is to build a large deviation theory in this time-inhomogeneous discrete setting. A careful investigation of the law of the exit point and time from sets is made, based on the Venttsel'-Frejdlin decomposition of the state space into cycles. It is hoped that giving a precise description of how trajectories escape from attractors brings a qualitative contribution to the insight one may have into the behaviour of simulated annealing. The usefulness of the sharp large deviations estimates obtained is illustrated by considering the following topics: convergence to ground states, asymptotical equidistribution on ground states, thermical quasi-equilibrium, and the shape of optimal cooling schedules.
Mathematics Subject Classification ID: 60F10
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 93E20
zbMATH DE Number: 28814
zbMATH Keywords: simulated annealing algorithms
zbMATH Keywords: Monte Carlo simulation
zbMATH Keywords: large deviation theory
zbMATH Keywords: optimal cooling schedules
author: Olivier Catoni
reviewed by: Marius Iosifescu
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 28814