Readings in Optimization Presentation

Semidefinite Programming (SDP) and the GoemansWilliamson MAXCUT Paper Outline • Alternate View of Linear Progr • Facts about Symmetric and Semidefinite Matr • • SDP • Approximately Solving MAXCUT using SDP and V • Interior-Point Methods for 2 Linear Programming Alternative Perspective LP : minimize c · x s.t. ai · x = bi, i = 1, . . . , m x ∈ n+.
n “c · x” means the linear function “ j=1 cj xj ” n+ := {x ∈ n | x ≥ 0} is the nonnegative orthant. n+ is a convex cone. K is convex cone if x, w ∈ K and α, β ≥ 0 ⇒ αx + βw ∈ K. 3 Linear Programming Alternative Perspective LP : minimize c · x s.t. ai · x = bi, i = 1, . . . , m x ∈ n+. “Minimize the linear function c · x, subject to the condition that x must solve m given equations ai · x = bi, i = 1, . . . , m, and that x must lie in the convex cone K = n+.” 4 Alternative Perspective Linear Programming LP Dual Problem... LD : maximize s.t. m
i=1 m
yi b i yi a i + s = c i=1 n . s ∈ + For feasible solutions x of LP and (y, s) of LD, the duality gap is simply   m m   yi a i · x = s · x ≥ 0 c·x− yi b i = c − i=1 i=1 5 Alternative Perspective Linear Programming ...LP Dual Problem If LP and LD are feasible, then there exists x∗ and (y ∗, s∗) feasible for the primal and dual, respectively, for which m  c · x∗ − yi∗bi = s∗ · x∗ = 0 i=1 6 Facts about the Semidefinite Cone If X is an n × n matrix, then X is a symmetric positive semidefinite (SPSD) matrix if X = X T and v T Xv ≥ 0 for any v ∈ n If X is an n × n matrix, then X is a symmetric positive definite (SPD) matrix if X = X T and v T Xv > 0 for any v ∈ n, v = 0 7 Facts about the Semidefinite Cone S n denotes the set of symmetric n × n matrices n S+ denotes the set of (SPSD) n × n matrices. n S++ denotes the set of (SPD) n × n matrices. 8 Facts about the Semidefinite Cone Let X, Y ∈ S n. “X  0” denotes that X is SPSD “X  Y ” denotes that X − Y  0 “X 0” to denote that X is SPD, etc. n Remark: S+ = {X ∈ S n | X  0} is a convex cone. 9 Facts about Eigenvalues and Eigenvectors If M is a square n × n matrix, then λ is an eigenvalue of M with corresponding eigenvector q if M q = λq and q = 0 . Let λ1, λ2, . . . , λn enumerate the eigenvalues of M . 10 Facts about Eigenvalues and Eigenvectors The corresponding eigenvectors q 1, q 2, . . . , q n of M can be chosen so that they are orthonormal, namely  i T  j   i T  i  q = 0 for i = j, and q q =1 q Define:  1 2  n Q := q q · · · q Then Q is an orthonormal matrix: QT Q = I, equivalently QT = Q−1 11 Facts about Eigenvalues and Eigenvectors λ1, λ2, . . . , λn are the eigenvalues of M q 1, q 2, . . . , q n are the corresponding orthonormal eigenvectors of M   Q := q 1 q 2 · · · q n QT Q = I, equivalently QT = Q−1 Define D:  λ1  0  D :=  0 Property: M = QDQT . 0 λ2 0 ...    .  λn 12 Facts about Eigenvalues and Eigenvectors The decomposition of M into M = QDQT is called its eigendecomposition. 13 Facts about Symmetric Matrices • If X ∈ S n, then X = QDQT for some orthonormal matrix Q and some diagonal matrix D. The columns of Q form a set of n orthogonal eigenvectors of X, whose eigenvalues are corresponding entries of the diagonal matrix D • X  0 if and only if X = QDQT where the eigenvalues (i.e the diagonal entries of D) are all nonnegative • X 0 if and only if X = QDQT where the eigenvalues (i.e the diagonal entries of D) are all positive 14 Facts about Symmetric Matrices • If M is symmetric, det(M ) = n  λj j=1 15 Facts about Symmetric Matrices • Consider the matrix M defined as follo  M= P vT v d  , where P 0, v is a vector, and d is a scalar. Then M  0 if and only if d − v T P −1v ≥ 0. • For a given column vector a, the matrix X := aaT is SPSD, i.e., X = aaT  0. • If M  0, then there is a matrix N for which M = N T N . To 1 see this, simply take N = D 2 QT . 16 Semidefinite Programming SDP Think about X Let X ∈ S n. Think of X as: • a matr • an array of n2 components of the form (x11, . . . , xnn) • an object (a vector) in the space S n All three different equivalent ways of looking at X will be useful. 17 Semidefinite Programming SDP Linear Function of X Let X ∈ S n. What will a linear function of X look like? If C(X) is a linear function of X, then C(X) can be written as C • X, where C • X := n  n  Cij Xij . i=1 j=1 There is no loss of generality in assuming that the matrix C is also symmetric. 18 Semidefinite Programming SDP Definition of SDP SDP : minimize C • X s.t. Ai • X = bi , i = 1, . . . , m, X  0, n “X  0” is the same as “X ∈ S+ ” The data for SDP consists of the symmetric matrix C (which is the data for the objective function) and the m symmetric matrices A1, . . . , Am, and the m−vector b, which form the m linear equations. 19 Semidefinite Programming SDP Example...   1 0 1 A1 =  0 3 7  , 1 7 5       1 2 3 0 2 8 11 A2 =  2 6 0  , b = , and C =  2 9 0  , 19 8 0 4 3 0 7 The variable X will be the 3 × 3 symmetric matrix:   x11 x12 x13 X =  x21 x22 x23  , x31 x32 x33 SDP : minimize s.t. x11 + 4x12 + 6x13 + 9x22 + 0x23 + 7x33 x11 + 0x12 + 2x13 + 3x22 + 14x23 + 5x33 = 11 0x11 + 4x12 + 16x13 + 6x22 + 0x23 + 4x33 = 19  x11 X =  x21 x31 x12 x22 x32  x13 x23   0. x33 20 Semidefinite Programming SDP SDP : minimize s.t. ...Example x11 + 4x12 + 6x13 + 9x22 + 0x23 + 7x33 x11 + 0x12 + 2x13 + 3x22 + 14x23 + 5x33 = 11 0x11 + 4x12 + 16x13 + 6x22 + 0x23 + 4x33 = 19  x11 X =  x21 x31 x12 x22 x32  x13 x23   0. x33 It may be helpful to think of “X  0” as stating that each of the n eigenvalues of X must be nonnegative. 21 Semidefinite Programming SDP LP ⊂ SDP LP : minimize c · x s.t. ai · x = bi, i = 1, . . . , m x ∈ n+. Define:  ai1  0 Ai =   ... 0 0 ai2 ... 0   ... 0 c1  0 ... 0   , i = 1, . . . , m, and C = ...  ...  ... 0 . . . ain 0 c2 ... 0  ... 0  ... 0  . . . ...  . . . . cn SDP : minimize C • X s.t. Ai • X = bi , i = 1, . . . , m, Xij =0, i = 1, . . . , n, j= i + 1, . . . , n, x1 0 . . . 0  0 x2 . . . 0  X= ... ...  ...  ...   0, 0 0 . . . xn 22 SDP Duality SDD : maximize m
yi b i i=1 s.t. m
yi A i + S = C i=1 S  0. Notice S=C− m  yiAi  0 i=1 23 SDP Duality and so equivalently: SDD : maximize m
yi b i i=1 s.t. C− m
yiAi  0 i=1 24 Example SDP Duality   1 0 1 A1 =  0 3 7  , 1 7 5   0 2 8 A2 =  2 6 0  , b = 8 0 4  11 19    1 2 3 , and C =  2 9 0  3 0 7 SDD : maximize 11y1 + 19y2  s.t.      1 0 1 0 2 8 1 2 3 y 1  0 3 7  + y2  2 6 0  + S =  2 9 0  1 7 5 8 0 4 3 0 7 S0 25 Example SDP Duality SDD : maximize 11y1 + 19y2  s.t.      1 0 1 0 2 8 1 2 3 y 1  0 3 7  + y2  2 6 0  + S =  2 9 0  1 7 5 8 0 4 3 0 7 S0 is the same as: 11y1 + 19y2 SDD : maximize s.t.   1 − 1y1 − 0y2 2 − 0y1 − 2y2 3 − 1y1 − 8y2  2 − 0y1 − 2y2 9 − 3y1 − 6y2 0 − 7y1 − 0y2   0. 3 − 1y1 − 8y2 0 − 7y1 − 0y2 7 − 5y1 − 4y2 26 Weak Duality SDP Duality Weak Duality Theorem: Given a feasible solution X of SDP and a feasible solution (y, S) of SDD, the duality gap is C•X − m  yi b i = S • X ≥ 0 . i=1 If C •X − m  yi b i = 0 , i=1 then X and (y, S) are each optimal solutions to SDP and SDD, respectively, and furthermore, SX = 0. 27 Strong Duality SDP Duality ∗ Strong Duality Theorem: Let zP∗ and zD denote the optimal objective function values of SDP and SDD, respectively. Suppose that there exists a feasible solution X̂ of SDP such that ˆ 0, and that there exists a feasible solution (ˆ ˆ of SDD X y, S) such that Ŝ 0. Then both SDP and SDD attain their optimal values, and ∗ . zP∗ = zD 28 Some Important Weaknesses of SDP • There may be a finite or infinite duality gap • The primal and/or dual may or may not attain their • Both programs will attain their common optimal value if programs have feasible solutions that are SPD • There is no finite algorithm for solving SDP • There is a simplex algorithm, but it is not a finite algor There is no direct analog of a “basic feasible solution” for SDP 29 The MAX CUT Problem G is an undirected graph with nodes N = {1, . . . , n} and edge set E. Let wij = wji be the weight on edge (i, j), for (i, j) ∈ E. We assume that wij ≥ 0 for all (i, j) ∈ E. The MAX CUT problem is to determine a subset S of the nodes N for which the sum of the weights of the edges that cross from ¯ := N \ S). ¯ is maximized (S S to its complement S 31 Formulations The MAX CUT Problem The MAX CUT problem is to determine a subset S of the nodes N for which the sum of the weights wij of the edges that cross ¯ := N \ S). ¯ is maximized (S from S to its complement S ¯ Let xj = 1 for j ∈ S and xj = −1 for j ∈ S. M AXCU T : maximizex 41 s.t. n
n
wij (1 − xixj ) i=1 j=1 xj ∈ {−1, 1}, j = 1, . . . , n. 32 Formulations The MAX CUT Problem M AXCU T : maximizex 41 s.t. n
n
wij (1 − xixj ) i=1 j=1 xj ∈ {−1, 1}, j = 1, . . . , n. Let Y = xxT . Then Yij = xixj i = 1, . . . , n, j = 1, . . . , n. 33 Formulations The MAX CUT Problem Also let W be the matrix whose (i, j)th element is wij for i = 1, . . . , n and j = 1, . . . , n. Then M AXCU T : maximizeY,x s.t. 1 4 n
n
wij (1 − Yij ) i=1 j=1 xj ∈ {−1, 1}, j = 1, . . . , n Y = xxT . 34 Formulations The MAX CUT Problem M AXCU T : maximizeY,x 41 s.t. n
n
wij (1 − Yij ) i=1 j=1 xj ∈ {−1, 1}, j = 1, . . . , n Y = xxT . 35 Formulations The MAX CUT Problem The first set of constraints are equivalent to Yjj = 1, j = 1, . . . , n. M AXCU T : maximizeY,x 41 s.t. n
n
wij (1 − Yij ) i=1 j=1 Yjj = 1, j = 1, . . . , n Y = xxT . 36 Formulations The MAX CUT Problem M AXCU T : maximizeY,x s.t. 1 4 n
n
wij (1 − Yij ) i=1 j=1 Yjj = 1, j = 1, . . . , n Y = xxT . Notice that the matrix Y = xxT is a rank-1 SPSD matrix. 37 Formulations The MAX CUT Problem We relax this condition by removing the rank-1 restriction: RELAX : maximizeY s.t. 1 4 n
n
wij (1 − Yij ) i=1 j=1 Yjj = 1, j = 1, . . . , n Y  0. It is therefore easy to see that RELAX provides an upper bound on MAXCUT, i.e., M AXCU T ≤ RELAX. 38 Computing a Good Solution The MAX CUT Problem RELAX : maximizeY s.t. 1 4 n
n
wij (1 − Yij ) i=1 j=1 Yjj = 1, j = 1, . . . , n Y  0. Let Ŷ solve RELAX Factorize Yˆ = Vˆ T Vˆ  ˆij = Vˆ T Vˆ v1 v ˆ2 · · · v ˆn] and Y Vˆ = [ˆ  ij =v ˆiT v ˆj 39 The MAX CUT Problem Computing a Good Solution ˆ solve RELAX Let Y Factorize Yˆ = Vˆ T Vˆ  ˆij = V ˆ T Vˆ v1 v ˆ2 · · · v ˆn] and Y Vˆ = [ˆ  ij =v ˆiT v ˆj Let r be a random uniform vector on the unit n-sphere S n S := {i | r T v̂i ≥ 0} S := {i | r T v̂i < 0} 40 The MAX CUT Problem Computing a Good Solution Proposition: T   arccos(ˆ ˆj ) v T T i v P sign(r v ˆi) =  sign(r v ˆj ) = . π 41 The MAX CUT Problem Computing a Good Solution ^ V i ^ Vj 0 42 The MAX CUT Problem Computing a Good Solution Let r be a random uniform vector on the unit n-sphere S n S := {i | r T v̂i ≥ 0} S := {i | r T v̂i < 0} Let E[Cut] denote the expected value of this cut. Theorem: E[Cut] ≥ 0.87856 × M AXCU T 43 Computing a Good Solution The MAX CUT Problem E[Cut] = = = = 1 2 1 2 1 2
i,j
i,j
 wij × P sign(r v ˆi) =  sign(r v ˆj ) T T viT v ˆj ) arccos(ˆ wij π arccos(Ŷij ) wij π
i,j 1 2π  wij arccos(Ŷij ) i,j 44 The MAX CUT Problem E[Cut] = 1 2π Computing a Good Solution
wij arccos(Ŷij ) i,j   ˆ
1 2 arccos(Yij ) ˆ = 4 wij 1 − Yij π 1−Yˆ ij i,j  
1 ≥ 4 wij 1 − Yˆij min−1≤t≤1 π2 arccos(t) 1−t i,j θ = RELAX × min0≤θ≤π π2 1−cos θ ≥ RELAX × 0.87856 45 The MAX CUT Problem Computing a Good Solution So we have M AXCU T ≥ E[Cut] ≥ RELAX × 0.87856 ≥ M AXCU T × 0.87856 This is an impressive result, in that it states that the value of the semidefinite relaxation is guaranteed to be no more than 12.2% higher than the value of N P -hard problem MAXCUT. 46 The Logarithmic Barrier Function for SPD Matrices n Let X  0, equivalently X ∈ S+ . X will have n nonnegative eigenvalues, say λ1(X), . . . , λn(X) ≥ 0 (possibly counting multiplicities). n ∂S+ = {X ∈ S n | λj (X) ≥ 0, j = 1, . . . , n, and λj (X) = 0 for some j ∈ {1, . . . , n}}. 47 The Logarithmic Barrier Function for SPD Matrices n ∂S+ = {X ∈ S n | λj (X) ≥ 0, j = 1, . . . , n, and λj (X) = 0 for some j ∈ {1, . . . , n}}. A natural barrier function is: B(X) := − n  j=1  ln(λi(X)) = − ln  n   λi(X) = − ln(det(X)). j=1 This function is called the log-determinant function or the logarithmic barrier function for the semidefinite cone. 48 The Logarithmic Barrier Function for SPD Matrices B(X) := − n  j=1  ln(λi(X)) = − ln  n   λi(X) = − ln(det(X)). j=1 ¯ Quadratic Taylor expansion at X = X:     1 1 1 1 1 ¯ − 2 DX ¯ − 2 DX ¯ + αD) ≈ B(X) ¯ + αX ¯ −2 • X ¯ −2 . ¯ −1 • D + α2 X B(X 2 B(X) has the same remarkable properties in the context of interior-point methods for SDP as the barrier function
n − j=1 ln(xj ) does in the context of linear optimization. 49 Primal and Dual SDP Interior-point Methods for SDP SDP : minimize C • X s.t. Ai • X = bi , i = 1, . . . , m, X0 and SDD : maximize s.t. m
i=1 m
y i bi yi Ai + S = C i=1 S0. If X and (y, S) are feasible for the primal and the dual, the duality gap is: m  C •X − yi bi = S • X ≥ 0 . Also, i=1 S • X = 0 ⇐⇒ SX = 0 . 50 Interior-point Methods for SDP B(X) = − n  Primal and Dual SDP  ln(λi(X)) = − ln  j=1 n   λi(X) = − ln(det(X)) . j=1 Consider: BSDP (µ) : minimize C • X − µ ln(det(X)) s.t. Ai • X = bi , i = 1, . . . , m, X 0. Let fµ(X) denote the objective function of BSDP (µ). Then: −∇fµ(X) = C − µX −1 51 Interior-point Methods for SDP Primal and Dual SDP BSDP (µ) : minimize C • X − µ ln(det(X)) s.t. Ai • X = bi , i = 1, . . . , m, X 0. ∇fµ(X) = C − µX −1 Karush-Kuhn-Tucker conditions for BSDP (µ) are:   Ai • X = bi , i = 1, . . . , m,       X 0,    m 
 −1  yi Ai .  C − µX = i=1 52 Interior-point Methods for SDP Primal and Dual SDP  Ai • X = bi , i = 1, . . . , m,    X 0, m
 −1  yi A i .  C − µX = i=1 Define S = µX −1 , which implies XS = µI , 53 Interior-point Methods for SDP Primal and Dual SDP and rewrite KKT conditions as:   Ai • X = bi , i = 1, . . . , m, X  
m yi A i + S = C   i=1  XS = µI. 0 54 Interior-point Methods for SDP Primal and Dual SDP   Ai • X = bi , i = 1, . . . , m, X  
m yi A i + S = C   i=1  XS = µI. 0 If (X, y, S) is a solution of this system, then X is feasible for SDP , (y, S) is feasible for SDD, and the resulting duality gap is S•X = n  n  i=1 j=1 n n   Sij Xij = (SX)jj = (µI)jj = nµ. j=1 j=1 55 Interior-point Methods for SDP Primal and Dual SDP   Ai • X = bi , i = 1, . . . , m, X  
m yi A i + S = C   i=1  XS = µI. 0 If (X, y, S) is a solution of this system, then X is feasible for SDP , (y, S) is feasible for SDD, the duality gap is S • X = nµ. 56 Interior-point Methods for SDP Primal and Dual SDP This suggests that we try solving BSDP (µ) for a variety of values of µ as µ → 0. Interior-point methods for SDP are very similar to those for linear optimization, in that they use Newton’s method to solve the KKT system as µ → 0. 57