zbMATH — the first resource for mathematics

Interval computations, rigour and non-rigour in deterministic continuous global optimization. (English) Zbl 1228.90080
Summary: Deterministic branch and bound methods for the solution of general nonlinear programs have become increasingly popular during the last decade or two, with increasing computer speed, algorithmic improvements, and multiprocessors. Presently, there are several commercial packages. Although such packages are based on exhaustive search, not all of them rigorously take account of round-off error, singularities, and other possibilities. Popular non-rigorous packages have much in common with mathematically rigorous packages, including overall structure and basic techniques. Nonetheless, it is not trivial to make non-rigorous packages rigorous. We (1) define different kinds of answers that global optimization software can claim to provide; (2) explain where rigour might be needed and where it is not practical; (3) briefly review salient techniques common to deterministic branch and bound methods; (4) illustrate pitfalls in non-rigorous branch and bound methods; (5) outline some of the techniques to make non-rigorous software rigorous, and provide guidance for research into and implementation of these techniques; (6) provide some theoretical backing, with examples, for the convergence of common relaxation techniques.

90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI