SDP Relaxation

SDP relaxation replaces a hard nonconvex problem with a tractable semidefinite program by lifting variables into a matrix and dropping a rank constraint.

Lifting to matrices

Many hard problems are quadratic in binary or unit-norm variables. The lifting trick introduces a matrix X = x x^T to linearize the quadratic terms, since x^T Q x = trace(Q X). The matrix X x x^T is exactly the positive-semidefinite matrices of rank one. Keeping the positive-semidefinite condition but dropping the rank-one requirement gives a convex semidefinite program that lower-bounds (for minimization) the original.

The MAX-CUT example

MAX-CUT asks for a partition of a graph's vertices maximizing the weight of edges crossing the partition, with each vertex a variable in {-1, +1}. Writing the objective as a quadratic and lifting gives an SDP over a matrix with unit diagonal. The Goemans-Williamson algorithm solves this SDP, then rounds by a random hyperplane, achieving at least 0.878 of the optimum, a guarantee provably out of reach for the natural linear relaxation.

import numpy as np, cvxpy as cp

def maxcut_sdp(W):
    n = W.shape[0]
    X = cp.Variable((n, n), PSD=True)
    obj = cp.Maximize(0.25*cp.sum(cp.multiply(W, 1 - X)))
    prob = cp.Problem(obj, [cp.diag(X) == 1])
    prob.solve()
    return X.value   # relax rank-1; round with a random hyperplane

Rounding and the gap

The SDP solution is generally not rank one, so it must be rounded back to a valid discrete solution, typically by factoring X and projecting onto a random direction. The ratio between the rounded value and the SDP bound measures the relaxation's quality. A tight relaxation gives strong approximation guarantees; the Lasserre and Sum-of-Squares hierarchies add higher-order moment constraints to tighten it further at rising cost.

Why it is important

SDP relaxation is the strongest generally applicable convex relaxation for quadratic and polynomial problems, delivering approximation guarantees, certified bounds, and, in control and power systems, sometimes exact recovery. It is the tool of choice when a linear relaxation is too loose to be useful.