Optimization Methods - Semidefinite Optimization (cont.)

1 Outline Slide 1 1. SDO formulation 2. The Maximum cut problem 3. Minimizing Polynomials as an SDP 4. Linear Difference Equations and Stabilization 5. Barrier Algorithm for SDO 2 SDO formulation 2.1 Primal and dual • (P ) : Slide 2 min s.t. C •X Ai • X = bi X�0 • (D) : m � max i = 1, . . . , m y i bi i=1 C− s.t. m � yi Ai � 0 i=1 3 MAXCUT Slide 3 • Given G = (N, E) undirected graph, weights wij ≥ 0 on edge (i, j) ∈ E � • Find a subset S ⊆ N : ¯ wij is maximized i∈S,j∈S • xj = 1 for j ∈ S and xj = −1 for j ∈ S¯ n M AXCU T : s.t. 3.1 n 1 �� wij (1 − xi xj ) 4 i=1 j=1 max xj ∈ {−1, 1}, j = 1, . . . , n Reformulation Slide 4 • Let Y = xx� , i.e., Yij = xi xj • Let W = [wij ] 1 • Equivalent Formulation n M AXCU T : max s.t. n 1 �� wij − W • Y 4 i=1 j=1 xj ∈ {−1, 1}, j = 1, . . . , n Yjj = 1, j = 1, . . . , n Y = xx� 3.2 Relaxation Slide 5 • Y = xx� � 0 • Relaxation n RELAX : n 1 �� wij − W • Y 4 i=1 j=1 max s.t. Yjj = 1, j = 1, . . . , n Y �0 3.3 Feasible set -0.5 Slide 6 -1 0 0.5 1 • For n = 3, we have ⎡ 1 Y12 ⎣ Y12 1 Y13 Y23 1 ⎤ Y13 Y23 ⎦ � 0 1 0.5 0 -0.5 -1 -1 -0.5 0 0.5 An outer approximation to the true feasible set. 1 • M AXCU T ≤ RELAX • It turns out that: 0.87856 RELAX ≤ M AXCU T ≤ RELAX • The value of the SDO relaxation is guaranteed to be no more than 12% higher than the value of the very difficult to solve problem MAXCUT 2 Slide 7 4 Minimizing Polynomials 4.1 Sum of squares • A polynomial f (x) is a sum of squares (SOS) if � f (x) = gj2 (x) Slide 8 j for some polynomials gj (x). • A polynomial satisfies f (x) ≥ 0 for all x ∈ R if and only if it is a sum of squares. • Not true in more than one variable! 4.2 Proof Slide 9 � 2 j gj (x) then f (x) ≥ 0. � � • (⇒) Factorize f (x) = C j (x − rj )nj k (x − ak + ibk )mk (x − ak − ibk )mk . Since f (x) is nonnegative, then C ≥ 0 and all the nj are even. Then, f (x) = f1 (x)2 + f2 (x)2 , where • (⇐) Obvious. If f (x) = f1 (x) = 1 C2 � (x − rj ) nj 2 j f2 (x) = C 1 2 � (x − ak )mk k (x − rj ) nj 2 j 4.3 � � m bk k k SOS and SDO Slide 10 • Let x̃ = (1, x, x2 , . . . , xk )� . • f (x) = x ˜� Q˜ x is a sum of squares if and only if f (x) = x ˜� Q˜ x, where Q � 0, i.e., Q = L� L. • Then, f (x) = x ˜� L� L˜ x = ||L˜ x||2 . 4.4 Formulation Slide 11 • Consider min f (x). • Then, f (x) ≥ γ if and only if f (x) − γ = x ˜� Q˜ x with Q � 0. This implies linear constraints on γ and Q. • Reformulation � s.t. max γ f (x) − γ = Q � 3 ˜� Q˜ x x 0 4.5 4.5.1 Example Reformulation Slide 12 min f (x) = 3 + 4x + 2x2 + 2x3 + x4 . f (x) − γ = 3 − γ + 4x + 2x2 + 2x3 + x4 = (1, x, x2 )� Q(1, x, x2 ). max s.t. γ 3 − γ = q11 4 = 2q12 , 2 = 2q13 + q22 2 = 2q ⎡23 , 1 = q33 ⎤ q11 q12 q13 Q = ⎣ q12 q22 q23 ⎦ � 0 q13 q23 q33 Extensions to multiple dimensions. 5 Stability Slide 13 • A linear difference equation x(k + 1) = Ax(k), x(0) = x0 • x(k) converges to zero iff |λi (A)| < 1, i = 1, . . . n • Characterization: |λi (A)| < 1 ∀i ⇐⇒ ∃P � 0 5.1 A� P A − P � 0 Proof Slide 14 • (⇐=) Let Av = λv. Then, 0 > v � (A� P A − P )v = (|λ|2 − 1) �v ��� P v, � >0 and therefore |λ| < 1 �∞ � • (=⇒) Let P = i=0 Ai QAi , where Q � 0. The sum converges by the eigenvalue assumption. Then, A� P A − P = ∞ � � Ai QAi − i=1 ∞ � i=0 4 � Ai QAi = −Q � 0 5.2 Stabilization Slide 15 • Consider now the case where A is not stable, but we can change some elements, e.g., A(L) = A + LC, where C is a fixed matrix. • Want to find an L such that A + LC is stable. • Use Schur complements to rewrite the condition: (A + LC)� P (A + LC) − P � 0, P �0 � � � P (A + LC)� P �0 P (A + LC) P Condition is nonlinear in (P , L) 5.3 Changing variables Slide 16 • Define a new variable Y := P L � P PA + Y C A� P + C � Y � P � �0 • This is linear in (P , Y ). • Solve using SDO, recover L via L = P −1 Y 6 Primal Barrier Algorithm for SDO • X � 0 ⇔ λ1 (X) ≥ 0, . . . , λn (X) ≥ 0 Slide 17 • Natural barrier to repel X from the boundary λ1 (X) > 0, . . . , λn (X) > 0: − n � log(λi (X)) = j=1 − log( n � λi (X)) = − log(det(X)) j=1 Slide 18 • Logarithmic barrier problem min s.t. Bµ (X) = C • X − µ log(det(X)) Ai • X = bi , i = 1, . . . , m, X�0 • Derivative: �Bµ (X) = C − µX−1 Follows from log det(X + H) ≈ log det(X) + trace(X −1 H) + · · · 5 • KKT conditions Ai • X = bi , i = 1, . . . , m, m � C − µX−1 = yi Ai . i=1 X � 0, • Given µ, need to solve these nonlinear equations for X, C, yi • Apply Newton’s method until we are “close” to the optimal • Reduce value of µ, and iterate until the duality gap is small 6.1 Another interpretation Slide 19 • Recall the optimality conditions: m � Ai • X = bi , i = 1, . . . , m, yi Ai + S =C X, S XS � 0, =0 i=1 • Cannot solve directly. Rather, perturb the complementarity condition to X S = µI. • Now, unique solution for every µ > 0 (the “central path”) • Solve using Newton, for decreasing values of µ. 7 Differences with LO Slide 20 • Many different ways to linearize the nonlinear complementarity condition X S = µI • Want to preserve symmetry of the iterates • Several search directions, most common is Nesterov-Todd. 8 Convergence 8.1 Stopping criterion • The point (X, yi ) is feasible, and has duality gap: C•X− m � yi bi = µX−1 • X = nµ i=1 • Therefore, reducing µ always decreases the duality gap �√ �0 � iterations to reduce duality gap from �0 n log • Barrier algorithm needs O � to � 6 Slide 21 9 Conclusions Slide 22 • SDO is a very powerful modeling tool • SDO represents the present and future in continuous optimization • Barrier and primal-dual algorithms are very powerful • Many good solvers available: SeDuMi, SDPT3, SDPA, etc. • Pointers to literature and solvers: www-user.tu-chemnitz.de/~helmberg/semidef.html 7