zbMATH — the first resource for mathematics

Simulated annealing via Sobolev inequalities. (English) Zbl 0643.60092
The new idea of the paper is to use the Sobolev inequality and logarithmic Sobolev inequality to study the simulated annealing algorithm. Even though the state space treated here is finite many results are meaningful for other cases. The approach yields some information about the rate at which the annealing process is tending to the minima of the given cost function. In fact, it is proved that the estimates for the rate are optimal in some sense.
Reviewer: Chen Mufa

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60F99 Limit theorems in probability theory
Full Text: DOI
[1] Chiang, T.-S., Chow, Y.: On eigenvalues and annealing rates, (to appear in Math. Oper. Res.): On the convergence rate of a special class of annealing processes. (to appear in Soochow J. Math.): On the convergence rate of annealing process. Preprint
[2] Geman, S., Geman, D.: Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell.6, 721-741 (1984) · Zbl 0573.62030 · doi:10.1109/TPAMI.1984.4767596
[3] Geman, S., Hwang C.-R.: Diffusions for global optimization: Preprint (1984)
[4] Gidas, B.: Non-stationary Markov chains and convergence of the annealing algorithm. J. Stat. Phys.39, 73-131 (1985) · Zbl 0642.60049 · doi:10.1007/BF01007975
[5] Goldstein, L.: Mean square rates of convergence in the continuous time simulated annealing algorithm onR d . Preprint (1986)
[6] Gross, L.: Logarithmic Sobolev inequalities, Am. J. Math.97, 1061-1083 (1976) · Zbl 0318.46049 · doi:10.2307/2373688
[7] Hajek, B.: Cooling schedules for optimal annealing. Preprint submitted to Math. Oper. Res. (1985)
[8] Kirkpatrick, S., Gelett, C. D., Vecchi, M. P.: Optimization by simulated annealing. Science220, 621-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[9] Stroock, D.: An introduction to the theory of large deviations. Berlin, Heidelberg, New York: Springer 1984 · Zbl 0552.60022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.