Simulated annealing type Markov chains and their order balance equations

Abstract

Generalized simulated-annealing type Markov chains where the transition probabilities are proportional to powers of a vanishing small parameter are considered. An 'order of recurrence,' which quantified the asymptotic behavior of the state occupation probability is associated with each state. These orders of recurrence satisfy a fundamental balance equation across every edge-cut in the graph of the Markov chain. The Markov chain converges in a Cesaro-sense to the set of states having the largest recurrence orders. These results convert the analytic problem of determining the asymptotic properties of the time-inhomogeneous stochastic process into a purely algebraic problem of solving the balance equations to determine the recurrence orders. Graph theoretic algorithms are provided to determine the solutions of the balance equations. By applying these results to the problem of optimization by simulated annealing, it is shown 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. This allows the necessary and sufficient condition for the optimization algorithm to hit the global minimum with probability one to be obtained.