A Contractor Based on Convex Interval Taylor

Ignacio Araya 1 Gilles Trombettoni 2, 3, 4, * Bertrand Neveu 5, 6
* Auteur correspondant
2 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe BIOINFO
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
4 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
6 IMAGINE [Marne-la-Vallée]
CSTB - Centre Scientifique et Technique du Bâtiment, LIGM - Laboratoire d'Informatique Gaspard-Monge, ENPC - École des Ponts ParisTech
Abstract : Interval Taylor has been proposed in the sixties by the interval analysis community for relaxing non-convex continuous constraint systems. However, it generally produces a non-convex relaxation of the solution set. A simple way to build a convex polyhedral relaxation is to select a corner of the studied domain/box as expansion point of the interval Taylor form, instead of the usual midpoint. The idea has been proposed by Neumaier to produce a sharp range of a single function and by Lin and Stadtherr to handle n * n (square) systems of equations. This paper presents an interval Newton-like operator, called X-Newton, that iteratively calls this interval convexification based on an endpoint interval Taylor. This general-purpose contractor uses no preconditioning and can handle any system of equality and inequality constraints. It uses Hansen's variant to compute the interval Taylor form and uses two opposite corners of the domain for every constraint. The X-Newton operator can be rapidly encoded, and produces good speedups in constrained global optimization and non-convex constraint satisfaction. First experiments compare X-Newton with affine arithmetic.
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00673447
Contributeur : Gilles Trombettoni <>
Soumis le : jeudi 23 février 2012 - 19:09:14
Dernière modification le : lundi 5 novembre 2018 - 15:48:02
Document(s) archivé(s) le : vendredi 23 novembre 2012 - 14:31:14

Fichier

RR-7887.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00673447, version 1

Citation

Ignacio Araya, Gilles Trombettoni, Bertrand Neveu. A Contractor Based on Convex Interval Taylor. [Research Report] RR-7887, INRIA. 2012, pp.23. 〈hal-00673447〉

Partager

Métriques

Consultations de la notice

705

Téléchargements de fichiers

370