scieee AI-readable full text Open interactive document viewer

A Short note on non-symmetric semidefinite programming

Xhafa Xhafa, Fatos

Abstract

We show that optimizing over non-symmetrical matrices is not polynomial solvable unless P=NP. This is in contrast to the symmetric case for which several polynomials time algorithms are known.

Full text

A Short Note on Non-Symmetric Semidenite Programming  Fatos Xhafa y Abstract We show that optimizing over non-symmetric matrices is not p olynomial time solvable, unless P=NP. This is in contrast to the symmetric case for which several p olynomial time algorithms are known. 1 Intro duction The classical Semidenite Programming (SDP) is the problem of optimizing a linear function of a symmetric matrix sub ject to linear constraints and the condition that the matrix of variables b e p ositive semidenite. SDP has proved p owerful to cast combinatorial problems and very recently, it has b een used to obtain striking approximation algorithms for several problems (Max CUT [GW95], Max 2SAT [GW95, FG95], COLORING [KMS94] and BETWEENESS [CS95].) In all of them, the basic step is solving (in p olynomial time) a semidenite relaxation for the problem at hand and then derive a feasible solution to the problem whose measure is within a certain b ound of the optimum. In an attempt to nd a semidenite relaxation for the problem of Minimum Linear Arrangement (MinLA) on graphs we came up with a semidenite program but it turned out to b e non-symmetric . This motivated our interest in studying whether such kind of semidenite programs without the condition for the matrix of variables to b e symmetric can b e solved in p olynomial time. We start with the denition of a p ositive semidenite matrix and some observations. In dening the semideniteness for a square real matrix A there is no condition at all ab out the symmetry of the matrix. However, there is a big difference b etween the case when the matrix is symmetric and the non-symmetric one, rst, in characterizing such matrices, and secondly with resp ect to all the basic topics of matrix theory (decomp ositions, systems of linear equations, etc.) and optimization theory. Denition 1 Let A be a symmetric n  n matrix. The matrix A is positive semidenite (psd, for short) i for al l x 2 R n , x T A x  0 . The matrix A is positive denite i for al l x 2 R n ? f 0 g , x T A x > 0 .  This research was supp orted by the ESPRIT Long Term Research Pro ject No. 20244 - ALCOM IT. y Departament de Llenguatges i Sistemes Informatics, Modul C6 - Campus Nord, Jordi Girona Salgado, 1-3, 08034-Barcelona, E-mail: [email protected] 1 For a given n  n matrix A , we will denote by  1 ;  2 ;:::;  n the principal minors of A , where  k is the determinant of the upp er left-hand corner k  k submatrix of A , and by  1 ;  2 ;:::; n its eigenvalues. For real symmetric matrices there are several equivalent criteria to test the semideniteness prop erty (see, e.g., [PSU88, pages 13{36]), given b elow. Prop osition 1 Let A be a real n  n symmetric matrix. The fol lowing statements are equivalent: (a) Matrix A is positive semidenite; (b) Al l the eigenvalues of the matrix A are non-negative numbers; (c) There exists a matrix L such that A = LL T ; (d) The principal minors of the matrix A are  1 > 0 ;  2 > 0 ; : : : ;  n ? 1 > 0 and  n = 0 . We notice that when a (symmetric) matrix is psd then all its principal minors are non-negative, however the reverse not necessarily is true. It is easy to see that, when the matrix A is not symmetric the equivalent prop erties of Prop osition 1 do es not hold anymore. Indeed, when the matrix is not symmetric, its eigenvalues may well b e complex numb ers, the principal minors may satisfy condition ( d ) but this do es not imply p ositive semideniteness of the matrix, etc. For a avor of this, let us consider the matrices: A =   m ? m   and B =  0 : 5 ? 2 2 ? 8  for which we have:  Matrix A is p ositive denite (hence psd) however its eigenvalues are  1 =  + I  m ,  2 =  ? I  m (i.e., not p ositive real numb ers). Thus, ( a ) ) ( b ) do esn't hold.  Clearly, ( a ) , ( c ) cannot hold for non-symmetric matrices since for any matrix L , the matrix LL T is symmetric.  Matrix B has its principal minors  1 = 0 : 5,  2 = 0, however the matrix is not psd (there are vectors x 2 R 2 such that x T A x < 0, e.g. x = (1 ; 1)), hence ( d ) ) ( a ) do es not hold. However, it's worth mentioning here that ( a ) ) ( d ) holds indep endently of whether the matrix is symmetric or not (cf. [GVL83, page 140]). From this dierence b etween the symmetric and non-symmetric case can b e explained somehow why the symmetric case is the most studied and useful one. Indeed, symmetric psd matrices play an imp ortant role in the theory of symmetric linear systems compared to the non-symmetric ones (see, e.g., [GVL83, Chapter 4]). More remarkably, the symmetric psd matrices are crucial in the theory of convex optimization (see, e.g., [GLS88]) since the space of such matrices has the nice prop erty of b eing convex. Our interest here is to see how do es this dierence impacts in solving ef- ciently optimization problems over semidenite matrices with or without the 2 condition of b eing symmetric. Let C , A (1) ; A (2) ;:::;A ( m ) b e n  n matrices and b an m -vector. Let us consider the following optimization problem: max P n i =1 P n j =1 C ij X ij s.t. P i;j A ( k ) ij X ij = b k ; 1  k  m X psd (SDP) that means, in words, optimize (maximize, minimize) a linear function on X sub ject to linear constraints on X and the constraint on X to b e psd. Now, if we address the question of whether this problem is solvable in p olynomial time, the answer dep ends heavily on over which matrices are we optimizing . Sp eci- cally, when the matrix X is symmetric (i.e., the conditions to b e optimized over are those ( b )-( d )) the ab ove problem is the standard Semidenite Programming (hereafter referred to as Symmetric SDP). Symmetric SDP is well-studied and we already know that it is p olytime solvable either through the Ellipsoid Metho d [GLS81] or Interior-Point Metho d [Kar84, Ali95, HRVO93, VB96]). Interestingly, as we mentioned previously, there are several combinatorial optimization problems (e.g., Max CUT, COLORING, BETWEENESS) for which, to any instance of the problem, there is asso ciated a Symmetric SDP over a matrix X that satises the equivalent conditions (a) - (d) . 2 Main Result In what follows we show that the optimization problem derived from (SDP) without the condition for the matrix X to b e symmetric, called Non-Symmetric Semidenite Programming (Non-Symmetric SDP), is hard to solve under a reasonable complexity assumption. Theorem 1 The Non-Symmetric Semidenite Programming is not polytime solvable, unless P=NP. Proof: Let us consider an instance C of Max SAT problem consisting of m clauses C 1 ;:::;C m over variables x 1 ; x 2 ;:::;x n . We can write the following integer program for it 1 : max P C j 2C z j s.t. 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 f 0 ; 1 g ; 1  i  n (1) z j 2 f 0 ; 1 g ; 8 C j 2 C (2) (SAT) where I + j (resp. I ? j ) is the set of variables app earing p ositively (resp. negatively) in clause C j and the intended meaning of variables is as follows: y i = 1 i variable x i is set true and 0 otherwise; z j = 1 i clause C j is satised and 0 1 This is a folklore formulation for the problem. 3 otherwise. Notice that (SAT) computes an exact solution to a given instance of Max SAT. Now, we will write (SAT) equivalently as Non-Symmetric SDP. As we mentioned ab ove, if a matrix is p ositive semidenite then all its principal minors are non-negative indep endently whether the matrix is symmetric or not. Therefore, we can express conditions (1), (2), resp ectively, 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., they are expressed as a linear restriction together with a condition for a matrix to b e psd. It is straightforward to see that (3) (resp. (4)) express (1) (resp. (2)). Indeed, Y i psd would imply that y i  0 and that y i ( y i ? 1)  0 and therefore in combination with y i  1 gives y i = 0 or y i = 1. Further the conditions Y i psd, for all 1  i  n , can b e written in a unique condition 2 by letting Y b e the blo ck-diagonal matrix whose i th blo ck is the matrix Y i , and then conditioning Y b e psd. Similarly, the conditions on Z j are summarized in that of Z b eing psd. Finally, we see (SAT) as a Non-Symmetric SDP on matrices Y ; Z . The theorem thus follows since if we could solve in p olynomial time our Non-Symmetric SDP, it would imply that we can nd in p olynomial time the optimal solution to (SAT) which is known to b e NP-complete. 2 Discussion It is well-known from Linear Algebra that symmetric matrices have likeable prop erties as opp osed to non-symmetric matrices. Our result shows that such dierence is also present when optimization over matrices is considered. In view of the recent approximation results derived from symmetric semidenite programming, our result may explain somehow why this technique resists the extension to other combinatorial optimization problems. Acknowlegment Many thanks to Josep Daz and Maria Serna for several helpful comments. I'm grateful to Madhu Sudan for discussions on SDP from which we came up with the hardness result. Madhu also made several comments on a draft of this pap er which signicantly improved it. References [Ali95] F. Alizadeh. Interior-Point Metho ds in Semidenite Programming with Applications to Combinatorial Optimization. SIAM Journal on Optimization , 5:13{51, 1995. 2 Actually this is not needed since one or more conditions on matrices to b e psd are p ermitted in a semidenite program. 4 [CS95] B. Chor and M. Sudan. A Geometric Approach to Betweeness. In Third European Symposium on Algorithms , Lecture Notes in Computer Science, pages 227{237. Springer-Verlag, 1995. [FG95] U. Feige and M. Go emans. Approximating the Value of Two Prover Pro of Systems, with Applications to Max DICUT and Max 2SAT. In Proceedings of 3rd Israel Symposium on Theory and Computing Systems , 1995. [GLS81] M. Grotschel, L. Lovasz, and A. Schrijver. The Ellipsoid Metho d and its Consequences in Combinatorial Optimization. Combinatorica , 1:169{197, 1981. [GLS88] M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization . Springer Verlag, 1988. [GVL83] G.H. Golub and C.F. Van Loan. Matrix Computations. John Hopkins University Press, 1983. [GW95] M.X. Go emans and D.P. Williamson. Improved Approximation Algorithms for Maximum Cut and Satisability Problems Using Semidenite Programming. Journal of the ACM , 42(6):1115{1145, 1995. [HRVO93] C. Helmb erg, F. Rendl, R.J. Vanderb ei, and M.L. Overton. An Interior-Point Metho d for Semidenite Programming. Technical Rep ort CORR 93-20, SOR 93-15, Dept. of Combinatorics and Optimization, Waterlo o, Ont., 1993. [Kar84] A. Karmarkar. A New Polynomial Time Algorithm in Linear Programming. Proc. 16th Annual ACM Symposium on Theory of Computing , pages 302{311, 1984. [KMS94] D. Karger, R. Motwani, and M. Sudan. Approximate Graph Coloring via Semidenite Programming. In 35th Annual Symposium on Foundations of Computer Science , 1994. [PSU88] A.L. Peresini, F.E. Sullivan, and J.J. Uhl, Jr. The Mathematics of Nonlinear Programming. eds. Ewing, J.H. Springer Verlag, 1988. [VB96] L. Vandenb erghe and S. Boyd. Semidenite Programming. SIAM Journal of Computing , 38:49{95, 1996. 5