Week 5: Semidefinite Programming

The PSD cone#

Let $\mathbb{S}^n$ denote the set of $n \times n$ real symmetric matrices. A matrix $X \in \mathbb{S}^n$ is positive semidefinite (PSD), written $X \succeq 0$, if:

$v^T X v \geq 0 \quad \forall v \in \mathbb{R}^n$

Equivalent characterisations:

• All eigenvalues of $X$ are $\geq 0$.
• All principal minors are $\geq 0$ (Sylvester's criterion for PD, extended for PSD).
• $X = L L^T$ for some $L$ (Cholesky factorisation exists when $X \succ 0$).

The set $\mathbb{S}^n_+ = \{X \in \mathbb{S}^n \mid X \succeq 0\}$ is the PSD cone — a closed, convex, pointed, full-dimensional cone in $\mathbb{S}^n$.

Proof of convexity. Let $X, Y \succeq 0$ and $\theta \in [0,1]$. For any $v$, $v^T (\theta X + (1-\theta)Y) v = \theta v^T X v + (1-\theta) v^T Y v \geq 0$ since both terms are $\geq 0$. The set is closed under nonnegative scaling and addition, forming a proper cone.

The PSD cone generalises the nonnegative orthant. For diagonal matrices, $X \succeq 0$ reduces to $x_i \geq 0$ — every diagonal entry must be nonnegative. The off-diagonal entries introduce coupling: $X \succeq 0$ requires $x_{ii} x_{jj} \geq x_{ij}^2$ for each $2 \times 2$ principal submatrix.

Worked PSD test — $2 \times 2$:

$X = \begin{pmatrix} a & b \\ b & c \end{pmatrix} \succeq 0 \iff a \geq 0,\; c \geq 0,\; ac - b^2 \geq 0$

• $X = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}$: eigenvalues $3, 1 \geq 0$, so PSD.
• $X = \begin{pmatrix} 1 & 3 \\ 3 & 1 \end{pmatrix}$: eigenvalues $4, -2$ — not PSD.
• $X = \begin{pmatrix} 0 & 0 \\ 0 & 0 \end{pmatrix}$: PSD (zero matrix is always PSD).

SDP standard form#

A semidefinite program (SDP) is:

where $C, A_i \in \mathbb{S}^n$ and $b \in \mathbb{R}^m$. The decision variable is the entire $n \times n$ matrix $X$, and the objective is linear in $X$ (the trace inner product). The single constraint $X \succeq 0$ is nonlinear and cone-shaped — it is the defining complexity of an SDP.

Why matrix variable? Many problems naturally involve matrix decisions — covariance estimation, experiment design, kernel matrix learning. The constraint $X \succeq 0$ enforces that covariance/kernel matrices are valid PSD.

LP as a special case. If we constrain $X$ to be diagonal, $\langle C, X \rangle = \sum_i C_{ii} X_{ii}$, and $X \succeq 0$ becomes $X_{ii} \geq 0$. Setting $c_i = C_{ii}$, $x_i = X_{ii}$, the SDP reduces to $\min c^T x$ s.t. $Ax = b$, $x \geq 0$ — a standard-form LP. Every LP is an SDP; SDPs are strictly more expressive.

Dual SDP. The Lagrangian dual of an SDP is also an SDP:

$\max_{y \in \mathbb{R}^m} \; b^T y \quad \text{s.t.} \quad C - \sum_{i=1}^m y_i A_i \succeq 0$

The dual variable $y$ has dimension $m$ (the number of equality constraints), and the dual constraint is a linear matrix inequality (LMI). This dual structure enables elegant theoretical guarantees.

Spectrahedra#

The feasible set of an SDP, $\{X \succeq 0 \mid \langle A_i, X \rangle = b_i\}$, is the intersection of an affine subspace with the PSD cone. In dual space, the feasible set $\{y \mid C - \sum y_i A_i \succeq 0\}$ is a spectrahedron — a set defined by a linear matrix inequality. Spectrahedra are convex sets that generalise polyhedra (which are defined by $x \geq 0$ rather than $X \succeq 0$).

Every polyhedron is a spectrahedron, but the converse is false. Spectrahedra can have curved boundaries described by polynomial inequalities (determinantal constraints), giving them richer geometry than polyhedra. This is why SDPs can model problems that LPs cannot.

Visualising spectrahedra in 3D. The set $\{(y_1, y_2, y_3) \mid \begin{pmatrix} 1 & y_1 & y_2 \\ y_1 & 1 & y_3 \\ y_2 & y_3 & 1 \end{pmatrix} \succeq 0\}$ is a convex body known as the $3 \times 3$ elliptope. Its boundary has smooth curved regions and sharp ridges where the matrix drops rank — a shape no polyhedron can produce.

Relaxations#

Many hard combinatorial problems become tractable convex programs via SDP relaxation. The core trick: replace a vector variable $x$ with a matrix variable $X = xx^T$.

Rank-1 lifting. Consider a quadratic problem:

$\min_{x \in \mathbb{R}^n} \; x^T C x \quad \text{s.t.} \quad x^T A_i x = b_i,\; x \in \{-1, 1\}^n$

The objective $x^T C x = \langle C, xx^T \rangle$, so define $X = xx^T$. Then $X \succeq 0$, $X$ has rank 1, and $X_{ii} = 1$ (since $x_i \in \{-1, 1\}$). The nonconvex rank-1 constraint is the source of hardness. Dropping it yields an SDP:

$\min_{X \succeq 0} \; \langle C, X \rangle \quad \text{s.t.} \quad \langle A_i, X \rangle = b_i,\; X_{ii} = 1$

This SDP provides a lower bound on the original problem. If the SDP solution happens to have rank 1, it is exact. In practice, rounding heuristics (e.g., random hyperplane rounding for Max-Cut) recover feasible solutions from the fractional SDP optimum with provable approximation guarantees.

Matrix completion. Given partially observed entries of a low-rank matrix, one can recover the full matrix by solving an SDP that minimises $\|X\|_*$ (nuclear norm, the sum of singular values) subject to matching observations. The nuclear norm is the convex envelope of rank — minimising it is an SDP relaxation of rank minimisation. This underlies recommendation systems and collaborative filtering.

When SDPs appear in learning#

SDPs are not a first-line tool in deep learning training, but they appear wherever structure matters:

• Kernel learning: learning a valid PSD kernel matrix $K$ from data reduces to an SDP.
• Covariance estimation: estimating a sparse inverse covariance (graphical Lasso) under PSD constraint.
• Robust PCA: separating a low-rank matrix from sparse corruption via SDP.
• Certification: SDPs can certify robustness of neural networks against adversarial perturbations, providing formal guarantees.

The pattern is the same: when your learning problem has a matrix decision variable that must be PSD, you are in SDP territory. The solver (IPM, Week 6) handles the constraint; your job is recognising when that constraint applies.

Knowledge Check#

Browser lab#

Check PSD status of several $3 \times 3$ matrices via eigenvalues. Implement spectral projection onto the PSD cone: zero out negative eigenvalues and reconstruct.

import numpy as np

def is_psd(M):
    """Check PSD by computing eigenvalues."""
    evals = np.linalg.eigvalsh(M)
    return np.all(evals >= -1e-10), evals

def project_psd(M):
    """Project symmetric M onto the PSD cone by zeroing negative eigenvalues."""
    evals, evecs = np.linalg.eigh(M)
    evals_pos = np.maximum(evals, 0)
    return evecs @ np.diag(evals_pos) @ evecs.T

# Test matrices
matrices = {
    "PSD": np.array([[2, 1, 0.5], [1, 2, 0.3], [0.5, 0.3, 1.5]]),
    "Indefinite": np.array([[1, 3, 0], [3, 1, 0], [0, 0, -0.5]]),
    "Negative definite": np.array([[-2, 0, 1], [0, -1, 0], [1, 0, -2]]),
    "Near-PSD (rank deficient)": np.array([[1, 1, 0], [1, 1, 0], [0, 0, 0.5]]),
}

for name, M in matrices.items():
    psd_flag, evals = is_psd(M)
    print(f"{name:30s} PSD={psd_flag}  evals={np.round(evals, 4)}")

print()

# Demonstrate projection onto PSD cone
print("Spectral projection onto PSD cone:")
M_inf = np.array([[1.0,  3.0, 0.0],
                  [3.0,  1.0, 0.0],
                  [0.0,  0.0, 1.0]])  # eigenvalues: 4, -2, 1

print("Original matrix:")
print(M_inf)
_, evals_orig = is_psd(M_inf)
print(f"Eigenvalues: {np.round(evals_orig, 4)}")

M_proj = project_psd(M_inf)
print("\nProjected matrix (negative eigenvalues zeroed):")
print(np.round(M_proj, 4))
_, evals_proj = is_psd(M_proj)
print(f"Eigenvalues: {np.round(evals_proj, 4)}")

# Verify projection is PSD
psd_flag_proj, _ = is_psd(M_proj)
print(f"\nProjected matrix is PSD: {psd_flag_proj}")

# Frobenius distance (minimal among all PSD matrices)
print(f"Frobenius distance ||M - proj(M)||_F = {np.linalg.norm(M_inf - M_proj, 'fro'):.4f}")

print("Notice: zeroing the negative eigenvalues is the nearest PSD matrix: the projection is PSD, at Frobenius distance 2.0000 from the indefinite input.")

Key takeaways#

• The PSD cone is convex. It generalises the nonnegative orthant: diagonal PSD is elementwise nonnegativity, with off-diagonal coupling added.
• An SDP has a matrix variable $X \succeq 0$ and a linear objective $\langle C, X \rangle$; every LP is the diagonal special case.
• The dual of an SDP is another SDP, with a linear matrix inequality $C - \sum_i y_i A_i \succeq 0$. Its feasible set is a spectrahedron, which can have curved boundaries no polyhedron can produce.
• Relaxation lifts a vector $x$ to a matrix $X = xx^T$ and drops the nonconvex rank-1 constraint. The SDP gives a lower bound, exact when the solution is rank 1.
• Nuclear-norm minimisation is the convex envelope of rank, which is why matrix completion is an SDP relaxation.
• SDPs appear in machine learning wherever a matrix decision must be PSD — kernel learning, covariance estimation, robust PCA, and robustness certification.

Further reading#

• Lieven Vandenberghe & Stephen Boyd, "Semidefinite Programming" (SIAM Review, 1996) — the canonical survey, freely available.
• Henry Wolkowicz, Romesh Saigal & Lieven Vandenberghe (eds.), Handbook of Semidefinite Programming (Springer, 2000) — theory, algorithms, and applications.
• Stephen Boyd & Lieven Vandenberghe, Convex Optimization (Cambridge University Press, 2004) — §4.6 introduces the SDP cone and spectrahedra.