On constrained simulation and optimization by Metropolis chains

Let \(\pi\) be an everywhere positive probability measure on a finite state space \(E\) given by \(\pi(x)= z^{-1}\exp[-H(x)]\), where \(H: E\to R\) is the associated energy function. One is interested in some subset \(E_c\subset E\) defined by a constrained equation \(E_i:= \{J=0\}\), where the function of constraints \(J: E\to R^+\) is otherwise positive. Let \(\pi_c\) be the restriction of \(\pi\) on \(E_c\). There are two problems: (1) simulate the distribution \(\pi_c\); (2) minimize \(H\) over \(E_c\). To solve these problems, Markov chains endowed with a time-inhomogeneous Metropolis dynamic is a natural idea. Let \((\beta_k)\), \((\lambda_k)\) be two positive nondecreasing sequences and \[ H_k(x):= \beta_k[H(x)+ \lambda_kJ(x)],\qquad k\geq 1. \] Let \(P^{(m,k)}= P_{m+1}\cdots P_k\) be the transition probabilities from time \(m\) to \(k\). The aim of the note is to establish conditions on the control sequences \((\beta_k)\) an \((\lambda_k)\) which guarantee that the chain \((X_k)\) is strongly ergodic in the sense that, for all \(m\geq 1\), \[ \lim_{k\to\infty} \sup_\mu\|\mu P^{(m,k)}- \pi_\infty\|= 0, \] where \(\|\cdot\|\) is the total variation distance and the supremum is taken over all probability measures on \(E\). Under ergodicity the inhomogeneous Markov chain \((X_k)\) will simulate the constrained distribution \(\pi_c\) and with the defined dynamic the chain provides a minimizing sequence \(H\) over \(E_c\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On constrained simulation and optimization by Metropolis chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1971384)