Rates of convergence for sequential annealing: A large deviation approach. (English) Zbl 0776.90063

Catoni, Olivier

Simulated annealing. Parallelization techniques, 25-35 (1992).

[For the entire collection see Zbl 0746.00020.]
This paper reviews the results of three recent papers of the author [Ann. Inst. Henri Poincaré, Probab. Stat. 27, No. 3, 291-383 (1991; Zbl 0746.60024); ibid. 27, No. 4, 463-518 (1991; Zbl 0752.60025); Ann. Probab. 20, No. 3, 1109-1146 (1992; Zbl 0755.60021)]. Large deviation estimates of the exit time and point from cycles of the energy landscape allows a precise understanding of the most probable trajectories of simulated annealing algorithms for any non increasing sequence of temperatures. It is then possible to derive a series of results about convergence and convergence speed. The most striking is that optimizing the probability of convergence after \(N\) iterations requires to choose the whole sequence of temperatures \(T^ N_ 1,\dots,T^ N_ N\) as a function of \(N\) and that exponential triangular schedules of the form \(T^ N_ n=A\rho(N)^ n\), \(n\leq N\) lead to robust almost optimal probabilities of convergence after \(N\) iterations.

Reviewer: O.Catoni

MSC:

90C27	Combinatorial optimization
90-08	Computational methods for problems pertaining to operations research and mathematical programming
60F10	Large deviations

Keywords:

exponential colling schedules; simulated annealing; convergence speed

Citations:

Zbl 0746.00020; Zbl 0746.60024; Zbl 0752.60025; Zbl 0755.60021