On the problem of exit from cycles for simulated annealing processes - A backward equation approach

• 成果类型: Article
• 署名作者: Chiang, TS; Chow, YY
• 署名单位: Academia Sinica - Taiwan
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• 发表日期: 1998
• 页码: 896-916
• 关键词: relaxation; schedules

摘要

For a simulated annealing process X-t on S with transition rates g(ij)(t) = p(ij) exp(-(u(i, j))/T(t)) where i, j is an element of S and T(t) down arrow 0 in a suitable way, we study the exit distribution P-t,P-i(X-tau = a) and mean exit time E-t,E-i(tau) of X-t from a cycle c as t --> infinity. A cycle is a particular subset of S whose precise definition will be given in Section 1. Here tau is the exit time of the process from c containing i and a is an arbitrary state not in c. We consider the differential (backward) equation of P-t,P-i(X-tau = a) and E-t,E-i(tau) and show that lim(t-->infinity) P-t,P-i(X-tau = a)/exp(-(U(c, a)- V(c))/T(t)) and lim(t-->infinity) E-t,E-i(tau)/exp(V(c)/T(t)) exist and are independent of i is an element of c. The constant U(c, a) is usually referred to as the cost from c to a and V(c), (less than or equal to U(c, a)) is the minimal cost coming out of c. We also obtain estimates of \P-t,P-i(X-tau = a) - P-t,P-j(X-tau = a)\ and \E-t,E-i(tau)- E-t,E-j(tau)\ for i not equal j as t --> infinity. As an application, we shall show that similar results hold for the family of Markov processes with transition rates q(ij)(epsilon) = p(ij) exp(-U(i, j)/epsilon) where epsilon > 0 is small.