Fast simulated annealing in \R^d and an application to maximum likelihood estimation

arXivmath/0609353MaRDI QIDQ6477845FDOQ6477845

Authors: Sylvain Rubenthaler, Tobias Rydén, Magnus Wiktorsson 

Publication date: 13 September 2006

Abstract: Using classical simulated annealing to maximise a function $psi$ defined on a subset of $R^d$, the probability $p(psi(het{a}_n)leqps{i}_{max}-epsilon)$ tends to zero at a logarithmic rate as $n$ increases; here $het{a}_n$ is the state in the $n$-th stage of the simulated annealing algorithm and $ps{i}_{max}$ is the maximal value of $psi$. We propose a modified scheme for which this probability is of order $n^{-1/3}logn$, 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.

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Monte Carlo methods (65C05) Central limit and other weak theorems (60F05) Sequential estimation (62L12) Stochastic programming (90C15) Continuous-time Markov processes on general state spaces (60J25)

This page was built for publication: Fast simulated annealing in $\R^d$ and an application to maximum likelihood estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6477845)