Optimization Methods - Semidefinite Optimization

1 Outline 1. 2. 3. 4. 5. Slide 1 Preliminaries SDO Duality SDO Modeling Power Barrier Algorithm for SDO 2 Preliminaries A symmetric matrix A is positive semidenite (A
0) if and only if u Au  0 0 8 Slide 2 u 2 Rn A
0 if and only if all eigenvalues of A are nonnegative n X n X Inner product A B = Aij Bij i=1 j =1 2.1 The trace The trace of a matrix A is dened trace(A) = Slide 3 n X j =1 Aj j trace(AB ) = trace(B A) A B = trace(A B) = trace(B A) 0 0 3 SDO C symmetric n  n matrix Ai i = 1 : : : m symmetric n  n matrices bi i = 1 : : : m scalars Semidenite optimization problem (SDO) (P ) : min s:t: C X Ai X = bi i = 1 : : : m X
0 1 Slide 4 3.1 Example Slide 5 n = 3 and m = 2 01 0 11 00 2 81 01 2 31 A1 = @ 0 3 7 A A2 = @ 2 6 0 A C = @ 2 9 0 A 1 7 5 8 0 4 b1 = 11 b2 = 19 3 0 7 0x x x 1 11 12 13 X = @ x21 x22 x23 A x31 x32 x33 Slide 6 (P ) : min x11 + 4x12 + 6x13 + 9x22 + 7x33 s:t: x11 + 2x13 + 3x22 + 14x23 + 5x33 = 11 4x12 + 16x13 + 6x22 + 4x33 = 19 0x x x 1 11 12 13 X = @ x21 x22 x23 A
0 x31 x32 x33 3.2 Convexity Slide 7 (P ) : min C X s:t: Ai X = bi i = 1 : : : m The feasible set is convex: X
0 X1 X2 feasible =) X1 + (1 ; )X2 feasible 0    1 . A (X1 + (1 ; )X2) =  |A {zX1} +(1 ; ) |A {zX2} = bi i i i bi bi . u (X1 + (1 ; )X2)u =  |u X{z1u} +(1 ; ) |u X{z2u}  0 0 0 0 0 � 2 0 � 3.3 LO as SDO Slide 8 LO : min c x s:t: Ax = b 0 0 ai1 Ai = BB@ 0.. 0 ai2 . . .. 0 0 ::: 0 ::: 0 . . . ... : : : ain x0 1 0 c1 CC C = BB 0 A @ ... 0 c2 .. . 0 0 ::: ::: ... ::: 01 0C .. C .A cn Slide 9 (P ) : min C X s:t: Ai X = bi i = 1 : : : m Xij = 0 i = 1 : : : n j = i + 1 : : : n X
0 0 x1 X = BB@ 0.. 0 x2 . . .. 0 0 4 Duality (D) : max s:t: m X i=1 m X i=1 ::: ::: ... ::: 01 0C .. C .A xn Slide 10 yi bi yi Ai + S = C S
0 Equivalently, (D) : max m X i=1 yi bi s:t: C ; 3 m X i=1 yi Ai
0 4.1 Example (D) max 11y01 + 19y2 1 00 2 81 01 2 31 1 0 1 s:t: y1 @ 0 3 7 A + y2 @ 2 6 0 A + S = @ 2 9 0 A 1 7 5 8 0 4 3 0 7 Slide 11 S
0 (D) max 11y 19y2 1 0 11 ;+ 1y 1 ; 0y2 2 ; 0y1 ; 2y2 3 ; 1y1 ; 8y2 s:t: @ 2 ; 0y1 ; 2y2 9 ; 3y1 ; 6y2 0 ; 7y1 ; 0y2 A
0 3 ; 1y1 ; 8y2 0 ; 7y1 ; 0y2 7 ; 5y1 ; 4y2 Slide 12 y2 1 0.8 0.6 0.4 0.2 -2 -1.5 -1 -0.5 0.5 1 y1 Optimal value u 13.9022 y1 u 0:4847 y2 u 0:4511 � � 4.2 Weak Duality Theorem Given a feasible solution X of (P ) and a feasible solution (y S ) of (D), m X C X ; yibi = S X  0 m X i=1 If C X ; yi bi = 0, then X and (y S) are each optimal solutions to (P ) i=1 and (D) and SX = 0 4 Slide 13 4.3 Proof We must show that if S
0 and X
0, then S X  0 Let S = P DP and X = QEQ where P Q are orthonormal matrices and D E are nonnegative diagonal matrices Slide 14 0 0 S X = trace(S X ) = trace(SX ) = trace(P DP QEQ ) n X = trace(DP QEQ P ) = Dj j (P QEQ P )j j  0 0 0 0 0 0 0 0 j =1 since Dj j  0 and the diagonal of P QEQ P must be nonnegative. Suppose that trace(S X ) = 0. Then 0 n X j =1 0 Dj j (P QEQ P )j j = 0 0 0 Then, for each j = 1 : : : n, Dj j = 0 or (P QEQ P )j j = 0. The latter case implies that the j th row of P QEQ P is all zeros. Therefore, DP QEQ P = 0, and so S X = P DP QEQ = 0. 0 0 0 0 0 0 0 0 4.4 Strong Duality (P ) or (D) might not attain their respective optima There might be a duality gap, unless certain regularity conditions hold Theorem If there exist feasible solutions X^ for (P ) and (y^ S^ ) for (D) such that X^ 0, S^ 0 Slide 15 Then, both (P ) and (D) attain their optimal values zP and zD Furthermore, zP = zD � � � � 5 SDO Modeling Power 5.1 Quadratically Constrained Problems min (A0 x + b0) (A0 x + b0) ; c0 x ; d0 s:t: (Ai x + bi ) (Aix + bi ) ; ci x ; di  0 0 0 0 0 5 Slide 16 i = 1 ::: m (Ax + b) (Ax + b) ; c x ; d  0 " 0 0 I (Ax + b) Ax + b c x+d 0 0 # ,
0 Slide 17 min t s:t: (A0 x + b0) (A0 x + b0) ; c0 x ; d0 ; t  0 (Ai x + bi ) (Aix + bi ) ; ci x ; di  0 8 i 0 0 0 , min " 0 t Slide 18 # A0x + b0
0 c0x + d0 + t # Aix + bi
0 8 i c i x + di I s:t: (A0 x + b0) " I (Ai x + bi ) 0 0 0 0 5.2 Eigenvalue Problems Slide 19 X : symmetric n  n matrix max (X ) = largest eigenvalue of X 1 (X )  2 (X )   m (X ) eigenvalues of X i (X + t I ) = i (X ) + t Theorem: max (X )  t , t I ; X
0 Sum of k largest eigenvalues: k X i=1 i (X )  t , t ; k s ; trace(Z )  0 Z
0 Z ;X +sI
0 Follows from the characterization: k X i=1 i (X ) = maxfX V : trace(V ) = k 0 V 6 Ig 5.3 Optimizing Structural Dynamics Select xi , cross-sectional area of structure i, i = 1 : : : n M (x) = M 0 + Pi xi M i, mass matrix K (x) = K 0 + Pi xi K i, stiness matrix P Structure weight w = w0 + i xi wi Dynamics M (x)d + K (x)d = 0 d(t) vector of displacements n X di (t) = j =1 Slide 20 Slide 21 ij cos(!j t ; j ) det(K (x) ; M (x)!2 ) = 0 !1  !2   !n =2 (M (x) K (x)) Fundamental frequency: !1 = 1min We want to bound the fundamental frequency !1   () M (x)2 ; K (x) 0 Minimize weight Problem: Minimize weight subject to Fundamental frequency !1   Limits on cross-sectional areas Formulation Slide 22 P min w0 + i xi wi s:t: M (x) 2 ; K (x) 0 li  xi  ui 5.4 Measurements with Noise x: ability of a random student on k tests Ex] = x , E(x ; x )(x ; x ) ] =
y: score of a random student on k tests v: testing error of k tests, independent of x Ev] = 0, Evv ] = D, diagonal (unknown) 0 0 7 Slide 23 y = x + v Ey] = x E(y ; x )(y ; x ) ] =
b =
+ D Objective: Estimate reliably x and
0 Slide 24 Take samples of y from which we can estimate x , b e x: total ability on tests e y: total test score Reliability of test:= Vare x] = e
e = 1 ; e De Vare y] e
b e e
b e 0 0 0 0 0 0 0 0 Slide 25 We can nd a lower bound on the reliability of the test min e
e s:t:
+ D =
b 0
D
0 D diagonal Equivalently, max e D e s:t: 0 D
b D diagonal 0 5.5 Further Tricks If B 0,  A = BC CD 0 Slide 26
0 () D ; CB 1C
0 ; 0  x Ax + 2b x + c  0 8 x () bc Ab 0 0 0 8
0 5.6 MAXCUT Given G = (N E ) undirected graph, weights wij  0 on edge (i j) 2 E P Find a subset S  N : i S
j S wij is maximized xj = 1 for j 2 S and xj = ;1 for j 2 S 2 Slide 27 2 n X n X wij (1 ; xixj ) M AX C U T : max 41 i=1 j =1 s:t: xj 2 f;1 1g j = 1 : : : n 5.6.1 Reformulation Slide 28 Let Y = xx , i.e., Yij = xi xj Let W = wij ] Equivalent Formulation 0 n X n X wij ; W Y M AX C U T : max 41 i=1 j =1 s:t: xj 2 f;1 1g j = 1 : : : n Yj j = 1 j = 1 : : : n Y = xx 0 5.6.2 Relaxation Y = xx
0 Slide 29 0 Relaxation n X n X wij ; W Y RELAX : max 41 i=1 j =1 s:t: Yj j = 1 j = 1 : : : n Y
0 M AX C U T  RELAX It turns out that: 0:87856 RELAX  M AX C U T  RELAX The value of the SDO relaxation is guaranteed to be no more than 12% higher than the value of the very dicult to solve problem MAXCUT 9 Slide 30 6 Barrier Algorithm for SDO X
0 , 1(X )  0 : : : n(X )  0 Natural barrier to repel X from the boundary 1 (X ) > 0 : : : n(X ) > 0: n X ; log(i (X )) = ; log( Slide 31 j =1 n Y j =1 i (X )) = ; log(det(X )) Slide 32 Logarithmic barrier problem min B (X ) = C X ;  log(det(X )) s:t: Ai X = bi i = 1 : : : m X 0 Barrier algorithm needs O from 0 to  n log 0 iterations to reduce duality gap p 7 Conclusions SDO is a very powerful modeling tool SDO represents the present and future in continuous optimization Barrier Algorithm is very powerful Many good solvers available: SeDuMi, SDPT3, SDPA, etc. Pointers to literature and solvers: www-user.tu-chemnitz.de/~helmberg/semidef.html 10 Slide 33