Global optimization and simulated annealing (Q1176572)

The first six pages of this well-written paper can be considered an introduction to global optimization algorithms that first focuses on stochastic methods, then on simulated annealing. The authors then present theoretical results for an idealized simulated annealing algorithm that are based on the ergodic theory of Markov chains. The main result gives a formula for the probability that this idealized algorithm converges to within a given tolerance of global minima of the objective function. A second part of the paper considers practical variants of the ideal algorithm. Here, the authors present natural choices for tuning parameters, such as the length of the truncated Markov chains, stopping criteria, and initial choice of and amount to decrement the control parameter. A theorem, analogues to that for the ideal algorithm, is presented. Numerical results comparing six other algorithms to the one in the paper are reported. The authors claim that the new algorithm may allow solution of higher-dimensional optimization problems, since it uses less storage than alternatives, yet does not require substantially greater running time. They indicate that further research is necessary to refine the ideas. A significant set of test problems for global optimization appears in two appendices. Twenty-seven references appear.