Second-order cone programming

A second-order cone program has a linear objective and affine constraints taking values in products of second-order cones and nonnegative orthants. Norm epigraphs have the form $(t,z)\in \mathcal{Q}$; quadratic epigraphs admit the affine lift $((q+1)/2,(q-1)/2,a)\in {\mathcal{Q}}_3$, equivalent to $q\ge a^2$. Product-cone self-concordant barriers give interior-point methods.

The objective $\Vert u-g{\Vert }_2+\lambda {\sum }_i((Gu{)}_i{)}_{+}^2$ has the exact lift $\min t+\lambda {\sum }_i{q}_i$ with $(t,u-g)\in {\mathcal{Q}}_{n+1}$, $((q_i+1)/2,(q_i-1)/2,a_i)\in {\mathcal{Q}}_3$, $a_i\ge 0$ and $a_i\ge (Gu{)}_i$. Every lifted feasible value bounds the original objective, and choosing tight epigraph variables proves equality. The product-cone barrier parameter is $4n+2$: two for each Lorentz block and one for each orthant slack. The fidelity norm remains unsquared, and negative derivatives remain unpenalized.