Quantum Information Theory

C Semidefinite programs

C.1 General form

We start with the simpler case of linear programs. A linear program (LP) is an optimization of a linear function over a set of real variables defined by linear constraints. The general form of an LP is

(C.1)$\begin{array}{rl}\underset{\mathit{x}}{\mathrm{infimum}}& \mathit{a}·\mathit{x}\\ \text{subject to}& \mathit{L}\mathit{x}\ge \mathit{b}\mathrm{,}\mathit{x}\ge 0\mathrm{,}\mathit{x}\in {\mathbb{R}}^{\mathit{n}}\mathrm{,}\end{array}$

with $\mathit{a}\in {\mathbb{R}}^{\mathit{n}}$, $\mathit{b}\in {\mathbb{R}}^{\mathit{m}}$, $\mathit{L}\in {\mathbb{R}}^{\mathit{m}\times \mathit{n}}$. The optimization is thus completely defined by the three parameters $\mathrm{(}\mathit{L}\mathrm{,}\mathit{a}\mathrm{,}\mathit{b}\mathrm{)}$. The constraints are given by a set of m inequalities to the variable vector $\mathit{x}\in {\mathbb{R}}^{\mathit{n}}$. The inequality is pointwise: ${\mathrm{(}\mathit{L}\mathit{x}\mathrm{)}}_{\mathit{j}}\ge {\mathit{b}}_{\mathit{j}}$ for the jth component of $\mathit{L}\mathit{x}$ and b, respectively, for all j. Equality conditions can be specified by pairs of inequalities, e. g., ${\mathit{x}}_0={\mathit{b}}_0$ by ${\mathit{x}}_0\ge {\mathit{b}}_0$ and $-{\mathit{x}}_0\ge -{\mathit{b}}_0$ for a given component.

If the resulting feasible set is closed, it forms a polytope. ...