Ž.
Jou nal o Ma hema ical Analysis and Applica ions 259, 462᎐475 2001
doi:10.1006 jmaa.2000.7417, a ailable online a h p: www.idealib a y.com on
Duali y in Nondi e en iable Vec o P og amming
R. Osuna-Gomez, A. Ru ian-Lizana, and P. Ruız-Canales
´´ ´
Depa amen o de Es adıs ica e In¨es igacion Ope a i¨a, Fac. de Ma ema icas,
´´
c Tae ia s n 41012 Se¨ille, Spain
E-mail: [email p o ec ed]
Submi ed by Augus ine Esogbue
Recei ed Janua y 8, 1998
In his pape we s udy he saddle poin op imali y condi ions and Lag ange
duali y in mul iobjec i e op imiza ion o gene alized subcon ex-like unc ions. We
ob ain esul s which will allow us o cha ac e ize he solu ions o mul iobjec i e
p og amming p oblems om he saddle poin condi ions and allow us o ela e
hem o he dual p oblem solu ions which will be adequa ely de ined. We also
de ine a new dual p oblem o he mul iobjec i e p og amming p oblem wi h he
special p ope y o being a scala p og amming p oblem.
䊚
2001 Academic P ess
1. INTRODUCTION
Lag ange duali y is an a ac i e opic in op imiza ion heo y. In he pas
ew yea s, se e al s udies ha e been dedica ed o his subjec , discussing i
wx
wi hin he mul iobjec i e op imiza ion heo y amewo k 1, 2, 5, 9, 11, 12 .
One o he basic ques ions is how o weaken he assump ions o he known
esul s, as well as de ining adequa e dual p oblems ha migh acili a e he
sea ch o solu ions o mul iobjec i e op imiza ion p oblems.
The ec o op imiza ion p oblem conside ed in his pape can be o mu-
la ed as
VOP Min x
Ž. Ž.
s. . gxO0,
Ž.
n
xgS:⺢,
whe e :S:⺢nª⺢pand g:S:⺢nª⺢m.
Le us deno e by X he se o easible poin s o his p oblem, ha is,

nŽ.
4
XsxgS:⺢such ha gxO0.
462
0022-247X 01 $35.00
Copy igh
䊚2001 by Academic P ess
All igh s o ep oduc ion in any o m ese ed.
NONDIFFERENTIABLE VECTOR DUALITY 463
The e does no exis a unique solu ion concep o ec o ial p og am-
ming p oblems such as occu s o scala p og amming p oblems. Amongs
he nume ous de ini ions o solu ions o mul iobjec i e op imiza ion p ob-
lems which exis in he li e a u e, we will emphasize hose we conside he
mos impo an , and hose will be he ones used in his wo k.
Ž
DEFINITION 1.1. xgXis said o be an e icien solu ion a weakly
.Ž.
e icien solu ion o P oblem VOP i he e exis s no o he easible x
Ž. Ž.ŽŽ. Ž..
such ha xF x x- x.
Kuhn and Tucke no ed ha some e icien solu ions p esen ed an
undesi able p ope y wi h espec o he a io be ween he ma ginal p o i
o an objec i e unc ion and he loss o some o he . To hese solu ions,
hey in oduced he concep o he nonin e io p ope solu ion. Subse-
wx
quen ly, Geo ion 6 modi ied he concep sligh ly and de ined he
p ope ly e icien solu ions o a mul iobjec i e p oblem as ollows.
DEFINITION 1.2. xgXis said o be a p ope ly e icien solu ion o
Ž.
P oblem VOP i i is e icien and i he e exis s a scala M)0 such
ha , o each i, we ha e
xy x
Ž. Ž.
ii
-M
xy x
Ž. Ž.
jj
Ž. Ž. Ž. Ž.
o some jsuch ha x) xwhene e xgXand x- x.
jj ii
This pape consis s o six pa s. In Sec ion 2, some basic de ini ions and
heo ems a e i s in oduced. Sec ions 3 and 4 discuss saddle poin
heo ems o mul iobjec i e p og amming p oblems. Sec ion 5 add esses
he Lag ange duali y, and Sec ion 6 in oduces a new dual p oblem o he
mul iobjec i e p oblem wi h he special p ope y o being a scala p o-
g amming p oblem. Some conclusions a e gi en in Sec ion 7.
2. BASIC RESULTS AND PRELIMINARIES
Fi s , we in oduce a ew no a ions and de ini ions.
Ž.
TŽ.
Tp
Le xsx,..., x,ysy,..., yg⺢, hen
1p1p
xsyi xsy,is1,..., p;
ii
xOyi xFy,is1,..., p;
ii
xFyi xFy,is1,..., p,
ii
wi h s ic inequali y holding o a leas one i;
x-yi x-y,is1,..., p.
ii
OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES
´´ ´
464
I :S:⺢nª⺢p, we deno e by he i h componen o ; i.e.,
i
Ž. Ž Ž. Ž..
T
xs x,..., x .
1p
wx
Yang 15 de ined he concep o gene alized subcon ex-like unc ions
and p o ided an al e na i e heo em o hese unc ions.
DEFINITION 2.1. Le :S:⺢nª⺢p. is said o be gene alized
pŽ.
subcon ex-like on Si ᭚ug⺢,u)0, such ha ᭙
␣
g0, 1 , ᭙x,xgS,
12
and ᭙
⑀
)0, ᭚xgS,᭚
␳
)0 such ha
3
⑀
uq
␣
x q1y
␣
x G
␳
x .
Ž. Ž .Ž. Ž.
123
Fo hese unc ions was p o ed he ollowing gene alized al e na i e
wx
heo em 15 .
Ž.
THEOREM 2.1 Gene alized Al e na i e Theo em . Le S be a nonemp y
se in ⺢nand le :Sª⺢pbe a gene alized subcon¨ex-like unc ion on S.
Then ei he
Ž. Ž .
i x-0has a solu ion x gS,o
Ž. TŽ. p
ii w xG0 o all x gS, o some w g⺢,wG0,
bu bo h al e na i¨es a e ne¨e ue.
No e 2.1. In he p e ious heo em, we can suppose ha wTes1 since
Žp.T
i no , de ining ¨sw Ýw, we ha e ha ¨es1, and his ¨ e i ies
js1j
TŽ.
ha ¨ xG0᭙xgS.
Now we show some use ul p ope ies o he gene alized subcon ex-like
unc ions ha will be used subsequen ly.
LEMMA 2.1. I is a gene alized subcon¨ex-like unc ion and M )0, hen
M is a gene alized subcon¨ex-like unc ion wi h espec o he same poin .
pŽ.
P oo . I he e exis s ug⺢,u)0, such ha ᭙
␣
g0, 1 , ᭙x,xgS,
12
and ᭙
⑀
)0, ᭚xgSand ᭚
␳
)0 such ha
3
⑀
uq
␣
x q1y
␣
x G
␳
x ,
Ž. Ž .Ž. Ž.
123
hen o u⬘sMu )0 and
␳
⬘sM
␳
)0, M is gene alized subcon ex-like
on Swi h espec o he same poin x.
3
LEMMA 2.2. Le :Sª⺢pbe a gene alized subcon¨ex-like unc ion on
S.Then o all i,js1,..., p, q is a gene alized subcon¨ex-like unc ion
ij
wi h espec o he same poin .
P oo . I is gene alized subcon ex-like, hen o any i,js1,..., p
Ž.
he e exis u,u)0 such ha ᭙
␣
g0, 1 , ᭙x,xgS, and ᭙
⑀
)0
ij 12
᭚xgS,᭚
␳
)0 such ha
3
⑀
uq
␣
x q1y
␣
x G
␳
x
Ž. Ž .Ž. Ž.
ii1i2i3
NONDIFFERENTIABLE VECTOR DUALITY 465
and
⑀
uq
␣
x q1y
␣
x G
␳
x.
Ž. Ž .Ž. Ž.
jj1j2j3
Then, aking usuqu)0 we ha e ha q is gene alized subcon-
ij ij
ex-like.
Gene alized subcon ex-like unc ions p esen a special ype o i egula -
i y, which no o he gene alized con ex unc ion p esen s. I is gene al-
ized subcon ex-like and ag⺢p, hen he unc ion aq does no ha e o
be a gene alized subcon ex-like unc ion, as is shown in he ollowing
example.
Ž.Ž.
EXAMPLE 2.1. Le x,ysx,y, and be gene alized subcon ex-like
2
4
Ž.Ž.Ž .
on Ss⺢y0FxF1, 0 FyF1 . Bu x,yy1, 1 sxy1, yy1
qŽ.
is no a gene alized subcon ex-like unc ion on Sbecause o x,ys
11
1
Ž.Ž .Ž.
1, 0 , x,ys0, 1 , and
␣
s he e would ha e o exis a u)0 and a
22
2
␳
)0 such ha ᭙
⑀
)0,
11
⑀
u,uqy ,yG
␳
xy1, yy1 wi h x,ygS.
Ž. Ž .Ž.
12 3 3 33
ž/
22
Bu his is impossible.
3. EFFICIENCY CONDITIONS
In o de o ope a ionalize he concep o solu ions o a mul iobjec i e
p og amming p oblem we should ela e hem o amilia concep s. The
mos common s a egy is o cha ac e ize hem in e ms o op imal solu-
wx
ions o app op ia e scala op imiza ion p oblems 3, 10 . Among he many
Ž.
possible ways o ob aining a scala p oblem associa ed wi h VOP , he
ollowing is known as a scala weigh ing p oblem.
VP Min
␭
T x
Ž. Ž.
␭
s. . gxO0,
Ž.
n
xgS:⺢,

pp
4
whe e
␭
gL
Ls
␭
g⺢
␭
G0 and Ý
␭
s1.
jjs1j
wx
Geo ion 6 es ablished he ollowing undamen al esul .
Ž. Ž.
THEOREM 3.1. Le
␭
)0
␭
G0be ixed.I x is op imal in VP , hen x
␭
Ž.Ž.
is p ope ly e icien weakly e icien in VOP .
Assuming ha and ga e con ex unc ions and ha Sis a con ex se ,
Geo ion also es ablished he con e se o he abo e heo em. This esul
OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES
´´ ´
466
is based on Go dan’s al e na i e heo em. Hence by eplacing Go dan’s
Ž
al e na i e heo em wi h he Gene alized Al e na i e Theo em Theo em
.
2.1 we ob ain he ollowing esul .
Ž.
THEOREM 3.2. Le x be a p ope ly e icien solu ion in VOP and le
p
Ž.
y x be gene alized subcon¨ex-like on X.Then he e exis s
␭
g⺢,
Ž.
␭
)0, such ha x is op imal in VP .
␭
P oo . I xis p ope ly e icien , hen he e exis s a scala M)0 such
ha , o each is1,..., p, he sys em
x- x,
Ž. Ž.
ii
xqM x - xqM x o all j/i
Ž. Ž. Ž. Ž.
iji j
admi s no solu ion in X. By Lemma 2.1 and Lemma 2.2 and he Gene al-
ized Al e na i e Theo em, o each is1,..., p he e exis wig⺢,wiG0,
wi h Ýpwis1, such ha
js1j
ii ii
w x qw xqM x Gw x qw xqM x ,
Ž. Ž. Ž. Ž. Ž. Ž.
Ž. Ž.
ÝÝ
ii j i j ii j i j
j
/ij/i
o equi alen ly
ii
xqMw xG xqMw x,2
Ž. Ž. Ž. Ž. Ž.
ÝÝ
ijjijj
j
/ij/i
o each is1,..., pand o all xgX.
Ž.
Summing 2 o e iyields, a e some ea angemen ,
pp
ii
1qMw xG1qMw x,
Ž. Ž.
ÝÝ ÝÝ
jj jj
ž/ ž/
j
s1i/jjs1i/j
o all xgX.
i
Ž. Ž.
Then, aking
␭
s1qMÝw,xis op imal in VP .
ji/jj
␭
The nex heo em p o es an analogous esul o weakly e icien solu-
ions.
Ž.
THEOREM 3.3. Le x be a weakly e icien solu ion in VOP , and le
p
Ž.
y x be gene alized subcon¨ex-like on X.Then he e exis s
␭
g⺢,
Ž.
␭
G0, such ha x is op imal in VP .
␭
P oo . I xis a weakly e icien solu ion, hen he sys em
xy x-0, is1,..., p,
Ž. Ž.
ii
has no solu ion a xgX. By he Gene alized Al e na i e Theo em, he e
exis s
␭
G0 such ha
T
␭
xy x G0᭙xgX,
Ž. Ž.
Ž.

NONDIFFERENTIABLE VECTOR DUALITY 467
which implies ha
TT
␭
xG
␭
x ᭙xgX.
Ž. Ž.
Ž.
Thus xis he op imal solu ion o VP .
␭
We ema k ha no assump ion on he con exi y o he se Xis made in
he abo e heo ems.
4. SADDLE POINTS CONDITIONS
Fo scala ma hema ical p og amming he ela ionships be ween he
solu ions o a cons ained scala p og amming p oblem and he poin s
which ul ill ce ain condi ions known as he saddle poin op imali y
wx
c i e ia a e well known 8 . In his sec ion we ex end hese esul s o
mul iobjec i e p og amming p oblems. To do his we begin by gi ing new
de ini ions o saddle poin s o he ec o case.
npm
Ž.
DEFINITION 4.1. x, ,¨g⺢)⺢)⺢is said o be a ¨ec o
Ž.Ž.
F i z᎐John saddle poin o P oblem VOP i ,¨G0, and he ollowing
inequali ies hold ᭙¨P0 and ᭙xgS:
TTTTTT
x q¨gxF x q¨gxF x q¨gx.3
Ž. Ž. Ž. Ž. Ž. Ž. Ž.
npm
Ž.
DEFINITION 4.2. x, ,¨g⺢)⺢)⺢is said o be a ¨ec o
Ž.Ž.
Kuhn᎐Tucke saddle poin o P oblem VOP i ,¨G0, /0, and he
ollowing inequali ies hold ᭙¨P0 and ᭙xgS:
TTTTTT
x q¨gxF x q¨gxF x q¨gx.4
Ž. Ž. Ž. Ž. Ž. Ž. Ž.
Le us no e ha De ini ion 4.1 and De ini ion 4.2 coincide wi h he
F i z᎐John and Kuhn᎐Tucke saddle-poin de ini ions i is a nume ical
unc ion.
The abo e de ini ions ha e se e al ad an ages o e hose al eady exis -
wx
ing in he li e a u e 2, 4, 7, 13, 14, 16 . Fi s , he mul iplie o he
es ic ions is a ec o and no a unc ion o a ma ix. Second and mo e
impo an , he ec o saddle poin condi ions a e scala condi ions, no
ec o condi ions. Thus, i is no necessa y o sol e any ec o p oblem in
o de o ind he ec o saddle poin s, which simpli ies he ask.
Ž.
P oblem VOP is said o sa is y he gene alized Sla e cons ain
Ž.
quali ica ion i he e exis s a xgXsuch ha gx-0. We use his
ˆˆ
cons ain quali ica ion o p o e he ollowing esul ha ela es ec o
Kuhn᎐Tucke saddle poin s wi h ec o F i z᎐John saddle poin s.
OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES
´´ ´
468
Ž.
LEMMA 4.1. I x, ,¨is a ¨ec o F i z᎐John saddle poin and he
Ž.
gene alized Sla e cons ain quali ica ion is sa is ied, hen x, ,¨is a ¨ec o
Kuhn᎐Tucke saddle poin .
P oo . Le us suppose ha s0, hen he ec o F i z᎐John saddle
poin condi ions a e
TTT
¨gxF¨gxF¨gx,5
Ž. Ž. Ž. Ž.
Ž.
᭙¨P0 and ᭙xgS. Fo ¨s0, he inequali ies 5 become
TT
0F¨gxF¨gx,6
Ž. Ž. Ž.
TŽ.
᭙xgS. The e o e, 0 F¨gx o all xgS.
Since he gene alized Sla e cons ain quali ica ion is sa is ied, he e
T
Ž. Ž. Ž.
exis s a xgSsuch ha gx-0. Then o his x,¨gx-0. Bu , by 6 ,
ˆˆ ˆˆ
TŽ.
¨gxG0, and his is a con adic ion.
ˆ
The ollowing esul p o es ha ec o Kuhn᎐Tucke saddle poin s a e
Ž.
weakly e icien poin s o VOP wi hou equi ing addi ional condi ions,
as in he scala case.
Ž.
THEOREM 4.1. I x, ,¨is a ¨ec o Kuhn᎐Tucke saddle poin , hen x is
Ž.
weakly e icien o VOP .
Ž. Ž .
P oo . I /0, by 4 , x, sol es a Kuhn᎐Tucke saddle poin
Ž.
p oblem o he scala p og amming p oblem VP , and hus xis op imal
Ž.
o VP . As G0, om Theo em 3.1, xis a weakly e icien poin o
Ž.
VOP .
Unde a ce ain con exi y condi ion he ollowing esul shows he
e e se o he abo e heo em.
ŽŽ..
THEOREM 4.2. Le y x,g be a gene alized subcon¨ex-like unc ion
Ž.
on S,and le x be a weakly e icien solu ion o VOP . Then he e exis s
Ž. Ž . Ž .
,¨G0such ha x, ,¨is a ¨ec o F i z᎐John saddle poin o VOP .
Ž.
P oo . I xis a weakly e icien solu ion o VOP hen he sys em
xy x-0
Ž. Ž.
gxO0
Ž.
has no solu ion in S, he e o e he sys em
xy x-0
Ž. Ž.
gx-0
Ž.
has no solu ion in S.
NONDIFFERENTIABLE VECTOR DUALITY 469
pqm
Ž. Ž.
By Theo em 2.1, he e exis ,¨g⺢wi h ,¨G0 such ha
TTT
x q¨gxG x ᭙xgS.7
Ž. Ž. Ž. Ž.
In pa icula , we ha e ha
T
¨gxG0. 8
Ž. Ž.
Because xis easible we also ha e
T
¨gxF0. 9
Ž. Ž.
T
Ž. Ž. Ž . Ž.
By 8 and 9 we ha e ha ¨gxs0. Hence, by 7
TTTTTTT
x q¨gxG x q¨gxs x G x q¨gx
Ž. Ž. Ž. Ž. Ž. Ž. Ž.
᭙xgSand ᭙¨P0, and hus xis a ec o F i z᎐John saddle poin .
F om Lemma 4.1 and Theo em 4.2 we ha e he ollowing.
ŽŽ..
THEOREM 4.3. Le y x,g be a gene alized subcon¨ex-like unc ion
Ž.
and le x be a weakly e icien solu ion.Suppose ha he P oblem VOP
Ž.
sa is ies he gene alized Sla e cons ain quali ica ion.Then he e exis s ,¨
Ž. Ž.
G0such ha x, ,¨is a ¨ec o Kuhn᎐Tucke saddle poin o VOP .
F om Theo em 3.1 i is easy o show he ollowing esul o p ope ly
e icien solu ions.
Ž.
THEOREM 4.4. Le x, ,¨be a ¨ec o Kuhn᎐Tucke saddle poin wi h
Ž.
)0, hen x is a p ope ly e icien solu ion o VOP .
As be o e, unde gene alized con exi y condi ions, we p o e he e e se.
THEOREM 4.5. Suppose ha x is a p ope ly e icien solu ion o P oblem
Ž.Ž Ž..
VOP . I y x,g is gene alized subcon¨ex-like on S and he gene al-
ized Sla e quali ica ion cons ain is sa is ied, hen he e exis )0and ¨P0
Ž. Ž.
such ha x, ,¨is a ¨ec o Kuhn᎐Tucke saddle poin o VOP .
Ž.
P oo . I xis a p ope ly e icien solu ion o VOP , he sys em
xy x-0
Ž. Ž.
ii
xqM x y xyM x -0 o all j/i
Ž. Ž. Ž. Ž.
ijij
gx-0
Ž.
admi s no solu ion in S o each is1,..., p. Thus he e exis ig⺢p
im Žii
.pi
and ¨g⺢, wi h ,¨G0, and Ý s1, o each is1,..., p, such
js1j
ha
ii i
xqM xq¨gxG xqM x ᭙xgS.10
Ž. Ž. Ž. Ž. Ž. Ž .
ÝÝ
ijj ijj
j
/ij/i
OSUNA-GOMEZ,RUFIAN-LIZANA,AND RUIZ-CANALES
´´ ´
470
i
Ž. Ž.
F om 10 , xsxǬgxG0 o all is1,..., p. On he o he hand,
iŽ.
¨gxF0 o all is1,..., p. The e o e
i
¨gxs0. 11
Ž. Ž .
Ž. Ž.
Summing o e iyields 10 , and by 11 we ge
pp
ii
1qM xq¨gx
Ž. Ž.
ÝÝ Ý
jj
ž/
j
s1i/jis1
pp
ii
G1qM xq¨gx.
Ž. Ž.
ÝÝ Ý
jj
ž/
ž/
j
s1i/jis1
i
Assuming ha s1qMÝ )0 o each js1,..., pand ¨s
ji/jj
Ýp¨i, we ha e
is1
TTTT
x q¨gxG x q¨gx
Ž. Ž. Ž. Ž.
TT T
s x G x q¨gx,
Ž. Ž. Ž.
n
o all xgSand o all ¨g⺢wi h ¨P0.
5. LAGRANGE DUALITY FOR A
MULTIOBJECTIVE PROBLEM
We de ine he ec o - alued Lag ange unc ion wi h espec o P oblem
Ž.
VOP as
Lx,
␭
s xq
␭
Tgxe,x,
␭
gS=L
L,
Ž.Ž. Ž. Ž.
Ž.
p

mT
4
whe e es1,...,1 g⺢and L
Ls
␭
g⺢
␭
G0,
␭
es1.
i
Ž.
Le us deno e by W
W
␭
he se o weakly e icien solu ions o he
ollowing ec o ial p og amming p oblem:
Min Lx,
␭
Ž.
s. . xgS.
Ž.

Ž. TŽ. Ž.
4
Le ⍀
␭
s xq
␭
gxewi h xgW
W
␭
.
Ž.
Fo VOP , he co esponding Lag ange dual p oblem is he ollowing:
DVP Max ⍀
␭
Ž. Ž.
s. .
␭
gL
L.
Ž.Ž.
Now we p o e he classical duali y heo ems be ween VOP and DVP .