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.