Why do interior-point methods solve convex programs in Newton steps? Nesterov and Nemirovskii's answer is self-concordance: a convex function whose third derivative is controlled by its second, along every line, admits a Newton analysis with absolute constants and no condition number — and the logarithmic barrier is self-concordant. This mission formalizes §9.6 and Chapter 11 of Boyd & Vandenberghe: the self-concordance calculus, the Newton-decrement analysis, the duality gap along the central path, the per-centering work bound , and the crown result — with the aggressive schedule the barrier method reaches duality gap after
centering steps, each of uniformly bounded Newton cost.
theorem ConvexOptimization.barrier_method_sqrt_m_complexity_sc {n mI : ℕ} (hmI : 0 < mI)
(α β t0 ε εnt : ℝ)
(hα0 : 0 < α) (hα : α < 1 / 2) (hβ0 : 0 < β) (hβ1 : β < 1)
(ht0 : 0 < t0) (hε : 0 < ε) (hεnt0 : 0 < εnt) (hεnt : εnt < 1 / 4)
(f₀ : EuclideanSpace ℝ (Fin n) → ℝ) (hf₀ : ConvexOn ℝ Set.univ f₀)
(fc : Fin mI → EuclideanSpace ℝ (Fin n) → ℝ)
(hfc : ∀ i, ConvexOn ℝ Set.univ (fc i))
(hf₀_diff : Differentiable ℝ f₀) (hfc_diff : ∀ i, Differentiable ℝ (fc i))
(hSC : ∀ t : ℝ, 0 ≤ t →
IsSelfConcordantOn {x | ∀ i, fc i x < 0}
(fun x => t * f₀ x + logBarrier fc x))
(hclosed : ∀ t : ℝ, 0 < t → ∀ c : ℝ,
IsClosed {x | (∀ i, fc i x < 0) ∧ t * f₀ x + logBarrier fc x ≤ c})
(g : ℝ → EuclideanSpace ℝ (Fin n) → EuclideanSpace ℝ (Fin n))
(hg : ∀ t : ℝ, 0 < t → ∀ x, (∀ i, fc i x < 0) →
HasGradientAt (fun y => t * f₀ y + logBarrier fc y) (g t x) x)
(H : ℝ → EuclideanSpace ℝ (Fin n) →
EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin n))
(hH : ∀ t : ℝ, 0 < t → ∀ x, (∀ i, fc i x < 0) →
HasFDerivAt (g t) (H t x) x)
(hHpd : ∀ t : ℝ, 0 < t → ∀ x, (∀ i, fc i x < 0) →
∀ v, v ≠ 0 → 0 < ⟪H t x v, v⟫)
(xc : ℝ → EuclideanSpace ℝ (Fin n))
(hxc_str : ∀ t : ℝ, 0 < t → ∀ i, fc i (xc t) < 0)
(hxc_min : ∀ t : ℝ, 0 < t →
IsMinOn (fun x => t * f₀ x + logBarrier fc x) {x | ∀ i, fc i x < 0} (xc t)) :
∃ (w : ℕ → ℕ → EuclideanSpace ℝ (Fin n)) (K : ℕ → ℕ),
(∀ i, w i 0 = xc ((1 + 1 / Real.sqrt mI) ^ i * t0)) ∧
(∀ i, IsDampedNewtonRunOn {x | ∀ i', fc i' x < 0}
(fun x => (1 + 1 / Real.sqrt mI) ^ (i + 1) * t0 * f₀ x + logBarrier fc x)
(g ((1 + 1 / Real.sqrt mI) ^ (i + 1) * t0))
(H ((1 + 1 / Real.sqrt mI) ^ (i + 1) * t0)) α β (w i)) ∧
(∀ i, ((1 + 1 / Real.sqrt mI) ^ (i + 1) * t0 * f₀ (w i (K i)) +
logBarrier fc (w i (K i))) -
((1 + 1 / Real.sqrt mI) ^ (i + 1) * t0 *
f₀ (xc ((1 + 1 / Real.sqrt mI) ^ (i + 1) * t0)) +
logBarrier fc (xc ((1 + 1 / Real.sqrt mI) ^ (i + 1) * t0))) ≤ εnt) ∧
(∀ i, (K i : ℝ) ≤
(20 - 8 * α) / (α * β * (1 - 2 * α) ^ 2) / 2 +
Real.logb 2 (Real.logb 2 (1 / εnt)) + 2) ∧
(mI : ℝ) / ((1 + 1 / Real.sqrt mI) ^
⌈Real.sqrt mI * Real.logb 2 (mI / (t0 * ε))⌉₊ * t0) ≤ ε := by
sorry
Complexity of the barrier method with the outer schedule — Boyd & Vandenberghe §11.5, with the inner line search confined to the strictly feasible set.
Consider the inequality-constrained convex program
with and all convex and differentiable, and let be the logarithmic barrier. Assume the §11.5.1 self-concordance hypothesis: is self-concordant on the strictly feasible set for every , with positive definite Hessian and closed sublevel sets, and let denote the exact minimiser — the central path.
Run the barrier method with the outer schedule and , each centering step warm-started at the previous centre and carried out by damped Newton with backtracking. Then:
Newton steps — a bound independent of the outer index , of and of . The reason is that the objective gap inherited from the previous centre is at most by (11.25)–(11.26), and for the elementary estimate makes this at most ;
Multiplying the two gives the 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 whose trial point is both strictly feasible and Armijo-acceptable — exactly what B&V's convention " off " (§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 at and 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 and of each is assumed, as it is throughout B&V §11, since the central-path/duality argument behind (11.25)–(11.26) needs the individual gradients and not merely the gradient of the sum. A hypothesis that the sublevel sets of within the strictly feasible set are closed is stated explicitly, as the Dikin-ellipsoid argument behind (9.55) needs it.
No open leaves. Every sub-goal is proved or awaiting decomposition.