Piecewise constant triangular cooling schedules for generalized simulated annealing algorithms
We investigate how to tune a generalized simulated annealing algorithm with piecewise constant cooling schedule to get an optimal convergence exponent. The optimal convergence exponent of generalized simulated annealing algorithms has been computed in [6] and [25]. It is reached only with triangular sequences of temperatures, meaning that di erent nite sequences are used depending on the time resource available for computations (expressed by an overall number of iterations). We show rst that it is possible to get close to the optimal convergence exponent uniformly over suitably bounded families of energy landscapes using a xed number of temperature steps. Then we show that letting the number of steps increase with the time resource, we can build a cooling schedule which is universally robust with respect to the convergence exponent: a xed triangular sequence of temperatures gives an optimal convergence exponent for any energy landscape. Piecewise constant temperature sequences are often used in practice: in favourable cases, the use of the same temperature during a large number of iterations allows to tabulate the exponential penalties appearing in the transition matrix, thus sparing a signi cant amount of computer time. The proofs we give rely on Freidlin and Wentzell's closed formulas for the exit time and point from subdomains of time homogeneous Markov chains. key words: Large deviations, Metropolis dynamics, cycle decomposition, simulated annealing, di culty, critical depth. DMI, Laboratoire de Math ematiques de l'Ecole Normale Sup erieure, UA 762 du CNRS, 45 rue d'Ulm, 75230 Paris Cedex 05-France and Laboratoire de Mod elisation Stochastique et Statistique, Universit e Paris Sud, Math ematiques, Bat̂ ment 425, 91405 Orsay Cedex, France. E-mail address: cot@dmi.ens.fr and cot@stats.matups.fr y DIAM, Laboratoire de Math ematiques de l'Ecole Normale Sup erieure, UA 762 du CNRS, 45 rue d'Ulm, 75230 Paris Cedex 05-France. E-mail adress: catoni@dmi.ens.fr