Semidefinite Programming

Optimization · Axiom Academy

LESSON Semidefinite Programming A powerful generalization of linear programming that optimizes over positive semidefinite matrix constraints 1. Defining Semidefinite Programming A semidefinite program has the form: where x is the decision variable vector, c is a cost vector, and F(x) is an affine matrix function: The constraint F(x) ⪰ 0 means that F(x) must be positive semidefinite (all eigenvalues non-negative). 2. The Cone of Positive Semidefinite Matrices A symmetric matrix X is positive semidefinite (X ⪰ 0) if and only if: This condition is equivalent to all eigenvalues being non-negative: λᵢ(X) ≥ 0 for all i. The set of all positive semidefinite matrices forms a convex cone in the space of symmetric matrices, which is the foundation of SDP's tractability. 3. Linear Programming as a Special Case Every linear program can be expressed as a semidefinite program by using diagonal matrices. This is equivalent to the SDP: where diag(x) is the diagonal matrix with x on the diagonal. Eigenvalue Optimization: Minimize the largest eigenvalue of a matrix-valued function: This can be reformulated as an SDP by introducing a scalar t: Matrix Completion: Given partial observations of a matrix, find the lowest-rank matrix consistent with the observations. This has applications in collaborative filtering, system identification, and quantum state tomography. 5. Interior Point Methods for SDP

This is the written version of the interactive lesson above. See the full Optimization course.