Optimization by simulated annealing: a necessary and sufficient condition for convergence
Bruce Hajek · Lecture notes-monograph series · 1986
A Monte Carlo optimization technique called "simulated annealing" is a descent algorithm modified by random ascent moves in order to escape local minima which are not global minima.The level of randomization is determined by a control parameter T, called temperature, which tends to zero according to a deterministic "cooling schedule"We give a simple necessary and sufficient condition on the cooling schedule for the algorithm state to converge in probability to the set of globally minimum cost statesIn the special case that the cooling schedule has parametric form T^ » c/log(l+k), the condition for convergence is that c be greater than or equal to the depth, suitably defined, of the deepest local minimum which is not a global minimum state."Annealing" in the physics literature refers to the process of slowly cooling a substance in order to reach globally minimum energy states.Cerny (1982) and Kirkpatrick, Gelatt and Vecchi (1983) suggested simulating such a process in order to solve large-scale minimization problems on a computer Randomization is introduced using the classical method of Metropolis et al. (1953) for generating sample realizations of random fields.See Geman and Geman (1984), Kirkpatrick et al. (1983) and the references therein for more background information.