Abstract:
We consider the performance of the Metropolis algorithm when employed
for solving combinatorial optimization problems. One finds in the
literature two notions of success for the Metropolis algorithm in the
context of such problems. First, we show that both these notions are
equivalent. Next, we provide two characterizations, in other words,
necessary and sufficient conditions, for the success of the algorithm,
both characterizations being conditions on the family of Markov chains
which the Metropolis algorithm gives rise to when applied to an
optimization problem. The first characterization is that the
Metropolis algorithm is successful iff in every chain, for every set
$A$ of states not containing the optimum, the ratio of the ergodic
flow out of $A$ to the capacity of $A$ is high. The second
characterization is that in every chain the stationary probability of
the optimum is high and that the family of chains mixes rapidly. We
illustrate the applicability of our results by giving alternative
proofs of certain known results.
Bio