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

⚠️ DEPRECATED — superseded, and under-specified as stated.

Use ConvexOptimization.barrier_method_sqrt_m_complexity_sc instead: the same statement plus the hypotheses Differentiable ℝ f₀ and ∀ i, Differentiable ℝ (fᵢ), which B&V assume throughout Chapter 11.

Why the extra hypotheses. The per-centering step count rests on the objective gap inherited from the previous centre being at most $m(\mu - 1 - \log\mu)$, i.e. on (11.25)–(11.26), formalized as ConvexOptimization.barrier_centering_potential_gap. That estimate is proved through the central path and the dual feasible point $\lambda_i = -1/(t f_i(x))$, so it needs the individual gradients $\nabla f_i$. The Newton hypotheses of this statement only supply the gradient of the sum $t f_0 + \varphi$ on the strictly feasible set — enough to recover $\nabla f_0$ and $\nabla\varphi$ there, but not the separate $\nabla f_i$. This statement is not known to be false; it is simply missing the standing regularity assumption of §11, and is retired in favour of the version that states it.

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 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$, $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}}$ in at most

Newton steps — a bound independent of $i$, of $m$ and of $n$ — because the objective gap inherited from the previous centre is at most $m(\mu - 1 - \log\mu) \le 1/2$ for this $\mu$. Together with the duality gap $m/t$ along the central path, $\lceil \sqrt m \log_2(m/(t^{(0)}\varepsilon))\rceil$ outer iterations bring the gap below $\varepsilon$, so the total Newton effort is $O(\sqrt m \log(1/\varepsilon))$.

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 — which is exactly what B&V's convention "$f = +\infty$ off $\operatorname{dom} f$" (§9.1) delivers. This has to be said explicitly here 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 earlier formalization ConvexOptimization.barrier_method_sqrt_m_complexity, which used the unconfined line search, is false for exactly this reason and has been disproved. A hypothesis that the sublevel sets of $t f_0 + \varphi$ within the strictly feasible set are closed is also stated explicitly, as the Dikin-ellipsoid argument behind (9.55) needs it. Otherwise the statement is unchanged.