Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms
type: Item
instance of: scholarly article
title: Rough large deviation estimates for the optimal convergence speed exponent of generalized simulated annealing algorithms
zbMATH Open document ID: 0853.60029
author: Alain Trouvé
published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques
publication date: 1997-01-05T00:00:00Z
full work available at URL: http://www.numdam.org/item
full work available at URL: https://eudml.org/doc/77537
review text: The author introduces the notion of generalized simulated annealing that covers, e.g., versions of parallel sequential annealing. Various results of \textit{O. Catoni} [Ann. Probab. 20, No. 3, 1109-1146 (1992; Zbl 0755.60021)] on convergence and large deviation of sequential annealing schemes are transferred and proved in this generalized framework. In particular, the following setting is considered: Let \(E\) be a finite set, \(\kappa\in [0, \infty]\), \(q(.,.)\) an irreducible Markov kernel on \(E\), \(\{Q_t (.,.) \}_{t\geq 0}\) a family of Markov kernels such that \[ \kappa^{-1} q(i, j)e^{-V (i,j)/t} \leq Q_t (i, j)\leq \kappa q(i, j) e^{-V (i,j) /t} \] for any \(V: E\times E\to [0, \infty]\) which is finite if \(q(i, j)> 0\). Then the coordinate process \(\{X_n \}_{n\in \mathbb{N}}\) in \(E^\mathbb{N}\) is called generalized simulated annealing process, if there is a family \(\{Q_t (.,.) \}_{t\geq 0}\) (as above), a sequence \(\{T_n \}_{n\in \mathbb{N}} \subset \mathbb{R}_+\), and an initial distribution \(\nu_0\) such that \(\mathbb{P}_{(Q_t, T_n, \nu_0)}\) is the unique probability measure on \(E^\mathbb{N}\) that turns \(\{X_n \}_{n\in \mathbb{N}}\) into a Markov chain with respect to its natural filtration, initial distribution \(\nu_0\), and transition kernels \(Q_{T_n} (.,.)\) at time \(n\). In this situation, a large deviation principle for the exit time of arbitrary subsets and generalized simulated annealing is proved. The estimates hold uniformly with respect to the cooling scheme \(\{T_n \}_{n\in \mathbb{N}}\). The technique of the proof follows Catoni's approach but is also based on a renormalization of the function \(V(.,.)\) which makes it possible to consider both arbitrary sets and generalized annealing. Necessary and sufficient conditions for the convergence of the annealing schemes (similar to those of the sequential case) are given. Under some additional conditions on \(\{Q_t \}_{t\geq 0}\) and \(\{T_n \}_{n\in \mathbb{N}}\) the optimal conver…
Mathematics Subject Classification ID: 60F10
zbMATH DE Number: 898064
zbMATH Keywords: generalized simulated annealing
zbMATH Keywords: large deviations
zbMATH Keywords: parallel annealing
reviewed by: R. L. Schilling
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 898064