Stopping Rules for Global Optimization
One of the major problems in heuristics for global optimization
is the choice of an adequate stopping rule. In the presentation of test
results, methods are usually compared on the basis of their
performance on problems with known solutions. However, in practical
problems, one does not know the solution in advance, and needs a
criterion that tells the program when to stop searching for a better
local minimizer.
The criterion should be stringent enough that it
does not waste too many function values after the global minimum has
been found, but it should also be loose enough to ensure that in typical
cases, the algorithm does not terminate before the global minimizer
has been found. That these two goals are conflicting makes the
problem so difficult.
Stochastic approaches to the design of suitable stopping criteria
are surveyed in Section 6 of the article
C.G.E. Boender and H.E. Romeijn, Stochastic methods,
pp. 829-869 in: R. Horst and P.M. Pardalos (eds.),
Handbook of Global Optimization, Kluwer, Dordrecht 1995.
A recurring simple scheme in this discussion is that an algorithm that
employs multiple local searches should be stopped when the number n of
local minimizations done is related to the number w of different local
minima obtained by n>N(w), where N(w) is a function depending on the
assumptions made. (Several specific implicit definitions of N(w) are
given in the above reference.)
This result is theoretically justified for the
multiple random start method only, but may serve as a guideline also for
other methods that use multiple local searches. A suitable function N(w)
should probably be determined empirically for each algorithm by
testing on a large number of cases obtained by randomly
varying algorithmic choices or test problem characteristics (such as
bound constraints).
Global Optimization
my
home page (http://www.mat.univie.ac.at/~neum)
Arnold Neumaier (Arnold.Neumaier@univie.ac.at)