×

zbMATH — the first resource for mathematics

Singular perturbed Markov chains and exact behaviors of simulated annealing processes. (English) Zbl 0755.60047
Summary: We study asymptotic properties of discrete and continuous time generalized simulated annealing processes \(X(\cdot)\) by considering a class of singular perturbed Markov chains which are closely related to the large deviation of perturbed diffusion processes. Convergence of \(X(t)\) in probability to a set \(S_ 0\) of desired states, e.g., the set of global minima, and in distribution to a probability concentrated on \(S_ 0\) are studied. The corresponding two critical constants denoted by \(d\) and \(\Lambda\) with \(d\leq\Lambda\) are given explicitly. When the cooling schedule is of the form \(c/\log t\), \(X(t)\) converges weakly for \(c>0\). Whether the weak limit depends on \(X(0)\) or concentrates on \(S_ 0\) is determined by the relation between \(c\), \(d\), and \(\Lambda\). When \(c>\Lambda\), the expression for the rate of convergence for each state is also derived.

MSC:
60J05 Discrete-time Markov processes on general state spaces
60F10 Large deviations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cerny, V. (1982).A Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm, Institute of Physics and Biophysics, Comenius University, Bratislava, Czechoslovakia.
[2] Chiang, T.-S., and Chow, Y. (1988). On the convergence rate of annealing processes.SIAM J. Control Opt. 17, 1455-1470. · Zbl 0665.60090
[3] Chiang, T.-S., and Chow, Y. (1989). A limit theorem for a class of inhomogeneous Markov processes.Ann. Prob. 17, 1483-1502. · Zbl 0687.60070
[4] Chiang, T.-S., Hwang, C.-R., and Sheu, S.-J. (1987). Diffusion for global optimization in ? n .SIAM J. Control Opt. 25, 737-753. · Zbl 0622.60093
[5] Freidlin, M. I., and Wentzell, A. D. (1984).Random Perturbations of Dynamical Systems, Springer-Verlag, New York. · Zbl 0522.60055
[6] Geman, S., and Geman, D. (1984). Stochastic relaxation, Gibbs distribution, and the Baysian restoration of images.IEEE Trans. Pattern Anal. Mach. Intel. 6, 721-741. · Zbl 0573.62030
[7] Geman, S., and Hwang, C.-R. (1986). Diffusion for global optimization.SIAM J. Control Opt. 24, 1031-1043. · Zbl 0602.60071
[8] Gihman, I. I., and Shorohod, A. V. (1975).The Theory of Stochastic Processes II. Springer-Verlag, New York.
[9] Hajek, B. (1985). Cooling schedules for optimal annealing.Math. Oper. Res. 13, 311-329. · Zbl 0652.65050
[10] Hwang, C.-R., and Sheu, S.-J. (1989). On the weak reversibility condition in simulated annealing.Soochow J. Math. 15, 159-170. · Zbl 0694.60064
[11] Hwang, C.-R., and Sheu, S.-J. (1990). Large-time behavior of perturbed diffusion Markov processes with applications to the second eigenvalue problem for Fokker-Planck operators and simulated annealing.Acta Appl. Math. 19, 253-295. · Zbl 0708.60056
[12] Kirkpatrick, S., Gelatt, C. D., and Veochi, M. P. (1983). Optimization by simulated annealing.Science 220, 671-680. · Zbl 1225.90162
[13] Tsitsiklis, J. (1985).Markov Chains with Rare Transitions and Simulated Annealing, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA.
[14] van Laarhoven, P. J. M., and Aarts, E. M. L. (1987).Simulated Annealing: Theory and Applications, D. Reidel, Dordrecht. · Zbl 0643.65028
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.