Simulated annealing with time-dependent energy function via Sobolev inequalities (Q1272167)

The approach to the investigation of the simulated annealing algorithm based on the spectral gap estimates and Sobolev inequalities [see e.g. \textit{R. Holley} and \textit{D. Stroock}, Commun. Math. Phys. 115, No. 4, 553-569 (1988; Zbl 0643.60092)] is extended to the case of a time dependent energy function. More precisely: let \(X\) be a finite set, let us consider a family of energy functions \(U_{t} : X\to \mathbf R\). Let \(q\) be an irreducible transition probability on \(X\) with a reversible measure \(\pi \), let \(\beta : \mathbf R_{+}\to ]0,+\infty [\) be an increasing function. Set \[ q_{t}(x,y) = \exp \{-\beta _{t}(U_{t}(y)-U_{t}(x))^{+}\}q(x,y), \;x\neq y, \quad q_{t}(x,x) = 1-\sum _{y\neq x} q_{t}(x,y), \] then \(q_{t}\) is reversible with respect to the Gibbs measure \(\pi _{t}\) with energy \(U_{t}\) at inverse temperature \(\beta _{t}\) with a reference measure \(\pi \). Define a self-adjoint operator \(L_{t}\) on \(L^{2}(\pi _{t})\) by \(L_{t}\Phi = \sum _{y\in X} (\Phi (y)-\Phi (\cdot))q_{t}(\cdot , y)\) and denote by \(Y_{t}\) the Markov process corresponding to transition kernels \(P_{s,t}\) on \(X\) that solve the Kolmogorov equation \[ \frac {\partial}{\partial t} (P_{s,t}\Phi)(x) = P_{s,t}(L_{t}\Phi)(x), \quad P_{s,s}\Phi = \Phi , \quad t>s, \;x\in X. \] Under some regularity assumptions on \(U_{t}\) and \(\beta _{t}\), at first the precise order of the second smallest eigenvalue of \(-L_{t}\) is established and then an upper bound on the \(L^{2}(\pi _{t})\)-norm of the Radon-Nikodym derivative of the law of \(Y_{t}\) with respect to \(\pi _{t}\) is given. Furthermore, the entrance time of the algorithm into a set \(V\subset X\) is estimated in terms of \(\pi _{t}(X\setminus V)\).