Introduction to Semidefinite Programming

1 Introduction to Semidefinite Programming (SDP) Robert M. Freund 1 Introduction Semidefinite Programming (SDP) is the most exc iting development in math ematical Programming in the 1990 s. SDP has applications in such diverse fields as traditional convex constrained optimization, control theory, and combinatorial optimization. Because SDP is solvable vi a interior point methods, most of these applications can usually be solved very efficiently in practice as well as in theory. 2 Revi ew of Linear Programming Consider the linear Programming problem in standard form: LP : minimize c x ai x = bi, i = 1.

2 , m n +.x Here x is a vector of n variables, and we write c x for the inner-product P jn =1 cjxj , etc. Also, n + n x 0}, and we call n + the nonnegative orthant. n := {x |In fact, is a closed convex cone, where K is called a closed a convex cone + if K satisfies the following two conditions: 1 P P P3 If x, w K, then x+ w K for all nonnegative scalars and . K is a closed set. In words, LP is the following problem: Minimize the linear function c x, subject to the condition that x must solve m given equations ai x = bi, i = 1.

3 , m, and that x must lie in the closed convex cone K = n . + We will write the standard linear Programming dual problem as: m LD : maxi mize yibi i=1 m yiai + s = c i=1 n +.s Given a feasible solution x of LP and a feasible solution (y, s) of LD, the duality gap is simply c x Pmi=1 yibi = (c Pmi=1 yiai)x = s x 0, because x 0 and s 0. We kn ow from LP duality theory that so long as the pri mal problem LP is feasible and has bounded optimal objective value, then the primal and the dual both attain their optima with no duality gap.

4 That is, there exi sts x and (y , s ) feasible for the primal and dual, respectively, m such that c x i=1 yi bi = sx = 0. Facts about Matrices and the Semidefinite Cone If X is an n n matrix, then X is a positive Semidefinite (psd) matrix if n v TXv 0 for any v . 2 If X is an n n matrix, then X is a positive definite (pd) matrix if n v TXv > 0 for any v , v =60. Let Sn nmatrices, and let Sn +the set of positive Semidefinite (psd) n n sym metric matrices. Similarly let Sn denote the set of positive definite (pd)n n sym metric matrices.

5 ++ Let X and Y be any sym metric matrices. We write X 0 to denote that X is sym metric and positive Semidefinite , and we write X Y to denote that X Y 0. We write X 0 to denote that X is sym metric and positive definite, etc. 2 Remark 1 Sn + denote the set of sym metric n denote {X Sn | X 0} is a closed convex cone in n (n + 1)/2. of = dimension n nTo see why this remark is true, suppose that X, W S + , 0. For any v n, we have: v T( X + W)v = vTXv + vTW v 0, . Pick any scalars whereby X nn W SThis shows that S+ +++forward to show that Sn Recall the following properties of sym metric matrices: If X Sn, then X = QDQT for some orthonormal matrix Q and some diagonal matrix D.

6 (Recall that Q is orthonormal means that Q 1 = QT, and that D is diagonal means that the off- diagonal entries of D are all zeros.) 3 is a cone. It is also straight . is a closed set. X X 4 If X = QDQT as above, then the columns of Q form a set of n orthogonal eigenvectors of X, whose eigenvalues are the corresponding diagonal entries of D. X 0 if and only if X = QDQT where the eigenvalues ( , the diagonal entries of D) are all nonnegative. X 0 if and only if X = QDQT where the eigenvalues ( , the diagonal entries of D) are all positive.

7 If X 0 and if Xii = 0, then Xij = Xji = 0 for all j= 1, .. , n. Consider the matrix M defined as follows: Pv M = T , vd where P 0, v is a vector, and d is a scalar. Then M 0 if and only if d vTP 1v > 0. Semidefinite Programming Let X Sn . We can think of X as a matrix, or equ ivalently, as an array of n2 components of the form (x11, .. , xnn). We can also just think of X as an object (a vector) in the space Sn . All three diffe rent equ ivalent ways of looki ng at X will be useful. What will a linear function of X look like?

8 If C(X) is a linear function of X, then C(X) can be written as CX, where nn CX := CijXij. i=1 j=1 If X is a sym metric matrix, there is no loss of generality in assuming that 4 the matrix C is also sym metric. With this notation, we are now ready to define a Semidefinite program. A Semidefinite program (SDP) is an opti mization problem of the form: SDP : minimize CX Ai X = bi , i = 1, .. , m, X 0, Notice that in an SDP that the variable is the matrix X, but it might be helpful to think of X as an array of n2 numbers or simply as a vector in Sn.

9 The objective function is the linear function CX and there are m linear equ ations that X must satisfy, namely Ai X = bi , i = 1, .. , m. The variable X also must lie in the (closed convex) cone of positive semidef inite sym metric matrices Sn Note that the data for SDP consists of the +. sym metric matrix C (which is the data for the objective function) and the m sym metric matrices A1, .. , Am, and the m vector b, which form the m linear equ ations. Let us see an exa mple of an SDP for n = 3 and m = 2. Define the following matrices: 1 0 1 0 2 8 1 2 3 A1 = 0 3 7 ,A2 = 2 6 0 , and C = 2 9 0 , 1 7 5 8 0 4 3 0 7 and b1 = 11 and b2 = 19.

10 Then the variable X will be the 3 3 sym metric matrix: 5 x11 x12 x13 X = x21 x22 x23 , x31 x32 x33 and so, for exa mple, CX = x11 + 2x12 + 3x13 + 2x21 + 9x22 + 0x23 + 3x31 + 0x32 + 7x33 = x11 + 4x12 + 6x13 + 9x22 + 0x23 + 7x33. since, in particular, X is sym metric. Therefore the SDP can be written as: SDP : minimize x11 + 4x12 + 6x13 + 9x22 + 0x23 + 7x33 x11 + 0x12 + 2x13 + 3x22 + 14x23 + 5x33 = 11 0x11 + 4x12 + 16x13 + 6x22 + 0x23 + 4x33 = 19 x11 x12 x13 X = x21 x22 x23 0. x31 x32 x33 Notice that SDP looks remarkably similar to a linear program.