Convergence Results for a Class of Time-Varying Simulated Annealing Algorithms

Mathieu Gerber; Luke Bornn

doi:10.1016/j.spa.2017.07.007

Convergence Results for a Class of Time-Varying Simulated Annealing Algorithms

Mathieu Gerber, Luke Bornn

Research output: Contribution to journal › Article (Academic Journal) › peer-review

9 Citations (Scopus)

266 Downloads (Pure)

Abstract

We provide a set of conditions which ensure the almost sure convergence of a class of simulated annealing algorithms on a bounded set X ⊂ R^d based on a time-varying Markov kernel. The class of algorithms considered in this work encompasses the one studied in Belisle (1992) and Yang (2000) as well as its derandomized version recently proposed by Gerber and Bornn (2016). To the best of our knowledge, the results we derive are the first examples of almost sure convergence results for simulated annealing based on a time-varying kernel. In addition, the assumptions on the Markov kernel and on the cooling schedule have the advantage of being trivial to verify in practice.

Original language	English
Number of pages	22
Journal	Stochastic Processes and their Applications
Early online date	19 Jul 2017
DOIs	https://doi.org/10.1016/j.spa.2017.07.007
Publication status	E-pub ahead of print - 19 Jul 2017

Keywords

Digital sequences
Global optimization
Simmulated annealing

Access to Document

10.1016/j.spa.2017.07.007

Full-text PDF (accepted author manuscript)
This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Elsevier at http://www.sciencedirect.com/science/article/pii/S0304414917301758?via%3Dihub. Please refer to any applicable terms of use of the publisher.
Accepted author manuscript, 438 KB

https://arxiv.org/abs/1511.07304

Handle.net

Persistent link

Dr Mathieu Gerber
- mathieu.gerberbristol.acuk
- School of Mathematics - Senior Lecturer in Statistical Science
- Statistical Science
Person: Academic , Member

Cite this

@article{8ae1d4f377df460cbd3dfce8a98b70c2,

title = "Convergence Results for a Class of Time-Varying Simulated Annealing Algorithms",

abstract = "We provide a set of conditions which ensure the almost sure convergence of a class of simulated annealing algorithms on a bounded set X ⊂ Rd based on a time-varying Markov kernel. The class of algorithms considered in this work encompasses the one studied in Belisle (1992) and Yang (2000) as well as its derandomized version recently proposed by Gerber and Bornn (2016). To the best of our knowledge, the results we derive are the first examples of almost sure convergence results for simulated annealing based on a time-varying kernel. In addition, the assumptions on the Markov kernel and on the cooling schedule have the advantage of being trivial to verify in practice. ",

keywords = "Digital sequences, Global optimization, Simmulated annealing",

author = "Mathieu Gerber and Luke Bornn",

year = "2017",

month = jul,

day = "19",

doi = "10.1016/j.spa.2017.07.007",

language = "English",

journal = "Stochastic Processes and their Applications",

issn = "0304-4149",

publisher = "Amsterdam:Elsevier",

}

TY - JOUR

T1 - Convergence Results for a Class of Time-Varying Simulated Annealing Algorithms

AU - Gerber, Mathieu

AU - Bornn, Luke

PY - 2017/7/19

Y1 - 2017/7/19

N2 - We provide a set of conditions which ensure the almost sure convergence of a class of simulated annealing algorithms on a bounded set X ⊂ Rd based on a time-varying Markov kernel. The class of algorithms considered in this work encompasses the one studied in Belisle (1992) and Yang (2000) as well as its derandomized version recently proposed by Gerber and Bornn (2016). To the best of our knowledge, the results we derive are the first examples of almost sure convergence results for simulated annealing based on a time-varying kernel. In addition, the assumptions on the Markov kernel and on the cooling schedule have the advantage of being trivial to verify in practice.

AB - We provide a set of conditions which ensure the almost sure convergence of a class of simulated annealing algorithms on a bounded set X ⊂ Rd based on a time-varying Markov kernel. The class of algorithms considered in this work encompasses the one studied in Belisle (1992) and Yang (2000) as well as its derandomized version recently proposed by Gerber and Bornn (2016). To the best of our knowledge, the results we derive are the first examples of almost sure convergence results for simulated annealing based on a time-varying kernel. In addition, the assumptions on the Markov kernel and on the cooling schedule have the advantage of being trivial to verify in practice.

KW - Digital sequences

KW - Global optimization

KW - Simmulated annealing

U2 - 10.1016/j.spa.2017.07.007

DO - 10.1016/j.spa.2017.07.007

M3 - Article (Academic Journal)

SN - 0304-4149

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

ER -

Convergence Results for a Class of Time-Varying Simulated Annealing Algorithms

Abstract

Keywords

Access to Document

Handle.net

Fingerprint

Profiles

Dr Mathieu Gerber

Cite this