×

zbMATH — the first resource for mathematics

Simulated annealing with time-dependent energy function. (English) Zbl 0790.90058
We consider, in a general algebraic framework, a class of time- inhomogeneous evolutions which reduce to a variant (with time-dependent energy function) of the well-known simulated annealing algorithm when the algebra \(\mathcal M\) involved is \({\mathcal L}^ \infty(X)\), \(X\) being a finite set or the \(d\)-dimensional torus. We compare the time evolved \(\varphi_ n\) of an arbitrary initial state \(\varphi_ 0\) on \(\mathcal M\) with the instantaneous equilibrium state \(\mu_ n\) of the inhomogeneous evolution, and we prove asymptotic indistinguishability of the two under suitable conditions.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] Chiang, T.S., Hwang, K.R., Sheu, S.J.: Diffusion for Global Optimization in \(\mathbb{R}\)n. SIAM J. Control Optim.25, 737–753 (1987) · Zbl 0622.60093
[2] Davies, E.B.: Heat Kernels and Spectral Theory. Cambridge: Cambridge University Press 1989 · Zbl 0699.35006
[3] Frigerio, A.: Simulated Annealing and Quantum Detailed Balance. J. Stat. Phys.58, 325–354 (1990) · Zbl 0716.47039
[4] Frigerio, A., Verri, M.: Long-Time Asymtotic Properties of Dynamical Semigroups onW *-algebras. Math. Z.180, 275–286 (1982) · Zbl 0481.46031
[5] Geman, S., Geman, D.: Stochastic Relaxation, Gibbs Distribution, and the Bayesian Restoration of Images. IEEE Trans. Pattern Anal. Math. Intell.6, 721–741 (1984) · Zbl 0573.62030
[6] Geman, S., Hwang, C.R.: Diffusions for Global Optimization. SIAm J. Control. Optim.24, 1031–1043 (1986) · Zbl 0602.60071
[7] Gidas, B.: Non-Stationary Markov Chains and Convergence of the Annealing Algorithm. J. Stat. Phys.39, 73–131 (1985) · Zbl 0642.60049
[8] Hajek, B.: Cooling Schedules for Optimal Annealing. Math. Oper. Res.13, 311–329 (1988) · Zbl 0652.65050
[9] Holley, R.A., Kusuoka, S., Stroock, D.W.: Asymptotics of the spectral gap with application to the theory of simulated annealing. J. Funct. Anal.83, 333–347 (1989) · Zbl 0706.58075
[10] Holley, R., Stroock, D.W.: Simulated Annealing via Sobolev Inequalities. Commun. Math. Phys.115, 553–569 (1988) · Zbl 0643.60092
[11] Hwang, C.R.: Laplace’s method revisited: weak convergence of probability measures. Ann. Probab.8, 1177–1182 (1980) · Zbl 0452.60007
[12] Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by Simulated Annealing. Science220, 621–680 (1983) · Zbl 1225.90162
[13] Kossakowski, A., Frigerio, A., Gorini, V., Verri, M.: Quantum Detailed Balance and KMS Condition. Commun. Math. Phys.57, 97–110 (1977); Erratum, Commun. Math. Phys.60, 96 (1978) · Zbl 0374.46060
[14] Verbeure, A.: Detailed Balance and Critical Slowing Down. In: Accardi, L., von Waldenfels, W. (eds.) Quantum Probability and Applications III. Proceedings, Oberwolfach 1987. (Lect. Notes Math., vol. 1303, pp. 354–362) Berlin Heidelberg New York: Springer 1988 · Zbl 0639.60100
[15] Younes, L.: Estimation and Annealing for Gibbsian Fields. Ann. Inst. H. PoincarĂ© B24, 269–294 (1988) · Zbl 0651.62091
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.