Asymptotic study of simulated annealing algorithms.

Summary Simulated annealing algorithms are an approach to optimization where the state space is explored by an inhomogeneous markov chain. We study the dynamics of metropolis on a finite space by large deviation methods. A decomposition of the space into cycles, following wentzell and freidlin, leads to estimate the law of time and of the entry point in a set for the trajectories remaining in another given set. The proof, by recurrence, establishes that the estimates are conserved by composition of the laws by tensor inner product. Applications follow: a complement to hajek's theorem on the necessary and sufficient conditions for convergence, an upper bound for the speed of convergence, estimates of the law of the system for different temperature sequences. We show that the optimal temperature sequence in the far finite horizon decreases as the inverse of the logarithm in its first part, but in general not in its part near the horizon. On the other hand, we obtain an asymptotically optimal convergence rate in the sense of logarithmic equivalents with geometric temperature sequences whose rate is suitably adapted to the horizon.