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

Introduce the primal slack $s=Ax-b\in K$. The Lagrangian is $L(x,y)=c^{\top }x-⟨y,Ax-b⟩$, with $y\in K^{\ast }=K$. Minimizing over $x$ is finite only when $A^{\top }y=c$. Thus the conic dual problem isThe primal-dual gap at feasible points is $c^{\top }x-b^{\top }y=⟨s,y⟩\ge 0$. Self-duality specifies the multiplier cone; it does not alone guarantee feasible or bounded problems. The central-path discussion assumes primal and dual strict feasibility and a finite optimum. These additional existence conditions are not implied by the given full column rank of $A$.

Let $F$ be the canonical logarithmically homogeneous self-concordant barrier, with parameter $\nu$ and $F(ts)=F(s)-\nu \log t$. For each $\mu >0$, minimizing $c^{\top }x+\mu F(Ax-b)$ defines the primal central path. Its stationarity defines the dual path through $y=-\mu \nabla F(s)\in \mathrm{int}K$. The joint characterization isEuler's identity for logarithmic homogeneity gives $⟨s,\nabla F(s)⟩=-\nu$, so $\boxed{⟨s,y⟩=\nu \mu }$. The gap tends to zero as $\mu \downarrow 0$. If $F_{\ast }(y)={\sup }_{s\in \mathrm{int}K}[-⟨y,s⟩-F(s)]$ is the dual barrier, the equivalent dual relation is $s=-\mu \nabla F_{\ast }(y)$. A self-dual cone does not justify identifying two arbitrary primal and dual barrier functions without this relation.

For a target parameter $\bar{\mu }>0$, form residuals $r_p=Ax-b-s$, $r_d=A^{\top }y-c$ and $r_c=y+\bar{\mu }\nabla F(s)$. Linearization gives the central-path Newton systemFor a strictly feasible primal-dual iterate with $r_p=r_d=0$, elimination reduces it toThe barrier Hessian is positive definite and $A$ has full column rank, so the reduced matrix is positive definite. Alternatively a changing path parameter can be included as an additional linear term $\Delta \mu \nabla F(s)$; the displayed system instead fixes the new target parameter before solving.

This is an interior-point method because iterates stay in the cone interiors where the barrier and its gradient/Hessian are defined. A full Newton step need not do so. Use a fraction-to-boundary or backtracking step: decrease $\alpha >0$ until $s+\alpha \Delta s$ and $y+\alpha \Delta y$ lie in $\mathrm{int}K$, then enforce an appropriate barrier or residual decrease. Such a positive step exists because the current points are interior. Local barrier norms can also certify an interior step via the Dikin ellipsoid.

For a practical starting point, choose $e\in \mathrm{int}K$ and solve a conic phase-I problem, for example minimizing $t$ subject to $Ax-b+te\in K$ and $t\ge -1$. A large positive $t$ with an arbitrary $x$ gives a strictly feasible start for this auxiliary problem. A feasible point with $t<0$ certifies $Ax-b\in \mathrm{int}K$. If the original problem is strictly feasible, a small negative $t$ is feasible, so phase I can find such a certificate. A similar feasibility procedure handles the dual equality and interior. Alternatively an infeasible-start primal-dual method or homogeneous self-dual embedding starts with interior cone variables while allowing nonzero linear residuals, and can report infeasibility rather than presume an interior solution exists.

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.