1
$\begingroup$

I'm reading a technical report on Simulated Annealing: On the Convergence Time of Simulated Annealing, by Sanguthevar Rajasekaran. You may find it following this link.

Given $G=(V, E)$ is the graph whose vertices are possible solutions to the given problem, and $E$ is the set of edges between the neighbours, the goal is to prove convergence of SA. For that purpose, the author assumed that $G$ is strongly connected and denoted the diameter of $G$, its degree and maximal energy difference between vertices by $D$, $d$ and $\Delta$, respectively.

There is a lemma on the 6th page:

If $X$ is any state in $V$, then the expected number of steps before a global optimal state is visited starting from $X$ is $\le (\frac 1 d \times e^{-\Delta / T})^{-D}$.

The probability to visit a neighbour $S_j$ after $S_i$ is:

$$\frac 1 d \times e^{\frac{-\Delta E}{T}}$$ where $\frac 1 d$ is the probability of selecting $S_j$ of all $d$ neighbours of $S_i$, and $e^{\frac{-\Delta E}{T}}$ is the probability to actually move to it. $T$ is held constant in the model.

In the proof of the lemma, the author determines the probability to visit a global optimum $g$ from any state $X$ as $\ge [\frac 1 d \times e^{-\frac \Delta T}]^D$ and finishes the proof:

This implies that the expected number of steps before $g$ is visited is $\le [d e^{\frac \Delta T}]^D$.

Would anyone care to explain how do we get the estimate for the number of steps? I'm stuck with it, but am really, really intrigued to figure this out. :)

$\endgroup$
  • $\begingroup$ In addition to the answer by Jannis Teunissen, the easiest way to find answers would have been to contact the author of the paper :-) $\endgroup$ – Wolfgang Bangerth Dec 28 '15 at 19:30
1
$\begingroup$

Suppose the probability to reach the optimum from any state is $p$, in other words at each step the probability of reaching the optimum has a Bernoulli distribution with parameter $p$. The number of steps required then has a Geometric distribution, with mean $1/p$. If you add back the inequality signs you get the result you stated.

$\endgroup$

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.