Short-step path following takes $O(\sqrt{\nu }\log (\nu \mathrm{/}(\epsilon t_0)))$ Newton steps

Log homogeneity gives $DF(x)[x]=-\nu$, $D^{2}F(x)[x,x]=\nu$, and $D^{3}F(x)[x,x,x]=-2\nu$. The self-concordance inequality in [F1] therefore implies $2\nu \le 2{\nu }^{3\mathrm{/}2}$, hence $\nu \ge 1$.

At an iterate with ${\lambda }_t(x)\le 1\mathrm{/}4$, set $\alpha =1+1\mathrm{/}(8\sqrt{\nu })$ and $B(x)=F(h-Gx)$. On $\ker A$, $D^{2}B(x)[d,d]=D^{2}F(s)[Gd,Gd]$, so the restricted dual norm of $DB(x)$ is at most the ambient dual norm of $DF(s)$, hence at most $\sqrt{\nu }$ by [F1]. Since $D{\mathrm{\Phi }}_{\alpha t}=\alpha D{\mathrm{\Phi }}_t+(1-\alpha )DB$, the triangle inequality gives ${\lambda }_{\alpha t}(x)\le \alpha {\lambda }_t(x)+(\alpha -1)\sqrt{\nu }\le 3\mathrm{/}8+1\mathrm{/}(32\sqrt{\nu })\le 13\mathrm{/}32$.

Adding the linear term $t^{+}{c}^{T}x$ does not change the barrier Hessian, local norms, or third derivatives, so [F2] applies to ${\mathrm{\Phi }}_{t^{+}}$. The starting decrement is at most $13\mathrm{/}32<1$, so [F4] gives a unique attained center for that subproblem. After the first damped correction the decrement is at most $2(13\mathrm{/}32{)}^2=338\mathrm{/}1024$. Applying [F2] once more gives at most $2(338\mathrm{/}1024{)}^2<1\mathrm{/}4$. Dikin inclusion keeps both corrections in the cone interior. Thus each path update is recentered in at most two corrections.

Let $x_{\ast }(t)$ be the exact center at the new $t$ and let $x$ be the accepted iterate with ${\lambda }_t(x)\le 1\mathrm{/}4$. By [F2], $r=\mathrm{\parallel }x-x_{\ast }(t){\mathrm{\parallel }}_x\le 1\mathrm{/}3$. Applying its local Hessian comparison to this segment gives $\mathrm{\parallel }x-x_{\ast }(t){\mathrm{\parallel }}_{x_{\ast }(t)}\le r\mathrm{/}(1-r)\le 1\mathrm{/}2$. For $h=x-x_{\ast }(t)$, the restricted barrier norm is $\mathrm{\parallel }Gh{\mathrm{\parallel }}_{s_{\ast }(t)}=\mathrm{\parallel }h{\mathrm{\parallel }}_{x_{\ast }(t)}$. Stationarity of $x_{\ast }(t)$ along the feasible affine space gives $t{c}^{T}h=-DF(s_{\ast }(t))[s(x)-s_{\ast }(t)]$. The restricted barrier dual norm of this functional is at most the ambient $\sqrt{\nu }$ from [F1], because restricting the unit-vector supremum can only decrease it. Hence $\mathrm{\mid }{c}^{T}h\mathrm{\mid }\le \sqrt{\nu }\mathrm{/}(2t)$. Combining this with [F3] yields $c^{T}x-p^{\ast }\le (\nu +\sqrt{\nu }\mathrm{/}2)\mathrm{/}t\le 3\nu \mathrm{/}(2t)$, since $\nu \ge 1$.

Each path update multiplies $t$ by $\alpha$, so $t_k=t_0{\alpha }^k$. The bound in step 3.1 is at most $\epsilon$ once $t_k\ge 3\nu \mathrm{/}(2\epsilon )$, which gives the displayed ceiling. For $u=1\mathrm{/}(8\sqrt{\nu })\le 1\mathrm{/}8$, $\log (1+u)\ge u\mathrm{/}(1+u)\ge 1\mathrm{/}(9\sqrt{\nu })$; hence $k\le 1+9\sqrt{\nu }\log R$. Step 2.1 bounds corrections by $2k\le 2+18\sqrt{\nu }\log R$, giving the uniform bound. As $\nu \mathrm{/}(\epsilon t_0)\to \mathrm{\infty }$, $\log R=\log (\nu \mathrm{/}(\epsilon t_0))+\log (3\mathrm{/}2)$ gives the asserted asymptotic bound.