Semidefinite Programming

A correlation matrix built by stitching together pairwise correlations estimated at different times, or from illiquid instruments with stale prices, can end up mathematically broken: it fails to be a valid correlation matrix at all, even though every individual entry looks like a normal correlation between −1 and 1. Specifically, it can have a negative eigenvalue, which would imply some portfolio has negative variance — nonsense. Fixing this isn't a matter of optimizing over a handful of numbers; it's an optimization problem where the variable itself is a whole matrix, constrained to always stay a legitimate covariance-like object. Semidefinite programming (SDP) is exactly the framework for optimizing over matrices under that constraint.

The analogy: sculpting clay that must always stand up

Ordinary optimization variables are just numbers or vectors, free to take any values respecting some constraints. In SDP, the variable is a matrix, and it must remain positive semidefinite at every step — informally, "physically sensible as a covariance matrix," meaning every possible portfolio built from it has non-negative variance. Think of sculpting a piece of clay that must, at every stage of the sculpting, still be able to stand upright under its own weight: you can reshape it freely, but certain shapes (the equivalent of a matrix with a negative eigenvalue) are simply off-limits, no matter how tempting they'd be to reach a better "objective."

The mechanics, one symbol at a time

A matrix $X$ is positive semidefinite (written $X \succeq 0$) if $\mathbf{v}^\top X \mathbf{v} \ge 0$ for every vector $\mathbf{v}$ — equivalently, all its eigenvalues are non-negative. A semidefinite program is

$$\min_{X} \; \langle C, X \rangle \quad \text{subject to} \quad \langle A_i, X \rangle = b_i \; (i=1,\dots,m), \quad X \succeq 0,$$

where $\langle C,X\rangle = \operatorname{trace}(C^\top X)$ is a matrix inner product playing the role of a linear objective, and the $A_i$ constraints are linear equations on the entries of $X$. In plain English: minimize a linear function of a matrix's entries, subject to some linear equations the matrix must satisfy, while never letting the matrix leave the set of matrices that are legitimately "covariance-shaped" (no negative eigenvalues) — the SDP analogue of the vector constraint $\mathbf{x}\ge0$ in linear programming, but for the entire eigenvalue spectrum of a matrix at once.

Worked example 1: checking positive semidefiniteness by hand

Is $X = \begin{pmatrix}1 & 0.9\\0.9 & 1\end{pmatrix}$ (implied correlation 0.9) a valid correlation matrix? Its eigenvalues solve $(1-\lambda)^2 - 0.81 = 0$, giving $\lambda = 1\pm0.9$, i.e. $\lambda_1=1.9,\ \lambda_2=0.1$ — both non-negative, so $X\succeq0$: valid. Now try $X' = \begin{pmatrix}1 & 1.2\\1.2 & 1\end{pmatrix}$ (a correlation "of 1.2," an error a naive pairwise-fill could produce): eigenvalues solve $(1-\lambda)^2 - 1.44=0$, giving $\lambda=1\pm1.2$, i.e. $\lambda_1=2.2,\ \lambda_2=-0.2$ — negative! $X'$ is not positive semidefinite and cannot be a genuine correlation matrix, even though 1.2 might have slipped through as "just a large correlation" if no one checked the eigenvalues.

Worked example 2: the nearest valid correlation matrix

Given the broken $X'$ above, the nearest-correlation-matrix problem finds the closest (in matrix distance) positive semidefinite matrix with 1's on the diagonal. A quick approximate fix: clip the negative eigenvalue to zero, reconstruct, then rescale the diagonal back to 1. Using $\lambda_2=-0.2\to0$ and keeping $\lambda_1=2.2$ with its eigenvector $(1/\sqrt2,1/\sqrt2)$, the reconstructed (rank-1) matrix is $2.2 \times \begin{pmatrix}0.5&0.5\\0.5&0.5\end{pmatrix} = \begin{pmatrix}1.1&1.1\\1.1&1.1\end{pmatrix}$; rescaling the diagonal to 1 gives off-diagonal $1.1/1.1 = 1.0$ — so this crude version repairs the matrix to a correlation of exactly 1 here (an extreme case reflecting only one surviving eigenvalue); a full SDP solver does this more carefully, finding the true nearest valid correlation matrix (typically a correlation somewhat below the broken 1.2, not exactly 1) while respecting every constraint simultaneously rather than a rough clip-and-rescale.

Try entries like (1, 1.2, 1.2, 1) to see a transformation with a negative-eigenvalue direction — the unit circle maps to a shape that inverts along one axis, the geometric signature of a matrix that has left the positive-semidefinite set entirely.

What this means in practice

SDP is the standard tool for repairing correlation and covariance matrices assembled from asynchronous or noisy data (the nearest-correlation-matrix problem), for robust portfolio optimization where worst-case risk over a set of plausible covariance matrices must be bounded, and for relaxations of otherwise hard combinatorial problems (like certain risk-budgeting or clustering formulations) into a tractable convex form. Any time "this matrix must remain a valid covariance/correlation matrix throughout an optimization" is a real requirement, SDP is the right framework rather than an ad hoc patch.