Upper bounding in inner regions for global optimization under inequality constraints

IGNACIO DANIEL ARAYA ZAMORANO, Gilles Trombettoni, Bertrand Neveu, Gilles Chabert

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

In deterministic continuous constrained global optimization, upper bounding the objective function generally resorts to local minimization at several nodes/iterations of the branch and bound. We propose in this paper an alternative approach when the constraints are inequalities and the feasible space has a non-null volume. First, we extract an inner region, i.e., an entirely feasible convex polyhedron or box in which all points satisfy the constraints. Second, we select a point inside the extracted inner region and update the upper bound with its cost. We describe in this paper two original inner region extraction algorithms implemented in our interval B&B called IbexOpt (AAAI, pp 99–104, 2011). They apply to nonconvex constraints involving mathematical operators like , (Formula presented.). This upper bounding shows very good performance obtained on medium-sized systems proposed in the COCONUT suite.

Original languageEnglish
Pages (from-to)145-164
Number of pages20
JournalJournal of Global Optimization
Volume60
Issue number2
DOIs
StatePublished - 1 Jan 2014

Keywords

  • Branch and bound
  • Global optimization
  • Inner regions
  • Interval Taylor
  • Intervals
  • Upper bounding

Fingerprint

Dive into the research topics of 'Upper bounding in inner regions for global optimization under inequality constraints'. Together they form a unique fingerprint.

Cite this