Second-Order Cone & Semidefinite Programs

Swap the componentwise ordering of a linear program for an ice-cream cone, or for the positive semidefinite matrices.

The idea

Second-order cone programs and semidefinite programs generalize linear programming by changing what an inequality means. A linear program's constraint $Ax \preceq b$ is checked coordinate by coordinate; replace that componentwise comparison by membership in another convex cone and a much larger family of problems appears, still convex and still solvable by the same machinery. Two cones cover almost every case met in practice.

The first is the second-order cone $K = \{(y,t) : \|y\|_{2} \le t\}$.

Definition (Second-order cone program).

A second-order cone program (SOCP) minimizes a linear objective subject to constraints $\|A_{i}x + b_{i}\|_{2} \le c_{i}^{T}x + d_{i}$, each stating that an affine function of $x$ lies in $K$.

The second is the cone of positive semidefinite matrices.

Definition (Semidefinite program).

A semidefinite program (SDP) minimizes a linear objective subject to a linear matrix inequality $x_{1}F_{1} + \cdots + x_{n}F_{n} + G \preceq 0$, where the $F_{i}$ and $G$ are fixed symmetric matrices.

The left-hand side of the matrix inequality is affine in $x$, and the single matrix inequality encodes infinitely many scalar ones, since $M \succeq 0$ says $z^{T}Mz \ge 0$ for every vector $z$.

Proposition.

The classes nest, each a special case of the next: $\text{LP} \subseteq \text{QP} \subseteq \text{SOCP} \subseteq \text{SDP}.$

Recognizing that a problem can be written in one of these forms is what makes it solvable.

Ways to work on it

• Walkthrough. Cone constraints, robust linear programming, linear matrix inequalities, and the chain LP inside QP inside SOCP inside SDP.
• Proof. The Schur complement, by completing the square in block form — and the second-order cone as a linear matrix inequality.
• Practice. Recognize cone constraints, test linear matrix inequalities by hand, and place problems in the chain.
• Hardest. Minimizing the largest eigenvalue — an objective with no formula, handed to a solver as one matrix inequality.

Not sure where to start? Take the ten-question placement test.