# Mathematical foundation of using MCMC in global optimization

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.

• Have you checked the keyword simulated annealing? – Xi'an Jan 5 '16 at 7:06
• Thanks. I did. I have seen no material that proves the correctness of simulated annealing in any sense, though. Give me a link if you have. – zell Jan 5 '16 at 15:41
• Proof of correctness of simulated annealing: Do it and hope you get the right answer. QED. – Mark L. Stone Apr 17 '16 at 18:15

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.

• Note that historically the Metropolis-Hastings algorithm was not used for optimisation in the above sense. – Xi'an Jan 5 '16 at 15:29
• what that is supposed to mean @Xi'an? AFAIK historically MH was not used for optimisation all together, or was it? – Jorge Leitao Jan 5 '16 at 15:36
• I think you've missed the point of simulated annealing a bit. By using a carefully designed sequence of $\beta$ values, you can ensure that the simulated annealing algorithm will converge to a global optimum with high probability. Simulated annealing algorithms are actually very well established for solving global optimization problems. Note that because the resulting algorithm doesn't have the Markov property (it's non-stationary), the samples generated by simulated annealing aren't a proper sample from the distribution. – Brian Borchers Jan 5 '16 at 15:40
• @Leitao. MCMC is guaranteed to converge to the sampled distribution -- reason why it shines. But in your response, you seem to ignore that fact. I up-voted for acknowledging your inputs only but I believe your vision about MCMC or simulated annealing is too limited to give a correct answer. – zell Jan 5 '16 at 15:53
• @BrianBorchers, The OP asked for "what is the reason why the Metropolis-Hasting algorithm can handle problem B". I answered that question, and justified why MH fails to guarantee a global maximum. Stimulated annealing is arguably a MCMC for the reason you mentioned, and it is arguably a MH algorithm, as it also violates detailed balance in the limit $\beta \rightarrow \infty$. For these reasons, I decided to only lightly touch the topic by making the connection of MH with S. Annealing. I agree with your remarks, but I don't see how they help to answer the question. – Jorge Leitao Jan 5 '16 at 15:57