Files in this item



application/pdf9215802.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:An eigenvalue-based approach to the finite time behavior of simulated annealing
Author(s):Desai, Madhav P.
Doctoral Committee Chair(s):Rao, Vasant B.
Department / Program:Electrical and Computer Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
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.
Issue Date:1992
Rights Information:Copyright 1992 Desai, Madhav Pandurang
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9215802
OCLC Identifier:(UMI)AAI9215802

This item appears in the following Collection(s)

Item Statistics