Analysis of Simulated Annealing for Optimization.

Abstract

Simulated annealing is a popular Monte Carlo algorithm for combinatorial optimization. The annealing algorithm simulates a nonstationary finite state Markov chain whose state space is the domain of the cost function to be minimized. We analyze this chain focusing on those issues most important for optimization. In all of our results we consider an arbitrary partition optimization: important special cases are when I is the set of minimum cost states or a set of all states with sufficiently small cost. We give a lower bound on the probability that the chain visits I at some time. This bound may be useful even when-the algorithm does not converge. We give conditions under which the chain converges to I in probability and obtain an estimate of the rate of convergence as well. We also give conditions under which the chain visits I infinitely often visits I almost always, or does not converge to I with probability 1. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1985
Accession Number
ADA170174

Entities

People

  • Sanjoy K. Mitter
  • Saul B. Gelfand

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Annealing
  • Classification
  • Computer Science
  • Computers
  • Convergence
  • Electrical Engineering
  • Markov Chains
  • Massachusetts
  • Notation
  • Numbers
  • Optimization
  • Probability
  • Random Variables
  • Real Numbers
  • Two Dimensional
  • Weak Convergence

Fields of Study

  • Mathematics

Readers

  • Adaptive Control and Estimation with Uncertainty in Dynamic Systems.
  • Operations Research
  • Statistical inference.

Technology Areas

  • Space