×

zbMATH — the first resource for mathematics

Large-time behavior of perturbed diffusion Markov processes with applications to the second eigenvalue problem for Fokker-Planck operators and simulated annealing. (English) Zbl 0708.60056
Summary: We study the large-time behavior and rate of convergence to the invariant measures of the processes \[ dX^{\epsilon}(t)=b(X^{\epsilon}(t))dt+\epsilon \sigma (X^{\epsilon}(t))dB(t). \] A crucial constant \(\Lambda\) appears naturally in our study. Heuristically, when the time is of the order \(\exp (\Lambda -\alpha)/\epsilon^ 2\), the transition density has a good lower bound and when the process has run for about \(\exp (\Lambda +\alpha)/\epsilon^ 2\), it is very close to the invariant measure. Let \(L^{\epsilon}=(\epsilon^ 2/2)\Delta -\nabla U\cdot \nabla\) be a second-order differential operator on \({\mathbb{R}}^ d\). Under suitable conditions, \(L^{\epsilon}\) has the discrete spectrum \[ 0=\lambda^{\epsilon}_ 1>-\lambda^{\epsilon}_ 2...\text{ and } \lim_{\epsilon \to 0}\epsilon^ 2 \log \lambda^{\epsilon}_ 2=- \Lambda. \] Let U be a function from \({\mathbb{R}}^ d\) to \([0,\infty)\) with suitable conditions. A nonhomogeneous Markov process Y(\(\cdot)\) governed by \[ dY(t)=-\nabla U(Y(t))dt+\sqrt{c/\log (2+t)}dB(t), \] with \(Y(0)=x\) is used to search for a global minimum of U. Let \b{S}\(=\{x |\) \(U(x)=\min_{y}U(y)\}\). There exists a critical constant \(d^*\) such that for \(c>d^*\), Y(t) uniformly converges to \b{S} in probability over x in a compact set.
The above statement fails for \(c<d^*\). For \(c>\Lambda\), Y(t) converges weakly to a probability measure which does not depend on the starting point x and concentrates on \b{S}. The techniques can also be used to study discrete simulated annealing.

MSC:
60H10 Stochastic ordinary differential equations (aspects of stochastic analysis)
60J70 Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.)
60F10 Large deviations
35P15 Estimates of eigenvalues in context of PDEs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] AartsE. M. L. and KorstJ. M. M.:Simulated Annealing and Boltzmann Machines, Wiley, New York, 1989.
[2] AgmonShmuel:Lectures on Exponential Decay of Solutions of Second-Order Elliptic Equations: Bounds on Eigenfunctions of N-Body Sch?dinger Operators, Princeton University Press, Princeton, NJ, 1982.
[3] Azencott, R.:Simulated Annealing, S?minaire Bourbaki, No. 697, 1987-88.
[4] CatoniO.: Grandes d?viations et d?croissance de la temp?rature dans les algorithmes de recuit,C.R. Acad. Sci. Paris S?rie I,307, (1988), 535-539.
[5] CernyV.: A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm,J. Optim. Theory Appl. 45 (1985), 41-51. · Zbl 0534.90091
[6] ChiangT.-S. and ChowY.: On the convergence rate of annealing processes,SIAM J. Control Optim. 26 (1988), 1455-1470. · Zbl 0665.60090
[7] ChiangT.-S. and ChowY.: A limit theorem for a class of inhogeneous Markov processes.Ann. Probab. 17 (1989), 1483-1502. · Zbl 0687.60070
[8] Chiang, T.-S. and Chow, Y.: The asymptotic behavior of simulated annealing processes with absorption, Technical Reports, Inst. of Math., Academia Sinica, 1989. · Zbl 0804.60063
[9] ChiangT.-S., HwangC.-R. and SheuS.-J.: Diffusion for global optimization inR n,SIAM J. Control Optim. 25 (1987), 737-753. · Zbl 0622.60093
[10] Connors, D. P. and Kumar, P. R.: Balance of recurrence order in time inhomogeneous Markov chains with application to simulated annealing, Preprint, 1987. · Zbl 1134.60330
[11] DayMartin V.: On the exponential exit law in the small parameter exit problem,Stochastics 8 (1983), 297-323. · Zbl 0504.60032
[12] DayMartin V.: On the asymptotic relation between equilibrium density and exit measure in the exit problem,Stochastics 12(3/4) (1984), 303-330. · Zbl 0526.60052
[13] Day, Martin V.: Localization results for densities associated with stable small-noise diffusions, Preprint, 1985.
[14] FreidlinM. I. and WentzellA. D.:Random Perturbations of Dynamical Systems, Springer, New York, 1984.
[15] FriedmanA.:Stochastic Differential Equations and Applications, Academic Press, New York, Vol. 1, 1975, Vol. 2, 1976.
[16] Geman, D.: Random fields and inverse problems in imaging, to appear inLN in Mathematics, Springer-Verlag, 1990. · Zbl 0718.60119
[17] GemanS. and GemanD.: Stochastic relaxation, Gibbs distribution and the Baysian restoration of images.IEEE Trans. Pattern Analysis Machine Intelligence 6 (1984), 721-741. · Zbl 0573.62030
[18] GemanS. and HwangC.-R.: Diffusion for global optimization,SIAM J. Control Optim. 24 (1986), 1031-1043. · Zbl 0602.60071
[19] Grenander, U.: Tutorial in pattern theory, Lecture Notes Volume, Div. Appl. Math., Brown Univ., 1984.
[20] HajekB.: Cooling schedules for optimal annealing,Math. Oper. Res. 13 (1985), 311-329. · Zbl 0652.65050
[21] HajekB.: A tutorial survey of theory and applications of simulated annealing,Proc. 24th IEEE Conf. Decision and Control, Vol. 2, pp. 755-760, 1985.
[22] HasminskiiR. Z.:Stochastic Stability of Differential Equations, Sijthoff and Noordoff Intl., Alphen-aanden-Rijn, 1980.
[23] MolleyR. and StroockD.: Simulated annealing via Sobolev inequalities,Comm. Math. Phys. 115 (1988), 553-569. · Zbl 0643.60092
[24] Holley, R., Kusuoka, S. and Stroock, D.: Asymptotics of the spectral gaps with applications to the theory of simulated annealing, 1989. · Zbl 0706.58075
[25] HwangC.-R.: Laplace’s method revisited: weak convergence of probability measures,Ann. Probab. 8 (1980), 1177-1182. · Zbl 0452.60007
[26] Hwang, C.-R., Sheu, S.-J.: Large time behaviors for perturbed diffusion Markov processes with applications, I, II, III, Technical Reports, Institute of Math., Academia Sinica, 1986.
[27] HwangC.-R. and SheuS.-J.: On the weak reversibility condition in simulated annealing,Soochow J. Math. 158 (1989), 159-170.
[28] Hwang, C.-R. and Sheu, S.-J.: Singular perturbed Markov chains and the exact behaviors of simulated annealing processes, Technical Reports, Institute of Math., Academia Sinica, 1988.
[29] KirkpatrickS., GelattC. D., and VecchiM. P.: Optimization by simulated annealing,Science 220 (1983), 671-680. · Zbl 1225.90162
[30] Kushner, H. J.: Asymptotic global behavior for stochastic oximations and diffusion with slowly decreasing noise effects: global minimization via Monte Carlo, preprint, Div. Appl. Math., Brown Univ., 1985.
[31] VanLaarhovenP. J. M. and AartsE. M. L.:Simulated Annealing: Theory and Applications, D. Reidel, Dordrecht, 1987.
[32] MatkowskyB. J. and SchussZ.: Eigenvalues of the Fokker-Planck operator and the approach to equilibrium for diffusions in potential fields,SIAM J. Appl. Math. 40 (1981), 242-254. · Zbl 0477.60057
[33] MetropolisM., RosenbluthA., RosenbluthM., TellerA. and TellerE.: Equation of state calculations by fast computing machines,J. Chem. Phys. 21 (1953), 1087-1092.
[34] MitraD., RomeoF. and Sangiovanni-VincentelliA.: Convergence and finite time behavior of simulated annealing,Adv. in Appl. Probab. 18 (1986), 747-771. · Zbl 0604.60067
[35] RieszF. and Sz. NagyB.:Functional Analysis, 3rd ed., Ungar, New York, 1955.
[36] ReedM. and SimonB.:Method of Modern Mathematical Physics, Vol. IV, Academic Press, New York, 1978.
[37] RoyerG.: A remark on simulated annealing of diffusion processes,SIAM. J. Control Optim. 27, (1989), 1403-1408. · Zbl 0689.60059
[38] SimonB.: Semiclassical analysis of low lying eigenvalues. I,Ann. Inst. H. Poincar? Sec. A 38 (1984), 295-307.
[39] SimonB.: Semiclassical analysis of low lying eigenvalues. II,Ann. of Math. (2) 120 (1984), 89-118. · Zbl 0626.35070
[40] SheuS.-J.: Asymptotic behavior of transition density of diffusion Markov process with small diffusion,Stochastics 13 (1984), 131-163.
[41] SchussZ.:Theory and Applications of Stochastic Differential Equations, Wiley, New York, 1980.
[42] StroockD. and VaradhanS. R. S.:Multidimensional Diffusion Processes, Springer, New York, 1979.
[43] Trouv?A.: Probl?mes de convergence et d’ergodicit? pour les algorithmes de recuit parall?lises,C.R. Acad. Sci. Paris, Serie I 307 (1988), 161-164. · Zbl 0661.60125
[44] Tsitsiklis, J. N.: Markov chains with rate transitions and simulated annealing, Preprint, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, 1985.
[45] YounesL.: Estimation and annealing for Gibbs fields,Ann. Inst. H. Poincar? 24 (1988), 269-294.
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.