  Using classical simulated annealing to maximise a function $\psi$ defined on
a subset of $\R^d$, the probability $\p(\psi(\theta\_n)\leq
\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, and give an example of maximising the
log-likelihood function for a state-space model.
