15 081J 6 251J Introduction to Mathematical Programming Lecture 23 Semide nite Optimization 1 Outline Slide 1 1 Preliminaries 2 SDO 3 Duality 4 SDO Modeling Power 5 Barrier Algorithm for SDO 2 Preliminaries Slide 2 A symmetric matrix A is positive semide nite A 0 if and only if u Au 0 u Rn A 0 if and only if all eigenvalues of A are nonnegative A B n n Aij Bij i 1 j 1 2 1 The trace Slide 3 The trace of a matrix A is de ned trace A n Ajj j 1 trace AB trace BA A B trace A B 3 SDO Slide 4 C symmetric n n matrix Ai i 1 m symmetric n n matrices bi i 1 m scalars Semide nite optimization problem SDO P min C X s t Ai X bi X 0 1 i 1 m 3 1 Example Slide 5 n 3 and m 2 1 0 A1 0 3 1 7 1 0 2 7 A2 2 6 5 8 0 b1 11 2 9 0 b2 19 x11 X x21 x31 P 8 1 0 C 2 4 3 x12 x22 x32 3 0 7 x13 x23 x33 Slide 6 min x11 4x12 6x13 9x22 7x33 s t x11 2x13 3x22 14x23 5x33 11 4x12 16x13 6x22 4x33 19 x11 x12 x13 X x21 x22 x23 0 x31 x32 x33 3 2 LO as SDO Slide 7 LO ai1 0 Ai 0 P 0 ai2 0 min c x s t Ax b x 0 0 c1 0 0 C ain 0 min C X s t Ai X bi 0 0 0 c2 0 cn i 1 m Xij 0 i 1 n j i 1 n X 0 x1 0 0 0 x2 0 X 0 0 xn 2 Slide 8 4 Duality D m max s t Slide 9 yi bi i 1 m yi Ai S C m yi bi i 1 S 0 Equivalently D max i 1 s t C m yi Ai 0 i 1 4 1 Example Slide 10 D max 11y1 19y2 1 0 1 0 s t y1 0 3 7 y2 2 1 7 5 8 S 0 11y1 19y2 1 1y1 0y2 s t 2 0y1 2y2 3 1y1 8y2 2 8 1 2 6 0 S 2 9 0 4 3 0 D max 4 2 2 0y1 2y2 9 3y1 6y2 0 7y1 0y2 3 0 7 3 1y1 8y2 0 7y1 0y2 0 7 5y1 4y2 Weak Duality Slide 11 Theorem Given a feasible solution X of P and a feasible solution y S of D m yi bi S X 0 C X i 1 If C X m yi bi 0 then X and y S are each optimal solutions to P i 1 and D and SX 0 3 4 3 Proof Slide 12 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 S X trace S X trace SX trace P DP QEQ trace DP QEQ P n Djj P QEQ P jj 0 j 1 since Djj 0 and the diagonal of P QEQ P must be nonnegative Suppose that trace SX 0 Then n Djj P QEQ P jj 0 j 1 Then for each j 1 n Djj 0 or P QEQ P jj 0 The latter case implies that the j th row of P QEQ P is all zeros There fore DP QEQ P 0 and so SX P DP QEQ 0 4 4 Strong Duality Slide 13 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 then both P and D attain their optimal values zP and zD zP zD 5 SDO vs LO Slide 14 There may be a nite or in nite duality gap The primal and or dual may or may not attain their optima Both problems will attain their common optimal value if both programs have feasible solutions in the interior of the semide nite cone 4 There is no nite algorithm for solving SDO There is a simplex algorithm but it is not a nite algorithm There is no direct analog of a basic feasible solution for SDO Given rational data the feasible region may have no rational solutions The optimal solution may not have rational components or rational eigen values 6 SDO Modeling Power 6 1 Quadratically Constrained Problems Slide 15 min A0 x b0 A0 x b0 c 0 x d0 s t Ai x bi Ai x bi c i x di 0 i 1 m Ax b Ax b c x d 0 I Ax b Ax b min c x d 0 Slide 16 t s t A0 x b0 A0 x b0 c 0 x d0 t 0 Ai x bi Ai x bi c i x di 0 i min s t t 6 2 Slide 17 A0 x b0 I 0 c 0 x d0 t Ai x bi 0 i c i x di A0 x b0 I Ai x bi Eigenvalue Problems Slide 18 X symmetric n n matrix max X largest eigenvalue of X 1 X 2 X m X eigenvalues of X 5 Theorem max X t t I X 0 k i X t t k s trace Z 0 i 1 Z 0 Z X sI 0 Recall trace Z n Zii i 1 6 3 Optimizing Structural Dynamics Slide 19 Select xi cross sectional area of structure i i 1 n M x M 0 i xi M i mass matrix K x K 0 i xi K i sti ness matrix Structure weight w w0 i xi wi Dynamics K x d 0 M x d Slide 20 d t vector of displacements di t n ij cos j t j j 1 det K x M x 2 0 1 2 n 1 2 Fundamental frequency 1 min M x K x We want to bound the fundamental frequency 1 M x 2 K x 0 Minimize weight Slide 21 Problem Minimize weight subject to Fundamental frequency 1 Limits on cross sectional areas Formulation min w0 i xi wi s t M x 2 K x 0 li xi ui 6 6 4 Measurements with Noise Slide 22 x ability of a random student on k tests E x x E x x x x y score of a random student on k tests v testing error of k tests independent of x E v 0 E vv D diagonal unknown y x v E y x D E y x y x Objective Estimate reliably x and Slide 23 Take samples of y from which we can estimate x e x total ability on tests e y total test score Reliability of test e De Var e x e e …