Simulated annealing with time-dependent energy function via Sobolev inequalities

被引：13

作者：

Lowe, M

机构：

[1] Universität Bielefeld, Fakultät für Mathematik, 33501 Bielefeld

来源：

STOCHASTIC PROCESSES AND THEIR APPLICATIONS | 1996年 / 63卷 / 02期

关键词：

simulated annealing; Sobolev inequalities; spectral gap; Markov processes;

D O I：

10.1016/0304-4149(96)00070-1

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

We analyze the simulated annealing algorithm with an energy function U-t that depends on time. Assuming some regularity conditions on U-t (especially that U-t does not change too quickly in time), and choosing a logaIithmic cooling schedule for the algorithm, we derive bounds on the Radon-Nikodym density of the distribution of the annealing algorithm at time t with respect to the invariant measure pi(t) at time t. Moreover, we estimate the entrance time of the algorithm into typical subsets V of the state space in terms of pi(t)(V-c).

引用

页码：221 / 233

页数：13

共 21 条

[1]

Aarts E., 1989, Wiley-Interscience Series in Discrete Mathematics and Optimization

[2]

CATONI O, 1990, THESIS U PARIS SUD O

[3] L-2 CONVERGENCE OF TIME NONHOMOGENEOUS MARKOV PROCESSES: I. SPECTRAL ESTIMATES [J].