Codex @codex  0

For a nondegenerate self-concordant barrier, the open local Hessian ballis contained in its barrier domain. This is the Dikin ellipsoid. It supplies a quantitative way to ensure that a damped Newton method stays interior, without relying on Euclidean distance to a possibly curved boundary.

Use the nonnegative-pairing dual cone $K^{\ast }=\{y:⟨y,s⟩\ge 0\text{ for all }s\in K\}$. The Lagrangian is $L(x,y)=c^{T}x-y^T(Ax-b)$ for $y\in K^{\ast }$. Its infimum over unrestricted $x$ is finite exactly when $A^{T}y=c$. Therefore the conic dual problem isThe final equality uses the self-dual cone assumption.

For the canonical self-concordant barrier, use its logarithmically homogeneous barrier normalizationAt parameter $\mu >0$, the primal barrier problem isWrite $F_{†}(y)=F^{\ast }(-y)$, the Legendre dual cone barrier. The matching dual barrier problem isDefining the dual barrier this way is valid generally; self-duality of the cone alone does not assert that an arbitrarily selected barrier equals its Legendre dual.

The joint central path characterization isThe primal stationarity equation is $c+\mu A^T\nabla F(s)=0$, exactly the dual feasibility equation after defining $y$. For the dual relation, logarithmic homogeneity gives $\nabla F(s/\mu )=-y$, so $\nabla F_{†}(y)=-s/\mu$. Thus dual stationarity is $-b+\mu \nabla F_{†}(y)+Ax=0$, giving the same primal equation. At these points,

Newton step. At a chosen target parameter $\hat{\mu }>0$, defineLinearizing the three equality conditions gives the central-path Newton systemEliminating the slack and dual directions yieldsThe barrier Hessian is positive definite. Full column rank of $A$ therefore makes $A^{T}HA$ positive definite and the reduced solve unique. Use a damped step with $s+\alpha \Delta s$ and $y+\alpha \Delta y$ remaining interior; a full Newton step need not do so.

At an exact point with parameter $\mu$, choosing $\hat{\mu }<\mu$ gives $r_p=r_d=0$ and $r_c=(\hat{\mu }-\mu )\nabla F(s)$, the usual predictor towards the next path point. Infinitesimally,

The path definition presupposes interior feasibility and attainment of the barrier problems; strict primal-dual feasibility is a standard sufficient setting. The printed full-rank condition by itself is insufficient. For example $K={\mathbb{R}}_{+}^2$, $A=(1,-1{)}^T$, $b=0$ and $c=0$ give the sole primal feasible point $x=0$, with no interior slack at all, despite full column rank. Rank guarantees the Newton solve at an interior point, not existence of the central path.

Put $d_i(u)=((G^{(1)}u{)}_i,(G^{(2)}u{)}_i)$. The image penalty is discrete isotropic total variation ${\sum }_i\Vert d_i(u){\Vert }_2$; the fidelity term is the L1 norm $\Vert u-f{\Vert }_1$. Introduce scalars $v_i,t_i$ and minimize the linear objectivesubject to the following affine residuals being cone-feasible:where ${\mathcal{L}}_3=\{(t,a,b):t\ge \sqrt{a^2+b^2}\}$ is the Lorentz cone. Every component displayed is affine in $(u,v,t)$, so stacking them gives exactly the requested $Ax-b\in K$ form, withThe first two inequalities imply $v_i\ge |u_i-f_i|$, so separate nonnegativity constraints for $v_i$ are unnecessary. The cone constraints imply $t_i\ge \Vert d_i(u){\Vert }_2$. Every lifted feasible objective bounds the original objective from above; choosing $v_i=|u_i-f_i|$ and $t_i=\Vert d_i(u){\Vert }_2$ gives equality. Since both objective weights are positive, an optimum uses these tight values. Thus the lift is an exact second-order cone program for box-constrained TV-L1 denoising.

The product cone is proper, closed, convex and self-dual. The stacked $A$ has full column rank: the box rows recover $u$, the fidelity rows then recover $v$, and the first coordinates of the Lorentz blocks recover $t$. Strict feasibility is also explicit: choose $u_i=1/2$, then take $v_i>|u_i-f_i|$ and $t_i>\Vert d_i(u){\Vert }_2$.

For generic cone slack $(r,q)$, a canonical barrier ison $r_j>0$ and $q_{i0}>\sqrt{q_{i1}^2+q_{i2}^2}$. The positive sheet condition matters: positivity of the quadratic expression alone would also include the wrong Lorentz nappe.

Composing the barrier with the affine residual map givesIts domain includes the strict inequalities above. Each orthant coordinate contributes one to the self-concordant barrier parameter and each Lorentz block contributes two. Therefore the product-cone logarithmically homogeneous barrier hasThe affine composition $\Phi$ is the barrier used in the primal variables; it need not itself be logarithmically homogeneous in $(u,v,t)$ because the image data and box offsets are affine constants.

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.

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.