Semidefinite Programming

Semidefinite programming (SDP) is a subfield of convex optimization in which the decision variable is a symmetric matrix constrained to be positive semidefinite, and the objective and constraints are linear in that matrix. It generalizes linear programming and provides the most powerful known framework for polynomial-time approximation of hard combinatorial problems. The geometry of the semidefinite cone — the set of matrices with nonnegative eigenvalues — is what makes SDP both computationally tractable and expressively richer than linear programming.

SDP is the workhorse of modern control theory: certifying stability via Lyapunov functions, designing controllers, and bounding structured singular values all reduce to SDPs. It also underlies the sum-of-squares relaxation for polynomial optimization and the Goemans-Williamson algorithm for MAX-CUT — one of the most elegant approximation algorithms in theoretical computer science.

The expressive power of semidefinite programming is also its epistemic danger: the ability to encode hard problems as SDPs tempts researchers to treat the relaxation as if it were the problem, rather than an approximation with its own geometry.