  


Complete Search in Continuous Global Optimization and Constraint Satisfaction
A. Neumaier (Arnold.Neumaierunivie.ac.at) Abstract: 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  centering around rounding error handling and testing methodology  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. Keywords: Category 1: Global Optimization (Theory ) Citation: to appear in: Acta Numerica 2004 (A. Iserles, ed.) Cambridge University Press 2004. http://www.mat.univie.ac.at/~neum/papers.html#glopt03 Download: [PDF] Entry Submitted: 10/20/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  