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.