## 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 language | English (US) |
---|---|

Pages (from-to) | 427-452 |

Number of pages | 26 |

Journal | Probability in the Engineering and Informational Sciences |

Volume | 16 |

Issue number | 4 |

DOIs | |

State | Published - 2002 |

## ASJC Scopus subject areas

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