3 ms·
Which paper? Is it this? https://link.springer.com/article/10.1007/BF00941892 https://link.springer.com/article/10.1007/BF00941892 I'm willing to give it a shot
by flir 3y ago
Which paper? Is it this? https://link.springer.com/article/10.1007/BF00941892 https://link.springer.com/article/10.1007/BF00941892 I'm willing to give it a shot but that abstract doesn't scream "easy to read" to me.
What's an epsilon-ball? I'm guessing it somehow describes the resolution you need to sample at in order to guarantee you've found all the local maximums? I guess what I'm struggling with is that, with a probabilistic search through a space you don't already know the properties of, I don't see how that can be anything other than checking every solution in turn - in other words a brute force search.
Does this all boil down to "the worse-case scenario of simulated annealing is brute force search"? And where does the logarithmic cooling schedule come in?
- archermarks 3y agoYeah, looking at it again it's not as accessible as I remember. It's quite mathy, but well-written. An epsilon-ball is just a "ball" (circle or sphere analogue of dimension n, where n is the number of inputs) of radius epsilon (some arbitrarily small number). So you're correct that it relates to the resolution at which we can be said to "know" the solution. With simulated annealing, the cooling schedule dictates how and when the algorithm switches from exploration to exploitation. With a logarithmic cooling schedule, the cooling rate is 1 / log (1 + t), so the temperature approaches zero extremely slowly, and the algorithm basically never switches out of exploration mode. You're correct that this is basically a brute force search of the domain, and this is the implication of the theorem I mention above--ANY global optimizer reduces to brute force search in the worst case.