1
$\begingroup$

My understanding of simulated annealing (SA) is that at any iteration $t$, a new sample $Y_t$ is generated, which, if the objective function $E$ is improved, i.e., $E(Y_t)<E(X_{t-1})$, then $Y_t$ is accepted, that is, $X_t=Y_t$, and the iteration moves on. Otherwise, the new sample is accepted by the following probability: $P(X_t=Y_t)=\exp(E(X_{t-1})-E(Y_t))\le1$. This setting is the same as in the Hastings-Metropolis (HM) algorithm, where detailed balance equation is indeed satisfied for the underlying Boltzmann distribution $\exp(-E(X)/T)$, assuming the proposal density is symmetric, e.g., a random walk.

However, in a number of papers, including this and this, which are popular papers, the acceptance probability seems to be set as $\frac{1}{1+\exp(E(Y_t)-E(X_{t-1}))}$, which is $\le\frac{1}{2}$ for the case $E(Y_t)\ge E(X_{t-1})$. Under this acceptance probability, the Metropolis' detailed balance equation no longer holds. I believe this is also the default setting for Matlab's implementation of SA.

Can somebody explain to me why do these authors use such an acceptance rate? I spent an entire weekend surveying a number of papers, none of them explain with any clarity.

Improve this question
$\endgroup$
1
  • $\begingroup$ The temperature should appear for annealing, not for Metropolis-Hastings. $\endgroup$
    – Xi'an
    Commented Mar 30, 2020 at 17:47

2 Answers 2

Reset to default
1
$\begingroup$

This alternative acceptance probability is Barker’s formula which got published in the Australian Journal of Physics at the beginning of Barker’s PhD at the University of Adelaide.

enter image description here

As shown in the above screenshot, the basis of Barker’s algorithm is indeed Barker’s acceptance probability, albeit written in a somewhat confusing way since the current value of the chain is kept if a Uniform variate is smaller than what is actually the rejection probability.

As in Metropolis et al. (1953), the analysis is made on a discretised (finite) space, building the Markov transition matrix, stating the detailed balance equation (called microscopic reversibility). Interestingly, while Barker acknowledges that there are other ways of assigning the transition probability, his is the “most rapid” in terms of mixing. And equally interestingly, he discusses the scale of the random walk in the [not-yet-called] Metropolis-within-Gibbs move as major, targetting 0.5 as the right acceptance rate, and suggesting to adapt this scale on the go.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your introduction to the Baker's MCMC. However, the algorithm implemented by Matlab is not like that, but that an improvement is ALWAYS accepted. In case of a worse sample, the acceptance rate is Baker's rate. So put together, it is not Baker's rate. The Baker's rate alone satisfies detailed balance for sure. $\endgroup$
    – user138668
    Commented Mar 30, 2020 at 19:10
  • $\begingroup$ If an improvement is always accepted then there is no detailed balance but simulated annealing does not require detailed balance or stationarity since it aims at finding the global maximum of the energy function. This gives much more freedom in choosing the moves of the (heterogeneous) Markov. $\endgroup$
    – Xi'an
    Commented Mar 31, 2020 at 6:22
  • $\begingroup$ So you are basically saying the SA is just following some heuristics, rather than any provable principle? Essentailly as long as the process is "ergodic", it will eventually find the global min. However, there is no guarantee that it will work better than exhaustive search? $\endgroup$
    – user138668
    Commented Apr 1, 2020 at 7:51
  • $\begingroup$ The only constraint on SA is that the sequence does not get stuck in a local suboptimal mode. Anything that prevents this freeze is practically acceptable. $\endgroup$
    – Xi'an
    Commented Apr 1, 2020 at 9:54
-1
$\begingroup$

Notice that

$$ \frac{1}{1 + e^{E(Y_t)-E(X_{t-1})}} = \frac{e^{E(X_{t-1})-E(Y_t)}}{1 + e^{E(X_{t-1})-E(Y_t)}} \propto e^{E(X_{t-1})-E(Y_t)} $$

so what you are proposing as a acceptance probability is really the proportional component of a normalized logistic probabilty.

I believe in the detailed balance equation the normalizing factor disappears leaving only the proportional component which you might have seen in some treatement.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This proportionality symbol is incorrect in both $y_t$ and $x_{t-1}$. $\endgroup$
    – Xi'an
    Commented Mar 30, 2020 at 17:45
  • $\begingroup$ But in one formula, the rate is in [0,1], in the other it is in [0,1/2]. They are thus obviously not the same. If detailed balance holds in one case, it cannot hold in the other, given that the target distribution is the same (holding T constant). $\endgroup$
    – user138668
    Commented Mar 30, 2020 at 18:37
  • $\begingroup$ Barker's formula leads to detailed balance just like Metropolis-Hastings. See for instance Art Owen's Monte Carlo notes or our own book.. $\endgroup$
    – Xi'an
    Commented Mar 30, 2020 at 18:51
  • $\begingroup$ Matlab's implementation is a hybrid between Baker's and standard HM, together they do not satisfy detailed balance. Please see my comment in the other answer. $\endgroup$
    – user138668
    Commented Mar 30, 2020 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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