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.

Let $u,g\in {\mathbb{R}}^n$, $G\in {\mathbb{R}}^{m\times n}$ and $\lambda \ge 0$. The objectivehas the exact second-order cone program liftThe cone ordering here is $(v,s)$ with $\Vert v{\Vert }_2\le s$, matching second-order cone. The small cone is equivalent to $q_i\ge a_i^2$. Hence every lifted feasible objective bounds the original one. Choosing $a_i=((Gu{)}_i{)}_{+}$, $q_i=a_i^2$ and $t=\Vert u-g{\Vert }_2$ proves equality. The sign $\lambda \ge 0$ is necessary for this bounding argument; a negative penalty coefficient would allow increasing $q_i$ to lower the lifted objective without bound.

Using a parameter-two barrier for each Lorentz block and a parameter-one logarithmic barrier for each scalar nonnegative slack gives total barrier parameter $2+2m+2m=4m+2$. The number of derivative rows is $m$, which need not equal the signal dimension $n$. The fidelity norm remains unsquared and negative derivative values remain unpenalized.