2
$\begingroup$

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)$.

  1. 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?

  2. 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?

  3. 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(1, \frac{p_{j} h_{ji}}{p_{i} h_{ij}}). $$

If $h$ is symmetric, i.e. $h_{ij}=h_{ji}$, then $$ a_{ij} = \min(1, \frac{p_{j}}{p_{i}}). $$

$\endgroup$
  • $\begingroup$ Interesting! I do not think it matters very much that the proposal is also temperature dependent given that the argument for convergence is not a Markovian one. The target is already moving with the temperature, so the Markov chain is inhomogeneous. Your question 1 has no answer in that the validation of the Metropolis-Hastings algorithm does not apply to inhomogeneous chains. $\endgroup$ – Xi'an May 7 '12 at 9:17
  • $\begingroup$ @Xi'an: Thanks! (1) It is nice to hear from another expert! I must confess I have been a fan of your for quite a while, and your books are still on my to-read list (once I get the money). (2) May I have some pointers to some references on this matter? Thanks! $\endgroup$ – Tim May 7 '12 at 13:41
  • $\begingroup$ Thanks! What I mean is that you need another approach than MCMC theory to handle simulated annealing. See, e.g., Andrieu et al., 2001 $\endgroup$ – Xi'an May 7 '12 at 20:04
1
$\begingroup$

Whether the proposal should depend on the temperature is problem-specific. If you mean can the proposal depend on the temperature, then the answer is yes. The only important things is that within each temperature, the chain is a convergent Markov chain. Note that it's not only within-chain proposals that can be temperature-dependent. The proposals to move from a point in one temperature to a point in a new temperature can depend on the two temperature's concerned and here I'd argue it's even more likely that a temperature(s) dependent proposal would be necessary.

$\endgroup$
  • $\begingroup$ Thanks! (1) Can you justify somehow for temperature dependent proposal? (2) Do you think temperature independent proposal wrong? $\endgroup$ – Tim May 7 '12 at 20:24
  • 1
    $\begingroup$ No, a temperature independent proposal isn't wrong but it may not be as good as one that does depend on the temperature. If you think about how flat the stationary distribution is at high temperatures and how peaked it may become at low temperatures, it makes sense that different proposals might be better at different temperatures. A simple example would be a random walk proposal where you migth want to adjust the scale according to temperature. $\endgroup$ – Steve Brooks May 8 '12 at 11:12
  • 1
    $\begingroup$ With regard your fist question, the stationary distribution at any temperature is obviously temperature dependent and so long as the Markov chain converges to this distribution then everything will work OK. There's nothing in the theory that says says the proposal can't depend on anything other than previous states of the chain (otherwise it's not Markov). $\endgroup$ – Steve Brooks May 8 '12 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.