Semidefinite Programming — Mathematics Knowledge System

Overview

Semidefinite programming (SDP) is a subfield of convex optimization in which the variable is a symmetric matrix constrained to be positive semidefinite, and the objective is a linear function of that matrix. SDP generalizes linear programming and second-order cone programming, and has powerful applications in control theory, combinatorial optimization, quantum information, and machine learning. The existence of polynomial-time interior-point solvers makes SDP tractable in practice.

Intuition

In linear programming one optimizes over a vector in a polyhedral cone; in SDP one optimizes over a matrix in the cone of positive semidefinite matrices. The positive semidefinite cone is convex, so all the machinery of convex optimization applies — duality, optimality conditions, and efficient algorithms. The power of SDP comes from the fact that many hard combinatorial and control problems admit tight convex relaxations as SDPs.

Formal Definition

Definition

The standard primal SDP is to minimize a linear objective over the intersection of the positive semidefinite cone with an affine subspace.

\min_{X \in \mathbb{S}^n} \langle C, X \rangle \quad \text{subject to} \quad \langle A_i, X \rangle = b_i,\; i=1,\ldots,m,\quad X \succeq 0

Primal SDP

\langle C, X \rangle = \operatorname{tr}(C^T X)

Inner product on symmetric matrices

X \succeq 0 \iff v^T X v \geq 0 \text{ for all } v \in \mathbb{R}^n

Positive semidefinite constraint

\max_{y \in \mathbb{R}^m} b^T y \quad \text{subject to} \quad \sum_{i=1}^m y_i A_i \preceq C

Dual SDP

Notation

Notation	Meaning
$\mathbb{S}^n$	Space of n×n symmetric real matrices
$X \succeq 0$	X is positive semidefinite
$\langle C, X \rangle = \operatorname{tr}(C^T X)$	Matrix inner product (trace inner product)
$\mathbb{S}_+^n$	Cone of positive semidefinite matrices

Theorems

Theorem 1: Weak Duality

\langle C, X \rangle \geq b^T y \text{ for any primal feasible } X \succeq 0 \text{ and dual feasible } y

Theorem 2: Strong Duality (Slater's Condition)

\text{If Slater's condition holds (strictly feasible primal and dual), then the optimal values coincide and both optima are attained}

Theorem 3: Goemans–Williamson MAX-CUT Bound

\text{The SDP relaxation of MAX-CUT achieves an approximation ratio of at least } 0.878

Worked Examples

1
A 2×2 symmetric matrix is PSD iff its eigenvalues are non-negative.
$\begin{pmatrix} a & b \\ b & c \end{pmatrix} \succeq 0$
2
Equivalently, the leading principal minors are non-negative.
$a \geq 0 \quad \text{and} \quad ac - b^2 \geq 0$

✓ Answer

The constraints are a ≥ 0 and ac − b² ≥ 0.

Practice Problems

Hardfree response

Show that every linear program can be written as a semidefinite program.

Hardproof writing

Prove that the set of n×n positive semidefinite matrices forms a convex cone.

Common Mistakes

Common Mistake

Confusing positive semidefinite (⪰ 0) with positive definite (≻ 0)

PSD allows zero eigenvalues; PD requires all eigenvalues strictly positive. Slater's condition for SDP requires a PD interior point.

Common Mistake

Assuming strong duality always holds for SDP

Unlike LP, SDP can have a positive duality gap without Slater's condition. Both primal and dual Slater conditions are needed for zero gap and attainment.

Quiz

Semidefinite programming generalizes which of the following optimization classes?

Nonlinear programming onlyLinear programming and second-order cone programmingInteger programmingStochastic programming

What condition guarantees strong duality in SDP?

Linearity of objectiveCompactness of feasible setSlater's condition (strict feasibility)Uniqueness of solution

Historical Background

Semidefinite programming emerged as a unified framework in the early 1990s, building on earlier work in semidefinite relaxations and interior-point methods. Nesterov and Nemirovskii's 1994 monograph on interior-point polynomial algorithms provided the theoretical foundation. Vandenberghe and Boyd's influential 1996 SIAM Review survey brought SDP to a broad engineering and applied mathematics audience, showcasing its breadth of applications.

1979
Ellipsoid method for convex optimization established polynomial-time framework
Leonid Khachiyan
1988
Karmarkar-style interior-point methods extended to semidefinite constraints
Yurii Nesterov, Arkadi Nemirovskii
1996
Vandenberghe and Boyd publish definitive SDP survey in SIAM Review
Lieven Vandenberghe, Stephen Boyd
2000s
SDP relaxations become standard in combinatorial optimization (MAX-CUT, graph coloring)

Summary

SDP optimizes a linear objective over the cone of positive semidefinite matrices intersected with an affine subspace.
It generalizes LP and SOCP and is solvable in polynomial time via interior-point methods.
Strong duality holds under Slater's condition; the duality gap can be positive otherwise.
Applications include the Lovász theta function, MAX-CUT relaxations, control (LMI constraints), and quantum information.

References

BookVandenberghe, L. & Boyd, S. — Semidefinite Programming, SIAM Review 38(1), 1996, pp. 49–95
BookBen-Tal, A. & Nemirovskii, A. — Lectures on Modern Convex Optimization (2001), Chapter 4
BookBlekherman, G., Parrilo, P.A. & Thomas, R.R. — Semidefinite Optimization and Convex Algebraic Geometry (2013)
WebsiteWikipedia — Semidefinite programming
WebsiteMathWorld — Semidefinite Programming