zbMATH — the first resource for mathematics

Complete search in continuous global optimization and constraint satisfaction. (English) Zbl 1113.90124
Summary: This survey covers the state of the art of techniques for solving general-purpose constrained global optimization problems and continuous constraint satisfaction problems, with emphasis on complete techniques that provably find all solutions (if there are finitely many). The core of the material is presented in sufficient detail that the survey may serve as a text for teaching constrained global optimization.
After giving motivations for and important examples of applications of global optimization, a precise problem definition is given, and a general form of the traditional first-order necessary conditions for a solution. Then more than a dozen software packages for complete global search are described.
A quick review of incomplete methods for bound-constrained problems and recipes for their use in the constrained case follows; an explicit example is discussed, introducing the main techniques used within branch and bound techniques. Sections on interval arithmetic, constrained propagation and local optimization are followed by a discussion of how to avoid the cluster problem. Then a discussion of important problem transformations follows, in particular of linear, convex, and semilinear (= mixed integer linear) relaxations that are important for handling larger problems.
Next, reliability issues – centring on rounding error handling and testing methodologies – are discussed, and the COCONUT framework for the integration of the different techniques is introduced. A list of challenges facing the field in the near future concludes the survey.

90C26 Nonconvex programming, global optimization
90B40 Search theory
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C51 Interior-point methods
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis
65Y15 Packaged methods for numerical algorithms
65G30 Interval and finite arithmetic
65K05 Numerical mathematical programming methods
PDF BibTeX Cite
Full Text: DOI