Inner regions and interval linearizations for global optimization

Gilles Trombettoni, Ignacio Araya, Bertrand Neveu, Gilles Chabert

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

30 Scopus citations

Abstract

Researchers from interval analysis and constraint (logic) programming communities have studied intervals for their ability to manage infinite solution sets of numerical constraint systems. In particular, inner regions represent subsets of the search space in which all points are solutions. Our main contribution is the use of recent and new inner region extraction algorithms in the upper bounding phase of constrained global optimization. Convexification is a major key for efficiently lower bounding the objective function. We have adapted the convex interval taylorization proposed by Lin & Stadtherr for producing a reliable outer and inner polyhedral approximation of the solution set and a linearization of the objective function. Other original ingredients are part of our optimizer, including an efficient interval constraint propagation algorithm exploiting monotonicity of functions. We end up with a new framework for reliable continuous constrained global optimization. Our interval B&B is implemented in the interval-based explorer Ibex and extends this free C++ library. Our strategy significantly outperforms the best reliable global optimizers.

Original languageEnglish
Title of host publicationAAAI-11 / IAAI-11 - Proceedings of the 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference
Pages99-104
Number of pages6
StatePublished - 2011
Externally publishedYes
Event25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, AAAI-11 / IAAI-11 - San Francisco, CA, United States
Duration: 7 Aug 201111 Aug 2011

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume1

Conference

Conference25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, AAAI-11 / IAAI-11
Country/TerritoryUnited States
CitySan Francisco, CA
Period7/08/1111/08/11

Fingerprint

Dive into the research topics of 'Inner regions and interval linearizations for global optimization'. Together they form a unique fingerprint.

Cite this