About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
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.
Related
Conference paper
Federated acoustic modeling for automatic speech recognition
Conference paper