Simulated Annealing

A stochastic local search algorithm used for finding the global minimum of some function \(E(x)\), in this context called the energy function. This is done by using a variant of the Metropolis-Hastings Algorithm as described below.

At iteration \(t\), we propose a new state \(x_{t+1} \sim \pi_p(x_{t+1}|x_t)\), and the acceptance probability is \(A_{t+1} = \min(1, e^{-\frac{E(x_{t+1})-E(x_t)}{T_t}})\)

Here, \(T_t\) is the temperature of the system, which is often changed over time according to some cooling schedule. Some examples are the logarithmic schedule \(T_t \propto \frac{1}{\log(t+1)}\), the exponential cooling schedule \(T_t = \gamma T_t : \gamma \in (0,1]\). At high temperatures there is a lot of movement on the energy function surface, meanwhile cooler temperatures will give smaller pertubations. Thus cooling too quickly could result in being stuck at local minima.