Improving Interval Analysis Bounds by Translations

Jou nal o Global Op imiza ion 29: 157–172, 2004. 157 © 2004 Kluwe Academic Publishe s. P in ed in he Ne he lands. Imp o ing In e al Analysis Bounds by T ansla ions EMILIO CARRIZOSA1, PIERRE HANSEN2and FRÉDÉRIC MESSINE3 1Uni e si ad de Se illa, Facul ad de Ma ema icas, Se illa, Spain (e-mail: [email p o ec ed]) 2GERAD, École des Hau es É udes Comme ciales o HEC Mon éal, Dépa emen des Mé hodes Quan i a i es, Mon éal (Québec), Canada (e-mail: [email p o ec ed]) 3Uni e si é de Pau e des Pays de l’Adou , Dépa emen d’In o ma ique, Pau, F ance e le Labo a oi e d’Élec o echnique e d’Élec onique Indus ielle UMR 5828, Équipe EM2, Toulouse, F ance (e-mail: [email p o ec ed] and [email p o ec ed]) (Recei ed 22 Ma ch 2002; accep ed 26 Augus 2003) Abs ac . We explo e how a simple linea change o a iable a ec s he inclusion unc ions ob ained wi h In e al Analysis me hods. Uni a ia e and mul i a ia e polynomial es unc ions a e conside ed, showing ha ansla ion-based me hods imp o e conside ably he bounds compu ed by s anda d inclusion unc ions. An In e al B anch-and-Bound me hod o global op imiza ion is hen implemen ed o compa e he di e en p ocedu es, showing ha , al hough wi h imes highe han hose gi en by Taylo o ms, he numbe o clus e s and i e a ions is s ongly educed. Ma hema ics Subjec Classifica ions. 90C26, 68N30 Key wo ds. inclusion unc ions, in e al analysis, in e al b anch and bound, Taylo o ms. 1. In oduc ion Designed as a echnique o con olling p opaga ion o e o s in compu ing [8], In e al Analysis was soon ecognized as a powe ul ool o global op imiza- ion [3, 5, 6, 10]. I s main use is hen in easibili y and op imali y es s o B anch-and-Bound me hods [8, 10] o sol ing p oblems o he o m min xgix⩾0i=12m Indeed, a egion Xcan be disca ded as soon as one de ec s i is ei he in easible (because an uppe bound o one o he unc ions gon Xis nega i e), o i canno con ain op imal solu ions (because a lowe bound o x on X u ns ou o be wo se han he alue o an al eady known easible solu ion). Hence, i is o g ea impo ance o know, o a gi en unc ion , he di ec image X o X, X= xx∈X o , i his is no possible, an enclosu e o i . This leads o he concep o inclusion unc ion, defined as ollows in he uni a ia e case: le deno e he se o in e als Xo he o m X=xLxU, wi h −⩽xL⩽xU⩽+. 158 E. CARRIZOSA ET AL. Gi en −→ , any F−→ con aining X is called an inclusion unc ion o F. A desi ed p ope y o an inclusion unc ion o is i s iso onici y: Fis said o be an iso one inclusion unc ion o i FY⊆FZ o all YZ wi h Y⊆Z Some examples o (iso one) inclusion unc ions will be in oduced he e; he eade is e e ed o [3, 9, 10] o u he de ails. I an analy ical exp ession o is gi en, one o mally eplaces he a iable x by he co esponding in e al a iable X, and all he algeb aic ope a ions in he defini ion o by hei co esponding In e al A i hme ic ope a ions, hen one ob ains he so-called Na u al Ex ension o , deno ed h oughou he pape by NE. Fo su ficien ly smoo h unc ions , i is possible o ob ain di e en inclusion unc ions om Taylo expansions by cons uc ing enclosu es o he emainde . Indeed, can hen be w i en as x= x0+ k−1  i=1 x−x0i i! ix0+x−x0k k! k o some ∈X.I Fk is an inclusion unc ion o k, hen k∈FkX, yielding he Taylo inclusion unc ion o o de kcen e ed a x0T kx0X, defined as Tkx0X= x0+ k−1  i=1 X−x0i i! ix0+X−x0k k!FkX (1) The mos used in e al Taylo inclusion unc ions a e ob ained om he cen- e ed expansions o fi s o second o de , T1X= m+X−mFX (2) T2X= m+X−m m+X−m2 2FX (3) (mbeing he midpoin o he in e al X=xLxU), o a non-cen e ed o m o T1x0X T1B due o Baumann [1], consis ing o aking, in (1), o k=2, x0gi en by x0=     xUi FUX⩽0 xLi FLX⩾0 FUXxL−FLXxU FUX−FLX o he wise IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 159 o maximize he lowe bound and x0=     xLi FUX⩽0 xUi FLX⩾0 FLXxL−FUXxU FLX−FUX o he wise o minimize he uppe bound. These will be he inclusion unc ions aken as benchma k, wi h which he inclusion unc ion we p opose in Sec ion 2 will be compa ed. 2. T ansla ion-based Me hods o Uni a ia e Polynomial Func ions 2.1. PROBLEM SETTING In his sec ion we add ess he p oblem o finding inclusion unc ions P, yielding sha p enclosu es o he ange o a eal uni a ia e polynomial unc ion p, px= n  k=0 akxkwi h ak∈and x∈X=xLxU∈(4) Th oughou his sec ion, nwill deno e he deg ee o he polynomial unc ion pconside ed. In his case, he Na u al Ex ension NE o his exp ession o pbecomes NEX= n  k=0 akXkX=xLxU∈(5) Ano he well-known choice is he Ho ne scheme H, HX=a0+X···an−2+Xan−1+anX··· (6) Obse e ha hese wo inclusion unc ions a e no compa able in e ms o he enclosu es hey p o ide. Fo ins ance, o px=x2−xand X=−11, we ha e NEX=X2−X =−12 ⊂−22=XX−1=HX Ne e heless, o he same pand X=12, we ob ain NEX=X2−X =−13 ⊃02=XX−1=HX 160 E. CARRIZOSA ET AL. Howe e , an inclusion unc ion sha pe han bo h NE and His di ec ly ob ained om H, by compu ing he ange in a box as he union o anges in sub-boxes co e ing he box, [9, 10]: DEFINITION 1. Gi en an iso one unc ion F −→ , and c∈, define Fc−→ ,as FcX=FxLc∪FcxU i c∈X FX o he wise LEMMA 1. Fcis an iso one unc ion sa is ying FcX⊆FX o all X∈. P oo . Fi s obse e ha Fcis well defined; indeed, o c∈X=xLxU, since Fis an inclusion unc ion, bo h FxLc and FcxU a e closed in e als ha ing c as common poin ; hence, FcX∈. Mo eo e , Fcis an inclusion unc ion. Indeed, i cX, one has FcX=FX⊇ X;i c∈X, one has xLc⊆FxLc cxU⊆FcxU Hence, X= xLc∪ cxU⊆FxLc∪FcxU=FcX showing ha Fcis also an inclusion unc ion. In o de o see ha Fcis iso one, conside YZ∈Y⊆Z. Th ee cases a e conside ed: 1. I c∈Z, hen he iso onici y o Fimplies ha FcY =FY⊆FZ=FcZ. 2. I c∈Yand c∈Z hen ei he Y⊆zLc o Y⊆czU. In he fi s case one has FcY =FY⊆FzLc⊆FzLc∪FczU=FcZ whe eas in he la e case one has FcY =FY⊆FczU⊆FzLc∪FczU=FcZ 3. I c∈Y( hus c∈Z) hen yLc⊆zLc, and cyU⊆czU. Hence, FcY =FyLc∪FcyU⊆FzLc∪FczU=FcZ. The e o e, Fcis iso one. IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 161 T i ially FcX⊆FX i cX.I c∈X, hen he iso onici y o Fimplies ha FxLc∪FcxU⊆FX, hus FcX⊆FX, as asse ed.  Pa icula ized o he inclusion unc ion H, spli ing by c=0, one ob ains he inclusion unc ion H0, defined as: H0X=     minHLxL0HL0xUmaxHUxL0HU0xU i 0∈X HX else (7) PROPOSITION 1. H0is an inclusion unc ion which is iso one and sa isfies o all X∈ 1. H0X⊆HX 2. H0X⊆NEX. P oo .H0is an iso one inclusion unc ion sa is ying H0X⊆HX by Lemma 1. By defining NE0 ollowing Defini ion 1, i su fices o show ha H0X⊆NE0X o all X∈. We show ha H0X⊆NEX by induc ion in he deg ee ko p. Fo k=01 he inclusion is s aigh o wa d. We assume ha he inclusion holds o all polynomial unc ions o deg ee smalle han k, and show he esul o he polynomial unc ion px=a0+a1x+···+ak+1xk+1, (o deg ee k+1). I 0X, hen H0X=HX=a0+XH∗X=a0+XH∗ 0X whe e H∗X ( espec i ely H∗ 0) ep esen s he Ho ne scheme H( espec i ely H0) o he polynomial unc ion p∗o deg ee k,p∗x=a1+a2x+···+ak+1xk. By he induc ion assump ion, one has H∗ 0X⊆NE∗X whe e NE∗deno es he na u al ex ension o p∗. Hence, a0+XH∗ 0X⊆a0+XNE∗X⊆NEX The e o e H0X⊆NEX ∀Xwi h 0X I 0∈X, a simila a gumen shows ha H0xL0⊆NExL0 and H00xU⊆NE0xU Hence, H0X⊆NE0X⊆NEX, and he esul holds.  162 E. CARRIZOSA ET AL. 2.2. TRANSLATION-BASED METHODS The idea o hese me hods is o ansla e he in e al Xconside ed in o he in e al X!=xL+!xU+! by using an exp ession o px di e en om (4), and hen choosing he alue o !yielding he sha pes enclosu e. Fi s , obse e ha , o any !∈, px= n  j=0 ajx+!−!j = n  j=0 x+!j n−j  k=0 ak+jk+j j−!k = n  j=0 j!x+!j(8) wi h j! defined as j!= n−j  k=0 ak+jk+j j−!k(9) Fo each inclusion unc ion Fp e iously defined one ob ains now, o each !∈, a new ansla ion-based inclusion unc ion TF!·. Fo ins ance, om he Ho ne scheme H, one ob ains TH, TH!X= 0!+X! 1!+X!··· n−1!+X! n! (10) wi h X!=X+! Fu he mo e, TH0is defined, ollowing Defini ion 1, as TH0!X=TH!X0(11) In he same way, TNETNE0TT1TTna e defined. Gi en an inclusion unc ion F, we ob ain o each ! he inclusion unc ion TF!·. By defini ion, TF0X=FX (12) hus by a ying he pa ame e !i may be possible o come up wi h mo e accu a e enclosu es. This poses he p oblem o de e mining he alues o !yielding he sha pes enclosu e. Fo his we define, o an inclusion unc ion F, he op imal ansla ion-based inclusion unc ion OTF as OTFX=max !∈TFL!X min !∈TFU!X(13) whe e TF!X=TFL!XTFU!X. IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 163 Obse e ha , by (12), OTFX⊆FX ∀X∈ Rema k 1. The unc ion OTF is only o in e es o heo e ical easons; indeed, he p ac ical de e mina ion o OTF amoun s o sol ing wo op imiza ion p oblems which can be non-di e en iable and non-con ex. Hence, in p ac ice, a ew s eps o a local-sea ch algo i hm will be used, yielding an enclosu e possibly less sha p han OTF bu wi h much less compu a ional e o . PROPOSITION 2. TH0!X⊆TNE!X=Tn−!X o all !∈X∈(14) P oo . Le !∈and X∈. The inclusion TH0!X⊆TNE!X di ec ly ollows om P oposi ion 1. Since pnx=n!an o all x, one has ha PnX n!ann!anis an inclusion unc ion o pn. By (1), Tn−!X can hen be w i en as Tn−!X=p−!+ n−1  i=1 X+!i i!pi−!+X+!n n!PnX =p−!+ n−1  i=1 X+!i i! n−i  k=0 k+i! k!ak+i−!k+X+!n n!n!an = n  i=0 X+!i n−i  k=0k+i iak+i−!k = n  i=0 X+!i i!=TNE!X This shows he esul .  F om (14) one di ec ly has PROPOSITION 3. OTH0X⊆OTNEX o all X∈. 2.3. NUMERICAL RESULTS The di e en inclusion unc ions p e iously sugges ed ha e been compa ed acco ding o he bounds hey p oduce. Table 1 summa izes he esul s ob ained o a se ies o uni a ia e polynomial unc ions, ei he aken om he li e a u e, [4, 11, 12], o andomly gene a ed. The fi s ones a e he ollowing: 1. p1x=1 10 −x−79 20 x2+71 10 x3+39 80 x4−52 25 x5+1 6x6X=−211, due o Wingo, [11]. The e is a misp in in he exp ession o he unc ion in [11]. 164 E. CARRIZOSA ET AL. Table 1. Resul s o lowe o uppe bounds o polynomial unc ions. Pb p1p2p3p4p5p6p7 lb ub lb lb lb lb ub lb NE −334E5312E5−333E10 −170E4−500E2−499E3616E5−462E2 H−373E5868E4−248E10 −140E4−123E3−457E3377E4−109E3 H0−319E5161E4−248E10 −140E4−400E2−457E3377E4−362E2 T1−108E6108E6−151E16 −467E4−420E3−137E5261E8−37E3 T1B−103E6103E6−515E11 −371E4−329E3−142E4409E6−307E3 T2−119E6159E6−979E11 −215E4−150E3−156E4384E6−121E3 T3−127E6123E6−365E17 −186E4−300E3−463E4822E8−296E3 OTH0−546E4235E2−101E3−996E2−672E1192 −311E1−164E2 !−63−1−108 −535 −087 −017 −065 −045 2. p2x=50 i=1aixix∈12, he coe ficien s a e a1n =−500, 2.5, 1.666666666, 1.25, 1, 0.833333333, 0.714285714, 0.625, 0.555555555, 1, −43636363636, 0.416666666, 0.384615384, 0.357142857, 0.333333333, 0.3125, 0.294117647, 0.277777777, 0.263157894, 0.25, 0.238095238, 0.227272727, 0.217391304, 0.208333333, 0.2, 0.192307692, 0.185185185, 0.178571428, 0.344827586, 0.666666666, −15483870970, 0.15625, 0.151515151, 0.147058823, 0.142857142, 0.138888888, 0.135135135, 0.131578947, 0.128205128, 0.125, 0.121951219, 0.119087619, 0.116279069, 0.113636363, 0.111111111, 0.108695652, 0.106382978, 0.208333333, 0.408163265, 08, he Moo e unc ion. 3. p3x =0000089248x−00218343x2+0998266x3−16995x4+02x5,x∈ 010, he Wilkinson unc ion. 4. p4x=4x2−4x3+x4x∈−55, he Dixon and Szegö unc ion. 5. p5x=7x4−5x3+4x2+3x+2, X=010, gene a ed andomly wi h in ege coe ficien s in he ange −1010. 6. p6x =−587x13 −232x12 −183x11 −1664x10 +771x9+871x8+526x7− 529x6−1769x5+347x4−124x3−1935x2−1937x+434X=077338, gene a ed andomly wi h eal coe ficien s in he in e al −2020. 7. p7x=10x−15x2−3x3+x4x∈−55, he Dixon unc ion. The inclusion unc ions conside ed a e NEHH0T1Band Tkk=123, ak- ing as x0 he midpoin o he in e al X. Mo eo e , OTH0is compu ed using minu o Ma Lab o pe o m a local sea ch, se ing !equal o 0 as s a ing poin , and pe o ming a mos 30 i e a ions. In o de o check he compu ed bounds, an ou wa dly ounded in e al a i hme ic code mus be used [6–8]. He e, we ha e de eloped in Ma Lab he needed ope a ions, i.e., addi ion and mul iplica- ion o compu ing polynomial unc ions, wi h ou wa dly ounded compu a ions. Hence, he esul s p esen ed a e nume ically co ec o each inclusion unc- ion. I may be possible ha he floa ing compu a ions pe o ming he ansla ion !p oduce some nume ical e o s and ha he esul di e s sligh ly, o in a e IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 165 cases la gely, om he op imal alue. Bu no nega i e e ec can occu , because TF!X is always an inclusion unc ion o all eal (o floa ing) alues o !. In mos cases, ei he he lowe bound (lb) o he uppe bound (ub) imp o ed conside ably wi h espec o he o he enclosu es, he op imal ! o he o he bound being close o ze o. The bounds, oge he wi h he op imal ! o OTH0 a e gi en in he las wo ows o he able. I appea s ha some su p ising imp o emen s o he bounds a e ob ained o polynomial unc ions bo h o low deg ee (e.g. p5) and high deg ee (e.g. p2). 2.4. EXTENSION TO UNIVARIATE RATIONAL FUNCTIONS The me hodology ex ends in a s aigh o wa d manne o unc ions gi en as he a io o wo polynomial unc ions pq. Indeed, i THp 0!1X and THq 0!2X ep esen ansla ion-based inclusion unc ions o pand qacco ding o (11), hen one ob ains, o each !1!2, he inclusion unc ion THp 0!1X THq 0!2X The op imiza ion in he ansla ion pa ame e s yields a new (and sha pe ) enclosu e, OTH p q 0X=OTHp 0X OTHq 0X (15) =max!1∈THp 0L!1X min!1∈THp 0U!1X max!2∈THq 0L!2X min!2∈THq 0U!2X ⊇max !∈THp 0!X THq 0!XL min !∈THp 0!X THq 0!XU(16) Rema k 2. Rema k ha he la es enclosu e, al hough less sha p, equi es he esolu ion o wo ins ead o ou op imiza ion p oblems. Mo eo e , i jus one ou o he wo bounds is needed, one has o sol e only one ins ead o ou op imiza ion p oblems. The imp o emen in p ecision o he enclosu es ob ained in his way is illus- a ed in Table 2. We ha e compa ed OTH p q 0, as defined in (15) as well as he enclosu e defined in (16) ( he wo las lines o he able) wi h he enclosu es NEHp 0 Hq 0, he fi s -o de Taylo expansion T1and he Baumann inclusion unc ion T1B. The nume ical es s a e pe o med on he a ional unc ion x=p1x p5x o e di e en in e als. Obse e ha , o la ge in e als, he s anda d enclosu es canno exclude ze o in he denomina o , yielding he i ial in e al −+using ex ended a i hme ic. 172 E. CARRIZOSA ET AL. Re e ences 1. Baumann, E. (1988), Op imal cen e ed o m, BIT, 28, 80–87. 2. Du, K. and Kea o , R.B. (1996), The clus e p oblem in mul i a ia e global op imiza ion, Jou nal o Global Op imiza ion, 10, 27–32. 3. Hansen, E. (1992), Global Op imiza ion Using In e al Analysis, Ma cel Dekke , New Yo k. 4. Hansen, P., Jauma d, B. and Lu, S.-H. (1989), Global minimiza ion o uni a ia e unc ions by sequen ial polynomial app oxima ion in e na ional, In e na ional Jou nal o Compu e Ma hema ics, 28, 183–193. 5. Ichida, K. and Fujii, Y. (1979), An in e al a i hme ic me hod o global op imiza ion, Compu ing, 23, 85–97. 6. Kea o , R.B. (1996), Rigo ous Global Sea ch: Con inuous P oblems, Kluwe Academic Publishe s, Do d ech , Bos on, London. 7. Messine, F. (1997), Mé hodes d’op imisa ion globale basées su l’analyse d’in e alle pou la ésolu ion de p oblèmes a ec con ain es, PhD Thesis, INPT-ENSEEIHT, Toulouse. A ailable on he websi e: www.uni -pau. /∼messine 8. Moo e, R.E. (1996), In e al Analysis, P en ice Hall, Englewood Cli s, N.J. 9. Ra schek, H. and Rokne, J. (1984), Compu e Me hods o he Range o Func ions, Ellis Ho wood, Chiches e , England. 10. Ra schek, H. and Rokne, J. (1988), New Compu e Me hods o Global op imiza ion, Ellis Ho wood, Chiches e , England. 11. Visweswa an, V. and Floudas, C.A. (1992), Uncons ained and cons ained global op imiza ion o polynomial unc ions in one a iable, Jou nal o Global Op imiza ion, 2(1), 73–100. 12. Wingo, D.R. (1985), Globally minimizing polynomials wi hou e alua ing de i a i es in e na- ional, Jou nal o Compu e Ma hema ics, 17, 287–294.