  Metastability is a formidable challenge to Markov chain Monte Carlo methods.
In this paper we present methods for algorithm design to meet this challenge.
The design problem we consider is temperature selection for the infinite
swapping scheme, which is the limit of the widely used parallel tempering
scheme obtained when the swap rate tends to infinity. We use a recently
developed tool for the analysis of the empirical measure of a small noise
diffusion to transform the variance reduction problem into an explicit
optimization problem. Our first analysis of the optimization problem is in the
setting of a double well model, and it shows that the optimal selection of
temperature ratios is a geometric sequence except possibly the highest
temperature. In the same setting we identify two different sources of variance
reduction, and show how their competition determines the optimal highest
temperature. In the general multi-well setting we prove that a pure geometric
sequence of temperature ratios is always nearly optimal, with a performance gap
that decays geometrically in the number of temperatures.
