Cooling schedules for optimal annealing. (English) Zbl 0652.65050

Let S be a finite set and V a function defined on S which is to be minimized. Let \(T_ 1\geq T_ 2\geq...\), with \(\lim_{k\to \infty}T_ k=0\), be a sequence of strictly positive numbers, called temperatures. A Monte-Carlo optimization technique, called “simulated annealing” is a descent algorithm, modified by random ascent moves, in order to escape local minima. The level of randomization is determined by the sequence of temperatures. The author gives a necessary and sufficient condition on the cooling schedule for the convergence in probability of the algorithm to the set of globally minimum cost states. The author shows that in the case studied by S.Geman and D. Geman [IEEE Trans. Pattern Anal. Mach. Intell. 6, 721-741 (1984; Zbl 0573.62030)] when \(T_ k=c/(\log (k+1))\), his result is consistent with this work. The author compares his work with some others in the same domain, too, and gives some examples.
Reviewer: A.Donescu


65K05 Numerical mathematical programming methods
65C05 Monte Carlo methods
90C15 Stochastic programming
60J27 Continuous-time Markov processes on discrete state spaces


Zbl 0573.62030
Full Text: DOI Link