Simulated Annealing Type Algorithms for Multivariate Optimization

Abstract

We study the convergence of a class of discrete-time continuous-state stimulated annealing type algorithms for multivariate optimization. The general algorithm that we consider is of the form Xk+1= Xk - a(k)(delU(Xk) + xik) + bkWk. Here U(.) is a smooth function on a compact subset of real number r, {xik} is a sequence of real number r - valued random variables, {Wk} is a sequence of independent standard r-dimensional Gaussian random variables, and {ak}, {bk} are sequences of positive numbers which tend to zero. These algorithms arise by adding slowly decreasing white Gaussian noise to gradient descent, random search, and stochastic approximation algorithms. We show that under suitable conditions on U(.), {xik}, {ak} and {bk} that Xk converges in probability to the set of global minima of U(.).

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1989
Accession Number
ADA460156

Entities

People

  • Sanjoy K. Mitter
  • Saul B. Gelfand

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Annealing
  • Convergence
  • Differential Equations
  • Digital Computers
  • Electrical Engineering
  • Engineering
  • Equations
  • Image Processing
  • Markov Chains
  • Markov Processes
  • Optimization
  • Probability
  • Random Variables
  • Sequences
  • Simulations
  • Standards

Fields of Study

  • Mathematics

Readers

  • Analytical Mechanics
  • Marine Mammal Biology
  • Operations Research