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

Sylvain Rubenthaler 

Université de Nice - Sophia Antipolis, Laboratoire Dieudonné, Parc Valrose,
06108 Nice Cédex 02, France

Tobias Rydén and  Magnus Wiktorsson

Centre for Mathematical Sciences, Lund University, Box 118, 221 00 Lund,
Sweden

Abstract

Abstract


We study simulated annealing algorithms to maximise a function   on a
subset of $\R^d$. In classical simulated annealing, given a current
state n in stage n of the algorithm, the probability to accept a
proposed state z at which   is smaller, is
exp(\beta_n+1(\psi(z)-\psi(\theta_n)) where (\beta_n) is the inverse
temperature. With the standard logarithmic increase of (\beta_n) the
probability P(\psi(\theta_n)<=\psi_max-eps), with  \psi_max the
maximal value of  \psi, then tends to zero at a logarithmic rate as n
increases. We examine variations of this scheme in which (\beta_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.

Key words: simulated annealing, convergence rate,maximum likelihood estimation.

2000 MSC: 60J22