Markov chains with rare transitions and simulated annealing

Markov chains with rare transitions and simulated annealing

0.00 Avg rating0 Votes
Article ID: iaor1988837
Country: United States
Volume: 14
Issue: 1
Start Page Number: 70
End Page Number: 90
Publication Date: Feb 1989
Journal: Mathematics of Operations Research
Authors:
Keywords: optimization: simulated annealing
Abstract:

We consider ‘approximately stationary’ Markov chains in which the entries of the one-step transition probability matrix are known to be of different orders of magnitude and whose structure (that is, the orders of magnitude of the transition probabilities) does not change with time. For such Markov chains we present a method for generating order of magnitude estimates for the t-step transition probabilities, for any t. We then notice that algorithms of the simulated annealing type may be represented by Markov chains which are approximately stationary over fairly long time intervals. Using our results we obtain a characterization of the convergent ‘cooling’ schedules for the most general class of algorithms of the simulated annealing type.

Reviews

Required fields are marked *. Your email address will not be published.