A Contractor Based on Convex Interval Taylor

Ignacio Araya; Gilles Trombettoni; Bertrand Neveu

hal-00673447, version 1

A Contractor Based on Convex Interval Taylor

Ignacio Araya ()^a^, 1, Gilles Trombettoni ( Author to contact preferably , )^b^, 2, 3, 4, Bertrand Neveu (, )^c^, 5, 6

N° RR-7887 (2012)

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.

a – Universidad Técnica Federico Santa María (UTFSM)
b – Université de Nice Sophia Antipolis (UNS)
c – ENPC
1: Departamento de Informatica [Valparaíso, Chile]
Universidad Técnica Federico Santa María (UTFSM)
2: Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe BIOINFO
Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
3: Institut de recherche en informatique de Toulouse (IRIT)
CNRS : UMR5505 – Institut National Polytechnique de Toulouse - INPT – Université des Sciences Sociales - Toulouse I – Université Toulouse I [UT1] Capitole – Université Toulouse le Mirail - Toulouse II – Université Paul Sabatier [UPS] - Toulouse III
4: COPRIN (INRIA Sophia Antipolis)
INRIA – Ecole des Ponts ParisTech
5: Laboratoire d'Informatique Gaspard-Monge (LIGM)
Université Paris-Est Marne-la-Vallée (UPEMLV) – ESIEE – Ecole des Ponts ParisTech – Fédération de Recherche Bézout – CNRS : UMR8049
6: IMAGINE
CSTB – Ecole des Ponts ParisTech – Université Paris-Est Créteil Val-de-Marne (UPEC)

hal-00673447, version 1
http://hal.inria.fr/hal-00673447
oai:hal.inria.fr:hal-00673447
From: Gilles Trombettoni <>
Submitted on: Thursday, 23 February 2012 19:09:14
Updated on: Monday, 27 February 2012 13:34:23

See detailed view

Associated documents

PDF :

Export

Bibtex EndNote TEI RefWorks

%% hal-00673447, version 1
%% http://hal.inria.fr/hal-00673447
@techreport{araya:hal-00673447,
    hal_id = {hal-00673447},
    url = {http://hal.inria.fr/hal-00673447},
    title = {{A Contractor Based on Convex Interval Taylor}},
    author = {Araya, Ignacio and Trombettoni, Gilles and Neveu, Bertrand},
    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.}},
    keywords = {intervals; Taylor; convex polyhedral relaxation; global optimization},
    language = {English},
    affiliation = {Departamento de Informatica [Valpara{\'\i}so, Chile] , Laboratoire d'Informatique, Signaux, et Syst{\`e}mes de Sophia-Antipolis (I3S) / Equipe BIOINFO , Institut de recherche en informatique de Toulouse - IRIT , COPRIN - INRIA Sophia Antipolis , Laboratoire d'Informatique Gaspard-Monge - LIGM , IMAGINE},
    pages = {23},
    type = {Research Report},
    institution = {INRIA},
    number = {RR-7887},
    year = {2012},
    month = Feb,
    pdf = {http://hal.inria.fr/hal-00673447/PDF/RR-7887.pdf},
}

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="hal-00673447"><monogr>
<author><persName><forename>Ignacio</forename><surname>Araya</surname></persName>
<affiliation>
<orgName type="team">Departamento de Informatica [Valparaíso, Chile]</orgName>
<country>CL</country>
<orgName type="institution">Universidad Técnica Federico Santa María (UTFSM)</orgName>
</affiliation>
</author>
<author><persName><forename>Gilles</forename><surname>Trombettoni</surname></persName>
<affiliation>
<orgName type="team">Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe BIOINFO</orgName>
<country>FR</country>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">IRIT</orgName>
<orgName type="team">Institut de recherche en informatique de Toulouse</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR5505</orgName>
<orgName type="institution">Institut National Polytechnique de Toulouse - INPT</orgName>
<orgName type="institution">Université des Sciences Sociales - Toulouse I</orgName>
<orgName type="institution">Université Toulouse I [UT1] Capitole</orgName>
<orgName type="institution">Université Toulouse le Mirail - Toulouse II</orgName>
<orgName type="institution">Université Paul Sabatier [UPS] - Toulouse III</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Sophia Antipolis</orgName>
<orgName type="team">COPRIN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Ecole des Ponts ParisTech</orgName>
</affiliation>
</author>
<author><persName><forename>Bertrand</forename><surname>Neveu</surname></persName>
<affiliation>
<orgName type="laboratory">LIGM</orgName>
<orgName type="team">Laboratoire d'Informatique Gaspard-Monge</orgName>
<country>FR</country>
<orgName type="institution">Université Paris-Est Marne-la-Vallée (UPEMLV)</orgName>
<orgName type="institution">ESIEE</orgName>
<orgName type="institution">Ecole des Ponts ParisTech</orgName>
<orgName type="institution">Fédération de Recherche Bézout</orgName>
<orgName type="institution">CNRS : UMR8049</orgName>
</affiliation>
<affiliation>
<orgName type="team">IMAGINE</orgName>
<country>FR</country>
<orgName type="institution">CSTB</orgName>
<orgName type="institution">Ecole des Ponts ParisTech</orgName>
<orgName type="institution">Université Paris-Est Créteil Val-de-Marne (UPEC)</orgName>
</affiliation>
</author>
<title type="main" level="m">A Contractor Based on Convex Interval Taylor</title><title type="main" level="m">A Contractor Based on Convex Interval Taylor</title><imprint><biblScope type="publicationDate">2012-02-23</biblScope><biblScope type="pp">23</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/hal-00673447</idno><idno type="HALFile">http://hal.inria.fr/hal-00673447/PDF/RR-7887.pdf</idno></biblStruct>
</listBibl>
</listBibl>