Cooling schedules for optimal annealing. (English) Zbl 0652.65050

Hajek, Bruce

Math. Oper. Res. 13, No. 2, 311-329 (1988).

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

MSC:

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

Keywords:

convergence; randomized optimization; Monte-Carlo optimization; simulated annealing; cooling schedule

Citations:

Zbl 0573.62030