Improving Interval Analysis Bounds by Translations

Journal of Global Optimization 29: 157–172, 2004. 157 © 2004 Kluwer Academic Publishers. Printed in the Netherlands. Improving Interval Analysis Bounds by Translations EMILIO CARRIZOSA1, PIERRE HANSEN2and FRÉDÉRIC MESSINE3 1Universitad de Sevilla, Facultad de Matematicas, Sevilla, Spain (e-mail: [email protected]) 2GERAD, École des Hautes Études Commerciales for HEC Montréal, Département des Méthodes Quantitatives, Montréal (Québec), Canada (e-mail: [email protected]) 3Université de Pau et des Pays de l’Adour, Département d’Informatique, Pau, France et le Laboratoire d’Électrotechnique et d’Électronique Industrielle UMR 5828, Équipe EM2, Toulouse, France (e-mail: [email protected] and [email protected]) (Received 22 March 2002; accepted 26 August 2003) Abstract. We explore how a simple linear change of variable affects the inclusion functions obtained with Interval Analysis methods. Univariate and multivariate polynomial test functions are considered, showing that translation-based methods improve considerably the bounds computed by standard inclusion functions. An Interval Branch-and-Bound method for global optimization is then implemented to compare the different procedures, showing that, although with times higher than those given by Taylor forms, the number of clusters and iterations is strongly reduced. Mathematics Subject Classifications. 90C26, 68N30 Key words. inclusion functions, interval analysis, interval branch and bound, Taylor forms. 1. Introduction Designed as a technique for controlling propagation of errors in computing [8], Interval Analysis was soon recognized as a powerful tool for global optimization [3, 5, 6, 10]. Its main use is then in feasibility and optimality tests of Branch-and-Bound methods [8, 10] for solving problems of the form minf xgix⩾0i=12m Indeed, a region Xcan be discarded as soon as one detects it is either infeasible (because an upper bound for one of the functions gon Xis negative), or it cannot contain optimal solutions (because a lower bound for fx on Xturns out to be worse than the value of an already known feasible solution). Hence, it is of great importance to know, for a given function f, the direct image fX of X, fX=fxx∈X or, if this is not possible, an enclosure of it. This leads to the concept of inclusion function, defined as follows in the univariate case: let denote the set of intervals Xof the form X=xLxU, with −⩽xL⩽xU⩽+. 158 E. CARRIZOSA ET AL. Given f−→ , any F−→ containing fX is called an inclusion function of F. A desired property of an inclusion function of fis its isotonicity: Fis said to be an isotone inclusion function of fif FY⊆FZ for all YZ with Y⊆Z Some examples of (isotone) inclusion functions will be introduced here; the reader is referred to [3, 9, 10] for further details. If an analytical expression of fis given, one formally replaces the variable x by the corresponding interval variable X, and all the algebraic operations in the definition of fby their corresponding Interval Arithmetic operations, then one obtains the so-called Natural Extension of f, denoted throughout the paper by NE. For sufficiently smooth functions f, it is possible to obtain different inclusion functions from Taylor expansions by constructing enclosures of the remainder. Indeed, fcan then be written as fx=fx0+ k−1  i=1 x−x0i i!fix0+x−x0k k!fk for some ∈X.IfFk is an inclusion function of fk, then fk∈FkX, yielding the Taylor inclusion function of order kcentered at x0T kx0X, defined as Tkx0X=fx0+ k−1  i=1 X−x0i i!fix0+X−x0k k!FkX (1) The most used interval Taylor inclusion functions are obtained from the centered expansions of first or second order, T1X=fm+X−mFX (2) T2X=fm+X−mf m+X−m2 2FX (3) (mbeing the midpoint of the interval X=xLxU), or a non-centered form of T1x0X T1B due to Baumann [1], consisting of taking, in (1), for k=2, x0given by x0=     xUif FUX⩽0 xLif FLX⩾0 FUXxL−FLXxU FUX−FLX otherwise IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 159 to maximize the lower bound and x0=     xLif FUX⩽0 xUif FLX⩾0 FLXxL−FUXxU FLX−FUX otherwise to minimize the upper bound. These will be the inclusion functions taken as benchmark, with which the inclusion function we propose in Section 2 will be compared. 2. Translation-based Methods for Univariate Polynomial Functions 2.1. PROBLEM SETTING In this section we address the problem of finding inclusion functions P, yielding sharp enclosures for the range of a real univariate polynomial function p, px= n  k=0 akxkwith ak∈and x∈X=xLxU∈(4) Throughout this section, nwill denote the degree of the polynomial function pconsidered. In this case, the Natural Extension NE of this expression of pbecomes NEX= n  k=0 akXkX=xLxU∈(5) Another well-known choice is the Horner scheme H, HX=a0+X···an−2+Xan−1+anX··· (6) Observe that these two inclusion functions are not comparable in terms of the enclosures they provide. For instance, for px=x2−xand X=−11, we have NEX=X2−X =−12 ⊂−22=XX−1=HX Nevertheless, for the same pand X=12, we obtain NEX=X2−X =−13 ⊃02=XX−1=HX 160 E. CARRIZOSA ET AL. However, an inclusion function sharper than both NE and His directly obtained from H, by computing the range in a box as the union of ranges in sub-boxes covering the box, [9, 10]: DEFINITION 1. Given an isotone function F −→ , and c∈, define Fc−→ ,as FcX=FxLc∪FcxU if c∈X FX otherwise LEMMA 1. Fcis an isotone function satisfying FcX⊆FX for all X∈. Proof. First observe that Fcis well defined; indeed, for c∈X=xLxU, since Fis an inclusion function, both FxLc and FcxU are closed intervals having fc as common point; hence, FcX∈. Moreover, Fcis an inclusion function. Indeed, if cX, one has FcX=FX⊇ fX;ifc∈X, one has fxLc⊆FxLc fcxU⊆FcxU Hence, fX=fxLc∪fcxU⊆FxLc∪FcxU=FcX showing that Fcis also an inclusion function. In order to see that Fcis isotone, consider YZ∈Y⊆Z. Three cases are considered: 1. If c∈Z, then the isotonicity of Fimplies that FcY =FY⊆FZ=FcZ. 2. If c∈Yand c∈Zthen either Y⊆zLc or Y⊆czU. In the first case one has FcY =FY⊆FzLc⊆FzLc∪FczU=FcZ whereas in the latter case one has FcY =FY⊆FczU⊆FzLc∪FczU=FcZ 3. If c∈Y(thus c∈Z) then 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. Therefore, Fcis isotone. IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 161 Trivially FcX⊆FX if cX.Ifc∈X, then the isotonicity of Fimplies that FxLc∪FcxU⊆FX, thus FcX⊆FX, as asserted.  Particularized to the inclusion function H, splitting by c=0, one obtains the inclusion function H0, defined as: H0X=     minHLxL0HL0xUmaxHUxL0HU0xU if 0∈X HX else (7) PROPOSITION 1. H0is an inclusion function which is isotone and satisfies for all X∈ 1. H0X⊆HX 2. H0X⊆NEX. Proof.H0is an isotone inclusion function satisfying H0X⊆HX by Lemma 1. By defining NE0following Definition 1, it suffices to show that H0X⊆NE0X for all X∈. We show that H0X⊆NEX by induction in the degree kof p. For k=01 the inclusion is straightforward. We assume that the inclusion holds for all polynomial functions of degree smaller than k, and show the result for the polynomial function px=a0+a1x+···+ak+1xk+1, (of degree k+1). If 0X, then H0X=HX=a0+XH∗X=a0+XH∗ 0X where H∗X (respectively H∗ 0) represents the Horner scheme H(respectively H0) for the polynomial function p∗of degree k,p∗x=a1+a2x+···+ak+1xk. By the induction assumption, one has H∗ 0X⊆NE∗X where NE∗denotes the natural extension for p∗. Hence, a0+XH∗ 0X⊆a0+XNE∗X⊆NEX Therefore H0X⊆NEX ∀Xwith 0X If 0∈X, a similar argument shows that H0xL0⊆NExL0 and H00xU⊆NE0xU Hence, H0X⊆NE0X⊆NEX, and the result holds.  162 E. CARRIZOSA ET AL. 2.2. TRANSLATION-BASED METHODS The idea of these methods is to translate the interval Xconsidered into the interval X!=xL+!xU+! by using an expression for px different from (4), and then choosing the value of !yielding the sharpest enclosure. First, observe that, for 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 fj!x+!j(8) with fj! defined as fj!= n−j  k=0 ak+jk+j j−!k(9) For each inclusion function Fpreviously defined one obtains now, for each !∈, a new translation-based inclusion function TF!·. For instance, from the Horner scheme H, one obtains TH, TH!X=f0!+X!f1!+X!···fn−1!+X!fn! (10) with X!=X+! Furthermore, TH0is defined, following Definition 1, as TH0!X=TH!X0(11) In the same way, TNETNE0TT1TTnare defined. Given an inclusion function F, we obtain for each !the inclusion function TF!·. By definition, TF0X=FX (12) thus by varying the parameter !it may be possible to come up with more accurate enclosures. This poses the problem of determining the values of !yielding the sharpest enclosure. For this we define, for an inclusion function F, the optimal translation-based inclusion function OTF as OTFX=max !∈TFL!X min !∈TFU!X(13) where TF!X=TFL!XTFU!X. IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 163 Observe that, by (12), OTFX⊆FX ∀X∈ Remark 1. The function OTF is only of interest for theoretical reasons; indeed, the practical determination of OTF amounts to solving two optimization problems which can be non-differentiable and non-convex. Hence, in practice, a few steps of a local-search algorithm will be used, yielding an enclosure possibly less sharp than OTF but with much less computational effort. PROPOSITION 2. TH0!X⊆TNE!X=Tn−!X for all !∈X∈(14) Proof. Let !∈and X∈. The inclusion TH0!X⊆TNE!X directly follows from Proposition 1. Since pnx=n!anfor all x, one has that PnX n!ann!anis an inclusion function for pn. By (1), Tn−!X can then be written 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+!ifi!=TNE!X This shows the result.  From (14) one directly has PROPOSITION 3. OTH0X⊆OTNEX for all X∈. 2.3. NUMERICAL RESULTS The different inclusion functions previously suggested have been compared according to the bounds they produce. Table 1 summarizes the results obtained for a series of univariate polynomial functions, either taken from the literature, [4, 11, 12], or randomly generated. The first ones are the following: 1. p1x=1 10 −x−79 20 x2+71 10 x3+39 80 x4−52 25 x5+1 6x6X=−211, due to Wingo, [11]. There is a misprint in the expression of the function in [11]. 164 E. CARRIZOSA ET AL. Table 1. Results for lower or upper bounds for polynomial functions. 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, the coefficients are 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, the Moore function. 3. p3x =0000089248x−00218343x2+0998266x3−16995x4+02x5,x∈ 010, the Wilkinson function. 4. p4x=4x2−4x3+x4x∈−55, the Dixon and Szegö function. 5. p5x=7x4−5x3+4x2+3x+2, X=010, generated randomly with integer coefficients in the range −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, generated randomly with real coefficients in the interval −2020. 7. p7x=10x−15x2−3x3+x4x∈−55, the Dixon function. The inclusion functions considered are NEHH0T1Band Tkk=123, taking as x0the midpoint of the interval X. Moreover, OTH0is computed using fminu of MatLab to perform a local search, setting !equal to 0 as starting point, and performing at most 30 iterations. In order to check the computed bounds, an outwardly rounded interval arithmetic code must be used [6–8]. Here, we have developed in MatLab the needed operations, i.e., addition and multiplication for computing polynomial functions, with outwardly rounded computations. Hence, the results presented are numerically correct for each inclusion function. It may be possible that the floating computations performing the translation !produce some numerical errors and that the result differs slightly, or in rare IMPROVING INTERVAL ANALYSIS BOUNDS BY TRANSLATIONS 165 cases largely, from the optimal value. But no negative effect can occur, because TF!X is always an inclusion function for all real (or floating) values of !. In most cases, either the lower bound (lb) or the upper bound (ub) improved considerably with respect to the other enclosures, the optimal !for the other bound being close to zero. The bounds, together with the optimal !for OTH0 are given in the last two rows of the table. It appears that some surprising improvements of the bounds are obtained for polynomial functions both of low degree (e.g. p5) and high degree (e.g. p2). 2.4. EXTENSION TO UNIVARIATE RATIONAL FUNCTIONS The methodology extends in a straightforward manner to functions rgiven as the ratio of two polynomial functions pq. Indeed, if THp 0!1X and THq 0!2X represent translation-based inclusion functions for pand qaccording to (11), then one obtains, for each !1!2, the inclusion function THp 0!1X THq 0!2X The optimization in the translation parameters yields a new (and sharper) enclosure, 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) Remark 2. Remark that the latest enclosure, although less sharp, requires the resolution of two instead of four optimization problems. Moreover, if just one out of the two bounds is needed, one has to solve only one instead of four optimization problems. The improvement in precision of the enclosures obtained in this way is illustrated in Table 2. We have compared OTH p q 0, as defined in (15) as well as the enclosure defined in (16) (the two last lines of the table) with the enclosures NEHp 0 Hq 0, the first-order Taylor expansion T1and the Baumann inclusion function T1B. The numerical tests are performed on the rational function rx=p1x p5x over different intervals. Observe that, for large intervals, the standard enclosures cannot exclude zero in the denominator, yielding the trivial interval −+using extended arithmetic. 172 E. CARRIZOSA ET AL. References 1. Baumann, E. (1988), Optimal centered form, BIT, 28, 80–87. 2. Du, K. and Kearfott, R.B. (1996), The cluster problem in multivariate global optimization, Journal of Global Optimization, 10, 27–32. 3. Hansen, E. (1992), Global Optimization Using Interval Analysis, Marcel Dekker, New York. 4. Hansen, P., Jaumard, B. and Lu, S.-H. (1989), Global minimization of univariate functions by sequential polynomial approximation international, International Journal of Computer Mathematics, 28, 183–193. 5. Ichida, K. and Fujii, Y. (1979), An interval arithmetic method for global optimization, Computing, 23, 85–97. 6. Kearfott, R.B. (1996), Rigorous Global Search: Continuous Problems, Kluwer Academic Publishers, Dordrecht, Boston, London. 7. Messine, F. (1997), Méthodes d’optimisation globale basées sur l’analyse d’intervalle pour la résolution de problèmes avec contraintes, PhD Thesis, INPT-ENSEEIHT, Toulouse. Available on the website: www.univ-pau.fr/∼messine 8. Moore, R.E. (1996), Interval Analysis, Prentice Hall, Englewood Cliffs, N.J. 9. Ratschek, H. and Rokne, J. (1984), Computer Methods for the Range of Functions, Ellis Horwood, Chichester, England. 10. Ratschek, H. and Rokne, J. (1988), New Computer Methods for Global optimization, Ellis Horwood, Chichester, England. 11. Visweswaran, V. and Floudas, C.A. (1992), Unconstrained and constrained global optimization of polynomial functions in one variable, Journal of Global Optimization, 2(1), 73–100. 12. Wingo, D.R. (1985), Globally minimizing polynomials without evaluating derivatives international, Journal of Computer Mathematics, 17, 287–294.