Jou nal o Global Op imiza ion 18: 35–58, 2000. 35
2000 Kluwe Academic Publishe s.P in ed in he Ne he lands.
Domina o s o Mul iple-objec i e Quasicon ex
Maximiza ion P oblems
1, 2
*
EMILIO CARRIZOSA and FRANK PLASTRIA
1
´
Facul ad de Ma ema icas,Uni e sidad de Se illa,C/Ta ia s/n,
41012
Se illa,Spain
E-mail
:
eca [email protected]
2
Depa men o Managemen In o ma ics,V ije Uni e si ei B ussel,Pleinlaan,
2,
B-
1050
B ussels,
Belgium (E-mail
:
F ank.Plas ia@ ub.ac.be)
(Recei ed 19 Janua y 1998; accep ed in e ised o m 6 Janua y 2000)
Abs ac . In his pape we add ess he p oblem o inding a domina o o a mul iple-objec i e
maximiza ion p oblem wi h quasicon ex unc ions. The one-dimensional case is discussed in some
de ail, showing how a B anch-and-Bound p ocedu e leads o a domina o wi h ce ain minimali y
p ope ies. Then, he well-known esul s a ing ha he se o e ices o a poly ope Scon ains an
op imal solu ion o single-objec i e quasicon ex maximiza ion p oblems is ex ended o mul iple-
objec i e p oblems, showing ha , unde uppe -semicon inui y assump ions, he se o (k⫺1)-
dimensional aces is a domina o o k-objec i e p oblems. In pa icula , o biobjec i e
quasicon ex p oblems on a poly ope S, he edges o Scons i u e a domina o , om which a
domina o wi h minimali y p ope ies can be ex ac ed by B anch-and Bound me hods.
Key wo ds: Mul iple-objec i e p oblems; Quasicon ex maximiza ion; Domina o s
1. In oduc ion
nnk
Gi en a nonemp y closed subse So ⺢and a unc ion F:S傺⺢→⺢, de ine he
mul iple-objec i e p oblem (P[F;S]),
max F(x), (P[F;S])
x僆S
which seeks hose al e na i es maximizing simul aneously he componen s
F,F,...,Fo F, [7, 28, 31].
12 k
Al hough he e m simul aneous maximiza ion is no uniquely de ined, i
cus oma ily means inding he se
Ᏹ
[F;S]o e icien o Pa e o-op imal solu ions o
(P[F;S]),
Ᏹ
[F;S]⫽兵x僆S:noy僆S e i ies F(y)⭓F(x)᭙i⫽1, 2, . . . , k
ii
wi h a leas one inequali y s ic 其
In gene al
Ᏹ
[F;S] lacks many desi able p ope ies such as being connec ed o
closed, and his seems o be qui e o en he case and no only in pa hological
´
* The esea ch o his au ho is pa ially suppo ed by G an PB96-1416-C02-02 o Di eccion Gene al de
˜
Ensenanza Supe io , Spain.
36 EMILIO CARRIZOSA AND FRANK PLASTRIA
Figu e
1
. Biobjec i e con ex maximiza ion.
examples: ake, o ins ance, he biobjec i e con ex maximiza ion p oblem in one
22
a iable (n⫽1, k⫽2) wi h F(x)⫽((x⫹1) , (x⫺1) ) and S⫽[⫺2, 1.5], plo ed in
Figu e 1.
Since F(⫺2)⭓F(x)᭙x僆]⫺2, 0], wi h a leas one inequali y s ic , and
F(1.5)⭓F(x)᭙x僆[0.5, 1.5[, wi h a leas one ineuali y s ic oo, i ollows ha he
se o Pa e o-op imal poin s mus be con ained in 兵⫺2其傼]0, 0.5[傼兵1.5其. In ac , i
is eadily seen om he plo ha
Ᏹ
[F;S]⫽兵⫺2其傼]0, 0.5[傼兵1.5其,
which is a disconnec ed non-closed se . See ollowing sec ions and also e.g. [3] o
o he ins ances.
Mo eo e , al hough he e exis p ocedu es o check whe he a gi en poin is
e icien o no , e.g. [7, 31], an algo i hm o cons uc
Ᏹ
[F;S] is only a ailable o a
ew classes o p oblems, such as mul iple-objec i e linea p oblems, [28].
This d awback has been o e come in he li e a u e by means o wo s a egies:
ei he
Ᏹ
[F;S] is sough , bu , due o he unabili y o ob aining i , an app oxima ion
(some imes wi h unknown deg ee o p ecision) is p o ided, e.g. [8, 18], o else he
concep o e iciency is elaxed and eplaced by a manageable su oga e o i .
In his pape we ollow he second app oach by using he concep o domina o ,
[5, 16, 21, 30], also called weak ke nel, e.g. in [31] which is de ined as any subse
S傺Ssuch ha , o any easible x僆
⁄
S,Scon ains a easible al e na i e a leas as
000
good as xwi h espec o all objec i es. See Sec ion 2 o a o mal de ini ion.
I should be ema ked ha his concep is no only use ul as a su oga e o he
idea o Pa e o-e iciency, bu also as a ool in he esolu ion o some single-objec i e
p oblems. Indeed, some o he mos popula op imiza ion me hods o single-
objec i e p oblems o he o m
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 37
max ⌿(x) (1.1)
x僆S
equi e he easible egion S o be bounded. Such is he case, among o he s, o he
B anch and Bound me hods o global op imiza ion, e.g. [15], which, in hei
simples e sion, equi e, as p e-p ocessing, he cons uc ion o a bounded poly-
hed on P(usually a hype - ec angle, o a simplex) including ei he he whole
easible egion, o , a leas a bounded subse S傺Sknown o con ain an op imal
0
solu ion. Mo eo e , he speed o con e gence o he p ocedu e is known o
de e io a e wi h he olume o P,soPshould be as small as possible in o de o
ob ain easonable compu a ion imes.
How o cons uc Pwill depend, o cou se, on he speci ic p ope ies o he
p oblem a hand. In pa icula , i (1.1) has he o m
max ⌽(F(x)) , (1.2)
x僆S
o some ⌽:F(S)→⺢componen wise non-dec easing, hen i is well known ha , i
(1.1) has op imal solu ions, hen any domina o o he mul iple-objec i e p oblem
max F(x) also con ains op imal solu ions o (1.1), [21]. In o he wo ds, we can
x僆S
ake as Sany bounded domina o o he mul iple-objec i e p oblem, and as Pany
0
supe se o Swi h he equi ed geome y.
0
This p ope y has been success ully exploi ed, among o he s, in [5, 21, 22, 30]
o p oblems o Linea Reg ession and Con inuous Loca ion, in which he
globalizing unc ion ⌽is an a bi a y non-dec easing unc ion and he unc ion Fis
componen wise conca e. Ou aim he e is o add ess he (ha de ) p oblem in which
he unc ion Fis componen wise (quasi)-con ex, showing as main esul (P oposi-
ion 19) ha , unde uppe -semicon inui y assump ions, he sea ch o a domina o can
be es ic ed o he (k⫺1)-dimensional aces o S.
The es o his pape is s uc u ed as ollows. In Sec ion 2 we o mally in oduce
he concep o domina o s and discuss some gene al p ope ies. These p ope ies a e
used in Sec ion 3 o add ess he one-dimensional case, o which domina o s wi h
ce ain minimali y p ope ies can be ob ained.
Sec ion 4 is de o ed o show ha , o mul iple-objec i e mul i-dimensional
p oblems, one can cons uc domina o s con ained in low dimensional aces o he
poly ope S.
The pape ends wi h an applica ion o hese esul s o he cons uc ion o a
domina o o a biobjec i e p oblem in Con inuous Loca ion. The eade is e e ed
also o [25] o ano he success ul applica ion o he echnique de eloped in his
pape .
2. Domina o s
⭓
De ining o each x僆S he uppe le el se a xo Fon S,
᏿
(x)as
⭓
᏿
(x)⫽兵y僆S:F(y)⭓F(x) o all i⫽1,2,...,k其,
ii
38 EMILIO CARRIZOSA AND FRANK PLASTRIA
he se
Ᏹ
[F;S] o e icien solu ions may be de ined by
⭓⭓
Ᏹ
[F;S]⫽兵x僆S:I y僆
᏿
(x) hen x僆
᏿
(y)其
⭓
⫽兵x僆S:I y僆
᏿
(x) hen F(x)⫽F(y)其
DEFINITION 1. A se S*傺S is said o be a domina o o (P[F;S]) i o each
x僆S he e exis s some x*僆S*which has,componen wise,a alue no smalle han
x.In o he wo ds,S*is a domina o i
⭓
(᭙x僆S)᭚x*僆
᏿
(x)傽S*
He ea e , he class o domina o s o (P[F;S]) will be deno ed by
Ᏸ
[F;S].
A di ec consequence o he de ini ion is he ollowing:
PROPOSITION 2. One has
1.
S僆
Ᏸ
[F;S]. In pa icula ,
Ᏸ
[F;S]is nonemp y.
2.
I D 僆
Ᏸ
[F;S]and D*sa is ies D 傺D*傺S, hen D*僆
Ᏸ
[F;S].
n
3.
Fo any class 兵S:j僆J其o nonemp y se s in ⺢,
j
I S*僆
Ᏸ
[F;S](᭙j僆J) hen 傼S*僆
Ᏸ
F;傼S
冋册
jj j j
j僆Jj僆J
n
4.
Fo any class 兵S:j僆J其o nonemp y se s in ⺢,
j
傽
Ᏸ
[F;S]傺
Ᏸ
F;傼S
冋册
jj
j僆Jj僆J
5.
I D 僆
Ᏸ
[F;S], hen
Ᏸ
[F;D]傺
Ᏸ
[F;S].
By P oposi ion 2, he class
Ᏸ
[F;S] is nonemp y since he whole easible se Sis
one o i s elemen s. Howe e Sdoes no seem o be he mos app op ia e domina o
since i possibly con ains ( oo) many domina ed al e na i es, being oo a om he
ideal aim o a smalles possible domina o .
PROPOSITION 3. Suppose each F is uppe -semicon inuous on S, hen any class o
j
compac nes ed domina o s is closed unde in e sec ions.In o he wo ds
:
i (I,Ɱ)is
᎐
a o ally o de ed se ,and 兵D其is a class o compac domina o s wi h D 傺D,
ii僆Iij
j僆I,iⱮj, hen
᎐
傽D僆
Ᏸ
[F;S].
i
i僆I
P oo . Take any x僆S. By he uppe -semicon inui y o he unc ions F, all uppe
j
le el se s 兵y僆S:F(y)⭓F(x)其a e closed, so hei in e sec ion
᏿
⭓(x) is also
jj
closed. By he de ini ion o domina o s and hei compac ness, i ollows o each
⭓⭓
i僆I ha
᏿
(x)傽Dis a nonemp y compac se , hus 兵
᏿
(x)傽D其cons i u es a
iii僆I
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 39
⭓
class o nes ed compac se s. By compac ness hei in e sec ion (i.e.,
᏿
(x)傽
傽D) is nonemp y.
i僆Ii
Howe e , i is e iden ha he whole class
Ᏸ
[F;S] is no closed unde
in e sec ions ( ake cons an unc ions F,...,F, hen any single ons 兵x其,兵y其傺Sa e
1k
domina o s, wi h emp y in e sec ion). Hence, a unique smalles domina o is
unlikely o exis . We hen elax he idea o smalles domina o by in oducing he
concep o (weak) minimal domina o s. Fi s de ine o each x僆S he s ic uppe
⬎
le el se o Fon S,
᏿
(x)as
⬎
᏿
(x)⫽兵y僆S:F(y)⬎F(x) o all i⫽1,2,...,k其.
ii
DEFINITION 4. A domina o S*is said o be minimal o (P[F;S]) i no p ope
subse o S*belongs o
Ᏸ
[F;S]. In o he wo ds,S*傺S is minimal i
⭓
(x,y僆S*, x⫽
⁄
y)⇒x僆
⁄᏿
(y)
A domina o S*傺S is said o be weak minimal o (P[F;S]) i
⬎
(x,y僆S*)⇒x僆
⁄᏿
(y)
The class o minimal
(
espec i ely weak minimal
)
domina o s o p oblem
(P[F;S]) will be deno ed by
Ᏸ
[F;S]( espec i ely
Ᏸ
[F;S]).
MWM
As a simple illus a ion o he concep s, conside he 2-dimensional 2-objec i e
op imiza ion p oblem max F(x), depic ed in Figu e 2, whe e he easible egion S
x僆S
2
is he polyhed on in ⺢wi h e ices a⫽(0, ⫺3), b⫽(4, ⫺1), c⫽(4, 0), d⫽(0,3),
and Fis gi en by
F(x,x)⫽x
11 2 1
F(x,x)⫽兩x兩
21 2 2
Then, he Pa e o op imal se is gi en by
Ᏹ
[F;S]⫽兵d其傼[a,b],
Figu e
2
.Sand F(S).

40 EMILIO CARRIZOSA AND FRANK PLASTRIA
only wo minimal domina o s exis , namely
S⫽[a,b]
1
S⫽]a,b]傼兵d其,
2
whe eas he polygonal S,
3
S⫽兵d其傼[a,b]傼[b,c]
3
is also weak minimal.
We obse e in his example ha he wo minimal domina o s a e p ope subse s
o
Ᏹ
[F;S]. This esul is mo e gene al, as s a ed in he ollowing:
PROPOSITION 5. Suppose ha S is compac and each F is uppe semicon inuous
i
on S.Then
1. Ᏹ
[F;S]is a weak minimal domina o .
2.
Minimal domina o s exis .
3. Ᏹ
[F;S]⫽傼S*.
S*僆
Ᏸ
[F;S]
M
⭓
P oo . By he uppe -semicon inui y assump ion, o each x僆S he se
᏿
(x)is
compac . Hence, by Theo em 6 o Chap e 2 o [31]
Ᏹ
[F;S] is a domina o , which,
by cons uc ion, is also weak minimal. Hence 1 holds.
To show 2, de ine on
Ᏹ
[F,S] he equi alence ela ion
␳
⫽兵(x,y)僆
Ᏹ
[F;S]⫻
Ᏹ
[F;S]:F(x)⫽F(y)其.
Taking exac ly one elemen in e e y equi alence class, we ob ain a se S* which is,
by cons uc ion, a minimal domina o . Indeed, i is a domina o because
Ᏹ
[F;S]isa
domina o , as shown in Pa 1. Mo eo e i is minimal: i he e exis s some
domina o M傺S*, M苷S*, o any x僆S* M he e would exis some y僆Mwi h
F(y)⭓F(x). Bu by cons uc ion o S* we would ha e F(y)苷F(x) con adic ing he
ac ha xis e icien . Hence, minimal domina o s exis .
Fo Pa 3, we i s show ha e e y e icien poin is in some minimal domina o :
le x*僆
Ᏹ
[F;S], and cons uc a subse S*o
Ᏹ
[F;S] aking exac ly one elemen o
e e y equi alence class (wi h espec o he equi alence ela ion
␳
abo e), x* being
he elemen chosen om i s equi alence class. Using he easoning abo e, i is seen
ha S* is a minimal domina o , and x*僆S*.
Finally o show ha any minimal domina o is included in he e icien se , ake
x*僆S*, o some S*僆
Ᏸ
[F;S], and assume x*僆
⁄Ᏹ
[F;S]. Then, he e exis s
M
some y僆Swi h F(y)⭓F(x), and a leas one inequali y s ic . Since S*僆
Ᏸ
[F;S],
M
he e mus exis some y*僆S* wi h F(y*)⭓F(y)⭓F(x*), hus he se S* 兵x*其will
also be a domina o , con adic ing he minimali y o S*. Hence, x*僆
Ᏹ
[F;S]. 䊐
REMARK 6. The uppe -semicon inui y assump ion is needed in o de o gua an ee
2
he non oidness o
Ᏸ
[F;S], as he ollowing coun e example shows: Le S傺⺢
WM
be he iangle whose endpoin s a e (⫺1, 0), (1, 0), (0, 1), and le F:S→⺢be
1
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 41
de ined as 1/(1⫺x) on he ela i e in e io o he wo op-edges, and ze o
2
elsewhe e. Since
lim F(x,x)⫽⫹⬁,
11 2
(x,x)→(0, 1),
12
(x,x)僆bd(S)
12
he maximum o Fon Sis no a ained, hus any D僆
Ᏸ
[F;S] mus con ain a
11
sequence o bounda y poin s con e ging o (0, 1), implying ha Dcon ains poin s
x,ywi h F(x)⬎F(y). Hence, no weak minimal domina o exis s. 䊐
11
3. Mul iple-objec i e one-dimensional p oblems
In his sec ion we add ess he mul iple-objec i e p oblem (P[F;S]) when Sis gi en
as a ini e union o compac in e als in ⺢, and each Fis quasicon ex on each
i
in e al. We i s discuss some p ope ies o one-dimensional single-objec i e
quasicon ex minimiza ion p oblems, which a e hen used o ackle (P[F;S]), i s
when S educes o a single compac in e al and hen in he gene al case. Fo he
basic p ope ies o quasicon ex unc ions we e e he eade o [1].
3.1. SINGLE-OBJECTIVE QUASICONVEX MINIMIZATION PROBLEMS ON AN INTERVAL
Le I傺⺢be a nonemp y compac in e al, and le g:I→⺢be quasicon ex. We
will deno e by cl g he closu e o g ela i e o I, namely
I
cl g(x)⫽in 兵 :᭚兵x其傺I, such ha x→x,g(x)→ 其
I
(3.3)
⫽lim in g(x)
x→x
LEMMA 7. One has
:
1.
g(x)⭓cl g(x) o all x 僆I.
I
2
. in g(x)⫽in cl g(x).
x僆Ix僆II
3.
cl g is quasicon ex and lowe -semicon inuous.
I
4.
The se a g min cl g(x)o op imal solu ions o min cl g(x)is a
x僆IIx僆II
nonemp y compac subin e al o I.
P oo . 1 o 3 immedia ely ollow om he de ini ion o quasicon exi y and (3.3).
By he lowe semicon inui y o cl g, he se a g min g(x) is compac and
Ix僆I
nonemp y; since cl gis also quasicon ex, i ollows ha a g min cl g(x) is also
Ix僆II
con ex, hus i is a compac in e al, and Pa 4 ollows. 䊐
We ecall ha a unc ion gis said o be semis ic ly quasicon ex, [1], i i sa is ies
he ollowing:
g(a)⬍g(b)⇒g(c)⬍g(b)
冎
c僆]a,b[
The nex lemma shows ha , due o he quasicon exi y o g, he beha io o gand
42 EMILIO CARRIZOSA AND FRANK PLASTRIA
cl ga e closely ela ed, he ela ionship being s onge o semis ic ly quasicon ex
I
g:
LEMMA 8. Le x*僆a g min cl g(x), and le z ,z僆I such ha z 僆]x*, z[.
x僆II12 12
One has
:
1.
g(z)⭐g(z).
12
2.
I g is also semis ic ly quasicon ex and g(z)⫽g(z), hen
12
]x*, z[傺a g min g(x).
2x僆I
P oo . By de ini ion o cl gand Pa 2 o Lemma 7, one can ake a sequence 兵x其
I
in Icon e ging o x* such ha in g(x)⫽in g(x)⫽cl g(x*).
x僆II
Since z⬎x*, he e exis s such ha x⬍z o all ⭓ , hus
10 10
z僆]x,z[ o all ⭓
1 20
Gi en ⭓ , i i we e he case ha g(z)⬍g(z), hen
021
g(z)⬍g(z)
21
⭐max兵g(z), g(x)其
2
Hence, g(z)⭐g(x) o each ⭓ hus one would ha e
1 0
g(z)⬍g(z)
21
⭐in g(x)
⫽in g(x),
x僆I
which is a con adic ion. Hence, g(z)⭓g(z), which shows 1.
21
To show 2, by he quasicon exi y o gi is enough o show ha , i g(z)⫽g(z),
12
hen 兵z,z其傺a g min g(x). Suppose ha , on he con a y, g(z)⫽g(z)⬎
12 x僆I12
in g(x). Then, by Lemma 7,
x僆I
g(z)⫽g(z)
12
⬎cl g(x*) ,
I
and we could ake a sequence 兵x其con e ging o x* wi h g(x) con e ging o
cl g(x*) and g(x)⬍g(z) o each . Since z僆]x*, z[, i would ollow ha
I 212
z僆]x,z[ o some , hus, by he s ic quasicon exi y o g,g(z)⬍g(z), which
1 212
would be a con adic ion. Hence g(z)⫽g(z)⫽cl g(x*), showing ha
12I
[z,z]傺a g min g(x).
12 x僆I
By he quasicon exi y o bo h gand cl g, and he op imali y o x* and [z,z] o
I12
min cl g(x), i hen ollows ha
x僆II
[x*, z]傺a g min g(x),
1x僆I
and he esul holds. 䊐
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 43
Ano he in e es ing p ope y, which will be exploi ed in he sequel, s a es ha ,
once p oblem min cl g(x) has been sol ed, any p oblem in g(x) wi h nes ed
x僆IIx僆J
easible in e al J傺Iis immedia ely sol ed. Indeed, deno ing by i(J) he in e io o
J, one has:
:
PROPOSITION 9. Le J ⫽[a,b]傺I be wo compac in e als in ⺢.One has
:
1.
cl g⭐cl gonJ,and
IJ
cl g(x)⫽cl g(x) o all x 僆i(J) (3.4)
IJ
2.
I (a g min cl g(x)) 傽i(J)苷5, hen
x僆II
in g(x)⫽min cl g(x) (3.5)
I
x僆Jx僆I
3.
I (a g min cl g(x)) 傽i(J)⫽5, hen
x僆II
in g(x)⫽min兵g(a), g(b)其(3.6)
x僆J
P oo . Pa 1 is a di ec consequence o he de ini ion o he closu e o gand
Lemma 7.
Fo Pa 2, le x*僆a g min cl g(x)傽i(J); hen, by Pa s 1, 2 o Lemma 7 and
x僆II
Pa 1 o his p oposi ion,
min cl g(x)⫽cl g(x*)
II
x僆I
⫽cl g(x*)
J
⫽min cl g(x)
J
x僆J
⫽in g(x)
x僆J
⭓in g(x)
x僆I
⫽min cl g(x)
I
x僆I
Pa 3 immedia ely ollows om Lemma 8 i a g min cl g(x) con ains poin s
x僆II
in I J. In he emaining case, a g min cl g(x) consis s o jus one endpoin o J,
x僆II
say a. I a sequence 兵x其傺Jexis s con e ging o awi h g(x) con e ging o
ii
min cl g(x)⫽cl g(a), hen he esul ollows om he de ini ion o cl g.
x僆III I
O he wise he e exis s x*⬍awi h g(x*)⬍g(a) and hen he quasicon exi y o g
implies ha , o any x僆J,
g(x*)⬍g(a)
⭐max兵g(a), g(x)其,
hus g(x)⭓g(a), showing (3.6). 䊐
50 EMILIO CARRIZOSA AND FRANK PLASTRIA
F(0)⫽(2, 1.8000, 1)
F(5)⫽(1.9730, 1.6000, 1)
F(7)⫽(1.9964, 1.8824, 0.6000)
F(9)⫽(1.9995, 1.9459, 0.2000)
We hen ob ain
IM(I)UB(I)
兵0其(2, 1.8000, 1) (2, 1.8000, 1)
[5, 9] (1.9964, 1.8824, 0.6000) (1.9995, 1.9459, 1)
We will only use he simples es , namely, (3.8) in he algo i hm.
Since no pai o in e als in
ᏸ
sa is ies condi ion (3.8), we go o I e a ion 2 wi h
he lis o in e als
ᏸ
⫽兵兵0其, [5, 7], [7, 9]其.
Two new midpoin s appea , namely, 6 and 8, wi h objec i e alues
F(6)⫽(1.9901, 1.8000, 0.8000)
F(8)⫽(1.9987, 1.9231, 0.4000) .
This enables us o upda e he able o ec o s M,UB yielding
IM(I)UB(I)
兵0其(2, 1.8000, 1) (2, 1.8000, 1)
[5, 7] (1.9901, 1.8000, 0.8000) (1.9964, 1.8824, 1)
[7, 9] (1.9987, 1.9231, 0.4000) (1.9995, 1.9459, 0.6000)
As in he p e ious i e a ion, no pai o in e als sa is ies condi ion (3.8), and we
go o I e a ion 3 wi h he upda ed lis o in e als
ᏸ
⫽兵兵0其, [5, 6], [6, 7], [7, 8], [8, 9]其
The new midpoin s gi e objec i e alues
F(5.5)⫽(1.9837, 1.7241, 0.9000)
F(6.5)⫽(1.9940, 1.8491, 0.7000)
F(7.5)⫽(1.9978, 1.9059, 0.5000)
F(8.5)⫽(1.9992, 1.9360, 0.3000)

MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 51
Wi h his, ou new able o ec o s M,UB is gi en by
IM(I)UB(I)
兵0其(2, 1.8000, 1) (2, 1.8000, 1)
[5, 6] (1.9837, 1.7241, 0.9000) (1.9901, 1.8000, 1)
[6, 7] (1.9940, 1.8491, 0.7000) (1.9964, 1.8824, 0.8000)
[7, 8] (1.9978, 1.9059, 0.5000) (1.9987, 1.9231, 0.6000)
[8, 9] (1.9992, 1.9360, 0.3000) (1.9995, 1.9459, 0.4000)
In his case, he su icien condi ion o dominance is sa is ied o he pai o
in e als 兵0其and [5, 6], so he in e al [5, 6] can be excluded o u he conside a-
ions.
We would hen ob ain a educed lis
ᏸ
⫽兵兵0其, [6, 7], [7, 8], [8, 9]其
o s a I e a ion 4, i desi ed. 䊐
The ollowing heo em shows ha he successi e s eps o he algo i hm abo e
p o ide a sequence o nes ed compac domina o s, con e ging o a domina o which,
unde mild u he assump ions on he unc ions F, enjoys minimali y p ope ies:
i
PROPOSITION 17. Deno e by D he union o all in e als o
ᏸ
a he end o
i e a ion ,and by D* he compac se
⬁
D*⫽傽D
⫽1
1.
D⫽X⫽傼I and D 傺D o all .
11⭐i⭐ i ⫹1
2.
I F is uppe -semicon inuous, hen
D*僆
Ᏸ
[F;X] (3.10)
3.
Mo eo e ,i F is con inuous, hen
D*僆
Ᏸ
[F;X] . (3.11)
ᐃᏹ
P oo . The i s p ope y is e iden om he algo i hm.
By cons uc ion, each Dis compac , hus hei in e sec ion is also compac .
Mo eo e , D僆
Ᏸ
[F;X], hus, by P oposi ion 3, (3.10) ollows.
To show (3.11), suppose, on he con a y, ha he e exis x,x僆D* wi h
12
⬎
x僆
᏿
(x). I , o each i⫽1, 2 and ⫽1, 2, . . . , we deno e by
Ᏽ
he class o
12 i
in e als Iin he lis a s age wi h x僆I, i will ollow om he spli ing p ocess
iii
ha he e exis s some such ha , o each ⭓ , and each I僆
Ᏽ
00ii
x僆
⁄
I, and x僆
⁄
I
12 21
52 EMILIO CARRIZOSA AND FRANK PLASTRIA
Since he unc ions Fa e con inuous, hus uni o mly con inuous on X, he e would
i
exis some such ha o each I僆
Ᏽ
ii
F(x)⬎F(y) o all x僆Iand y僆I,j⫽1, 2, . . . , k
jj 12
Hence UB(I)⬍M(I), implying ha I( hus x) would ha e been dele ed p io o
21 2 2
s age by (3.8), hus x僆
⁄
D*, which is a con adic ion. 䊐
2
4. Mul iple-objec i e mul i-dimensional p oblems
Fo he single-objec i e case (i.e., i k⫽1in(P[F;S])), i is a well-known esul o
1
Global Op imiza ion ha , i Sis a poly ope and Fis quasicon ex on S, hen he se
1
o e ices o Sis a domina o o (P[F;S]), [15].
1j
In o he wo ds, i , o j⫽0, 1, . . . , n,
Ᏺ
deno es he se o poin s o a poly ope
Scon ained in some j-dimensional ace o S, hen
0
Ᏺ
僆
Ᏸ
[F;S] (4.12)
1
The nex p oposi ion ex ends asse ion (4.12) o mul iple-objec i e quasicon ex
p oblems. To show i , we will use he ollowing
n
LEMMA 18. Le P be a polyhed on in ⺢,and le H ,H,...,H be closed
12
n
hal spaces in ⺢.I x*is an ex eme poin o P 傽傽H, hen x*belongs o
1⭐i⭐ i
some ace o P wi h dimension no g ea e han .
P oo . Le Pbe ep esen ed as
n
P⫽兵x僆⺢:a⬘x⭐b o all 僆R其
o some ini e index se R, and le each Hbe gi en as
i
n
兵x僆⺢:c⬘x⭐d其
ii
De ine he se s o ac i e indices R(x*) and T(x*) as
R(x*)⫽兵 僆R:a⬘x*⫽b其
T(x*)⫽兵i,1⭐i⭐ :c⬘x*⫽d其
ii
Then x* belongs o he ace Fo P,
n
F⫽P傽兵x僆⺢:a⬘x⫽b᭙ 僆R(x*)其
We will show ha Fhas dimension no g ea e han . Indeed, since x* is, by
assump ion, an ex eme poin o P傽傽H, hen he se o ec o s 兵a其傼
1⭐i⭐ i 僆R(x*)
兵c其has ank
ii僆T(x*)
ank(兵a其傼兵c其)⫽n
僆R(x*) ii僆T(x*)
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 53
Hence, deno ing by 兩T(x*)兩 he ca dinali y o T(x*), one ob ains
ank(兵a其)⭓n⫺兩T(x*)兩
僆R(x*)
⭓n⫺ ,
hus he dimension o Fcanno be g ea e han .䊐
n
PROPOSITION 19. Le S be a poly ope in ⺢,le k ⭐n⫹1, and le F ,...,Fbe
1k
quasicon ex unc ions on S,all bu possibly one o which a e uppe -semicon inuous.
Then
k⫺1
Ᏺ
僆
Ᏸ
[F;S] (4.13)
P oo . Wi hou loss o gene ali y we assume ha F,F,...,Fa e uppe -
12 k⫺1
semicon inuous on S. We will show ha , o any x僆S,
⭓k⫺1
᏿
(x)傽
Ᏺ
苷5(4.14)
Le x僆S, and deno e by
Ꮽ
(x) he index se
Ꮽ
(x)⫽兵i,1⭐i⭐k⫺1, F(y)⬍F(x) o some y僆S其.
ii
I
Ꮽ
(x) is emp y, we would ha e
F(y)⭓F(x)᭙y僆S,
⭓
hus any e ex y*o Ssa is ies y*僆
᏿
(x). Hence
⭓0⭓k⫺1
5苷
᏿
(x)傽
Ᏺ
傺
᏿
(x)傽
Ᏺ
,
showing (4.14).
We conside now he case
Ꮽ
(x)苷5. Fo each i僆
Ꮽ
(x), he con ex se
兵y僆S:F(y)⬍F(x)其is open in S(i s complemen is closed due o he uppe -
ii
semicon inui y o F) and does no con ain x. Hence, he e exis s some nonze o
i
i
ec o usuch ha
i
具u,y⫺x典⬎0 o all y僆Swi h F(y)⬍F(x) , (4.15)
ii
n
whe e 具⭈,⭈典s ands o he usual scala p oduc in ⺢.
Conside he polyhed on S(x),
ni
S(x)⫽S傽兵y僆⺢:具u,y⫺x典⭐0, ᭙i僆
Ꮽ
(x)其,
which is nonemp y because x僆S(x). Conside he op imiza ion p oblem
max F(y) (4.16)
k
y僆S(x)
Since Fis quasicon ex on he nonemp y polyhed on S(x), (4.16) has an op imal
k
solu ion a some e ex y*o S(x). We will show ha
k⫺1⭓
y*僆
Ᏺ
傽
᏿
(x) (4.17)
54 EMILIO CARRIZOSA AND FRANK PLASTRIA
Since y* is a e ex o S(x), Lemma 18 implies ha
兩
Ꮽ
(x)兩k⫺1
y*僆
Ᏺ
傺
Ᏺ
(4.18)
Since x僆S(x) and y* is op imal o (4.16),
F(y*)⭓F(x) (4.19)
kk
By de ini ion o
Ꮽ
(x),
F(y*)⭓F(x)᭙i僆兵1, 2, . . . , k⫺1其
Ꮽ
(x) (4.20)
ii
and by (4.15) and he ac ha y*僆S(x),
F(y*)⭓F(x)᭙i僆
Ꮽ
(x) (4.21)
ii
⭓k⫺1
Joining (4.18–4.21), (4.17) holds, hus
᏿
(x)傽
Ᏺ
苷5, as asse ed. 䊐
REMARK 20. The assump ion o uppe -semicon inui y o a leas k⫺1 unc ions is
no supe luous, as he ollowing example shows: le k⫽2, n⫽2, S⫽[0, 1]⫻[0, 1],
and he unc ions F,Fde ined as
12
11 11
᎐᎐ ᎐᎐
0, i x⬎o x⫽0, 0, i x⬎o x⫽1,
共兲 共兲
22
22 22
F(x)⫽F(x)⫽
再再
12
1, o he wise 1, o he wise
11
᎐᎐
Bo h unc ions a e quasicon ex bu a e no uppe -semicon inuous; le x*⫽( , ). I
22
is easily seen ha
⭓1
᎐
᏿
(x*)⫽
␭
,:0⬍
␭
⬍1
兵共 兲 其
2
⭓11
hus
᏿
(x*)傽
Ᏺ
⫽5, showing ha
Ᏺ
is no a domina o . 䊐
As a consequence o P oposi ions 19 and 2, one ob ains
n
COROLLARY 21. Le S be he union o poly opes S ,...,Sin⺢.Le F ,...,F
1 1k
be k ⭐n⫹1 eal- alued unc ions on S.On each S ,le all F be quasicon ex and
ji
all bu possibly one F be lowe -semicon inuous.Then he union o all k ⫺1- aces o
i
all S is a domina o o P[F;S].
j
P oposi ion 19 also enables us o de i e localiza ion esul s o single-objec i e
p oblems.
n
COROLLARY 22. Le S be he union o poly opes S ,...,Sin⺢.Le F ,...,F
1 1k
be k ⭐n⫹1 eal- alued unc ions on S,quasicon ex on each S .Fo any
j
componen wise nondec easing ⌽:F(S)→⺢such ha P oblem
max ⌽(F(x), F(x),...,F(x))
12 k
x僆S
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 55
has an op imal solu ion, he union o he se o k ⫺1- aces o all S also con ains an
j
op imal solu ion.
In pa icula , o F,F,...,Flinea ac ional unc ions wi h posi i e de-
12 k
nomina o s on a poly ope S, which a e well-known o be quasicon ex (see e.g.
[1], p. 165) and ⌽(s,s,...,s)⫽s⫹s⫹⭈⭈⭈⫹s,o ⌽(s,s,...,s)⫽
12 k12 k12 k
max兵s,s,...,s其, we ob ain
12 k
COROLLARY 23. The minimum o he sum
(
espec . he maximum
)
o k linea
ac ional unc ions wi h posi i e denomina o s o e a poly ope S in dimension
n⭓k⫺1is a ained a some k ⫺1- ace o S.
This gene alizes he esul s known o he case k⫽2 (see he e iew o [27] and
he e e ences he ein). Fo an applica ion see [25].
REMARK 24. Fo biobjec i e p oblems (k⫽2), since bo h Fa e quasicon ex on
j
each edge, a e embedding such edges as compac in e als o he eal line, one can
use he esul s in Sec ion 3 o design an algo i hm con e ging o a weak minimal
domina o .
Fo he case o gene al k, P oposi ion 19 seems a he momen o be mainly o
heo e ical in e es : In p inciple, Algo i hm 1 can be gene alized o he k-dimension-
al case, by eplacing in e als by e.g. simplices, al hough he co esponding
bounding scheme does no ex end o he gene al case, and less e icien schemes,
such as hose p oposed in [4, 14], should be used.
Ne e heless, his kind o localiza ion esul s can be used o design new heu is ic
esolu ion me hods o p oblems o he o m min ⌽(F(x)), whe e k, he numbe o
x僆S
componen s o F, is e y small, and, in pa icula , much smalle han he dimension
no he space.
We know hen ha he sea ch o op imal solu ions can be educed o he
k⫺1-dimensional aces o S, so ha algo i hms which al e na e a global sea ch in a
gi en low-dimensional ace wi h mo es o adjacen low-dimensional aces, can be
used.
5. Applica ion: Loca ion o a semi-obnoxious acili y
2
Le S⫽S傼S傼⭈⭈⭈傼S, each Sbeing a con ex polygon in ⺢. Two ini e
12 i
⫹⫺ 2⫹
subse s
Ꮽ
,
Ꮽ
o ⺢a e gi en. Associa ed wi h each a僆
Ꮽ
we ha e a conca e
unc ion g: [0, ⫹⬁)→⺢and a polyhed al gauge
␥
, [9, 10, 19], i.e., a Minkowski
aa
unc ional whose uni ball is a poly ope.
Le h: [0, ⫹⬁)→⺢be a noninc easing unc ion, and conside he biobjec i e
p oblem
min (F(x), F(x)) , (5.22)
12
x僆S

56 EMILIO CARRIZOSA AND FRANK PLASTRIA
whe e
F(x)⫽冘g(
␥
(x⫺a))
1aa
⫹
a僆
Ꮽ
F(x)⫽max h(储x⫺a储),
2
⫺
a僆
Ꮽ
储⭈储being he euclidean no m.
This p oblem has i s mo i a ion in Con inuous Loca ion o semidesi able
acili ies, see [17, 23] o an in oduc ion o Con inuous Loca ion in gene al and [6,
24] o semidesi able acili y loca ion models: A acili y is o be loca ed wi hin
egion S, and will in e ac wi h indi iduals who wan he acili y close ( hose in
⫹⫺⫹
Ꮽ
) and o he s who wan he acili y a ( hose in
Ꮽ
). In e ac ions wi h
Ꮽ
p o ide he i s objec i e in (5.22): he minimiza ion o he o al anspo a ion cos
⫹
F(x), whe e anspo a ion cos om a僆
Ꮽ
o xis gi en by a conca e unc ion g
1a
o he dis ance om a o x, he la e measu ed by he polyhed al gauge
␥
, [29].
a
⫺
On he o he hand, in e ac ions o he acili y wi h
Ꮽ
p o ide he second
⫺
objec i e F, which measu es he highes damage su e ed by poin s in
Ꮽ
, whe e
2⫺
he damage su e ed by a僆
Ꮽ
is assumed o be gi en by a noninc easing unc ion
ho he Euclidean dis ance om a o x, see [11, 24].
In p ac ice, he wo objec i es o (5.22) a e agg ega ed in o a single c i e ion,
yielding a p oblem o he o m
max ⌽⫺冘g(
␥
(x⫺a)), max h(储x⫺a储) , (5.23)
aa
冉冊
⫺
a僆
Ꮽ
⫹
a僆
Ꮽ
[6, 24] o some globalizing ⌽, and he esul ing p oblem (mul imodal, as a ule),
can be ackled e.g. by he 2-dimensional B anch and Bound me hod desc ibed in
[13]. Howe e , as shown below (P oposi ion 25), he sea ch o an op imal solu ion
o (5.23) can be es ic ed o a se ies o segmen s, hus (5.23) can be sol ed by
simply using single- a iable Global-Op imiza ion echniques, [2, 12], which a e
usually much as e han hei wo- a iable coun e pa s.
In o de o ob ain a domina o o (5.22) one should obse e i s ha , since his
assumed o be noninc easing, i su ices o ob ain a domina o o p oblem
max (⫺F(x), min 储x⫺a储) (5.24)
1
⫺
x僆Sa僆
Ꮽ
(in ac , i his dec easing, bo h p oblems a e equi alen ). Le us ew i e now (5.24)
wi hin ou amewo k. Fo polyhed al gauges, using he concep o elemen a y
con ex se o [10], one can ob ain a subdi ision
Ꮿ
o he plane in o polyhed a in
such a way ha , wi hin each C僆
Ꮿ
, each gauge
␥
is a ine, see [9, 10] o u he
a
de ails. Fo ins ance, i each
␥
is he lno m, hen he polyhed al subdi ision o he
a1
plane is ob ained a e cons uc ing ho izon al and e ical lines h ough each
⫹⫹2
a僆
Ꮽ
, yielding a o al o O(兩
Ꮽ
兩) cells.
⫺
Mo eo e , de ining, o each a僆
Ꮽ
, he Vo onoi cell V(a) associa ed wi h aas
2⫺
V(a)⫽兵x僆⺢:储x⫺a储⭐储x⫺b储 o all b僆
Ꮽ
其,
MULTIPLE-OBJECTIVE QUASICONVEX MAXIMIZATION 57
⫺2
he class
ᐂ
⫽兵V(a):a僆
Ꮽ
其also cons i u es a polyhed al subdi ision o ⺢in
⫺⫺⫺
O(兩
Ꮽ
兩) polyhed a, which can be e icien ly cons uc ed in O(兩
Ꮽ
兩log 兩
Ꮽ
兩), see
e.g. [20, 26].
Conside now he class
ᐆ
o all Zo he o m
S傽C傽V(a)
i
⫺
o some i,1⭐i⭐ ,C僆
Ꮿ
and a僆
Ꮽ
which a e nonemp y. On each Z僆
ᐆ
,we
ha e ha ⫺Fis con ex (i is he composi ion o he con ex unc ion ⫺兺g
⫹
1a僆
Ꮽ
a
wi h he a ine unc ions (wi hin Z!)
␥
, and Fis also con ex ( ecall ha , o Z僆
ᐆ
a2
⫺
ixed, he e exis s some a*僆
Ꮽ
such ha min 储x⫺a储⫽储x⫺a*储). Hence,
⫺
a僆
Ꮽ
ew i ing (5.24) as
max (⫺F(x), min 储x⫺a储),
1
⫺
x僆傼 Za僆
Ꮽ
Z僆
ᐆ
we can use Co olla y 21 o ob ain
PROPOSITION 25. The edges o he se s in
ᐆ
cons i u e a domina o o P oblem
(5.22)
.
A e embedding he edges o poly opes in
ᐆ
as compac in e als o he eal line,
one can use he algo i hm desc ibed in Sec ion 3.3 o educe he size o such
domina o , con e ging (in case o dec easing h) o a weak minimal domina o .
Re e ences
1. A iel, M., Diewe , W.E., Schaible, S. and Zang, I. (1988), Gene alized Conca i y, Plenum
P ess, New Yo k/London. ´´
2. Blanque o, R. (1999), Localizacion de se icios en el plano median e ecnicas de op-
´
imizacion d.c. Unpublished Ph.D., Uni e sidad de Se illa, Spain.
¯
3. Ca izosa, E., Conde, E., Munoz, M. and Pue o, J. (1995), Plana poin -objec i e loca ion
p oblems wi h noncon ex cons ain s: a geome ical cons uc ion. Jou nal o Global
Op imiza ion 6: 77–86.
4. Ca izosa, E., Conde, E. and Rome o-Mo ales, D. (1997), Loca ion o a semiobnoxious
acili y. A biobjec i e app oach. In Ad ances in Mul iple Objec i e and Goal P og amming.
Lec u e No es in Economics and Ma h.Sys ems 455, Sp inge , Be lin, 274–281.
5. Ca izosa, E. and F enk, J.B.G. (1998), Domina ing se s o con ex unc ions wi h some
applica ions. Jou nal o Op imiza ion Theo y and Applica ions 96: 281–295.
6. Ca izosa, E. and Plas ia, F. (1999), Loca ion o semi-obnoxious acili ies. S udies in
Loca ional Analysis 12: 1–27.
7. Chankong, V. and Haimes, Y. (1983), Mul iobjec i e Decision Making, No h-Holland.
8. Das, I. and Dennis, J.E. (1998), No mal-Bounda y In e sec ion: A New Me hod o
Gene a ing he Pa e o Su ace in Nonlinea Mul ic i e ia Op imiza ion P oblems. SIAM J.on
Op imiza ion 8: 631–657.
9. Du ie , R. (1990), On Pa e o op ima, he Fe ma -Webe p oblem and polyhed al gauges,
Ma hema ical P og amming 47: 65–79.
58 EMILIO CARRIZOSA AND FRANK PLASTRIA
10. Du ie , R. and Michelo , C. (1985), Geome ical P ope ies o he Fe ma -Webe p oblem,
Eu opean Jou nal o Ope a ional Resea ch 20: 332–343.
11. E ku , E. and Neuman, S. (1989), Analy ical Models o Loca ing Undesi able Facili ies,
Eu opean Jou nal o Ope a ional Resea ch 40: 275–291.
12. Hansen, P., Jauma d, B. and Lu, S.H. (1992), Global op imiza ion o uni a ia e Lipschi z
unc ions. II. New algo i hms and compu a ional compa ison. Ma hema ical P og amming
55: 273–292.
13. Hansen, P., Pee e s, D., Richa d, D. and Thisse, J.F. (1985), The minisum and mimimax
loca ion p oblems e isi ed. Ope a ions Resea ch 33: 125–126.
14. Hansen, P. and Thisse, J.F. (1981), The Gene alized Webe -Rawls P oblem, Ope a ions
Resea ch (J.P. B ans, ed.). No h Holland, pp. 487–495.
15. Ho s , R. and Tuy, H. (1990), Global Op imiza ion.De e minis ic App oaches. Sp inge -
Ve lag.
16. Kuhn, H.W. (1967), On a pai o dual nonlinea p og ams, in J. Abadie (ed.), Me hods o
Nonlinea P og amming. No h-Holland, pp. 37–54.
17. Lo e, R.F., Mo is, J.G. and Wesolowsky, G.O. (1988), Facili ies loca ion
:
models and
me hods, No h-Holland, New Yo k.
´
18. Ma eos, A. and Rıos-Insua, S. (1996), U ili y e iciency and i s app oxima ion. Top 4:
285–299.
19. Michelo , C. (1993), The ma hema ics o Con inuous Loca ion, S udies in Loca ional
Analysis 5: 59–83.
20. Okabe, A., Boo s, B. and Sugiha a, K. (1992), Spa ial essela ions.Concep s and applica-
ions o Vo onoi diag ams. Wiley.
21. Plas ia, F. (1983), Con inuous loca ion p oblems and cu ing plane algo i hms, Ph.D.
disse a ion, V ije Uni e si ei B ussel, B ussels.
22. Plas ia, F. (1984), Localiza ion in single acili y loca ion, Eu opean Jou nal o Ope a ional
Resea ch 18: 215–219.
23. Plas ia, F. (1995), Con inuous Loca ion P oblems, in Facili y Loca ion
:
A Su ey o
Applica ions and Me hods, Sp inge -Ve lag, New Yo k, pp. 225–262.
24. Plas ia, F. (1996), Op imal loca ion o undesi able acili ies: A selec i e o e iew,
JORBEL
:
Belgian Jou nal o Ope a ions Resea ch,S a is ics and Compu e Science 36:
109–127.
25. Plas ia, F. and Ca izosa, E. (1999), On gauges and median hype planes. Wo king pape
BEIF/112. V ije Uni e si ei B ussel, B ussels, Belgium.
26. P epa a a, F.P. and Shamos, M.I. (1985), Compu a ional Geome y –An In oduc ion,
Sp inge Ve lag.
27. Schaible, S. (1995), F ac ional P og amming, in R. Ho s and P.M. Pa dalos (eds.),
Handbook o Global Op imiza ion, Kluwe .
28. S eue , R. (1986), Mul iple c i e ia op imiza ion
:
Theo y,Compu a ion,Applica ion, Wiley.
29. Thisse, J.F., Wa d, J.E. and Wendell, R.E. (1984), Some P ope ies o Loca ion P oblems
wi h Block and Round No ms, Ope a ions Resea ch 32: 1309–1327.
30. Wendell, R.E. and Hu e , A.P. (1973), Loca ion heo y, dominance, and con exi y,
Ope a ions Resea ch 21: 314–320.
31. Whi e, D.J. (1982), Op imali y and E iciency. Wiley.