An eigenvalue-based approach to the finite time behavior of simulated annealing
Desai, Madhav P.
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/22215
Description
Title
An eigenvalue-based approach to the finite time behavior of simulated annealing
Author(s)
Desai, Madhav P.
Issue Date
1992
Doctoral Committee Chair(s)
Rao, Vasant B.
Department of Study
Electrical and Computer Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Language
eng
Abstract
In this thesis, we present a framework under which the finite time behavior of the simulated annealing for combinatorial optimization can be studied. We will use linear algebraic methods for this purpose. The simulated annealing algorithm will be modeled as a finite space, discrete time Markov chain which can then be represented by a probability transition matrix whose entries are controlled by a parameter known as the temperature.
We first consider a simpler version of the algorithm in which the temperature is held to a constant value. The algorithm can then be modeled by a time homogeneous Markov chain which converges to an equilibrium distribution. In this case, the speed of convergence can be ascertained if certain eigenvalues of the transition matrix are known, and the equilibrium distribution depends on the distribution of costs. We explore different approaches to obtain bounds on these eigenvalues and apply these bounds to study the convergence of the fixed-temperature algorithm to solve the integer composition problem, which is NP-complete. We present a detailed study of the cost distribution for this problem. Consequently, we are able to study the computational complexity of the fixed-temperature algorithm to solve the integer composition problem.
We also consider the case of simulated annealing in which the temperature is reduced according to a cooling schedule. By using an absorbing chain model of the algorithm, we are able to study its finite time behavior in terms of an eigenvalue of the absorbing chain's transition matrix. We provide asymptotic bounds for this eigenvalue from which we obtain an asymptotic sufficiency result for the annealing algorithm to find an optimal state. We also obtain structural bounds for this eigenvalue, from which the finite time behavior of the algorithm may be studied.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
