Optimization of the Norm of a Vector-Valued DC Function and Applications

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 107, No. 2, pp. 245–260, NOVEMBER 2000 Op imiza ion o he No m o a Vec o -Valued DC Func ion and Applica ions 1 R. B LANQUERO 2 AND E. C ARRIZOSA 3 Communica ed by P. Pa dalos Abs ac . In his pape , we show ha a DC ep esen a ion can be ob ained explici ly o he composi ion o a gauge wi h a DC mapping, so ha he op imiza ion o ce ain unc ions in ol ing e mso his kind can be made by using s anda d DC op imiza ion echniques. Appli- ca ions o acili y loca ion heo y and mul iple-c i e ia decision making a e p esen ed. Key Wo ds. Global op imiza ion, di e ence o con ex unc ions, loca ion heo y, mul iple-c i e ia decision making. 1. P oblem Fo mula ion DC unc ions ( unc ions ψ ha can be w i en as he di e ence o wo con ex unc ions ψ + , ψ − ) cons i u e a wide class o unc ions ha plays an impo an ole wi hin he ield o global op imiza ion (Re s. 1–3). Among o he p ope ies, he class o DC unc ions is closed unde ce ain ope - a ions. Fo ins ance, P oposi ion 4 in Re . 3 asse s ha he composi ion o DC unc ions is also a DC unc ion. Since he p oo is based on he ac ha any locally DC unc ion on a con ex se is also DC (Re . 4), i is a noncons uc i e p oo ; i.e., i does no p o ide a DC decomposi ion o ψ G γ ª , e en when DC decomposi ions o and γ a e known. F om an op imiza ion poin o iew, his is an impo an d awback, since mos powe ul DC op imiza ion echniques, such as b anch-and-bound me hods (Re . 1), need a DC ep esen a ion o he unc ion unde s udy. Fo his eason, speci ic me hods o ob aining DC decomposi ions ha e been p o- posed o pa icula unc ions γ ; see o example P oposi ions 3.5–3.7 in Re . 5. 1 This esea ch was pa ially suppo ed by G an PB96-1416-CO2-02, DGES, Mad id, Spain. 2 P o esso , Facul ad de Ma ema ´ icas, Uni e sidad de Se illa, Se illa, Spain. 3 P o esso , Facul ad de Ma ema ´ icas, Uni e sidad de Se illa, Se illa, Spain. 245 0022-3239兾00兾1100-0245$18.00兾02000 Plenum Publishing Co po a ion JOTA: VOL. 107, NO. 2, NOVEMBER 2000246 In his pape , we conside he pa icula case o composi ions o DC unc ions in which he ou e unc ion γ is a gauge, ha is, a con ex unc ion γ :⺢ m → ⺢,de ined as γ (x)Gin { H0:x∈ B}, x∈⺢ m , (1) whe e Bis a con ex se , he in e io o which con ains he o igin (Re s. 6–7).By Theo em 14.5 in Re . 7, e e y gauge γ can be w i en as γ (x)Gmax{〈u,x〉:u∈B 0 }, x∈⺢ m , (2) whe e 〈·,·〉deno es he usual scala p oduc and B 0 is he pola se o B, ha is B 0 G{ :〈 ,x〉⁄1,∀x∈B}. Using his p ope y, he p oo o P oposi ion 4 in Re . 3 can be ew i en o his pa icula case, yielding a global DC decomposi ion o γ ª ,as shown below. P oposi ion 1.1. Le Ω⊂⺢ n be a con ex se . Le γ :⺢ m → ⺢be a gauge in ⺢ m wi h uni ball B, le G( 1 ,..., m ):Ω → ⺢ m be a DC ec o - alued unc ion, wi h known DC decomposi ion, i G + i A − i , wi h + i and − i con ex. Fo any iG1,...,m, le M i ¤max{ γ (e i ), γ (−e i )}, whe e e i is he i h uni ec o o ⺢ m . Then, γ ª :Ω → ⺢is a DC unc ion, and a DC decomposi ion o i is gi en by γ ª GgAh, (3) wi h gG γ ª C ∑ m iG1 M i ( + i C − i ), hG ∑ m iG1 M i ( + i C − i ). P oo . Fi s , obse e ha a ini e M i ¤max{ γ (e i ), γ (−e i )} can be chosen, since he o igin is an in e io poin o Band, he e o e, he pola se B 0 is bounded. F om (2), he gauge γ can be globally ep esen ed as a poin wise maximum o he a ine unc ions ϕ u , JOTA: VOL. 107, NO. 2, NOVEMBER 2000 247 γ (y)Gmax u∈B 0 ϕ u (y), ∀y∈⺢ m , whe e ϕ u (y)G〈u,y〉. Then, ϕ u ( 1 ,..., m )G ∑ m iG1 u i + i A ∑ m iG1 u i − i G ∑ m iG1 (M i Cu i ) + i C ∑ m iG1 (M i Au i ) − i A ∑ m iG1 M i ( + i C − i ) Since M i ¤ γ (e i )Gmax u∈B 0 u i and M i ¤ γ (−e i )Gmax u∈B 0 −u i , i ollows ha ª can be w i en as he di e ence o wo con ex unc ions, namely, ϕ u ª Gp u Aq, whe e p u G ∑ m iG1 (M i Cu i ) + i C ∑ m iG1 (M i Au i ) − i , qG ∑ m iG1 M i ( + i C − i ). Then, γ ª Gmax u∈B 0 ϕ u ( 1 ,..., m ) Gmax u∈B 0 (p u Aq) G 冢 max u∈B 0 p u 冣 Aq G( γ ª Cq)Aq, and he esul holds. 䊐 JOTA: VOL. 107, NO. 2, NOVEMBER 2000248 This p o ides immedia ely DC decomposi ions o impo an classes o DC ec o - alued unc ions. In pa icula , i he gauge γ is an L p -no m, i can be aken M i G1, o e e y i, yielding he ollowing co olla y. Co olla y 1.1. Le 1 ,..., m be DC unc ions on he con ex se Ω, wi h DC decomposi ions i G + i A − i ,iG1,...,m. Then, o any p, 1⁄p⁄S,兩兩 兩兩 p is DC on Ω, a DC decomposi ion being gi en by 兩兩 兩兩 p GgAh, wi h gG兩兩 兩兩 p C ∑ m iG1 ( + i C − i ), hG ∑ m iG1 ( + i C − i ). The esul in P oposi ion 1.1 can be s eng hened i u he assump ions a e made on he gauge γ in use. Indeed, he p oo abo e can be ew i en e.g. o he case in which he pola ball B 0 is con ained in he posi i e o han . P oposi ion 1.2. Le Ω⊂⺢ n be a con ex se . Le γ :⺢ m → ⺢be a gauge in ⺢ m wi h uni ball B, such ha B 0 ⊂⺢ m C . Le G( 1 ,..., m ):Ω → ⺢ m be a DC ec o - alued unc ion, wi h known DC decomposi ion, i G + i A − i , wi h + i and − i con ex. Fo any iG1,...,m, le M i ¤ γ (e i ), whe e e i is he i h uni ec o o ⺢ m . Then, γ ª :Ω → ⺢is a DC unc ion, and a DC decomposi ion o i is gi en by γ ª GgAh, (4) wi h gG γ ª C ∑ m iG1 M i − i ,hG ∑ m iG1 M i − i . As a non i ial applica ion, le us ob ain a DC decomposi ion o he k h unc ion: gi en G( 1 ,..., m ), le ( (1) (x),..., (m) (x)) be he a ange- men o ( 1 (x),..., m (x)) wi h (1) (x)¤ (2) (x)¤···¤ (m) (x). Then, we ha e he ollowing p oposi ion. JOTA: VOL. 107, NO. 2, NOVEMBER 2000 249 P oposi ion 1.3. Le Ω⊂⺢ n be a con ex se . Le G ( 1 ,..., m ):Ω → ⺢ m be a DC ec o - alued unc ion, wi h known DC decomposi ion i G + i A − i , wi h + i and − i con ex. Le hG ∑ m iG1 − i and, o any kG1,...,m, le g k G (1) C (2) C··· (k) C ∑ m iG1 − i . Then, a DC decomposi ion o (1) C (2) C···C (k) is gi en by (1) C (2) C···C (k) Gg k Ah. (5) In pa icula , a DC decomposi ion o (k) is gi en by (k) G(g k Ch)A(g kA1 Ch). (6) P oo . The decomposi ion (5) ollows om he ac ha (1) C···C (k) Gmax 冦 〈 ,u〉: ∑ m iG1 u i Gk,0⁄u i ⁄1,∀i 冧 . Thus, we can use P oposi ion 1.3 o B 0 gi en by B 0 G 冦 u∈⺢ m : ∑ m iG1 u i Gk,0⁄u i ⁄1,∀i 冧 . The decomposi ion (6) ollows om (5) and he ac ha (k) G[ (1) C···C (k) ]A[ (1) C···C (kA1) ]. 䊐 2. Applica ions In his sec ion, we analyze applica ions o he ields o loca ion heo y and mul iple-c i e ia decision making ha jus i y he in e es o P oposi ion 1.1. 2.1. Facili y Loca ion. As an applica ion o P oposi ion 1.1 o acili y loca ion heo y, we conside he Fe ma –Webe p oblem wi h o bidden egions and mixed gauges. The aim is o ind a loca ion ou side in (S), he in e io o a egion S, o a new acili y in he plane in such a way ha he weigh ed sum o he dis ances be ween he acili y and he demand poin s JOTA: VOL. 107, NO. 2, NOVEMBER 2000250 ( ixed acili ies) is minimized; ha is, we ha e o sol e he op imiza ion p oblem min 冦 ∑ n iG1 γ i (xAa i ):x∈⺢ 2 in (S) 冧 , (7) we e γ i is a gauge measu ing he dis ance om any poin in he plane o a i , xis he unknown loca ion o he new acili y, a i is he loca ion o he i h demand poin , and Sis a subse o ⺢ 2 ha can be ep esen ed as he union o mpai wise disjoin connec ed (no necessa ily con ex) se s, SG* m jG1 S j . The usual s a egy o inding an op imal solu ion o (7) consis s o i s sol ing he uncons ained p oblem, and hen checking i any elemen in he se X* o op imal solu ions is a easible poin o p oblem (7). I his is he case, hen we ha e an op imal loca ion o he es ic ed p oblem. In o he cases, he con exi y o he objec i e unc ion allows us o ensu e he exis - ence o an op imal solu ion belonging o bd(S), he bounda y o S; hus, we jus need o sol e, o jG1,...,m, min 冦 ∑ n iG1 γ i (xAa i ):x∈bd(S j ) 冧 . (8) Mos pape s in he li e a u e do no add ess he p oblem in i s ull gene ali y, since hey impose s ong assump ions on he gauge (assumed o be he L 1 no m o L 2 no m) and he o bidden egion, which is conside ed o ha e an ex emely simple o m (a polyhed on o a ci cle); see Re s. 8– 10. Suppose ha a pa ame ic desc ip ion o bd(S j ) is known; i.e., we ha e a unc ion w j :[0,1] >⺢ 2 pa ame izing bd(S j ). Then, (8) can be w i en as min 0⁄ ⁄1 ∑ n iG1 γ i (w j ( )Aa i ), (9) which is a one-dimensional op imiza ion p oblem whose objec i e unc ion will be mul imodal in gene al, so global op imiza ion echniques mus be used o i s solu ion. In he pa icula case in which w j is a DC unc ion wi h a known DC decomposi ion, P oposi ion 1.1 p o ides a DC ep esen a ion o he objec- i e o (9), so he op imal solu ion can be ob ained by sol ing a DC uni a i- a e p oblem. Se e al esul s gi en in he li e a u e enable us o ob ain such DC decomposi ion, ei he di ec ly o by using simple unc ions wi h known ep esen a ion (Re s. 1, 3, 5, 11, 12). Fo ins ance, i w j is wice con inuously JOTA: VOL. 107, NO. 2, NOVEMBER 2000 251 di e en iable and K¤0 is a bound o he second de i a i e, a DC decomposi ion o w j is gi en by w j ( )G[w j ( )C(1兾2)K 2 ]A(1兾2)K 2 . (10) Example 2.1. As illus a ion o his echnique, we ha e conside ed he ollowing Webe p oblem wi h a o bidden egion: min ∑ 3 iG1 ω i 兩兩xAa i 兩兩 2 , s. . x∈⺢ 2 in (S), whe e a 1 G(0,3), a 2 G(−2,4), a 3 G(4,−2), w 1 G2, w 2 G3, w 3 G2, and Sis he egion enclosed by he cu e R, a pa ame ic desc ip ion o which is gi en by RG{(u( ), ( )), ∈[0,1]}, wi h u( )G5cos(8 π )cos(2 π ), ( )G5cos(8 π )sin(2 π ). The op imal solu ion o he uncons ained p oblem is a 1 G(0,3), an in e io poin o S(see Fig. 1), so he op imal solu ion o he cons ained p oblem will be loca ed a i s bounda y. Fig. 1. Fo bidden egion and demand poin s, Example 2.1. JOTA: VOL. 107, NO. 2, NOVEMBER 2000252 Taking in o accoun ha a pa ame ic desc ip ion o bd(S) is al eady gi en, he op imal solu ion can be compu ed by sol ing min ∈[0,2 π ] F( )_ ∑ 3 iG1 ω i 兩兩(u( )Aa i1 , ( )Aa i2 )兩兩 2 . The objec i e is a mul imodal unc ion, as can be seen in Fig. 2, so he use o global op imiza ion echniques is equi ed. Since uand a e C 2 in [0,1], hey a e DC unc ions and (10) p o ides he DC decomposi ion u( )Gu C ( )Au − ( ), ( )G + ( )A − ( ), wi h u + ( )G5cos(8 π )cos(2 π )C170 π 2 2 ,u − ( )G170 π 2 2 , + ( )G5cos(8 π )sin(2 π )C170 π 2 2 , − ( )G170 π 2 2 . Hence, by Co olla y 1.1, i can be claimed ha [F( )Ch( )]Ah( )isa DC decomposi ion o F, wi h h( )G7[u + ( )C + ( )Cu − ( )C − ( )]A16 G7[5cos(8 π )cos(2 π )C5cos(8 π )sin(2 π )C680 π 2 2 ]A16. An (-op imal solu ion o he p oblem abo e has been ob ained by using a co e ing algo i hm (Re . 13), yielding *G0.28527653858, Fig. 2. Objec i e unc ion o e bd(S), Example 2.1. JOTA: VOL. 107, NO. 2, NOVEMBER 2000 253 which co esponds o he poin x*G(−0.6947487405,3.082955211). 䊐 Whe eas i migh be he case, as in Example 2.1, ha a DC pa ame iz- a ion o bd(S j ) is al eady gi en, in gene al such pa ame iza ion mus also be de e mined. Fo una ely, his is an easy ask when S j is a con ex and compac se . Indeed, assuming wi hou loss o gene ali y ha he o igin is an in e io poin o S j , we ha e he ollowing pa ame ic desc ip ion o i s bounda y: ω j ( )G[cos(2 π )兾 γ j (cos2 π ,sin2 π ), sin(2 π )兾 γ j (cos2 π ,sin2 π )], ∈[0,1], (11) whe e γ j is he gauge wi h uni ball S j . Bo h cos(2 π ) and sin(2 π ) a e DC unc ions; so, by P oposi ion 1.1, γ j (cos2 π ,sin2 π ) is also DC (wi h a DC decomposi ion a hand); hus, e e y componen o (11) is he quo ien o wo DC unc ions, hus DC. In o de o sol e (9) wi h he ω j ( ) in (11) ia e.g. a b anch-and-bound me hod, we will simply need a DC decomposi ion and a p ocedu e o e al- ua ing he objec i e unc ion and cons uc ing he subg adien s a gi en poin s. In he sea ch o a DC ep esen a ion o e e y componen o w,i su ices o ob ain a DC decomposi ion o he quo ien o a con ex unc ion and a DC unc ion, since he nume a o s o (11) can be exp essed easily as he di e ence o wo con ex unc ions. In o de o achie e his, we need he ollowing lemma. Lemma 2.1. Le Ube a bounded se wi h U⊂{(x,y,z)∈⺢ 3 :yAz¤ α }, whe e α H0, and le u:U>⺢be de ined as u(x,y,z)Gx·(yAz) −1 . Then, he e exis ρ *, A,B,C∈⺢such ha u + (x,y,z)Gu(x,y,z)C(1兾2) ρ *(x 2 Cy 2 Cz 2 )CAxCByCCz, u − (x,y,z)G(1兾2) ρ *(x 2 Cy 2 Cz 2 )CAxCByCCz a e con ex and inc easing componen wise unc ions. P oo . The Hessian ma ix o uis gi en by HG[1兾(yAz) 2 ] 冤 0−11 −12x兾(yAz)−2x兾(yAx) 1−2x兾(yAz)2x兾(yAz) 冥 , JOTA: VOL. 107, NO. 2, NOVEMBER 2000260 4. H ARTMAN , P., On Func ions Rep esen able as a Di e ence o Con ex Func ions, Paci ic Jou nal o Ma hema ics, Vol. 9, pp.707–713, 1959. 5. T UY ,H.,Con ex Analysis and Global Op imiza ion, Kluwe Academic Pub- lishe s, Do d ech , Holland, 1998. 6. M ICHELOT ,C.,The Ma hema ics o Con inuous Loca ion, S udies in Loca ional Analysis, Vol. 5, pp.59–83, 1993. 7. R OCKAFELLAR , R. T., Con ex Analysis, P ince on Uni e si y P ess, P ince on, New Je sey, 1970. 8. A NEJA , Y. P., and P ARLAR ,M.,Algo i hms o Webe Facili y Loca ion in he P esence o Fo bidden Regions and兾o Ba ie s o T a el, T anspo a ion Science, Vol. 28, pp.70–76, 1994. 9. B RIMBERG , J., and W ESOLOWSKY ,G.O.,The Rec ilinea Dis ance Minimum P oblem wi h Minimum Dis ance Cons ain s, Loca ion Science, Vol. 3, pp.203– 215, 1995. 10. H AMACHER , H. W., and N ICKEL , S., Res ic ed Plana Loca ion P oblems and Applica ions, Na al Resea ch Logis ics, Vol. 42, pp.967–992, 1995. 11. B ITTNER , L., Some Rep esen a ion Theo ems o Func ions and Se s and Thei Applica ion o Nonlinea P og amming, Nume ische Ma hema ik, Vol. 16, pp.32–51, 1970. 12. H IRIART -U RRUTY ,J.B.,Gene alized Di e en iabili y, Duali y, and Op imiza ion o P oblems Dealing wi h Di e ences o Con ex Func ions, Con exi y and Duali y in Op imiza ion, Edi ed by J. Pons ein, Sp inge Ve lag, Be lin, Ge - many, pp.37–69, 1985. 13. B LANQUERO , R., and C ARRIZOSA , E., On Co e ing Me hods o DC Op imiz- a ion, To appea in Jou nal o Global Op imiza ion. 14. H IRIART -U RRUTY . J. B., Con ex Analysis and Minimiza ion Algo i hms, I, Sp inge Ve lag, Be lin, Ge many, 1993. 15. B AZARAA , M. S., S HERALI , H. D., and S HETTY ,C.M.,Nonlinea P og am- ming: Theo y and Algo i hms, John Wiley and Sons, New Yo k, NY, 1993. 16. Z ELENY ,M.,Comp omise P og amming, Mul iple-C i e ia Decision Making, Edi ed by J. L. Coch ane, and M. Zeleny, Uni e si y o Sou h Ca olina P ess, Columbia, Sou h Ca olina, pp.262–301, 1973. 17. Z ELENY ,M.,A Concep o Comp omise Solu ions and he Me hod o he Dis- placed Ideal, Compu e s and Ope a ions Resea ch, Vol. 1, pp.479–496, 1974. 18. Z ELENY ,M.,Mul iple-C i e ia Decision Making, Sp inge Ve lag, Be lin, Ge - many, 1976. 19. R OMERO ,C.,Handbook o C i ical Issues in Goal P og amming, Pe gamon P ess, Ox o d, England, 1991. 20. S ABER , H. M., and R AVINDRAN ,A.,Nonlinea Goal P og amming Theo y and P ac ice: A Su ey, Compu e s and Ope a ions Resea ch, Vol. 20, pp.275–291, 1993. 21. S ABER , H. M., and R AVINDRAN ,A.,A Pa i ioning G adien Based (PGB) Algo i hm o Sol ing Nonlinea Goal P og amming P oblems, Compu e s and Ope a ions Resea ch, Vol. 23, pp.141–152, 1995.