Simulated annealing with time-dependent energy function via Sobolev inequalities

AbstractWe analyze the simulated annealing algorithm with an energy function Ut that depends on time. Assuming some regularity conditions on Ut (especially that Ut does not change too quickly in time), and choosing a logarithmic cooling schedule for the algorithm, we derive bounds on the Radon-Nikodym density of the distribution of the annealing algorithm at time t with respect to the invariant measure πt at time t. Moreover, we estimate the entrance time of the algorithm into typical subsets V of the state space in terms of πt(Vc)