A Sho No e on Non-Symme ic Semideni e
P og amming

Fa os Xha a
y
Abs ac
We show ha op imizing o e non-symme ic ma ices is no p olyno-
mial ime sol able, unless P=NP. This is in con as o he symme ic
case o which se e al p olynomial ime algo i hms a e known.
1 In o duc ion
The
classical
Semideni e P og amming (SDP) is he p oblem o op imizing a
linea unc ion o a
symme ic
ma ix sub jec o linea cons ain s and he condi-
ion ha he ma ix o a iables b e p osi i e semideni e. SDP has p o ed p ow-
e ul o cas combina o ial p oblems and e y ecen ly, i has b een used o ob-
ain s iking app oxima ion algo i hms o se e al p oblems (Max CUT [GW95],
Max 2SAT [GW95, FG95], COLORING [KMS94] and BETWEENESS [CS95].)
In all o hem, he basic s ep is sol ing (in p olynomial ime) a semideni e elax-
a ion o he p oblem a hand and hen de i e a easible solu ion o he p oblem
whose measu e is wi hin a ce ain b ound o he op imum. In an a emp o
nd a semideni e elaxa ion o he p oblem o Minimum Linea A angemen
(MinLA) on g aphs we came up wi h a semideni e p og am bu i u ned ou
o b e
non-symme ic
. This mo i a ed ou in e es in s udying whe he such
kind o semideni e p og ams wi hou he condi ion o he ma ix o a iables
o b e symme ic can b e sol ed in p olynomial ime.
We s a wi h he deni ion o a p osi i e semideni e ma ix and some ob-
se a ions. In dening he semideni eness o a squa e eal ma ix
A
he e is no
condi ion a all ab ou he symme y o he ma ix. Howe e , he e is a big di -
e ence b e ween he case when he ma ix is symme ic and he non-symme ic
one,  s , in cha ac e izing such ma ices, and secondly wi h esp ec o all he
basic opics o ma ix heo y (decomp osi ions, sys ems o linea equa ions, e c.)
and op imiza ion heo y.
Deni ion 1
Le
A
be a symme ic
n

n
ma ix. The ma ix
A
is posi i e
semideni e (psd, o sho ) i o al l
x
2
R
n
,
x
T
A
x

0
. The ma ix
A
is
posi i e deni e i o al l
x
2
R
n
?
0
g
,
x
T
A
x
>
0
.

This esea ch was supp o ed by he ESPRIT Long Te m Resea ch P o jec No. 20244 -
ALCOM IT.
y
Depa amen de Llengua ges i Sis emes In o ma ics, Modul C6 - Campus No d, Jo di
Gi ona Salgado, 1-3, 08034-Ba celona, E-mail:
a [email protected]
1
Fo a gi en
n

n
ma ix
A
, we will deno e by 
1
;

2
;:::;

n
he p incipal
mino s o
A
, whe e 
k
is he de e minan o he upp e le -hand co ne
k

k
subma ix o
A
, and by

1
; 
2
;:::;
n
i s eigen alues.
Fo eal symme ic ma ices he e a e se e al equi alen c i e ia o es he
semideni eness p op e y (see, e.g., [PSU88, pages 13{36]), gi en b elow.
P op osi ion 1
Le
A
be a eal
n

n
symme ic ma ix. The ol lowing s a e-
men s a e equi alen :
(a)
Ma ix
A
is posi i e semideni e;
(b)
Al l he eigen alues o he ma ix
A
a e non-nega i e numbe s;
(c)
The e exis s a ma ix
L
such ha
A
=
LL
T
;
(d)
The p incipal mino s o he ma ix
A
a e

1
>
0
;

2
>
0
; : : : ;

n
?
1
>
0
and

n
= 0
.
We no ice ha when a (symme ic) ma ix is psd hen all i s p incipal mi-
no s a e non-nega i e, howe e he e e se no necessa ily is ue. I is easy
o see ha , when he ma ix
A
is no symme ic he equi alen p op e ies o
P op osi ion 1 do es no hold anymo e. Indeed, when he ma ix is no sym-
me ic, i s eigen alues may well b e complex numb e s, he p incipal mino s may
sa is y condi ion (
d
) bu his do es no imply p osi i e semideni eness o he
ma ix, e c. Fo a a o o his, le us conside he ma ices:
A
=

 m
?
m 

and
B
=

0
:
5
?
2
2
?
8

o which we ha e:

Ma ix
A
is p osi i e deni e (hence psd) howe e i s eigen alues a e

1
=

+
I

m
,

2
=

?
I

m
(i.e., no p osi i e eal numb e s). Thus, (
a
)
)
(
b
)
do esn' hold.

Clea ly, (
a
)
,
(
c
) canno hold o non-symme ic ma ices since o any
ma ix
L
, he ma ix
LL
T
is symme ic.

Ma ix
B
has i s p incipal mino s 
1
= 0
:
5, 
2
= 0, howe e he ma ix
is no psd ( he e a e ec o s
x
2
R
2
such ha
x
T
A
x
<
0, e.g.
x
= (1
;
1)),
hence (
d
)
)
(
a
) do es no hold. Howe e , i 's wo h men ioning he e ha
(
a
)
)
(
d
) holds indep enden ly o whe he he ma ix is symme ic o no
(c . [GVL83, page 140]).
F om his die ence b e ween he symme ic and non-symme ic case can b e
explained somehow why he symme ic case is he mos s udied and use ul
one. Indeed, symme ic psd ma ices play an imp o an ole in he heo y
o symme ic linea sys ems compa ed o he non-symme ic ones (see, e.g.,
[GVL83, Chap e 4]). Mo e ema kably, he symme ic psd ma ices a e c ucial
in he heo y o con ex op imiza ion (see, e.g., [GLS88]) since he space o such
ma ices has he nice p op e y o b eing con ex.
Ou in e es he e is o see how do es his die ence impac s in sol ing
e -
cien ly
op imiza ion p oblems o e semideni e ma ices wi h o wi hou he
2
condi ion o b eing symme ic. Le
C
,
A
(1)
; A
(2)
;:::;A
(
m
)
b e
n

n
ma ices and
b
an
m
- ec o . Le us conside he ollowing op imiza ion p oblem:
max
P
n
i
=1
P
n
j
=1
C
ij
X
ij
s. .
P
i;j
A
(
k
)
ij
X
ij
=
b
k
;
1

k

m
X
psd
(SDP)
ha means, in wo ds, op imize (maximize, minimize) a linea unc ion on
X
sub jec o linea cons ain s on
X
and he cons ain on
X
o b e psd. Now, i
we add ess he ques ion o whe he his p oblem is sol able in p olynomial ime,
he answe dep ends hea ily on
o e which ma ices a e we op imizing
. Sp eci-
cally, when he ma ix
X
is symme ic (i.e., he condi ions o b e op imized o e
a e hose (
b
)-(
d
)) he ab o e p oblem is he s anda d Semideni e P og am-
ming (he ea e e e ed o as Symme ic SDP). Symme ic SDP is well-s udied
and we al eady know ha i is p oly ime sol able ei he h ough he Ellipsoid
Me ho d [GLS81] o In e io -Poin Me ho d [Ka 84, Ali95, HRVO93, VB96]).
In e es ingly, as we men ioned p e iously, he e a e se e al combina o ial op i-
miza ion p oblems (e.g., Max CUT, COLORING, BETWEENESS) o which,
o any ins ance o he p oblem, he e is asso cia ed a Symme ic SDP o e a
ma ix
X
ha sa ises he equi alen condi ions
(a)
-
(d)
.
2 Main Resul
In wha ollows we show ha he op imiza ion p oblem de i ed om (SDP)
wi hou he condi ion o he ma ix
X
o b e symme ic, called Non-Symme ic
Semideni e P og amming (Non-Symme ic SDP), is ha d o sol e unde a ea-
sonable complexi y assump ion.
Theo em 1
The Non-Symme ic Semideni e P og amming is no poly ime
sol able, unless P=NP.
P oo :
Le us conside an ins ance
C
o Max SAT p oblem consis ing o
m
clauses
C
1
;:::;C
m
o e a iables
x
1
; x
2
;:::;x
n
. We can w i e he ollowing
in ege p og am o i
1
:
max
P
C
j
2C
z
j
s. .
P
i
2
I
+
j
y
i
+
P
i
2
I
?
j
(1
?
y
i
)

z
j
;
8
C
j
2 C
y
i
2
0
;
1
g
;
1

i

n
(1)
z
j
2
0
;
1
g
;
8
C
j
2 C
(2)
(SAT)
whe e
I
+
j
( esp.
I
?
j
) is he se o a iables app ea ing p osi i ely ( esp. nega i ely)
in clause
C
j
and he in ended meaning o a iables is as ollows:
y
i
= 1 i
a iable
x
i
is se ue and 0 o he wise;
z
j
= 1 i clause
C
j
is sa ised and 0
1
This is a olklo e o mula ion o he p oblem.
3
o he wise. No ice ha (SAT) compu es an exac solu ion o a gi en ins ance o
Max SAT.
Now, we will w i e (SAT) equi alen ly as Non-Symme ic SDP. As we men-
ioned ab o e, i a ma ix is p osi i e semideni e hen all i s p incipal mino s a e
non-nega i e indep enden ly whe he he ma ix is symme ic o no . The e o e,
we can exp ess condi ions (1), (2), esp ec i ely, as
y
i

1 and
Y
i
=

y
i
1
y
i
y
j

b e psd
;
(3)
z
j

1 and
Z
j
=

z
j
1
z
j
z
j

b e psd
:
(4)
i.e., hey a e exp essed as a linea es ic ion oge he wi h a condi ion o a
ma ix o b e psd. I is s aigh o wa d o see ha (3) ( esp. (4)) exp ess (1)
( esp. (2)). Indeed,
Y
i
psd would imply ha
y
i

0 and ha
y
i
(
y
i
?
1)

0
and he e o e in combina ion wi h
y
i

1 gi es
y
i
= 0 o
y
i
= 1. Fu he he
condi ions
Y
i
psd, o all 1

i

n
, can b e w i en in a unique condi ion
2
by
le ing
Y
b e he blo ck-diagonal ma ix whose
i
h blo ck is he ma ix
Y
i
, and
hen condi ioning
Y
b e psd. Simila ly, he condi ions on
Z
j
a e summa ized
in ha o
Z
b eing psd. Finally, we see (SAT) as a Non-Symme ic SDP on
ma ices
Y ; Z
. The heo em hus ollows since i we could sol e in p olynomial
ime ou Non-Symme ic SDP, i would imply ha we can nd in p olynomial
ime he op imal solu ion o (SAT) which is known o b e NP-comple e.
2
Discussion
I is well-known om Linea Algeb a ha symme ic ma ices ha e likeable
p op e ies as opp osed o non-symme ic ma ices. Ou esul shows ha such
die ence is also p esen when op imiza ion o e ma ices is conside ed. In
iew o he ecen app oxima ion esul s de i ed om symme ic semideni e
p og amming, ou esul may explain somehow why his echnique esis s he
ex ension o o he combina o ial op imiza ion p oblems.
Acknowlegmen
Many hanks o Josep Daz and Ma ia Se na o se e al help ul commen s. I'm
g a e ul o Madhu Sudan o discussions on SDP om which we came up wi h
he ha dness esul . Madhu also made se e al commen s on a d a o his pap e
which signican ly imp o ed i .
Re e ences
[Ali95] F. Alizadeh. In e io -Poin Me ho ds in Semideni e P og amming
wi h Applica ions o Combina o ial Op imiza ion.
SIAM Jou nal on
Op imiza ion
, 5:13{51, 1995.
2
Ac ually his is no needed since one o mo e condi ions on ma ices o b e psd a e p e -
mi ed in a semideni e p og am.
4
[CS95] B. Cho and M. Sudan. A Geome ic App oach o Be weeness. In
Thi d Eu opean Symposium on Algo i hms
, Lec u e No es in Com-
pu e Science, pages 227{237. Sp inge -Ve lag, 1995.
[FG95] U. Feige and M. Go emans. App oxima ing he Value o Two P o e
P o o Sys ems, wi h Applica ions o Max DICUT and Max 2SAT.
In
P oceedings o 3 d Is ael Symposium on Theo y and Compu ing
Sys ems
, 1995.
[GLS81] M. G o schel, L. Lo asz, and A. Sch ij e . The Ellipsoid Me ho d and
i s Consequences in Combina o ial Op imiza ion.
Combina o ica
,
1:169{197, 1981.
[GLS88] M. G o schel, L. Lo asz, and A. Sch ij e .
Geome ic Algo i hms
and Combina o ial Op imiza ion
. Sp inge Ve lag, 1988.
[GVL83] G.H. Golub and C.F. Van Loan.
Ma ix Compu a ions.
John Hop-
kins Uni e si y P ess, 1983.
[GW95] M.X. Go emans and D.P. Williamson. Imp o ed App oxima ion
Algo i hms o Maximum Cu and Sa isabili y P oblems Using
Semideni e P og amming.
Jou nal o he ACM
, 42(6):1115{1145,
1995.
[HRVO93] C. Helmb e g, F. Rendl, R.J. Vande b ei, and M.L. O e on. An
In e io -Poin Me ho d o Semideni e P og amming. Technical Re-
p o CORR 93-20, SOR 93-15, Dep . o Combina o ics and Op i-
miza ion, Wa e lo o, On ., 1993.
[Ka 84] A. Ka ma ka . A New Polynomial Time Algo i hm in Linea P o-
g amming.
P oc. 16 h Annual ACM Symposium on Theo y o Com-
pu ing
, pages 302{311, 1984.
[KMS94] D. Ka ge , R. Mo wani, and M. Sudan. App oxima e G aph Colo -
ing ia Semideni e P og amming. In
35 h Annual Symposium on
Founda ions o Compu e Science
, 1994.
[PSU88] A.L. Pe esini, F.E. Sulli an, and J.J. Uhl, J .
The Ma hema ics o
Nonlinea P og amming.
eds. Ewing, J.H. Sp inge Ve lag, 1988.
[VB96] L. Vandenb e ghe and S. Boyd. Semideni e P og amming.
SIAM
Jou nal o Compu ing
, 38:49{95, 1996.
5