Advanced

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

Rubenthaler, Sylvain; Rydén, Tobias LU and Wiktorsson, Magnus LU (2009) In Stochastic Processes and their Applications 119(6). p.1912-1931
Abstract
We study simulated annealing algorithms to maximise a function psi on a subset of R-d. In classical simulated annealing, given a current state theta(n) in stage n of the algorithm, the probability to accept a proposed state z at which psi 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) - epsilon), 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... (More)
We study simulated annealing algorithms to maximise a function psi on a subset of R-d. In classical simulated annealing, given a current state theta(n) in stage n of the algorithm, the probability to accept a proposed state z at which psi 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) - epsilon), 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. (C) 2008 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Simulated annealing, Convergence rate, Maximum likelihood estimation
in
Stochastic Processes and their Applications
volume
119
issue
6
pages
1912 - 1931
publisher
Elsevier
external identifiers
  • wos:000266149100007
  • scopus:64549131368
ISSN
1879-209X
DOI
10.1016/j.spa.2008.09.007
language
English
LU publication?
yes
id
9d95efea-846c-469e-814e-b6cfd0362232 (old id 1425502)
date added to LUP
2009-07-01 15:41:01
date last changed
2017-04-23 03:45:09
@article{9d95efea-846c-469e-814e-b6cfd0362232,
  abstract     = {We study simulated annealing algorithms to maximise a function psi on a subset of R-d. In classical simulated annealing, given a current state theta(n) in stage n of the algorithm, the probability to accept a proposed state z at which psi 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)) &lt;= psi(max) - epsilon), 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. (C) 2008 Elsevier B.V. All rights reserved.},
  author       = {Rubenthaler, Sylvain and Rydén, Tobias and Wiktorsson, Magnus},
  issn         = {1879-209X},
  keyword      = {Simulated annealing,Convergence rate,Maximum likelihood estimation},
  language     = {eng},
  number       = {6},
  pages        = {1912--1931},
  publisher    = {Elsevier},
  series       = {Stochastic Processes and their Applications},
  title        = {Fast simulated annealing in R-d with an application to maximum likelihood estimation in state-space models},
  url          = {http://dx.doi.org/10.1016/j.spa.2008.09.007},
  volume       = {119},
  year         = {2009},
}