The Langevin Equation as a Global Minimization Algorithm

  • Basilis Gidas
Conference paper
Part of the NATO ASI Series book series (volume 20)


During the past two years a great deal of attention has been given to simulated annealing as a global minimization algorithm in combinatorial optimization problems [11], image processing problems [2], and other problems [9]. The first rigorous result concerning the convergence of the annealing algorithm was obtained in [2]. In [4], the annealing algorithm was treated as a special case of non-stationary Markov chains, and some optimal convergence estimates and an ergodic theorem were established. Optimal estimates for the annealing algorithm have recently been obtained by nice intuitive arguments in [7].


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Dixon, L.C.W., and G.P. Szegö (eds.): Towards Global Optimization 2, North-Holland, (1978).Google Scholar
  2. 2.
    Geman, S. and D. Geman: “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images”, IEEE transactions, PAMI 6(1984), 721–741.CrossRefzbMATHGoogle Scholar
  3. 3.
    Geman, S. and C.R. Huang: “Diffusions for Global Optimization”, preprint, 1984.Google Scholar
  4. 4.
    Gidas, B.: “Non-Stationary Markov Chains and Convergence of the Ánnealing Algorithm”, J. Stat. Phys. 39 (1985), 73–131.CrossRefzbMATHMathSciNetGoogle Scholar
  5. 5.
    Gidas, B.: “Global Minimization via the Langevin Equation” in preparation.Google Scholar
  6. 6.
    Grenander, U.: Tutorial in Pattern Theory, Brown University, (1983).Google Scholar
  7. 7.
    Hajek, B.: “Cooling Schedules for Optimal Annealing”, preprint, 1985.Google Scholar
  8. 8.
    Helffer, B. and I. Sjöstrand: “Puits Multiples en Mecanique Semi-Classique IV, Etude du Complexe de Witten”, preprint, 1984.Google Scholar
  9. 9.
    Hinton, G., T. Sejnowski, and D. Ackley: “Boltzmann Machine: Constraint Satisfaction Networks that Learn”., preprint, 1984.Google Scholar
  10. 10.
    Kan, A., C. Boender, and G. Timmer: “A Stochastic Approach to Global Optimization”, preprint, 1984.Google Scholar
  11. 11.
    Kirkpatrick, S., CD. Gelatt, and M. Vecchi: “Optimization by Simulated Annealing”, Science 220, 13 May (1983) 621–680.MathSciNetGoogle Scholar
  12. 12.
    Metropolis, N., et. al.: “Equations of State Calculations by Past Computing Machines”, J. Chem. Phys. 21 (1953), 1087–1091.CrossRefGoogle Scholar
  13. 13.
    Parisi, G.: “Prolegomena To any Further Computer Evaluation of the QCD Mass Spectrum”, in Progress in Gauge Field Theory Cargese (1983).Google Scholar
  14. 14.
    Simon, B.: “Semiclassical Analysis of Low Lying Eigenvalues I. Non-degenerate Minima: Asymptotic Expansions”, Ann. Inst. Henri Poincaré 38 (1983), 295–307.zbMATHGoogle Scholar
  15. 15.
    Witten, E.: “Supersymmetry and Morse Theory”, J. Diff. Geometry 17 (1982), 661–692.zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1986

Authors and Affiliations

  • Basilis Gidas
    • 1
  1. 1.Division of Applied MathematicsBrown UniversityUSA

Personalised recommendations