Complete search in continuous global optimization and constraint satisfaction

Arnold Neumaier

Veröffentlichungen: Beitrag in FachzeitschriftReviewPeer Reviewed

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 - 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.
OriginalspracheEnglisch
Seiten (von - bis)271-369
Seitenumfang101
FachzeitschriftActa Numerica
Jahrgang13
PublikationsstatusVeröffentlicht - 2004

ÖFOS 2012

  • 1020 Informatik

Fingerprint

Untersuchen Sie die Forschungsthemen von „Complete search in continuous global optimization and constraint satisfaction“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitationsweisen