Log-barrier central paths and primal-dual Newton residuals

For a $C^2$ inequality problem with the convention of Inequality constrained programs, tangent cones, constraint qualifications, and KKT, let $D\subseteq {\mathbb{R}}^n$ be open and convex, let $f_0,g_1,\dots ,g_m$ be convex $C^2$ functions on $D$, and let $A\in {\mathbb{R}}^{p\times n}$ and $b\in {\mathbb{R}}^p$. Assume there exists $x\in D$ with $Ax=b$ and $g_i(x)<0$ for every $i$. For $t>0$, its log-barrier objective is ${\mathrm{\Psi }}_t(x)=t{f}_0(x)-{\sum }_{i=1}^m\log (-g_i(x)),Ax=b,g_i(x)<0.$ Any attained minimizer is a central point. Its central multipliers are ${\lambda }_i=-1\mathrm{/}(t{g}_i(x))>0$. A central point and multiplier tuple satisfy $Ax=b$, $g(x)<0$, and $\mathrm{\nabla }{f}_0(x)+Dg(x{)}^T\lambda +A^T\nu =0$ for an equality multiplier $\nu$.

For the conic model of Conic, LP, and convex QP primal-dual models, let $s=h-Gx\in \mathrm{int}K$ and let $F$ be a self-concordant barrier on $K$. The conic barrier objective is ${\mathrm{\Phi }}_t(x)=t{c}^{T}x+F(h-Gx)$ restricted to $Ax=b$. An attained minimizer $x_t$ satisfies $tc-G^{\ast }\mathrm{\nabla }F(s_t)+A^{T}w=0,A{x}_t=b,s_t=h-G{x}_t\in \mathrm{int}K$ for some $w\in {\mathbb{R}}^p$. Its barrier multiplier is $z_t=-\mathrm{\nabla }F(s_t)\mathrm{/}t$.

For a standard-form LP or convex QP with $n\ge 1$, $Ax=b$, $x\ge 0$, and objective $f_0(x)=\frac{1}{2}{x}^{T}Qx+c^{T}x$ ($Q=0$ for an LP), define the primal-dual residuals $r_d=Qx+c-A^{T}y-s,r_p=Ax-b,r_c=Xs-\sigma \mu \mathbf{1},$ where $X=\mathrm{diag}(x)$, $S=\mathrm{diag}(s)$, $\mu =x^{T}s\mathrm{/}n$, and $0<\sigma <1$. For $x,s>0$, the modified KKT Newton direction solves $\left[\begin{array}{ccc}Q& -A^T& -I\\ A& 0& 0\\ S& 0& X\end{array}\right]\left[\begin{array}{c}\mathrm{\Delta }x\\ \mathrm{\Delta }y\\ \mathrm{\Delta }s\end{array}\right]=-\left[\begin{array}{c}{r}_d\\ r_p\\ r_c\end{array}\right]\mathrm{.}$

For orthant, Lorentz, or positive-semidefinite cone factors, define the diagnostic conic residuals as $r_p=Ax-b$, $r_d=A^{T}y-G^{\ast }z-c$, and $r_c=s\circ z-\sigma \mu e$. These factors are self-dual under their standard Euclidean or trace pairings by The orthant logarithmic barrier has parameter equal to its dimension, The Lorentz logarithmic barrier has parameter two, and The positive semidefinite cone is self-dual and its log determinant barrier has parameter n, so $s$ and $z$ occupy the same factor spaces. For the orthant, $\circ$ is coordinatewise multiplication and $e=\mathbf{1}$. The Lorentz Jordan product is $(t,u)\circ (q,v)=(tq+u^{T}v,tv+qu)$ with $e=(1,0)$; for symmetric matrices $X\circ S=(XS+SX)\mathrm{/}2$ with $e=I$. In each factor, pairing $s\circ z$ with $e$ gives $⟨s,z⟩$: this is the coordinate sum for the orthant, the first coordinate for the Lorentz product, and $\mathrm{tr}((XS+SX)\mathrm{/}2)=\mathrm{tr}(XS)$ for symmetric matrices by the finite-index trace identity. In each product cone, $\mu =⟨s,z⟩\mathrm{/}\nu$, where $\nu$ is the sum of the factor barrier parameters. This Jordan target is a diagnostic convention, not in general the centered residual for the selected barrier $F$: for a Lorentz factor $F(t,u)=-\log (t^2-\mathrm{\parallel }u{\mathrm{\parallel }}_2^2)$, $s\circ (-\mathrm{\nabla }F(s))=2e$, whereas the orthant and log-determinant barriers give $e$. Thus their barrier multipliers have factor targets $2e\mathrm{/}t$ and $e\mathrm{/}t$, respectively, although the product gap gives $\mu =1\mathrm{/}t$. No equivalence between $r_c=0$ and that barrier central path is asserted. When forming a Newton direction for this diagnostic target, hold $\sigma \mu$ fixed. The linearized slack is $\mathrm{\Delta }s=-G\mathrm{\Delta }x$.

Residual tolerances describe a candidate unless an independent argument also verifies feasibility and a primal-dual gap. A finite iteration or factorization budget that returns a candidate, failure, or inconclusive status is not itself an optimality certificate.