Fast simulated annealing in Rd with an application to maximum likelihood estimation in statespace models
(2009) In Stochastic Processes and their Applications 119(6). p.19121931 Abstract
 We study simulated annealing algorithms to maximise a function psi on a subset of Rd. 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 Rd. 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 loglikelihood function for a statespace model. (C) 2008 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1425502
 author
 Rubenthaler, Sylvain; Rydén, Tobias ^{LU} and Wiktorsson, Magnus ^{LU}
 organization
 publishing date
 2009
 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
 1879209X
 DOI
 10.1016/j.spa.2008.09.007
 language
 English
 LU publication?
 yes
 id
 9d95efea846c469e814eb6cfd0362232 (old id 1425502)
 date added to LUP
 20090701 15:41:01
 date last changed
 20170423 03:45:09
@article{9d95efea846c469e814eb6cfd0362232, abstract = {We study simulated annealing algorithms to maximise a function psi on a subset of Rd. 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 loglikelihood function for a statespace model. (C) 2008 Elsevier B.V. All rights reserved.}, author = {Rubenthaler, Sylvain and Rydén, Tobias and Wiktorsson, Magnus}, issn = {1879209X}, keyword = {Simulated annealing,Convergence rate,Maximum likelihood estimation}, language = {eng}, number = {6}, pages = {19121931}, publisher = {Elsevier}, series = {Stochastic Processes and their Applications}, title = {Fast simulated annealing in Rd with an application to maximum likelihood estimation in statespace models}, url = {http://dx.doi.org/10.1016/j.spa.2008.09.007}, volume = {119}, year = {2009}, }