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

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

doi:10.1109/CDC.2005.1583226

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 proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Pages	6626-6631
Number of pages	6
DOIs	https://doi.org/10.1109/CDC.2005.1583226
State	Published - 2005
Event	44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 - Seville, Spain Duration: Dec 12 2005 → Dec 15 2005

Publication series

Name	Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Volume	2005

Other

Other	44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05
Country/Territory	Spain
City	Seville
Period	12/12/05 → 12/15/05

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1109/CDC.2005.1583226

Cite this

Hannig, J., Chong, E. K. P., & Kulkarni, S. R. (2005). Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms. In Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 (pp. 6626-6631). Article 1583226 (Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05; Vol. 2005). https://doi.org/10.1109/CDC.2005.1583226

Hannig, Jan ; Chong, Edwin K.P. ; Kulkarni, Sanjeev R. / Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms. Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05. 2005. pp. 6626-6631 (Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05).

@inproceedings{86c73c2b595543d280aa311ef91de582,

title = "Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms",

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.",

author = "Jan Hannig and Chong, {Edwin K.P.} and Kulkarni, {Sanjeev R.}",

year = "2005",

doi = "10.1109/CDC.2005.1583226",

language = "English (US)",

isbn = "0780395689",

series = "Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05",

pages = "6626--6631",

booktitle = "Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05",

note = "44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05 ; Conference date: 12-12-2005 Through 15-12-2005",

}

Hannig, J, Chong, EKP & Kulkarni, SR 2005, Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms. in Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05., 1583226, Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05, vol. 2005, pp. 6626-6631, 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05, Seville, Spain, 12/12/05. https://doi.org/10.1109/CDC.2005.1583226

Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms. / Hannig, Jan; Chong, Edwin K.P.; Kulkarni, Sanjeev R.
Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05. 2005. p. 6626-6631 1583226 (Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05; Vol. 2005).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Hannig, Jan

AU - Chong, Edwin K.P.

AU - Kulkarni, Sanjeev R.

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33847207753&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847207753&partnerID=8YFLogxK

U2 - 10.1109/CDC.2005.1583226

DO - 10.1109/CDC.2005.1583226

M3 - Conference contribution

AN - SCOPUS:33847207753

SN - 0780395689

SN - 9780780395688

T3 - Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05

SP - 6626

EP - 6631

BT - Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05

T2 - 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05

Y2 - 12 December 2005 through 15 December 2005

ER -

Hannig J, Chong EKP, Kulkarni SR. Relative frequencies of non-homogeneous Markov chains in simulated annealing and related algorithms. In Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05. 2005. p. 6626-6631. 1583226. (Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference, CDC-ECC '05). doi: 10.1109/CDC.2005.1583226

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

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this