In a nutshell

I found this paper that provides an upper bound for the amount of iterations we expect before visiting the global optimum at least once. (It then uses that number to find a lower bound on the probability of finding the optimum within a given number of steps). The trouble is, when I plugged in some numbers for the formula given in the paper, the number of iterations was so impossibly high, it would be useless. I must not have understood the paper as well as I thought. Can anyone explain why that is, or what's really going on with this formula?

My understanding so far

Stated in Lemma 3.1, the expected number of steps before the global optimal state is less than $(d \exp(\Delta / T))^D$. We're modeling the transitions between candidate solutions as a Markov process, so there's an underlying graph. The variable $d$ represents the max degree of that graph and $D$ represents the diameter, the largest distance (minimal path) between two states. In this context, $\Delta$ is the largest difference between any two state's costs out of every pair, and $T$ is the minimum temperature.

I used the traveling salesman problem to use a concrete example. The way I figured, if the method of finding new states is swapping two cities in the path, then the degree of the graph of the Markov chain would be $d={n\choose2}$, where $n$ is the number of cities. In trying to get the diameter, I used $n-1$, since I figured the worst you could do trying to get from one path to another was to swap and put each city in its place. The last city would be in the right place automatically.

For $\Delta$ and $T$, it really doesn't matter what I pick. If I plug $n=10$ into the equation $({n\choose 2}\exp(1))^{n-1}$, I get something on the order of $10^{18}$. A larger, slightly more realistic delta, like 100, breaks the calculator, it's so large.

Either my numbers for my example using TSP are way off, or I didn't understand the paper, or maybe the upper bound is too large to be useful. Possibly a fourth thing I haven't thought of. So what's going on? Thanks in advance.


If you know of any better reasons why SA works, that would be appreciated as well, since that's the ultimate goal of this inquiry. The idea of saying "it will have visited the best state within $k$ steps with probability $p$" appealed to me, but it hasn't been working out too well. I was trying to get a better understanding of why simulated annealing works. The intuitive explanation of striking a balance between a random walk and hill climbing works on some level, but I wanted a more mathematical understanding.

  • 1
    $\begingroup$ As far as I know, there is no guarantee known that SA will converge reasonably fast to an optimal solution, only that it will eventually. So, as with many other meta-heuristics, we don't really know why it works. $\endgroup$ – Discrete lizard Jan 30 '18 at 12:23
  • 1
    $\begingroup$ I'm surprised you are surprised. Theoretical bounds often fail to yield useful results when applied to specific values. The current focus of most CS theorists seems to be to demonstrate that there is a bound, not necessarily to shave all the elements down to the smallest ones possible. Some published results even have constant factors that are unavoidably and provably galactic, yet there seems to be little interest in bounds that yield insight into practical systems. (I disagree with this sentiment, but it is definitely there, evidenced by multiple anonymous reviews I have read.) $\endgroup$ – András Salamon Jan 30 '18 at 13:19
  • $\begingroup$ @Discretelizard I find that really unsatisfying, but I appreciate your insight. "Magic", I suppose. $\endgroup$ – Cordello Jan 31 '18 at 1:39
  • $\begingroup$ @AndrásSalamon I'm surprised by you're whole comment actually. I would have thought a hunt for tighter bounds would be revealing and sought after. Are you familiar with other approaches CS theorists use to try to learn more about meta-heuristics? Since an upper bound is not as prevalent as I assumed. $\endgroup$ – Cordello Jan 31 '18 at 1:42
  • $\begingroup$ @Cordello See also the more general question cstheory.stackexchange.com/q/20731/109 $\endgroup$ – András Salamon Jan 31 '18 at 7:55

Your Answer

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

Browse other questions tagged or ask your own question.