Semidefinite programming

A semidefinite program optimizes a linear function subject to equalities between affine functions and positive semidefinite matrix inequalities. It generalizes linear programming: a diagonal matrix is a positive semidefinite matrix exactly when its diagonal entries are nonnegative. Matrix trace expresses the objective as $⟨C,X⟩=\mathrm{tr}(CX)$ for real symmetric matrices.

Replacing $x{x}^T$ by a general positive semidefinite matrix relaxes maximization of $\Vert x{\Vert }_2^2$ subject to $|a_i^{T}x|\le 1$. The relaxed value is an upper bound because $x{x}^T$ has trace $\Vert x{\Vert }_2^2$ and satisfies the same quadratic constraints. Both problems are unbounded if the $a_i$ fail to span the ambient space. If they span it, $H={\sum }_i{a}_i{a}_i^T$ is positive definite and ${\lambda }_{\min }(H)\mathrm{tr}X\le \mathrm{tr}(HX)\le m$, proving boundedness and attainment of the relaxation.

Use an orthogonal eigendecomposition $X=V\Lambda V^T$ and a vector $\xi$ of independent Rademacher random variables. Because $\Lambda$ is diagonal and ${\xi }_j^2=1$, every sign vector gives $\Vert \hat{x}{\Vert }_2^2=\mathrm{tr}X$, without taking an expectation. If the scaling denominator $M$ is positive, then $x$ satisfies every slab constraint and $\Vert x{\Vert }_2^2=\mathrm{tr}X/M^2$. Under spanning constraints and positive trace, $M>0$ automatically. A nonzero $\hat{x}$ with $M=0$ instead certifies an unbounded direction.

For spanning slab normals, apply the maximum of finitely many Rademacher linear forms bound to $u_i=(V{\Lambda }^{1/2}{)}^T{a}_i$, whose squared norms are $a_i^{T}X{a}_i\le 1$. Some sign vector has scaling denominator squared at most $2\log (2m)$. Rademacher rounding for a semidefinite relaxation then produces a feasible vector of squared norm at least the displayed fraction of the SDP optimum. This is an existence guarantee from the probabilistic method.