Inner Regions and Interval Linearizations for Global Optimization

Gilles Trombettoni 1, 2 Araya Ignacio 3 Bertrand Neveu 4 Gilles Chabert 5
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
5 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
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.
Type de document :
Communication dans un congrès
AAAI 2011, Aug 2011, San Francisco, United States. 2011
Liste complète des métadonnées


https://hal.inria.fr/hal-00648085
Contributeur : Gilles Chabert <>
Soumis le : lundi 5 décembre 2011 - 09:55:42
Dernière modification le : mercredi 29 juillet 2015 - 01:25:38
Document(s) archivé(s) le : vendredi 16 novembre 2012 - 14:20:44

Fichier

trombettoni_AAAI2011.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00648085, version 1

Citation

Gilles Trombettoni, Araya Ignacio, Bertrand Neveu, Gilles Chabert. Inner Regions and Interval Linearizations for Global Optimization. AAAI 2011, Aug 2011, San Francisco, United States. 2011. <hal-00648085>

Partager

Métriques

Consultations de
la notice

555

Téléchargements du document

168