Barrier method: $O(\sqrt{m}\log(1/\varepsilon))$ Newton steps

Complexity of the barrier method with the $\sqrt{m}$ outer schedule — Boyd & Vandenberghe §11.5, with the inner line search confined to the strictly feasible set.

Consider the inequality-constrained convex program

with $f_0$ and all $f_i$ convex and differentiable, and let $\varphi(x) = -\sum_i \log(-f_i(x))$ be the logarithmic barrier. Assume the §11.5.1 self-concordance hypothesis: $t f_0 + \varphi$ is self-concordant on the strictly feasible set for every $t \ge 0$, with positive definite Hessian and closed sublevel sets, and let $x^{\star}(t)$ denote the exact minimiser — the central path.

Run the barrier method with the outer schedule $\mu = 1 + 1/\sqrt m$ and $t_i = \mu^{i} t^{(0)}$, each centering step warm-started at the previous centre $x^{\star}(t_i)$ and carried out by damped Newton with backtracking. Then:

• each centering step reaches accuracy $\varepsilon_{\mathrm{nt}}$ within

Newton steps — a bound independent of the outer index $i$, of $m$ and of $n$. The reason is that the objective gap inherited from the previous centre is at most $m(\mu - 1 - \log\mu)$ by (11.25)–(11.26), and for $\mu = 1+1/\sqrt m$ the elementary estimate $\log(1+u)\ge u - u^2/2$ makes this at most $\tfrac12$;

• $\lceil \sqrt m \,\log_2(m/(t^{(0)}\varepsilon))\rceil$ outer iterations drive the duality gap $m/t$ below $\varepsilon$, because $\sqrt m\,\log_2\!\bigl(1+1/\sqrt m\bigr) \ge 1$ for $m \ge 1$.

Multiplying the two gives the $O(\sqrt m \log(1/\varepsilon))$ total Newton complexity that is the whole point of the barrier method.

Formalization note. Each centering run is governed by IsDampedNewtonRunOn, whose line search IsBacktrackingStepOn accepts the largest step $\beta^j$ whose trial point is both strictly feasible and Armijo-acceptable — exactly what B&V's convention "$f = +\infty$ off $\operatorname{dom} f$" (§9.1, p. 457) delivers. This must be said explicitly because logBarrier is real-valued and returns finite junk values off the strictly feasible set (Mathlib's Real.log is $0$ at $0$ and $\log|\cdot|$ on the negatives), so the barrier does not blow up there; the original formalization ConvexOptimization.barrier_method_sqrt_m_complexity, which used the unconfined line search, is false for this reason and has been disproved. Differentiability of $f_0$ and of each $f_i$ is assumed, as it is throughout B&V §11, since the central-path/duality argument behind (11.25)–(11.26) needs the individual gradients $\nabla f_i$ and not merely the gradient of the sum. A hypothesis that the sublevel sets of $t f_0 + \varphi$ within the strictly feasible set are closed is stated explicitly, as the Dikin-ellipsoid argument behind (9.55) needs it.