Conic, LP, and convex QP primal-dual models

For a finite-dimensional real inner-product space $E$, a cone is a set closed under addition and multiplication by nonnegative scalars. A cone $K\subset E$ is proper when it is closed, convex, pointed ($K\cap (-K)=\{0\}$), and has nonempty interior. Its dual cone is $K^{\ast }=\{z\in E:⟨z,s⟩\ge 0\text{ for every }s\in K\}\mathrm{.}$

Let $A:{\mathbb{R}}^n\to {\mathbb{R}}^p$ and $G:{\mathbb{R}}^n\to E$ be linear, let $b\in {\mathbb{R}}^p$, $c\in {\mathbb{R}}^n$, and $h\in E$. A matrix $A$ has full row rank when its rows are linearly independent. The conic primal problem and its displayed dual pair are $\inf \{c^{T}x:Ax=b,h-Gx\in K\},\sup \{b^{T}y-⟨h,z⟩:A^{T}y-G^{\ast }z=c,z\in K^{\ast }\},$ where $G^{\ast }$ is the adjoint, defined by $⟨Gx,z⟩=x^T{G}^{\ast }z$. For any feasible pair, its gap is $c^{T}x-b^{T}y+⟨h,z⟩=⟨z,h-Gx⟩\ge 0.$ The special case $\inf \{c^{T}x:Ax=b,x\in K\}$ has dual $\sup \{b^{T}y:A^{T}y+z=c,z\in K^{\ast }\}$ and gap $⟨z,x⟩$.

For $K={\mathbb{R}}_{+}^n$, the latter is the standard-form LP $\min c^{T}x$ subject to $Ax=b$, $x\ge 0$, with dual variables $y$ free and $s=c-A^{T}y\ge 0$. A convex QP in this convention has objective $f_0(x)=\frac{1}{2}{x}^{T}Qx+c^{T}x$, with symmetric $Q⪰0$, the same equality, and $x\ge 0$. Its Lagrangian is $L(x,y,s)=f_0(x)+y^T(b-Ax)-s^{T}x$; a feasible KKT tuple obeys $Qx+c-A^{T}y-s=0$, and its dual function is $q(y,s)={\inf }_{w\in {\mathbb{R}}^n}L(w,y,s)$. The dual value is $d^{\ast }={\sup }_{y\in {\mathbb{R}}^p,s\ge 0}q(y,s)$.

For a Lorentz cone ${\mathcal{L}}_{d+1}=\{(t,u)\in \mathbb{R}\times {\mathbb{R}}^d:t\ge \mathrm{\parallel }u{\mathrm{\parallel }}_2\}$, let $F_j\in {\mathbb{R}}^{d_j\times n}$, $f_j\in {\mathbb{R}}^{d_j}$, $g_j\in {\mathbb{R}}^n$, and $h_j\in \mathbb{R}$. Then $\mathrm{\parallel }{F}_{j}x+f_j{\mathrm{\parallel }}_2\le g_j^{T}x+h_j$ is membership of $(g_j^{T}x+h_j,F_{j}x+f_j)$ in ${\mathcal{L}}_{d_j+1}$. With no equality constraints, the SOCP $\min c^{T}x$ under these constraints has dual $\max -{\sum }_j(f_j^T{u}_j+h_j{\tau }_j)\text{subject to }{\sum }_j(F_j^T{u}_j+g_j{\tau }_j)=c,({\tau }_j,u_j)\in {\mathcal{L}}_{d_j+1}\mathrm{.}$ For symmetric matrices, $S⪰0$ means $v^{T}Sv\ge 0$ for every $v$ and the pairing is $⟨X,S⟩=X\bullet S:=\mathrm{tr}(XS)$. Thus $\min C\bullet X$ subject to $\mathcal{A}(X)=b$, $X⪰0$ has dual $\max b^{T}y$ subject to ${\mathcal{A}}^{\ast }y+S=C$, $S⪰0$, with gap $X\bullet S$. The affine-matrix SDP $\min c^{T}x$ subject to $F_0+{\sum }_i{x}_i{F}_i⪰0$ has dual $\max -F_0\bullet Z$ subject to $F_i\bullet Z=c_i$ for every $i$ and $Z⪰0$.

The smooth convex inequality convention is that of Inequality constrained programs, tangent cones, constraint qualifications, and KKT: inequalities are written $g_i(x)\le 0$ and their multipliers are nonnegative. The Lagrangian dual-value convention is that of Finite-dimensional convex program, Lagrangian dual, and Slater condition.