×

Termination criteria in the Moore-Skelboe algorithm for global optimization by interval arithmetic. (English) Zbl 1048.90144

Floudas, Christodoulos A. (ed.) et al., Frontiers in global optimization. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7699-1/hbk). Nonconvex Optim. Appl. 74, 585-597 (2004).
Summary: We investigate unconstrained optimization with an objective function that has an unknown and possibly large number of local minima. By varying the selection and termination criteria, we obtain several variants of the Moore-Skelboe algorithm for distinct tasks in nonconvex global optimization. All of these terminate after having found the best answer that is possible, given the precision of the underlying hardware and given the expression for the objective function. The first algorithm finds the best lower bound for the global minimum. This is then extended to a version that adds an upper bound.
Often not only the global minimum is required, but also possibly existing points that achieve near-optimality, yet are far from the points at which the global minimum occurs. In response to this requirement we define the \(\delta\)-minimizer, the set of points at which the objective function is within \(\delta\) of the global minimum.
We then present algorithms that return a set of boxes. In one of these, the union of the boxes in this set contains a \(\delta\)-minimizer. If this union is small, then we know that there is a well-defined global minimum. In the other version, the union of the boxes returned is contained in a \(\delta\)-minimizer. If this union is large, then we know that there is a wide choice of parameters that yield near-optimal objective function values.
For the entire collection see [Zbl 1031.90001].

MSC:

90C26 Nonconvex programming, global optimization
65K05 Numerical mathematical programming methods
90C31 Sensitivity, stability, parametric optimization
65G30 Interval and finite arithmetic
PDFBibTeX XMLCite