NESTED ANNEALING - A PROVABLE IMPROVEMENT TO SIMULATED ANNEALING

Simulated annealing is a family of randomized algorithms for solving multivariate global optimization problems. Empirical results from the application of simulated annealing algorithms to certain hard problems including certain types of NP-complete problems demonstrate that these algorithms yield better results than known heuristic algorithms, But for the worst case input, the time bound can be exponential. In this paper, for the first time, we show how to improve the performance of simulated annealing algorithms by exploiting some special properties of the cost function to be optimized. In particular, the cost functions we consider are small-separable, with parameter s(n). We develop an algorithm we call "Nested Annealing" which is a simple modification of simulated annealing where we assign different temperatures to different regions. Simulated annealing can be shown to have expected run time 2-OMEGA(n) whereas our improved algorithm has expected performance 2-O(s(n)). Thus for example, in many vision and VLSI layout problems, for which s(n) = O(square-root n), our time bound is 2-O(square-root n) rather than 2-OMEGA(n).