MIT 6 251J - Semidefinite Optimization (12 pages)

Previewing pages 1, 2, 3, 4 of 12 page document View the full content.
View Full Document

Semidefinite Optimization



Previewing pages 1, 2, 3, 4 of actual document.

View the full content.
View Full Document
View Full Document

Semidefinite Optimization

41 views


Pages:
12
School:
Massachusetts Institute of Technology
Course:
6 251j - Introduction to Mathematical Programming

Unformatted text preview:

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



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Semidefinite Optimization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Semidefinite Optimization and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?