Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms

Jan Hannig, Edwin K.P. Chong, Sanjeev R. Kulkarni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We consider a class of non-homogeneous Markov chains arising in simulated annealing and related stochastic search algorithms. Using only elementary first principles, we analyze the convergence and rate of convergence of the relative frequencies of visits to states in the Markov chain. We describe in detail three examples, including the standard simulated annealing algorithm, to show how our framework applies to specific stochastic search algorithms - these examples have not previously been recognized to be sufficiently similar to share common analytical grounds. Our analysis, though elementary, provides the strongest sample-path convergence results to date for simulated annealing type Markov chains. Our results serve to illustrate that by taking a purely sample-path view, surprisingly strong statements can be made using only relatively elementary tools.

Original languageEnglish (US)
Title of host publicationProceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Pages6626-6631
Number of pages6
Volume2005
DOIs
StatePublished - Dec 1 2005
Event44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 - Seville, Spain
Duration: Dec 12 2005Dec 15 2005

Other

Other44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
CountrySpain
CitySeville
Period12/12/0512/15/05

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms'. Together they form a unique fingerprint.

Cite this