A Contractor Based on Convex Interval Taylor - École des Ponts ParisTech Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

A Contractor Based on Convex Interval Taylor

Résumé

Interval Taylor has been proposed in the sixties by the interval analysis community for relaxing continuous non-convex 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 andby 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 constraint satisfaction. First experiments compare X-Newton with affine arithmetic.
Fichier principal
Vignette du fichier
cpaior2012.pdf (192.97 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00733848 , version 1 (20-09-2012)

Identifiants

  • HAL Id : hal-00733848 , version 1

Citer

Ignacio Araya, Gilles Trombettoni, Bertrand Neveu. A Contractor Based on Convex Interval Taylor. CPAIOR 2012, 2012, Nantes, France. pp.1-16. ⟨hal-00733848⟩
677 Consultations
2545 Téléchargements

Partager

Gmail Facebook X LinkedIn More