Tobias Rydén

Fast simulated annealing in R^d


Abstract
	
Using classical simulated annealing to maximise a function \psi
defined on a subset of R^d, the probability
P(\psi(\theta_n)<=\psi_{max}-\epsilon) tends to zero at a logarithmic
rate as n increases; here \theta_n is the state in the n-th stage of
the simulated annealing algorithm and \psi_{max} is the maximal value
of \psi. We propose a modified scheme for which this probability is of
order n^{-1/3}log n, and hence vanishes at an algebraic rate. To
obtain this faster rate, the exponentially decaying acceptance
probability of classical simulated annealing is replaced by a more
heavy-tailed function, and the system is cooled faster. We also show
how the algorithm may be applied to functions that cannot be computed
exactly but only approximated.

See the preprint on:
http://fr.arxiv.org/abs/math.PR/0609353
for a more detailed account.