Suppose we are using Simulated Annealing (SA) to minimize a cost function $L:\mathbb{R} \to \mathbb{R}$. Here is my algorithm:
(1). Randomly choose a $x_0 \in \mathbb{R}$. Set $x=x_0$ and $T=T_0$.
for k=1:m
(2). Propose a new point $x_{new}$ by sampling $N(x, \sigma^2)$, where $\sigma$ is a constant.
(3). If $L(x_{new}) < L(x)$,
then set $x=x_{new}$.
else If $u \leq \exp(-\frac{L(x_{new}) - L(x)}{T})$, where u is a sample of $U(0,1)$, then set $x=x_{new}$.
(4). Lower $T$ according to some scheme, such as $T=cT$ for a constant $c \in (0,1)$.
end for for k
Someone (whose credibility is doubted by me) said that in step (2), the propose distribution for a new point $x_{new}$ should be $N(x, T)$ which changes as $T$ changes, instead of $N(x, \sigma^2)$ fixed for all $T$ values. The majority of the sources I have found do not mention much about the proposal distribution, including not mentioning if it depends on the temperature. But I found a similar claim on page 183 of this book Neuro-fuzzy and soft computing by Jang:
In conventional SA, also known as Boltzmann machines, the generating function is a Gaussian probability density function: $$x_{new} - x \sim N(0, T \times I_{n,n})$$ where $T$ is the temperature, and $n$ is the dimension of the space under exploration. It has been proven in ref (Geman and Geman's Stochastic relaxation, Gibbs distribution and the Bayesian Restoration in images, PAMI 1984) that a Boltzmann machine using the aforementioned generating function can find a global optimum of $L(x)$ if the temperature $T$ is reduced not faster than $T_0/\ln(k)$.
My understanding is that both choices for the proposal distribution are correct, since SA uses the Metropolis–Hastings (M-H) algorithm for sampling the target distribution with density $$p(x) = Z_T \exp(-\frac{x}{T}),$$ where $Z_T$ is a normalization factor for $p$ to be a probability density function. Under either of the two choices for the propose distribution of $x_{new}$, i.e. either $N(x, T)$ or $N(x, \sigma^2)$, according to the M-H algorithm (see the Appendix below), the accept probability of proposed state $x_{new}$ given current state $x$ in step (3) should be $$ a_{ij} = \min(1, \exp(-\frac{L(x_{new}) - L(x)}{T})), $$ which is exactly the same as in the step (3) of SA algorithm. So I think the two choices for the propose distribution of $x_{new}$, i.e. $N(x, T)$ and $N(x, \sigma^2)$, would both work. Am I correct?
Does the SA algorithm under both choices for the proposal distribution converge to the optimal solution in some probabilistic sense, possibly under some additional conditions?
If they do in question 2, which one is better, in terms of some standard(s)? For example, which one converges more quickly?
Thanks and regards!
Appendix: Calculating acceptance probability in the M-H algorithm.
Let
- $p_{i}$ be the target density at state $i$,
- $h_{ij}$ be the proposal density for transition to state $j$ given current state $i$,
- $a_{ij}$ be the accept probability of proposed state $j$ given current state $i$.
By the detailed balance equation, after choosing the proposal density $h$, the accept probabilities $a$ is computed as $$ a_{ij} = \min\left(1, \frac{p_{j} h_{ji}}{p_{i} h_{ij}}\right). $$
If $h$ is symmetric, i.e. $h_{ij}=h_{ji}$, then $$ a_{ij} = \min\left(1, \frac{p_{j}}{p_{i}}\right). $$
