Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 65 / 4 / b

The fidelity norm here is unsquared, as in the original PDF. Write $(s{)}_{+}=\max (s,0)$, so $h(Gu)={\sum }_i((Gu{)}_i{)}_{+}^2$. Introduce $a,q\in {\mathbb{R}}^n$ and $t\in \mathbb{R}$. The second-order cone reformulation of one-sided quadratic denoising issubject to the affine cone constraintswhere ${\mathcal{Q}}_d=\{(r,z):r\ge \Vert z{\Vert }_2\}$ is the second-order cone. All coordinates displayed inside the cone memberships are affine in the optimization variables, so stacking them has precisely the form $Ax-b\in K$. The first cone enforces $t\ge \Vert u-g{\Vert }_2$, and each three-dimensional cone enforces $q_i\ge a_i^2$. The two scalar inequalities give $a_i\ge ((Gu{)}_i{)}_{+}$.

Every feasible lift therefore has objective at least the original objective. Conversely, for any $u$, choose $a_i=((Gu{)}_i{)}_{+}$, $q_i=a_i^2$ and $t=\Vert u-g{\Vert }_2$ to attain equality. Thus the reformulation is exact. It is a second-order cone program over the product $K={\mathcal{Q}}_{n+1}\times {\mathcal{Q}}_3^n\times {\mathbb{R}}_{+}^{2n}$, a proper closed self-dual cone. It preserves the asymmetric derivative penalty; replacing it by $\Vert Gu{\Vert }^2$ would change the problem.

The canonical Lorentz-cone barrier is $-\log (r^2-\Vert z{\Vert }^2)$ on $r>\Vert z\Vert$, and each orthant coordinate contributes $-\log s$. Their sum, composed with the affine slack map, isIts domain explicitly requires $t>\Vert u-g\Vert$, $q_i>a_i^2$, $a_i>0$ and $a_i>(Gu{)}_i$; the positive Lorentz branch must not be inferred merely from positivity of a squared expression. The barrier parameter of the product-cone barrier is $\boxed{\nu =4n+2}$, with two per Lorentz block and one per scalar orthant slack. A strict feasible lift can always be obtained by choosing $a$ above both bounds, $q$ above $a^2$, and $t$ above the fidelity norm.