Simulated-Annealing Type Markov Chains and Their Order Balance Equations

摘要

Consider generalized simulated-annealing type Markov chains where the transition probabilities are proportional to powers of a vanishing small parameter. One can associate with each state an order of recurrence which quantifies the asymptotic behavior of the state of occupation probability. These orders of recurrence satisfy a fundamental balance equation across every edge cut in the graph of the Markov chain. Moreover, the Markov chain converges in a Cesaro sense to the set of states having the largest recurrence orders. We provide graph theoretic algorithms to determine the solutions of the balance equations. By applying these results to the problem of optimization by simulated annealing, we show that the sum of the recurrence order and the cost is a constant for all states in a certain connected set, whenever a weak-reversibility condition is satisfied. Keywords: Simulated annealing; Global optimization; Reprints. (jhd)