Convergence of Simulated Annealing Based Algorithms

Question

I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge fast (based on satisfying some properties) to global/local optimal point and doesn't oscillate in the optimal points (or any related fast about its stability). Are there any useful literature about it?

Answer 1

If you want to learn about the theory behind simulated annealing, you should look for "Markov chain Monte Carlo". You might learn from this how the temperature (schedule) influences the convergence, how it can be monitored (or even controlled) and when you still can expect "progress" of a simulated annealing run.

Is it worth to study simulated annealing at all, given statements like: "Note that simulated annealing usually performs much worse than modern methods."? I don't know. Some global optimizers like the "DIRECT optimization algorithm" are easy to use without any fiddle parameters, and reliably find the global minimum. Other modern methods may perform better than simulated annealing, but come with many fiddle parameters, and may miss the global minimum if you don't set these correctly. This means that you often need some experience before you can effectively employ some great new optimization algorithm. The problem is that this state of affairs makes it difficult to evaluate which of a suite of different optimization algorithms is the best for your given problem, because you never know whether you used these algorithms correctly, and whether they would have performed better had you only...

I have used simulated annealing in practice. If I made a mistake in the problem formulation such that the resulting problem was not well conditioned, simulated annealing was unable to find the global minimum. (There are methods which are less affected by this.) Often it was possible to formulate the problem in a better conditioned form, and this normally solved the problem. (Here, "not well conditioned" just means that the largest eigenvalue of the Hessian divided by the smallest non-zero eigenvalue is big.)

Answer 2

I copied this answer from computational science

There is a theorem that syas that a black box algorithm is guaranteed to find the global minimum of an arbitrary smooth (i.e., twice continuously differentiable) function if and only if it samples points densely in the search space.

Here dense is meant in the topological sense, i.e., it must sample points in arbirarily small neighborhoods of every point.

In this case, the worst case complexity is O((dδ)−n), [the Latex parser chokes with nested big brackets] where d is the diameter of the search space and δ the guaranteed error in x

Edit: While this looks like being the worst case complexity for locating an δ-accurate x rather than for locating a point for a ϵ-accurate f, the complexity for the latter is as bad (even for the rather big value of ϵ=(ffirst−fglobal)/2), as one can easily construct a smooth function which interpolates all data points so far but takes much smaller values in the center of the largest open ball not containing one of the points evaluated.

Thus guaranteed convergence to a global minimum is worthless in practice. (For example, uniformly random search has a convergence guarantee to the global minimizer, whereas most practically fast algorithms don't have one.)

Note that simulated annealing usually performs much worse than modern methods. Rather use code recommended in:

Comparison of derivative-free optimization algorithms (2012, by Nick Sahinidis)

Black-Box Optimization Benchmarking (BBOB) 2012 (by Auger, Hansen, et al.)