Acta Numerica 2004
Edited by Arieh Iserles
Acta Numerica (No. 13)
Publisher: Cambridge University Press
Print Publication Year: 2004
Online Publication Date:August 2010
Chapter DOI: http://dx.doi.org/10.1017/CBO9780511569975.004
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.