{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/22215"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/22215","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"An eigenvalue-based approach to the finite time behavior of simulated annealing","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Desai, Madhav P."],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":["Rao, Vasant B."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T13:32:44Z","date_published":"2011-05-07T13:32:44Z","updated_at":"2026-07-22T22:25:19Z","subjects":["Engineering, Electronics and Electrical"],"languages":["eng"],"rights":["Copyright 1992 Desai, Madhav Pandurang"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9215802","(UMI)AAI9215802"],"render_values":[{"text":"AAI9215802","href":null,"code":true},{"text":"(UMI)AAI9215802","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/22215","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Rao, Vasant B."]},{"key":"dc:creator","label":"Author","values":["Desai, Madhav P."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T13:32:44Z","10000-01-01","1992"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Engineering, Electronics and Electrical"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1992 Desai, Madhav Pandurang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/22215","AAI9215802","(UMI)AAI9215802"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2011-05-07T13:32:44Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9215802.pdf: 5107478 bytes, checksum: 34677d54ae74ca6fd7a5ae196dffbad3 (MD5) Previous issue date: 1992","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:56:06Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:26:12-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["An eigenvalue-based approach to the finite time behavior of simulated annealing"]}]}],"canonical_facts":{"dc:contributor":["Rao, Vasant B."],"dc:creator":["Desai, Madhav P."],"dc:date":["2011-05-07T13:32:44Z","10000-01-01","1992"],"dc:description":["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.","Made available in DSpace on 2011-05-07T13:32:44Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9215802.pdf: 5107478 bytes, checksum: 34677d54ae74ca6fd7a5ae196dffbad3 (MD5) Previous issue date: 1992","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:56:06Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:26:12-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["http://hdl.handle.net/2142/22215","AAI9215802","(UMI)AAI9215802"],"dc:language":["eng"],"dc:rights":["Copyright 1992 Desai, Madhav Pandurang"],"dc:subject":["Engineering, Electronics and Electrical"],"dc:title":["An eigenvalue-based approach to the finite time behavior of simulated annealing"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:19Z"}