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 optical convergenc e exponent. The optimal convergence exponent of generalized simulated annealing algorithms has been computed by Catoni and Trouve. It is rea ched only with triangular sequences of temperatures, meaning that diff erent finite sequences are used, depending on the time resource availa ble for computations (expressed by an overall number of iterations). W e show first that it is possible to get close to the optimal convergen ce exponent uniformly over suitably bounded families of energy landsca pes using a fixed number of temperature steps. Then we show that, lett ing the number of steps increase with the time resource, we can build a cooling schedule which is universally robust with respect to the con vergence exponent: a fixed triangular sequence of temperatures gives a n optimal convergence exponent for any energy landscape. Piecewise con stant temperature sequences are often used in practice: in favourable cases, the use of the same temperature during a large number of iterat ions allows tabulating the exponential penalties appearing in the tran sition matrix, thus sparing a significant amount of computer time. The proofs we give rely on Freidlin and Wentzell's closed formulas for th e exit time and point from subdomains of time homogeneous Markov chain s.