Mathematical foundation of using MCMC in global optimization

Question

MCMC is commonly used to compute the integral in the form of

$$\text{Problem A.}~~\int F(x)\pi(x) $$

where $\pi$ is hidden. In the literature, it is explained why MCMC can handle problem A by construcing an Metroplis Hasting sampling.

Then, people also claim that MCMC, in part., the Metropolis-Hasting algorithm, can be used to calculate function minima.

$$\text{Problem B.}~~\min F(x)$$

The Metropolis-Hasting algorithm itself is not hard to follow. My question is, what is the reason why the Metropolis-Hasting algorithm can handle problem B? Is there any mathematical guarantee? A precise, mathematical explanation would be appreciated.

Answer 1

Consider the Metropolis Hastings algorithm with a target distribution $\pi(x) = e^{-\beta E(x)}$ where $E$ is a real valued function (historically the energy of the physical system). (note that $\pi(x) = \pi(E(x))$).

Lets see what are the consequences of this choice to the expected relative number of samples with a given energy E, $H(E)$:

$$H(E) = \int \delta(E - E(x)) \pi(E(x)) P(x) dx = e^{-\beta E} P(E)/Z$$

where $P(E)$ is the marginal of $E$, given by

$$P(E) = \int P(x,E) dx = \int \delta(E - E(x)) P(x)dx$$

and $Z(\beta) = \int e^{-\beta E} P(E) dE$ is the normalization constant.

It is customary to write $P(E) = \exp(S(E))$ where $S$ is the entropy. This leads to

$$H(E) \propto e^{-\beta E + S(E)}$$

and the maximum of $H(E)$ occurs for $E^*$ solution of $\beta = dS/dE(E^*)$.(*)

Under the assumption that $dS/dE(E^*)$ is monotonic decreasing, increasing $\beta$ decreases $E^*$. In particular, as $\beta$ approaches $\infty$ ($-\infty$), the distribution $H(E)$ approaches a Dirac delta at $E^*=E_\min$ ($E^*=E_\max$).

When 1) $dS/dE(E^*)$ is not monotonically decreasing, this typically leads to an ergodicity breaking of the algorithm and other approaches are required. It can also happen that, even though $dS/dE(E^*)$ is monotonically decreasing, 2) the function $E(x)$ is very "rough" and the algorithm gets stuck on a particular local minima for an arbitrary long time.

To avoid 2), stimulated annealing is typically employed. To avoid 1) I'm not sure what it is typically done. I often use flat-histogram for both 1) and 2).

Two notes:

1. Stimulated annealing is not a MCMC because changing $\beta$ during the simulation makes the transition probability to depend on $t$ and therefore makes the algorithm non-markovian.

2. MH with $\beta \rightarrow \infty$ does not converge to the target distribution because it violates ergodicity. Once a given $E^*$ is achieved, any state with $E \le E^*$ is unvisitable.

The tricky part about reaching or not reaching the global minima requires analysing the actual convergence of the algorithm (e.g. polynomial, exponential); but I'm not familiar with these results. Maybe others can help on this.

(*) It is not a coincidence that this is also a definition of the microscopic thermodynamic temperature.