Second-order cone

The second-order cone, also called the Lorentz cone, is

For $(u,s),(v,t)$ in the second-order cone, the Cauchy-Schwarz inequality gives $u\cdot v+st\ge -\Vert u\Vert \Vert v\Vert +st\ge 0$. Thus the cone is contained in its dual cone. Conversely, if $s<\Vert u\Vert$ and $u\ne 0$, pairing $(u,s)$ with $(-u/\Vert u\Vert ,1)$ is negative. If $u=0$ and $s<0$, use $(0,1)$. Every point outside the cone therefore lies outside its dual, proving that it is a self-dual cone.

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.

For $x=(u,t)$ and $\rho =\Vert u{\Vert }_2$,