THE ENERGY TRANSFORMATION METHOD FOR THE METROPOLIS ALGORITHM COMPARED WITH SIMULATED ANNEALING

We present and analyze a new speed-up technique for Monte Carlo optimi zation: the Iterated Energy Transformation algorithm, where the Metrop olis algorithm is used repeatedly with more and more favourable energy functions derived from the original one by increasing transformations . We show that this method allows a better speed-up than Simulated Ann ealing when convergence speed is measured by the probability of failur e of the algorithm after a large number of iterations. We study also t he limit of a large state space in the special case when the energy is made of a sum of independent terms. We show that the convergence time of the I.E.T. algorithm is polynomial in the size (number of coordina tes) of the problem, but with a worse exponent than for Simulated Anne aling. This indicates that the I.E.T. algorithm is well suited for mod erate size problems but not for too large ones. The independent compon ent case is a good model for the end of many optimization processes, w hen at low temperature a neighbourhood of a local minimum is explored by small and far apart modifications of the current solution. We show that in this case both global optimization methods, Simulated Annealin g and the I.E.T. algorithm, are less efficient than repeated local sto chastic optimizations. Using the general concept of ''slow stochastic optimization algorithm'', we show that any ''slow'' global optimizatio n scheme should be followed by a local one to perform the last approac h to a minimum.