JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS: Vol. 110, No. 1, pp. 173–182, JULY 2001
Gauge Dis ances and Median Hype planes
1,2
F. P
LASTRIA
3
AND
E. C
ARRIZOSA
4
Communica ed by J. P. C ouzeix
Abs ac . A median hype plane in d-dimensional space minimizes he
weigh ed sum o he dis ances om a ini e se o poin s o i . When he
dis ances om hese poin s a e measu ed by possibly di e en gauges,
we p o e he exis ence o a median hype plane passing h ough a leas
one o he poin s. When all he gauges a e equal, some median hype -
plane will pass h ough a leas dA1 poin s, his numbe being inc eased
o dwhen he gauge is symme ic, i.e. he gauge is a no m.
Whe eas some o hese esul s ha e been ob ained p e iously by
di e en me hods, we show ha hey all de i e om a simple o mula
o he dis ance o a poin o a hype plane as measu ed by an a bi a y
gauge.
Key Wo ds. Gauges, dis ance o a hype plane, hype plane i ing.
1. Gauge Dis ance o a Hype plane
Le
γ
be a gauge on ⺢
d
wi h uni ball B; i.e., Bis a compac con ex
se con aining he o igin in i s in e io such ha
γ
(x)Gmin{ ¤0兩x∈ B};
see e.g. Re s. 1–2. Gi en a hype plane Hin ⺢
d
, he
γ
-dis ance o a poin
a∈⺢
d
o His de ined as
d
γ
(a,H)G
de
min{
γ
(xAa)兩x∈H}.
1
The esea ch o he second au ho was pa ially suppo ed by a DGES G an , Mad id, Spain.
2
The au ho s hank wo anonymous e e ees o many sugges ions which helped s eamline
his pape .
3
P o esso , Depa men o Managemen In o ma ics, V ije Uni e si ei , B ussels, Belgium.
4
P o esso , Facul ad de Ma ema
´ icas, Uni e sidad de Se illa, Se illa, Spain.
173
0022-3239兾01兾0700-0173$19.50兾02001 Plenum Publishing Co po a ion
JOTA: VOL. 110, NO. 1, JULY 2001174
Le
γ
°be he dual (o pola ) gauge o
γ
, gi en by
γ
°(û)G
de
max{〈û;y〉兩
γ
(y)⁄1},
which is well-de ined and also a gauge on ( he dual space o ) ⺢
d
; see e.g.
Re . 3. This de ini ion implies di ec ly he ollowing well-known gene alized
Cauchy–Schwa z inequali y (see e.g. Re . 3, p. 129):
〈û;y〉⁄
γ
°(û)
γ
(y), ∀û,y∈⺢
d
, (1)
in which o any ixed û≠0 equali y holds i yG
λ
z, o some
λ
¤0 and
some z∈∂
γ
°(û), whe e ∂
γ
°(û) deno es he (nonemp y) subdi e en ial o he
dual gauge a û; see e.g. Re . 2. No e ha equali y in (1) o û,y≠0 also
implies 〈û;y〉H0.
We will deno e he hype plane o equa ion 〈u;x〉G
β
,u≠0, by H(u,
β
),
and he se o all hype planes in ⺢
d
by H.
The ollowing heo em gi es a simple exp ession o he gauge dis ance
o a hype plane. The use o (1) enables us o simpli y he p oo gi en in
Re . 4 o a simila p oblem.
Theo em 1.1. Fo any gauge
γ
and any hype plane H(u,
β
), we ha e
d
γ
(a,H(u,
β
))G
冦
[
β
A〈u;a〉]兾
γ
°(u), when 〈u;a〉⁄
β
,
[〈u;a〉A
β
]兾
γ
°(−u), when 〈u;a〉H
β
.
Any
γ
-closes poin o H(u,
β
) oais ound as he unique in e sec ion poin
o H(u,
β
) wi h he line h ough aha ing as di ec ion any subg adien o
γ
°
a uwhen 〈u;a〉⁄
β
, and a Auwhen 〈u;a〉H
β
.
P oo . Le u≠0, and assume i s ha
〈u;a〉⁄
β
.
Fo any x∈H(u,
β
), a e subs i u ing ûby u(≠0) and yby xAain he
gene alized Cauchy–Schwa z inequali y (1), we ha e ha
γ
(xAa)¤〈u;xAa〉兾
γ
°(u)G[
β
A〈u;a〉]兾
γ
°(u),
whe e equali y happens a x∈H(u,
β
) i
xAais o he o m
λ
z, o some z∈∂
γ
°(u). (2)
Mo eo e , such an xexis s. Indeed, since u≠0, o any gi en z∈∂
γ
°(u)we
ha e
γ
°(z)G1,
JOTA: VOL. 110, NO. 1, JULY 2001 175
so ha by (1)
〈u;z〉G
γ
(z)
γ
°(u)G
γ
°(u)H0;
hus, he unc ion
λ
¤0>〈u;aC
λ
z〉A
β
G〈u;a〉A
β
C
λ
〈u;z〉
has a unique oo in [0, CS[. In o he wo ds, he e exis some
λ
¤0 and
x∈H(u,
β
) sa is ying (2).
The same easoning can be used o he case 〈u;a〉H
β
and will no be
epea ed he e. 䊐
When
γ
is symme ic [
γ
(−x)G
γ
(x), o all x∈⺢
d
], i.e.
γ
is a no m, hen
i s dual enjoys he same p ope y, and he ollowing simpli ied o mula
a ises di ec ly (compa e wi h Re . 5, which uses a p oo based on he Kuhn–
Tucke condi ions).
Co olla y 1.1. Fo any no m
ν
, we ha e
d
ν
(a,H(u,
β
))G兩
β
A〈u;a〉兩兾
ν
°(u).
No e also ha , o he pa icula case o he l
p
-dis ances, 1⁄p⁄CS,
his also p o es di ec ly he o mula (pains akingly de i ed by Re . 6)
d
l
p
(a,H(u,
β
))G兩
β
A〈u;a〉兩兾l
q
(u), 1兾pC1兾qG1,
by he well-known duali y
l°
p
Gl
q
, wi h 1兾pC1兾qG1,
including hei limi s
pG1, qG+So pG+S,qG1.
The p oo abo e also shows ha in ac his is a di ec consequence o he
Ho
¨lde inequali y
〈û;y〉⁄l
q
(û)l
p
(y).
2. Median Hype planes
Gi en a ini e se A⊂⺢
d
, oge he wi h co esponding posi i e weigh s
w
a
(a∈A) and gauges
γ
a
on ⺢
d
, any hype plane H* minimizing he weigh ed
sum o he gauge dis ances om Ais called a median hype plane; i.e.,
H*∈a g min{ (H)兩H∈H},
JOTA: VOL. 110, NO. 1, JULY 2001176
whe e
(H)G
∑
a∈A
w
a
d
γ
a
(a,H).
Since o any
λ
≠0, we ha e
H(
λ
u,
λβ
)GH(u,
β
),
he unc ion
H: ⺢
d
{0}B⺢
→
H:(u,
β
)>H(u,
β
)
is su jec i e, wi h he p ope y ha , o each one-dimensional linea space
Xin ⺢
d
B⺢,X≠{0}B⺢, he se H(X {0}) is educed o a single on; i.e., all
he nonze o poin s in Xa e mapped o he same hype plane.
I is a well-es ablished ac om opology ha no con inuous bijec i e
mapping may exis be ween a subse o ⺢
d
B⺢and he p ojec i e space H.
Se e al con inuous and bijec i e es ic ions o H may howe e be
conside ed.
Fo example, conside he es ic ion o H on he cylinde in ⺢
d
B⺢
wi h base some uni sphe e o ⺢
d
(i.e., S
dA1
B]0; +S[), whe e
S
dA1
G
de
{u∈⺢
d
兩兩兩u兩兩G1},
and whe e 兩兩·兩兩 deno es he s anda d Euclidean no m (o any o he no m).
This is an injec ion, he image o which con ains all Hexcep he hype -
planes h ough he o igin, i.e. o ype H(u, 0). No e ha allowing also
β
G
0 leads o loss o injec i i y, since
H(u,0)GH(−u, 0).
Res ic ion o H o some non e ical hype plane in ⺢
d
B⺢(which we
will a he call a supe plane, o dis inguish i om hype planes in ⺢
d
) no
passing h ough he o igin, and excep ing i s single poin on he
β
-axis,
yields ano he con inuous injec ion o H: conside he supe plane S(c,
λ
,
µ
),
µ
≠0,
λ
≠0, wi h equa ion
〈c;u〉C
λβ
G
µ
,
om which he poin (0,
µ
兾
λ
) is dele ed; hen, he only hype planes no
ep esen ed will be hose o o m H(û,
µ
兾
λ
), whe e û≠0 is any ec o o ho-
gonal o c.
The se o all hype planes in ⺢
d
no mal o some ixed u≠0 is deno ed
by
H
u
G{H(u,
β
)兩
β
∈⺢}.
JOTA: VOL. 110, NO. 1, JULY 2001 177
Lemma 2.1. Fo any ixed u∈⺢
d
{0}, he e exis s a hype plane H*
u
minimizing on H
u
which passes h ough some poin a∈A.
P oo . Fo ixed u≠0, Theo em 1.1 shows ha , o any a∈A, he
dis ance
γ
a
(a,H(u,
β
)) is a con ex piecewise linea unc ion o
β
: i consis s
o wo unbounded pieces wi h b eakpoin
β
a
u
G〈u;a〉, linea ly dec easing
wi h slope A1兾
γ
°(−u)on]−S;
β
a
u
] and linea ly inc easing wi h slope 1兾
γ
°(u)
on [
β
a
u
;CS[. No e also ha i is coe ci e, i.e. asymp o ically equal o +S
in any di ec ion.
I ollows ha , as he posi i ely weigh ed sum o e all a∈Ao such
dis ance unc ions, (H(u,
β
)) is con ex, coe ci e, and piecewise linea , wi h
b eakpoin s
β
a
u
,a∈A, and he e o e eaches i s minimum a leas a one o
hese b eakpoin s, say
β
a
0
u
wi h a
0
∈A. Bu
〈u;a
0
〉G
β
a
0
u
means ha he co esponding minimizing hype plane,
H*
u
GH(u,
β
a
0
u
),
passes h ough a
0
.䊐
Le us in oduce he no a ions A
#
(u,
β
) o any #∈{F,⁄,H,¤}by
A
#
(u,
β
)G{a∈A兩〈u;a〉
#β
}.
In ac , he p oblem o minimizing on H
u
may be seen as a one-
dimensional asymme ic dis ance Webe p oblem (Re . 7),
min
β
∈⺢
∑
a∈A
H
(u,
β
)
[w
a
兾
γ
°
a
(−u)]兩〈u;a〉A
β
兩C
∑
a∈A
F
(u,
β
)
[w
a
兾
γ
°
a
(u)]兩〈u;a〉A
β
兩, (3)
o which a ixed-poin op imali y p ope y was de i ed. This in e p e a ion
o he p oblem also enables us o s a e an impo an p ope y o median
hype planes.
De ini ion 2.1. The hype plane H(u,
β
) hal es Ai
∑
a∈A
¤
(u,
β
)
w
a
兾
γ
°
a
(−u)¤
∑
a∈A
F
(u,
β
)
w
a
兾
γ
°
a
(u), (4)
∑
a∈A
H
(u,
β
)
w
a
兾
γ
°
a
(−u)⁄
∑
a∈A
⁄
(u,
β
)
w
a
兾
γ
°
a
(u). (5)
The ollowing esul gene alizes analogous esul s in Re . 8, and he
i s pa p o es a conjec u e made he e on p. 182.

JOTA: VOL. 110, NO. 1, JULY 2001178
Theo em 2.1. The e exis s a median hype plane which passes h ough
some poin a∈A. Mo eo e , any median hype plane hal es A.
P oo . Lemma 2.1 shows ha , o e e y ixed u≠0, he minimum o
(H) is eached on H
u
a some hype plane H(u,
β
) wi h
β
∈[
β
l
u
,
β
h
u
], whe e
β
l
u
Gmin{
β
a
u
兩a∈A},
β
h
u
Gmax{
β
a
u
兩a∈A}.
The alues
β
l
u
and
β
h
u
a e clea ly con inuous in u, so hey each hei ex eme
alues
β
l
Gmin{
β
l
u
兩u∈S
dA1
},
β
h
Gmax{
β
h
u
兩u∈S
dA1
}
on he (compac ) uni sphe e S
dA1
.
I ollows ha inding he minimum o on His equi alen o inding
he minimum o (H(u,
β
)) on S
dA1
B[
β
l
,
β
h
], which is compac . Since is
con inuous, his minimum will be eached, es ablishing he exis ence o a
median hype plane. Then, he exis ence o a median hype plane which mee s
A ollows immedia ely om Lemma 2.1.
Finally, i H(u
0
,
β
0
)de ines a median hype plane, hen
β
0
mus sol e
(3) o uGu
0
. The le and igh di ec ional de i a i es o his con ex unc-
ion o
β
a e espec i ely
∑
a∈A
F
(u
0
,
β
0
)
w
a
兾
γ
°
a
(u
0
)A
∑
a∈A
¤
(u
0
,
β
0
)
w
a
兾
γ
°
a
(−u
0
),
∑
a∈A
⁄
(u
0
,
β
0
)
w
a
兾
γ
°
a
(u
0
)A
∑
a∈A
H
(u
0
,
β
0
)
w
a
兾
γ
°
a
(−u
0
).
A necessa y and su icien condi ion o a minimum is ha he i s should
be nonposi i e and he second nonnega i e; in o he wo ds, (u
0
,
β
0
) should
sa is y (4)–(5). 䊐
Obse e ha , when he e exis s a hype plane in ⺢
d
con aining A, hen
his is clea ly a median hype plane wi h objec i e alue 0. The e o e, we
u he assume ha his is no he case; i.e.
dim(A)Gd,
meaning ha Acon ains a leas dC1a inely independen poin s.
When all gauges a e symme ic and equal (i.e., when all dis ances a e
measu ed by a same no m), we may hen de i e a much s onge esul
which was ob ained al eady by o he means in Re s. 8–9.
In he sequel, we will w i e ′ o °H, i.e.,
′(u,
β
)G
de
(H(u,
β
)),
JOTA: VOL. 110, NO. 1, JULY 2001 179
and conside he median hype plane de e mina ion as he p oblem o mini-
mizing ′on ⺢
d
B⺢.
Theo em 2.2. Fo dis ances measu ed by a ixed no m, i.e.
γ
a
G
ν
,
a∈A, wi h
ν
(−x)G
ν
(x) o all x∈⺢
d
, when dim(A)Gd, some median hype -
plane passes h ough da inely independen poin s o A.
P oo . Le H(u
0
,
β
0
) be a median hype plane, he exis ence o which
ollows om Theo em 2.1. Wi hou loss o gene ali y, we may assume ha
ν
°(u
0
)G1. De ine T⊂⺢
d
B⺢by
(u,
β
)∈Ti
冦
〈u;a〉¤
β
,∀a∈A
¤
(u
0
,
β
0
),
〈u;a〉⁄
β
,∀a∈A
F
(u
0
,
β
0
),
and he ollowing linea unc ion:
g:⺢
d
B⺢
→
⺢
:(u,
β
)>
∑
a∈A
¤
(u
0
,
β
0
)
w
a
(〈u;a〉A
β
)C
∑
a∈A
F
(u
0
,
β
0
)
w
a
(
β
A〈u;a〉).
Conside he se Pin ⺢
d
B⺢de ined as
PG{(u,
β
)∈T兩g(u,
β
)Gg(u
0
,
β
0
)}.
Pis a closed polyhed al se in ⺢
d
B⺢:i isde ined by linea inequali ies and
one linea equali y in dC1 a iables.
Pis also bounded. Indeed, i unbounded, he e would exis some
(u,
β
)≠(0, 0) such ha
(
λ
uCu
0
,
λβ
C
β
0
)∈P, o all
λ
¤0.
This means ha we would ha e
〈u;a〉A
β
¤0, ∀a∈A
¤
(u
0
,
β
0
),
〈u;a〉A
β
⁄0, ∀a∈A
F
(u
0
,
β
0
),
g(u,
β
)G0,
which by he de ini ion o gimplies ha
〈u;a〉A
β
G0, o all a∈A;
in o he wo ds, A⊂H(u,
β
), which con adic s he assump ion dim(A)Gd.
The e o e, Pis a poly ope o (a mos ) dimension d. I con ains he op imal
solu ion (u
0
,
β
0
), so any solu ion op imizing ′on Pis also a global op imal
JOTA: VOL. 110, NO. 1, JULY 2001180
solu ion. Mo eo e ,
′(u,
β
)Gg(u,
β
)兾
ν
°(u)Gg(u
0
,
β
0
)兾
ν
°(u), ∀(u,
β
)∈P.
Hence, minimizing ′on P u ns ou o be equi alen o maximizing he
unc ion (u,
β
)>
ν
°(u)onP. Since his unc ion is con ex, i a ains i s
maximum on he poly ope Pa some ex eme poin (u
1
,
β
1
). Since (u
1
,
β
1
)is
ob ained as he poin common o dhype planes bounding linea ly indepen-
den hal spaces de ining P, i co esponds o he hype plane H(u
1
,
β
1
) pass-
ing h ough da inely independen poin s o A.䊐
Tha he p e ious heo em does no hold o an asymme ic gauge is
shown by he coun e example in Re . 8. Howe e , we may show he ollow-
ing only sligh ly weake esul .
Theo em 2.3. Fo dis ances measu ed by a ixed gauge (i.e.
γ
a
G
γ
,a∈
A), when dim(A)Gd, some median hype plane passes h ough dA1a inely
independen poin s o A.
P oo . Le H(u
0
,
β
0
) be a median hype plane, and de ine he unc ions
0
and gon ⺢
d
B⺢,
0
(u,
β
)G1
γ
°(u)
冤
∑
a∈A
¤
(u
0
,
β
0
)
w
a
(〈u;a〉A
β
)
冥
C1
γ
°(−u)
冤
∑
a∈A
F
(u
0
,
β
0
)
w
a
(
β
A〈u;a〉)
冥
G
de
¤
(u,
β
)C
F
(u,
β
),
g(u,
β
)G1
γ
°(u
0
)
冤
∑
a∈A
¤
(u
0
,
β
0
)
w
a
(〈u;a〉A
β
)
冥
C1
γ
°(−u
0
)
冤
∑
a∈A
F
(u
0
,
β
0
)
w
a
(
β
A〈u;a〉)
冥
.
Obse e ha gis linea ,
0
is nonlinea , while
g(u
0
,
β
0
)G
0
(u
0
,
β
0
)G ′(u
0
,
β
0
).
Le he subse P⊂⺢
d
B⺢be de ined by he cons ain s
〈u;a〉¤
β
,∀a∈A
¤
(u
0
,
β
0
),
〈u;a〉⁄
β
,∀a∈A
F
(u
0
,
β
0
),
g(u,
β
)G ′(u
0
,
β
0
).
JOTA: VOL. 110, NO. 1, JULY 2001 181
I is easy o see by simila a gumen s as hose used in Theo em 2.2 ha P
is a poly ope o (a mos ) dimension d. Since o all (u,
β
)∈P, we ha e
A
#
(u,
β
)GA
#
(u
0
,
β
0
),
#
∈{¤,F},
i ollows ha on Pwe ha e
0
G ′. Bu Pcon ains he op imal solu ion
(u
0
,
β
0
)o ′on ⺢
d
B⺢, so any minimum o
0
on Pwill also be a global
op imum o ′and yield a median hype plane.
Since
0
G
¤
C
F
,
any solu ion minimizing
0
on Pis an e icien solu ion o he biobjec i e
p oblem o minimizing bo h
¤
and
F
on P.
Each o he unc ions
¤
and
F
is quasiconca e on P(see e.g. Re . 10),
since hei uppe le el se s a le el
α
a e gi en espec i ely by inequali ies o
he o m
αγ
°(u)A
∑
a∈A
¤
(u
0
,
β
0
)
w
a
(〈u;a〉A
β
)⁄0,
αγ
°(−u)A
∑
a∈A
F
(u
0
,
β
0
)
w
a
(
β
A〈u;a〉)⁄0,
which, by he con exi y o
γ
°,de ine con ex se s in ⺢
d
B⺢.
I was shown in Re . 11 ha , in his case, he se o edges (one-dimen-
sional aces) o Pcons i u es a domina o o P; i.e., o any (u,
β
)∈P, he e
exis s some (u′,
β
′) on some edge o Pwi h
¤
(u′,
β
′)⁄
¤
(u,
β
),
F
(u′,
β
′)⁄
F
(u,
β
),
and hence
0
(u′,
β
′)⁄
0
(u,
β
).
And any edge o Pis he in e sec ion o dA1 hype planes bounding linea ly
independen hal spaces de ining P. The e o e, he e exis s some minimum
o
0
on P(and hence a global minimum o ′) sa is ying as equali y dA1
linea ly independen inequali ies among hose de ining P. Bu his co e-
sponds o a hype plane Hpassing h ough dA1a inely independen poin s
o A.䊐
Re e ences
1. D
URIER
, R., and M
ICHELOT
,C.,Geome ical P ope ies o he Fe ma –Webe
P oblem, Eu opean Jou nal o Ope a ional Resea ch, Vol. 20, pp. 332–343,
1985.