# 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.

## Thoughts

Created: 2022-03-13 Sun 21:45

Validate