On the convergence of Metropolis-type relaxation and annealing with constraints

We discuss the asymptotic behavior of time-inhomogeneous Metropolis chains for solving constrained sampling and optimization problems. In addition to the usual inverse temperature schedule (beta(n))(nis an element ofN*), the type of Markov processes under consideration is controlled by a divergent sequence (theta(n))(nis an element ofN*) of parameters acting as Lagrange multipliers. The associated transition probability matrices (P-betan,P-thetan)(nis an element ofN*) are defined by P-beta,(theta) = q (x, y)exp (-beta (W-theta(y) - W-theta(x))(+)) for all pairs (x, y) of distinct elements of a finite set Omega, where q is an irreducible and reversible Markov kernel and the energy function W-theta is of the form W-theta = U + thetaV for some functions U, V: Omega --> R. Our approach, which is based on a comparison of the distribution of the chain at time n with the invariant measure of P-betan,P-thetan, requires the computation of an upper bound for the second largest eigenvalue in absolute value of P-betan,P-thetan. We extend the geometric bounds derived by Ingrassia and we give new sufficient conditions on the control sequences for the algorithm to simulate a Gibbs distribution with energy U on the constrained set Omega = {x is an element of Omega: V(x) = min(zis an element ofOmega) V(z)} and to minimize U over Omega.