Semidefinite Programming

Some hard choices become easy one dimension up. SDP lifts vectors into matrices, trades the rank cliff for a curved cone, and bounds the original.

The PSD cone curves upward with definite interiors, singular boundaries, and infeasible outsides holding negative eigenvalues

Why Does This Exist?

Max-Cut, community detection, and robust control are NP-hard or non-convex in native variables. Branch-and-bound dies past hundreds of nodes. SDP lifts $x$ into $X = xx^\\top$ , drops the rank-1 cliff to $X \\succeq 0$ , and solves the curved convex problem for a bound plus a roundable solution.

Form: minimize $C \\bullet X$ over $A_i \\bullet X = b_i$ , $X \\succeq 0$ . Interior-point solves medium SDPs; first-order (ADMM, Burer-Monteiro) scales further. It generalizes linear programming from the nonnegative ray to the PSD cone within convex optimization.

The one idea you need first

$X \\succeq 0$ means all eigenvalues nonnegative: a curved cone, self-dual, with rank-1 matrices on extreme rays. Linear functions over it stay convex; the rank constraint is the only hard part, and SDP drops exactly it.

Think of It Like This

Shadows instead of sculptures

Carving the exact statue (rank-1) is hard. The SDP sculpts the shadow instead: a larger, smooth, convex shape containing every true shadow. Then it rounds the shadow back to a statue with a certified approximation ratio.

Goemans-Williamson cuts 87.8% of optimal from the shadow. Where it stops: shadows merge distinct statues, so rounding loses the gap. Tightness must be measured per instance.

How It Actually Works

Lift binary $x_i \\in \\{\\pm 1\\}$ to $X \\succeq 0$ with $X_{ii} = 1$ ; Max-Cut becomes $\\max \\tfrac{1}{4}L \\bullet X$ . Solve, factor $X = V^\\top V$ , round with random hyperplanes: expected 0.878 of optimum. Control LMIs $A^\\top P + PA \\prec 0$ certify stability. Burer-Monteiro factors $X = RR^\\top$ for large scale at the cost of non-convexity with benign landscape under rank excess.

Worked example

Triangle Max-Cut: 3 nodes, 3 edges, optimum cuts 2. SDP: $\\max \\sum_{i<j} (1 - X_{ij})/2$ ... normalized: optimum SDP value $2.25$ (vectors at 120 degrees, inner products $-1/2$ ). Ratio $2/2.25 \\approx 0.889$ above the 0.878 worst case. Rounding the 120-degree embedding with random hyperplanes cuts 2 edges with probability $3 \\times (2/3) \\times (1/3) \\times 2$ ... directly: each edge cut with probability $\\arccos(-1/2)/\\pi = (2\\pi/3)/\\pi = 2/3$ , expected cut $3 \\times 2/3 = 2$ . Bound 2.25, rounded 2, certificate in hand.

Code

1import numpy as np2
3inner = -0.5  # 120-degree SDP embedding4p_cut = float(np.arccos(inner) / np.pi)  # edge cut prob5print(round(p_cut, 3))  # -> 0.6676print(round(3 * p_cut, 2))  # -> 2.0

Edge probability 0.667 times 3 edges gives expected cut 2.0 against SDP bound 2.25.

Watch Out For

Rounding without measuring the gap

SDP bound 2.25 with rounded 1.5 is a 33% gap, not a certificate of near-optimality. Teams report the bound as the achievement and deploy the weak rounding.

Always report both: bound and feasible rounded value. If the gap yawns, tighten (more constraints) or round smarter.

Scaling interior-point past its weight

Dense SDPs beyond a few thousand dimensions exhaust interior-point memory ( $O(n^6)$ naive). Pushing anyway swaps to disk and stalls for days.

Use ADMM, sketching, or Burer-Monteiro past medium scale. If factor iterations outrun evidence, the solver choice is the bug.

The Quick Version

SDP lifts to $X \\succeq 0$ , drops rank, solves the curved convex bound.
Triangle Max-Cut: bound 2.25, rounded 2.0, ratio 0.889 above 0.878 worst case.
Random-hyperplane rounding converts embeddings to cuts with certified expectation.
LMIs certify control stability in the same cone.
Report bound and rounded values together, never the bound alone.
Scale past medium with first-order or factored methods.