Semidefinite Programming
Semidefinite programming optimizes a linear objective over symmetric matrices constrained to be positive semidefinite, generalizing linear programming.
The problem class
A semidefinite program (SDP) minimizes a linear function of a symmetric matrix variable X, subject to linear equality constraints on X and the requirement that X be positive semidefinite, written X >= 0, meaning all its eigenvalues are nonnegative. The objective and constraints are linear in the matrix entries; the only nonlinearity is the eigenvalue condition, which defines a convex cone.
A hierarchy of cones
SDP sits at the top of a nested family of tractable convex programs. Linear programming optimizes over the nonnegative orthant; second-order cone programming over the ice-cream cone; semidefinite programming over the cone of positive semidefinite matrices. Each contains the previous as a special case, so an SDP solver can handle LP and SOCP problems, at higher computational cost.
What it can express
The positive-semidefinite constraint encodes a surprising range of conditions: bounds on the largest eigenvalue of a matrix, that a polynomial is a sum of squares (hence nonnegative), Lyapunov stability of a linear system, and moment constraints in probability. This expressiveness makes SDP central to control theory, combinatorial relaxations, and robust and polynomial optimization.
- Eigenvalue optimization: minimize the largest eigenvalue of a matrix
- Sum-of-squares certificates for polynomial nonnegativity
- Lyapunov and LMI conditions for control-system stability
- Relaxations of hard combinatorial problems such as MAX-CUT
Solving and scaling
SDPs are solved to high accuracy by interior-point methods, which are reliable but scale poorly because each iteration handles a dense matrix; large instances instead use first-order methods (ADMM-based solvers) or exploit sparsity and low-rank structure. The Goemans-Williamson MAX-CUT algorithm shows the payoff: an SDP relaxation plus randomized rounding gives a provable approximation guarantee for a hard combinatorial problem that no simpler relaxation matches.