Week 5: Semidefinite Programming — Adv. Optimization

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:

\min_X &\quad \langle C, X \rangle = \operatorname{tr}(C^T X) = \sum_{i,j} C_{ij} X_{ij} \\ \text{s.t.} &\quad \langle A_i, X \rangle = b_i, \quad i = 1, \ldots, m \\ &\quad X \succeq 0 \end{aligned}$$ 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. <Exercise type="multiple-choice" question="Which of these $2 \times 2$ matrices is PSD?" options={["$\\begin{pmatrix} 1 & 2 \\\\ 2 & 1 \\end{pmatrix}$", "$\\begin{pmatrix} 3 & 1 \\\\ 1 & 1 \\end{pmatrix}$", "$\\begin{pmatrix} -1 & 0 \\\\ 0 & -1 \\end{pmatrix}$", "$\\begin{pmatrix} 0 & 1 \\\\ 1 & 0 \\end{pmatrix}$"]} correctIndex={1} explanation="$\begin{pmatrix} 3 & 1 \\\\ 1 & 1 \end{pmatrix}$ has trace $4 > 0$ and determinant $3-1 = 2 > 0$, so PSD. The first has determinant $-3$ (indefinite); the third is negative definite; the fourth has eigenvalues $\pm 1$." /> <Quiz questions={[ { type: "fill-blank", question: "In SDP standard form, the decision variable is a symmetric ____, constrained to be PSD.", correctAnswer: "matrix", explanation: "The variable is $X \in \mathbb{S}^n$ with $X \succeq 0$, and the objective is linear: $\langle C, X \rangle$." }, { type: "multiple-choice", question: "Why is the rank-1 constraint $X = xx^T$ dropped in SDP relaxations?", options: ["It is redundant", "It makes the problem nonconvex", "It is always satisfied by the SDP solution", "It only applies to LP"], correctIndex: 1, explanation: "The rank-1 constraint is nonconvex. Dropping it yields a convex SDP relaxation that provides a lower bound. If the solution happens to be rank-1, the relaxation is exact." }, { type: "multiple-choice", question: "A $2 \times 2$ symmetric matrix $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$ is PSD if and only if:", options: ["$a > 0$ and $c > 0$", "$a \geq 0$, $c \geq 0$, and $ac \geq b^2$", "$ac \geq b^2$ alone", "$a + c \geq 0$"], correctIndex: 1, explanation: "For a $2 \times 2$, PSD requires nonnegative diagonal entries ($a \geq 0, c \geq 0$) and nonnegative determinant ($ac - b^2 \geq 0$)." } ]} /> ## 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. ```python 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}") ```

← Previous

Week 4: LP, QP, and Conic Form

Week 6: Interior-Point Methods

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:

\min_X &\quad \langle C, X \rangle = \operatorname{tr}(C^T X) = \sum_{i,j} C_{ij} X_{ij} \\ \text{s.t.} &\quad \langle A_i, X \rangle = b_i, \quad i = 1, \ldots, m \\ &\quad X \succeq 0 \end{aligned}$$ 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. <Exercise type="multiple-choice" question="Which of these $2 \times 2$ matrices is PSD?" options={["$\\begin{pmatrix} 1 & 2 \\\\ 2 & 1 \\end{pmatrix}$", "$\\begin{pmatrix} 3 & 1 \\\\ 1 & 1 \\end{pmatrix}$", "$\\begin{pmatrix} -1 & 0 \\\\ 0 & -1 \\end{pmatrix}$", "$\\begin{pmatrix} 0 & 1 \\\\ 1 & 0 \\end{pmatrix}$"]} correctIndex={1} explanation="$\begin{pmatrix} 3 & 1 \\\\ 1 & 1 \end{pmatrix}$ has trace $4 > 0$ and determinant $3-1 = 2 > 0$, so PSD. The first has determinant $-3$ (indefinite); the third is negative definite; the fourth has eigenvalues $\pm 1$." /> <Quiz questions={[ { type: "fill-blank", question: "In SDP standard form, the decision variable is a symmetric ____, constrained to be PSD.", correctAnswer: "matrix", explanation: "The variable is $X \in \mathbb{S}^n$ with $X \succeq 0$, and the objective is linear: $\langle C, X \rangle$." }, { type: "multiple-choice", question: "Why is the rank-1 constraint $X = xx^T$ dropped in SDP relaxations?", options: ["It is redundant", "It makes the problem nonconvex", "It is always satisfied by the SDP solution", "It only applies to LP"], correctIndex: 1, explanation: "The rank-1 constraint is nonconvex. Dropping it yields a convex SDP relaxation that provides a lower bound. If the solution happens to be rank-1, the relaxation is exact." }, { type: "multiple-choice", question: "A $2 \times 2$ symmetric matrix $\begin{pmatrix} a & b \\ b & c \end{pmatrix}$ is PSD if and only if:", options: ["$a > 0$ and $c > 0$", "$a \geq 0$, $c \geq 0$, and $ac \geq b^2$", "$ac \geq b^2$ alone", "$a + c \geq 0$"], correctIndex: 1, explanation: "For a $2 \times 2$, PSD requires nonnegative diagonal entries ($a \geq 0, c \geq 0$) and nonnegative determinant ($ac - b^2 \geq 0$)." } ]} /> ## 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. ```python 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}") ```