A Short note on non-symmetric semidefinite programming

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