On the convergence rate of annealing processes. (English) Zbl 0665.60090

Chiang, Tzuushuh; Chow, Yunshyong

SIAM J. Control Optimization 26, No. 6, 1455-1470 (1988).

Let \(X_ t\) be an inhomogeneous Markov process defined on \(S=\{0,1,...,N\}\) with transition rate \[ Q_{ij}=P(i,j)\exp [-(u(j)- u(i))^ t/T(t)]\quad for\quad j\neq i,\quad and\quad =-\sum_{k\neq i}Q_{ik}(t)\quad for\quad j=i, \] where T(t) is the temperature and u(i) is the energy level at i. The paper investigates the rate of convergence of \(P(X_ t=i)\) and shows that \[ \lim_{t\to \infty}P(X(t)=i)/\exp (-u(i)/T(t)) \] exists and is positive for each \(i\in S\) under certain conditions on T(t). These limits are independent of the initial distribution of \(X_ 0\) and can be obtained through solving systems of linear equations.

Reviewer: L.Lakatos

MSC:

60J99	Markov processes
60J27	Continuous-time Markov processes on discrete state spaces
15B51	Stochastic matrices
15A18	Eigenvalues, singular values, and eigenvectors
90B40	Search theory

Keywords:

simulated annealing; forward equation; rate of convergence