# MIT 6 251J - Semideﬁnite Optimization (12 pages)

Previewing pages*1, 2, 3, 4*of 12 page document

**View the full content.**## Semideﬁnite Optimization

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

**View the full content.**View Full Document

## Semideﬁnite Optimization

0 0 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