To understand semidefinite programming, we first need to define positive semidefinite matrices. Let $x \in \mathbb{R}^{n}$.
- $\mathcal{S}_n$ is the set of $n \times n$ symmetric matrices.
- A symmetric matrix $X \in \mathcal{S}_n$ is positive semidefinite (PSD) if $x^T X x \ge 0$ for all $x \in \mathbb{R}^n$.
- For $A, B \in \mathcal{S}_n$, the inner product is $\langle A, B \rangle = \operatorname{tr}(A^T B)$.
The following are equivalent for $X \in \mathcal{S}_n$:
- $X$ is positive semidefinite.
- All eigenvalues of $X$ are non-negative.
- $X = V^T V$ for some $V \in \mathbb{R}^{n \times n}$.
- $X = \sum\limits_{i=1}^{n} \lambda_i w_i w_i^T$ for $\lambda_i \ge 0$ and orthonormal vectors $w_i \in \mathbb{R}^n$.
A semidefinite program (SDP) is a mathematical program where the variables form a symmetric matrix and the objective and constraints are all linear in those entries. Equivalently, it is a linear program over semidefinite matrices. Formally:
Semidefinite Programming
Minimize or maximize $\sum\limits_{i,j} c_{ij} x_{ij}$
such that $\sum\limits_{i,j} a_{ijk_1} x_{ij} = b_{k_1}$ $\forall k_1$
$\sum\limits_{i,j} a_{ijk_2} x_{ij} \ge b_{k_2}$ $\forall k_2$
$\sum\limits_{i,j} a_{ijk_3} x_{ij} \le b_{k_3}$ $\forall k_3$
$X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{n1} & x_{n2} & \cdots & x_{nn} \end{pmatrix}$ is positive semidefinite.
For any two PSD matrices $X$ and $Y$, $x^TXx \ge 0$ and $x^TYx \ge 0$ for all $x$. Therefore $x^T(\lambda X + (1-\lambda)Y)x \ge 0$ for $0 \le \lambda \le 1$, meaning the set of PSD matrices is convex. This convexity is why an SDP can be solved in polynomial time.
The SDP above is equivalent to the vector program below when $X = V^TV$. Since $X$ is positive semidefinite, such a $V$ always exists. If $V = \begin{pmatrix} v_1, v_2, \ldots, v_n \end{pmatrix}$, then $X = \begin{pmatrix} \langle v_1, v_1 \rangle & \langle v_1, v_2 \rangle & \cdots \\ \vdots & \ddots & \vdots \\ \cdots & \cdots & \langle v_n, v_n \rangle \end{pmatrix}$. This equivalent form is called a vector program since the variables are vectors.
Vector program
Minimize or maximize $\sum\limits_{i,j} c_{ij} <v_i, v_j>$
such that $\sum\limits_{i,j} a_{ijk_1} <v_i, v_j>$ $=$ $b_{k_1}$ $\forall k_1$
$\sum\limits_{i,j} a_{ijk_2} <v_i, v_j>$ $\ge$ $b_{k_2}$ $\forall k_2$
$\sum\limits_{i,j} a_{ijk_3} <v_i, v_j>$ $\le$ $b_{k_3}$ $\forall k_3$
Note that the number of vertices equals the dimension of each vector variable.