[PDF] Régions intérieures et linéarisations par intervalles en optimisation

View - Download Régions intérieures et linéarisations par intervalles en optimisation

Previous PDF

Next PDF

Actes JFPC 2011

Regions interieures et linearisations par intervalles en optimisation globaleGilles Trombettoni, Ignacio Araya, Bertrand Neveu, Gilles Chabert INRIA, I3S, Universite Nice{Sophia (France), UTFSM (Chili), Imagine LIGM Universite Paris{Est (France), LINA, EMN (France) Gilles.Trombettoni@inria.fr, iaraya@inf.utfsm.cl, Bertrand.Neveu@enpc.fr, Gilles.Chabert@emn.fr

Abstract

Les communautes d'analyse par intervalles et de pro- grammation (logique) par contraintes ont exploite les in- tervalles pour leur capacite a representer des ensembles innis de solutions dans les systemes de contraintes continus. En particulier, les bo^tes ou regionsinterieures permettent de representer des sous-ensembles de l'es- pace de recherche dans lesquelstoutpoint est solu- tion. Notre premiere contribution est l'utilisation d'al- gorithmes recents et nouveaux d'extraction de regions interieures dans la phase d'amelioration du majorant (fai- sable) en optimisation globale sous contraintes.

Larelaxation lineaireest egalement un ingredient

majeur, utilise notamment pour minorer la fonction ob- jectif. Nous avons adapte lataylorisation sur inter- valles convexe{ relaxation lineaire proposee par Lin et Stadtherr { pour produire des approximations po- lyhedrales ables interieure et exterieure de l'ensemble solution ainsi qu'une linearisation de la fonction objec- tif. Enn, d'autres ingredients originaux font partie de notre optimiseur, comme un algorithme de propagation de contraintes sur intervalles exploitant la monotonie des fonctions.

Nous proposons au nal un nouveau schema able

d'optimisation globale continue sous contraintes. Une implantation est disponible en tant qu'extension de l'ou- tilIbex(bibliotheque libre enC++de resolution par intervalles). En termes de performances, notre strategie depasse de maniere signicative les meilleurs optimiseurs globaux ables.

1 Introduction

Les algorithmes de B&B sur intervalles sont utili- ses pour resoudre des problemes d'optimisation glo- bale sous contraintes

1de maniere able. Ils four-1

Nous considerons dans cet article des problemes de minimi- sation.nissent soit une solution optimale (et le co^ut asso- cie avec une erreur bornee), soit une preuve d'infai- sablite. Historiquement, le B&B sur intervalles est ne avec l'analyse par intervalles [13]. Des travaux pion- niers sont decrits dans [13], [7] ou [9]. Au milieu des annees 1990, Kearfott a concu le resolveurGlobSol. Parallelement, des chercheurs en programmation par contraintes ont developpe les resolveursNumerica[21] etIcos[11], introduisant respectivement de la pro- pagation de contraintes sur intervalles et des relaxa- tions lineaires ables. Plus recemment, la communaute de programmation mathematique a propose un resol- veur, appele iciIBBA+, qui integre de la propagation de contraintes et de l'arithmetique ane [16]. Pour concilier abilite et bonne performance, les in- tervalles font face principalement a deux dicultes.

Ameliorer le majorant dans l'espace faisable

Larecherche localeest l'approche la plus utilisee

pour trouver un pointfaisable2(une solution satis- faisant les contraintes) qui ameliore la borne courante pour la fonction objectiff. Cependant, pour assurer la faisabilite en cas de contraintes d'egalite, il est neces- saire, des lors que l'espace explore contient potentiel- lement des points infaisables, d'appliquer un processus de correction et de certication apres chaque iteration de la recherche locale. Ce processus est base sur des techniques par intervalles co^uteuses [11]. Cette correc- tion rend du coup impossible, en termes de perfor-2 Une seconde approche consiste a chercher les points qui an- nulent le gradient def. Le minimum defest alors soit une solution de ce probleme, soit sur la frontiere du domaine. Mal- heureusement, la prise en compte des contraintes dans cette for- mulation (conditions de Kuhn-Tucker) aboutit souvent a une fonction d'agregation consequente et inadaptee aux calculs par intervalles [7]. mance, la competition avec des resolveursnonables d'optimisation globale, commeBaron[19]. Dans cet article, nous proposons une approche radi- calement dierente ou l'amelioration de la borne se fait en explorant des regions interieures, c.-a-d. des regions ou l'on prouve en amont que tous les points sont fai- sables. La notion de bo^te interieure a deja ete etudiee en programmation par contraintes, que ce soit pour le pavage de l'espace solution [6, 2] ou pour minimiser le nombre de contraintes numeriques d'inegalite non satisfaites [17]. En revanche, cette approche n'a pas encore ete exploitee dans un cadre general d'optimisa- tion globale sous contraintes d'egalite et d'inegalite.

Calcul d'un minorant par une relaxation lineaire

able

Tous les resolveurs existants calculent, a chaque

nud du B&B, une approximation convexe (en ge- neral polyhedrale) de l'espace solution. La meilleure solution de cette relaxation fournit un minorant du co^ut, ce dernier etant indispensable pour terminer la recherche. Rappelons que l'approximation exterieure doit contenir l'ensemble solution en depit des erreurs de calcul dues aux nombres a virgule ottante. Or, la plupart des relaxations lineaires sont trop sophisti- quees pour pouvoir ^etre rendues ables facilement. Des techniques speciques de reformulation-linearisation (RLT) [18] sont presentees dans [9] et [11]. Elles in- troduisent de nouvelles variables, representant les ope- rateurs de puissance et de produit, et denissent des contraintes lineaires entre ces variables. Ninin et al. utilisent, eux, l'arithmetique ane pour eectuer une linearisation able de chaque operateur [16]. Nous pro- posons, pour notre part, une linearisation able basee sur l'evaluation de Taylor par intervalles, au premier ordre. La simplicite de cette relaxation nous a permis de mettre aussi au point une version duale pouvant extraire une region polyhedrale cette fois interieure de l'ensemble solution et ainsi ameliorer la borne cou- rante.

1.1 Intervalles et optimisation globale sous

contraintes

Un intervalle [xi] = [xi;x

i] est l'ensemble des nombres reelsxitels quexixix i.IRrepresente l'ensemble de tous les intervalles. La taille ou largeur de [xi] estw([xi]) =x ixi. Une bo^te [x] est le pro- duit cartesien des intervalles [x1]:::[xi]:::[xn].

Sa largeur est denie par max

iw([xi]). Mid([x]) est le milieu de [x]. Un probleme continu d'optimisation globale sous contraintes se denit ainsi :Denition 1 (Optim globale sous contraintes) Soientxun vecteur de variablesx= (x1;:::;xi;:::xn) dans une bo^te[x],fune fonction a valeurs reelles f:Rn!R,g:Rn!Rmeth:Rn!Rp, des fonctions a valeurs vectorielles.Etant donne le systemeS= (f;g;h;x;[x]), le pro- bleme d'optimisation globale sous contraintes consiste a trouver : min x2[x]ff(x)t:q: g(x)0^h(x) = 0g: fest lafonction objectif;gethsont les contraintesd'inegalite et d'egalite. Un point est dit faisables'il satisfait les contraintes. Notre algorithme d'optimisation extrait desregions interieuresdans les bo^tes exterieures classiques.

Denition 2Soit un systeme(f;g;;;x;[x]out)ne

comprenant que des contraintes d'inegalite. Unere- gion interieurerinest un sous-ensemble faisable de [x]out, c.-a-d.rin[x]outet tous les pointsx2rin satisfontg(x)0. Une region interieure[x]inqui est une bo^te est ap- peleebo^te interieure. Un des operateurs de notre strategie eectue deslinea- risations interieureset extrait ainsi de l'espace faisable despolytopes interieurs. L'arithmetique d'intervalles[13] etend aIRles fonc- tions elementaires surR. Par exemple, la somme d'in- tervalles ([x1] + [x2] = [x1+x2;x 1+x

2]) contient

l'image de la fonction somme sur ses arguments, et cette propriete d'inclusion denit ce que nous appe- lons une extension aux intervalles.

Denition 3 (Extension d'une fonction aIR)

Soit une fonctionf:Rn!R.

[f] :IRn!IRest uneextensiondefaux inter- valles ssi :

8[x]2IRn[f]([x]) ff(x); x2[x]g;

8x2Rnf(x) = [f](x):

Dans notre contexte, l'expression d'une fonctionf

est toujours la composition de fonctions elementaires.

L'extension naturelle[f]Nest alors simplement la

composition des operateurs correspondants de l'arith- metique d'intervalles. Les linearisations exterieure et interieure proposees dans cet article sont liees a l'extension de Taylorau premier ordre [13], denie comme suit : [f]T([x]) =f(_x) +X i @f@x i N ([x])([xi]_xi) ou _xest un point quelconque de [x], par exemple,

Mid([x]).

Exemple.Soitf(x1;x2) = 3x21+x22+x1x2sur

la bo^te [x] = [1;3][1;5]. L'evaluation natu- relle donne : [f]N([x1];[x2]) = 3[1;3]2+ [1;5]2+ [1;3][1;5] = [0;27] + [0;25] + [5;15] = [5;67].

Les derivees partielles sont :

@f@x

1(x1;x2) = 6x1+x2,

@f@x

1]N([1;3];[1;5]) = [7;23],@f@x

2(x1;x2) =x1+

2x2, [@f@x

2]N([x1];[x2]) = [3;13]. L'evaluation de Tay-

lor avec _x= (1;2) produit : [f]t([x1];[x2]) = 9 + [7;23][2;2] + [3;13][3;3] = [76;94].

1.2 Transformer les equations en inegalites

Pour traiter les egalites, une premiere option est suivie par la communaute d'analyse par intervalles.

Elle consiste a trouverapproximativementun point

qui satisfaitexactementles contraintes. Le resolveur renvoie une petite bo^te de largeursoldans laquelle l'existence d'un point faisable a valeurs reelles est (souvent) garantie par des methodes de type Newton par intervalles. Une seconde option consiste a trouver exactementun point qui satisfaitapproximativement les contraintes. Les equations sont traitees avec une erreur de precision admissibleeq, c'est-a-dire qu'un point faisable a virgule ottantexdoit verierh(x)2 [eq;+eq]. Toutes les contraintes peuvent alors ^etre vues comme des inegalites :fg(x)0,h(x)eq0, h(x)eq0g. Ninin et al. ont ete guides vers ce choix par l'arithmetique ane, mais nous pensons que c'est une approche pertinente pour tout resolveur d'op- timisation globale. Remarquons tout d'abord que les deux approches ont un statut equivalent en termes de abilite. Ensuite, une precisioneqsur lesimagesdes fonctionshrepond mieux au probleme de la faisabilite qu'une precisionsolsur les inconnues. D'autre part, la plupart des equations denies par les utilisateurs sont deja \epaisses" et n'ont pas besoin d'une relaxa- tion additionnelle aeqpres. En eet, les contraintes contiennent souvent des coecients connus avec une incertitude bornee (par exemple une imprecision dans une mesure) ou des constantes irrationnelles comme qui ne peuvent ^etre entrees que sous forme d'in- tervalles. Enn, nos experimentations ont mis en evi- dence que le traitement de ces egalites epaisses peut ^etre ecace en pratique. La raison derriere cette bonne surprise est que cette approche permet aux resolveurs d'extraire des regions interieures dans des continuums de solutions.Les algorithmes d'extraction de regions interieures et de contraction peuvent focaliser la re- cherche dans le petit espace solution deni par les equations epaisses.2 Notre B&B sur intervalles

Notre strategieIbexOptsuit le schema bien connu

de separation-evaluation (B&B) decrit dans [8] pour resoudre un probleme d'optimisation globale sous contraintes. L'algorithme eectue recursivement, a partir d'une bo^te initiale, des decoupages jusqu'a ob- tenir une solution qui minimise la fonction objectif. Pendant la recherche, un minorant (generalement non faisable) de la fonction objectif est maintenu incremen- talement a partir de la liste des bo^tes traitees ou en attente. Nous notonslb(pourlower bound) le plus pe- tit de ces minorants. De m^eme,ub(pourupper bound) designe le co^ut du meilleur point faisable trouve au cours de la recherche. Un critere d'arr^et est atteint quandublbest inferieur a la precision requiseobj,3 et le point ottantxubde co^utubest retourne. Notons que les bo^tes dont la largeur est inferieure a la preci- sionsolne sont pas remises dans la liste et que leurs minorants prennent part au calcul delb. A chaque iteration, l'algorithme choisit dans la liste la bo^te [x] avec le plus petit minorant, realisant ainsi une recherche enmeilleur d'abord. La variablexi2x est choisie par une heuristique, son domaine [xi] est bissecte et la procedure principaleContract&Bound est appliquee sur les deux sous-bo^tes. On notera que l'arbre de recherche, c.-a-d. la\liste"des bo^tes a trai- ter, est implante par une structure detasqui permet d'acceder au plus petit element en temps constant. On trouvera plus de details sur ce schema dans [16]. La premiere t^ache de notre algorithme est l'intro- duction d'une nouvelle variableydans le systeme (f;g;h;x;[x]), a l'instar de Numerica [21] par exemple. Cette variable est liee aux autres par la contrainte sup- plementairey=f(x). Son domaine [y] est donc un intervalle qui contient l'image de la fonction objectif sur [x]. Cette extension du systeme permet de pro- pager et retro-propager automatiquement les contrac- tions entre [x] et les bornes globales sur le minimum. Ainsi, la bo^te etendue [x][y] denit l'etat courant de l'optimiseur. S'y ajoutent trois variables partagees par tous les nuds de l'arbre de recherche et mises a jour de maniere globale pendant la recherche : la meilleure solution courantexub, son co^utub(f(xub) =ub) etlb le minimum des minorants des bo^tes non traitees.

2.1 Strategie de bissection

A chaque nud de l'arbre de recherche, une variante de l'heuristique bien connue de lasmear function[10]

permet de choisir la prochaine variable a bissecter.Etant donne un systeme (f;g;h;x;[x]), la strategie

smearstandard choisit la variablexidexqui maximise3

Conformement aux implantations standard,objest un

pourcentage deubsijubj 1 et une distance absolue sijubj 1. suivant les cassmearMax(xi) =Maxfjsmear(xi;fj) ousmearSum(xi) =P f jsmear(xi;fj), oufjrepre- sente soit la fonction objectiff, soit une contrainte degouh. smear(xi;fj) est une mesure de l'impact de la va- riablexisur la fonctionfj. Son calcul implique la de- rivee partielle defjpar rapport axiet la largeur de [xi]. Plus precisement : smear(xi;fj) = @fj@x i N ([x])w([xi]):

Nous proposons une variante,smearRel(xi;fj), qui

mesure un impactrelatif, a valeur dans [0;1] : smearRel(xi;fj) =smear(xi;fj)P x k2xsmear(xk;fj): Finalement, notre strategie de bissectionSmearSumRel choisit la variablexidexavec le plus grand impact : smearSumRel(xi) =X f jsmearRel(xi;fj): M^eme si elle n'est pas toujours la meilleure, cette stra- tegie appara^t plus robuste que ses concurrentes sur l'ensemble des problemes testes.

2.2 La procedure Contract&Bound

L'algorithme principalContract&Bound(cf. algo-

rithme 1) est appele a chaque nud de notre B&B. La premiere ligne introduit dans le systeme courant le meilleur co^utubtrouve (comme dans toutB&B). La procedureOuterContractLBcontracte les domaines et ameliore le minorant.InnerExtractUBextrait une re- gion interieure dans [x], preleve en cas de succes un pointxdans cette region et, sixameliore le critere, remplacexubparxet le co^utubparf(x).Algorithm 1Contract&Bound(inS, [x];in-out:ub)y ubobj

OuterContractLB(S, [x][y]) /* contraction */

if[x][y] =;thenexitendif/* no solution */ InnerExtractUB(S, [x],ub,xub)/* inner regions */OuterContractLBappelle principalement deux pro- cedures. La premiere est l'algorithmeMohc[1] qui contracte la bo^te [x][y] en donnant, par eet de bord, un minorant a la fonction objectif. Cet algorithme re- cent de propagation de contraintes sur intervalles ex- ploite la monotonie des fonctions. Il utilise une proce- dureReviseecace qui contracte de maniere optimale la bo^te par rapport a une contrainte (par exemple, g j(x)0) sigj(x) est detectee comme etant mono-

tone suivant toutes les variables et en tout point dela bo^te, m^eme sigj(x) contient des occurrences mul-

tiples de variables. On notera que plus la bo^te est petite (ou de facon equivalente, plus on descend en profondeur dans l'arbre de recherche), plus les fonc- tions deviennent monotones.

La seconde procedure appelee parOuterContractLB

est une relaxation lineaire, nommee iciOuterLineari- zation, qui calcule un minorant de la fonction objectif et met a joury.

2.3 Relaxation lineaire exterieure

La relaxation lineaire ci-dessous est une adaptation directe de la forme de Taylor du premier ordre sur intervalles [12]. Soit une fonctionf:Rn!Rdenie sur une bo^te [x]. Pour toute variablexi2x, soit [ai] :h@f@x ii N ([x]). Le principe consiste a minorerf(x) par des fonctions lineaires :

8x2[x];f(x) +a1xl1+:::+anxlnf(x) (1)

8x2[x];f(x) +a

1xr1+:::+a

nxrnf(x) (2) avec :xli=xixietxri=xix i. La forme de Taylor au premier ordre sur intervalles peut s'appliquer avec n'importe quel point _xa l'in- terieur de la bo^te. Au lieu du milieu, choisi habi- tuellement, nous prenons ici uncoinde la bo^te :xdans la formule (1) ouxdans la formule (2). Si nous considerons une inegalitegj(x)0, l'expression (1) (ou (2)) denit ainsi un hyperplanglj(x) bornant in- ferieurement l'espace solution :glj(x)gj(x)0. En appliquant, par exemple, la formule (1) a la fonction objectiff(x) et aux inegalitesgj(x)0 (j= 1:::m), on peut generer un probleme lineaireLPlbqui est une relaxation du probleme initial : LP lb= minf(x) +a1xl1+:::+anxln sous:8j gj(x) +aj

1xl1+:::+ajnxln0

8i0xli; xliw([xi])

avec:xli=xixiOuterLinearizationinvoque ensuite l'algorithme du simplexe pour resoudreLPlb. Il calcule la valeur optimaleylou detecte une infaisabilite. L'infaisabilite indique que [x] ne contient pas de solution et peut ^etre eliminee. Si au contraireyly, alors le minorant de l'objectif sur la bo^te est mis a jour :y yl. Proposition 1Les linearisations par intervalles (1) et (2) sont correctes et ables, c.-a-d., elles peuvent ^etre rendues robustes par rapport aux erreurs d'arron- dis sur les nombres a virgule ottante. La abilite est assuree par la taylorisation sur inter- valles [14]. La correction de la relation (1) repose sur le choix d'un coin comme point d'expansion. Elle tient au fait que toute variablexliest positive puisque son domaine est [0;di], avecdi=w([xi]) =x ixi. Ainsi, le minimum de chaque terme [ai]xlipour un point x li2[0;di] est obtenu avecai. Symetriquement, la re- lation (2) est correcte puisquexri2[di;0]0, et le minimum de chaque terme est obtenu aveca i[12]. Il faut noter que, bien que nos linearisations soient ables, les erreurs de calcul dus aux nombres ottants dans l'algorithme du simplexe peuvent rendre ses re- sultats non ables. Pour rendre la solution du simplexe able, nous avons ajoute un post-traitement peu co^u- teux, propose dans [15], utilisant l'arithmetique d'in- tervalles. Nous avons apporte une amelioration a notre relaxa- tion lineaire pour calculer un polytope plus petit. Nous minorons une fonctionf(x) avec les expressions (1) et (2) simultanement, en utilisant une forme developpee :

1.f(x) +

P iai(xixi) =f(x) + P i(aix iaix i) =P iaix i+f(x)P iaix i2.f(x) +P ia i(xix i) =f(x) +P i(a ixia ix i) =P ia ixi+f(x)P ia ix i

2.4 Trouver des majorants dans des regions inte-

rieures

L'appel aOuterContractLBest suivi par un appel

aInnerExtractUB(cf. algorithme 2). La procedure commence par appeler une adaptation d'un algorithme recent, nomme iciInHC4[4], pour extraire une bo^te interieure a partir de la bo^te exterieure [x]out.4Ap- plique a une contrainte,InHC4renvoie une bo^te inte- rieure pour cette contrainte. Les dierentes bo^tes re- tournees pour les dierentes contraintes sont intersec- tees pour obtenir une bo^te interieure. CommeHC4[3], l'algorithme raisonne sur l'arbre syntaxique des ex- pressions et utilise desprojectionspour les operateurs unaires, avec arrondi vers l'interieur. De plus, dans le cas d'unions disjointes d'intervalles (par exemple, pour les operateursx2etsinus), on ne garde qu'un seulquotesdbs_dbs47.pdfusesText_47

[PDF] Minorité culturelle Plan detaille

[PDF] minority report analyse

[PDF] minority report dossier pédagogique

[PDF] minority report nouvelle

[PDF] minority report philip k pdf

[PDF] minuit cinq de malika ferdjoukh

[PDF] minute d'angle en degré

[PDF] minutes en heures

[PDF] Mirabeau et Lafayette

[PDF] Mirabeau, disours aux états généraux, "sur l'emprunt", 23 septembre 1789

[PDF] miracle économique italien dates

[PDF] mireille darc photos

[PDF] MIREN 75 ! j'ai besoin de toi! Comment contacter miren

[PDF] MIREN 75 j'ai besoin de ton aide!!!

[PDF] Miro et Nicolas de Stael