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

Marc C. Robini, Yoram Bresler, Isabelle E. Magnin

Research output: Contribution to journalArticlepeer-review

Abstract

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 (β n) n∈ℕ* the type of Markov processes under consideration is controlled by a divergent sequence (θ n) n∈ℕ* of parameters acting as Lagrange multipliers. The associated transition probability matrices (P βn,θn) n∈ℕ* are defined by P β,θ = q(x,y)exp(-β(W θ(y) - W θ(x)) +) for all pairs (x,y) of distinct elements of a finite set Ω, where q is an irreducible and reversible Markov kernel and the energy function W θ is of the form W θ = U + θV for some functions U, V:Ω→ℝ. Our approach, which is based on a comparison of the distribution of the chain at time n with the invariant measure of P βn,θn, requires the computation of an upper bound for the second largest eigenvalue in absolute value of P βn,θn, 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 Ω̃ = {x ∈ Ω: V(x) = min z∈Ω V(z)} and to minimize U over Ω̃.

Original languageEnglish (US)
Pages (from-to)427-452
Number of pages26
JournalProbability in the Engineering and Informational Sciences
Volume16
Issue number4
DOIs
StatePublished - 2002

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Fingerprint

Dive into the research topics of 'On the convergence of metropolis-type relaxation and annealing with constraints'. Together they form a unique fingerprint.

Cite this