Semidefinite Programming Relaxation

Core Idea

Semidefinite programming (SDP) extends linear programming by optimizing a linear objective over the cone of positive semidefinite matrices. SDP relaxations produce tighter bounds than LP relaxations for many combinatorial optimization problems. The landmark result is the Goemans-Williamson algorithm for MAX-CUT: relax binary variables to unit vectors, solve the SDP to find an optimal vector configuration, then round using a random hyperplane. This achieves an approximation ratio of ~0.878, which is optimal assuming the Unique Games Conjecture. SDP relaxations also yield the best known approximations for graph coloring, MAX-SAT, and constraint satisfaction problems, and the integrality gaps of SDP hierarchies (Lasserre, Sum-of-Squares) connect to fundamental questions in computational complexity.

Explainer

Linear programming relaxation, which you studied in approximation algorithms, replaces integer variables with continuous ones. Semidefinite programming relaxation is a more powerful generalization that replaces scalar variables with matrix variables constrained to be positive semidefinite. This extra structure captures pairwise relationships between variables — correlations, angles, inner products — that linear constraints cannot express. The result is tighter relaxations and better approximation ratios for many combinatorial problems.

The Goemans-Williamson algorithm for MAX-CUT is the most celebrated application. The integer program assigns each vertex a value in {-1, +1}, and the cut value is sum_{(i,j)} (1 - x_i * x_j) / 2. The SDP relaxation replaces scalars x_i with unit vectors v_i in R^n and optimizes sum_{(i,j)} (1 - v_i dot v_j) / 2 subject to |v_i| = 1. This can be reformulated as optimizing over a positive semidefinite matrix Y with Y_ii = 1 and Y_ij = v_i dot v_j. The SDP optimum is at least the integer optimum. The rounding step chooses a random hyperplane through the origin and assigns vertices to sides based on which side their vector falls on. The probability of separating v_i and v_j is arccos(v_i dot v_j) / pi, and the worst-case ratio of this probability to the SDP contribution (1 - v_i dot v_j)/2 is approximately 0.878.

The 0.878 ratio is remarkable because it is optimal under the Unique Games Conjecture: no polynomial-time algorithm can do better unless the conjecture fails or P = NP. This creates a tight connection between the algebraic structure of the SDP relaxation (its integrality gap) and the computational complexity of the problem (its hardness of approximation). For MAX-CUT, these match at ~0.878. For MAX-2SAT, the optimal ratio is ~0.940, again achieved by SDP rounding. The Unique Games Conjecture predicts this pattern extends broadly: the SDP integrality gap is the correct answer for many constraint satisfaction problems.

SDP hierarchies — the Lasserre hierarchy, Sum-of-Squares (SoS) — systematically strengthen SDP relaxations by adding higher-order moment constraints. After O(n) levels, the Lasserre hierarchy captures the integer hull exactly (but at exponential cost). The research frontier asks: how many levels suffice for good approximations? The Sum-of-Squares hierarchy has emerged as a unifying framework connecting approximation algorithms, proof complexity, and machine learning, with applications ranging from planted clique detection to tensor decomposition.