Short-step self-concordant path following with finite failure statuses

Let $K$ be a proper cone, $F$ a $\nu$-log-homogeneous self-concordant barrier on $\mathrm{int}K$, and consider $\min c^{T}x$ subject to $Ax=b$, $s=h-Gx\in K$. Require the barrier Hessian restricted to $\ker A$ to be positive definite, so the affine restriction has a local norm. The local calculus lemma proves that each barrier subproblem has an attained unique center whenever its Newton decrement is below one.

For a strict feasible $x$ with $Ax=b$, define the restricted local norm by $\mathrm{\parallel }d{\mathrm{\parallel }}_{t,x}=\sqrt{D^2{\mathrm{\Phi }}_t(x)[d,d]}$ for $d\in \ker A$. The decrement used below is the restricted dual norm ${\lambda }_t(x)=\sup \{\mathrm{\mid }D{\mathrm{\Phi }}_t(x)[d]\mathrm{\mid }:d\in \ker A,\mathrm{\parallel }d{\mathrm{\parallel }}_{t,x}\le 1\}\mathrm{.}$ Thus ${\lambda }_t(x)$ is induced by the barrier Hessian restricted to the feasible tangent space.

Inputs: $t_0>0$, target $\epsilon >0$, a strictly feasible $x_0$ with restricted decrement ${\lambda }_{t_0}(x_0)\le 1\mathrm{/}4$, integer caps $N_{out}\ge 0$ and $N_{in}\ge 2$, and an exact linear-system solver for the equality-constrained Newton equations. Output: a record with a status and optional iterate fields. gap-tolerance returns the feasible iterate $x$, current $t$, and certified gap bound $(\nu +\sqrt{\nu }\mathrm{/}2)\mathrm{/}t$. outer-cap, centering-cap, and newton-solve-failure return the last feasible iterate and current $t$ with no gap certificate. invalid-start returns no iterate and no gap certificate.

1. Verify $A{x}_0=b$, $h-G{x}_0\in \mathrm{int}K$, the stated initial decrement, and all cap/parameter conditions; otherwise return invalid-start. Set $x=x_0$, $t=t_0$, and both counters to zero.
2. While $(\nu +\sqrt{\nu }\mathrm{/}2)\mathrm{/}t>\epsilon$, first return outer-cap if the outer counter equals $N_{out}$. Set $\alpha =1+1\mathrm{/}(8\sqrt{\nu })$ and $t^{+}=\alpha t$.
3. At the current $x$, compute $\lambda ={\lambda }_{t^{+}}(x)$. While $\lambda >1\mathrm{/}4$ and the inner counter is below $N_{in}$, solve the restricted Newton equation $D^2{\mathrm{\Phi }}_{t^{+}}(x)[d,\cdot ]=-D{\mathrm{\Phi }}_{t^{+}}(x)[\cdot ]$ on $\ker A$. If the solve fails, return newton-solve-failure. Otherwise set $x\leftarrow x+d\mathrm{/}(1+\lambda )$, increment the inner counter, and recompute $\lambda$.
4. If $\lambda >1\mathrm{/}4$ after the inner loop, return centering-cap. Otherwise accept $t\leftarrow t^{+}$, increment the outer counter, reset the inner counter, and repeat step 2.
5. When the loop condition is false, return gap-tolerance with $x$, $t$, and bound $(\nu +\sqrt{\nu }\mathrm{/}2)\mathrm{/}t$.

The cap counts Newton corrections, not factorization operations. This definition does not construct a strict feasible start; a Phase-I certificate is a separate input obligation.