Fast simulated annealing in RdRd with an application to maximum likelihood estimation in state-space models

We study simulated annealing algorithms to maximise a function ψψ on a subset of RdRd. In classical simulated annealing, given a current state θnθn in stage nn of the algorithm, the probability to accept a proposed state zz at which ψψ is smaller, is exp(−βn+1(ψ(z)−ψ(θn))exp(−βn+1(ψ(z)−ψ(θn)) where (βn)(βn) is the inverse temperature. With the standard logarithmic increase of (βn)(βn) the probability P(ψ(θn)≤ψmax−ε)P(ψ(θn)≤ψmax−ε), with ψmaxψmax the maximal value of ψψ, then tends to zero at a logarithmic rate as nn increases. We examine variations of this scheme in which (βn)(βn) is allowed to grow faster, but also consider other functions than the exponential for determining acceptance probabilities. The main result shows that faster rates of convergence can be obtained, both with the exponential and other acceptance functions. 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.