Theorem 2, p. 317 — the BCD computes a (1 + ε)n-rounding ellipsoid of m points in ℝⁿ within O(n(1/ε + ln n + ln ln m)) iterations
ProvedKhachiyanRound.BCD.theorem_2There is a universal constant with the following property. Let , let have affine hull , and let . Run the BCD method on the centrally symmetric lifted set of (3.3) — with any tie-breaking rule — producing iterates , and let denote aggregated weights. Then there is an iterate with
that satisfies the relaxed optimality conditions (2.10) on with (3.2), whose moment matrix is positive definite, and for which the ellipsoid
of Lemma 5 is a -rounding of (1.2):
the shrinking being about the centre of .
This is the paper's main result: a simple first-order method computes a near-optimal rounding ellipsoid of an arbitrary polytope given by its vertices, in a number of iterations that depends on only through .
Formalization Note The page states arithmetic operations and comparisons. The Lean statement bounds the index of an iterate that passes the stopping test; the cost per iteration (, from the rank-one correction) and the cost of forming are not formalized. The bound is written in the lifted parameters , which keeps it positive for every (at , the page's is negative); wherever the page's expression is meaningful the two agree up to the constant. The constant is quantified before every instance datum. is the ellipsoid (3.4) of the aggregated weights.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_LinearOptimization_Ellipsoid import Definitions.Def_KhachiyanRound_BCD_Setting open scoped Pointwise
namespace KhachiyanRound.BCD
theorem theorem_2 :
∃ C : ℝ, 0 < C ∧ ∀ (n m : ℕ) (a : Fin m → Fin n → ℝ), 1 ≤ n →
affineSpan ℝ (Set.range a) = ⊤ → ∀ ε : ℝ, 0 < ε →
∀ p : ℕ → (Fin m ⊕ Fin m → ℝ), IsBCDRun (liftPts a) p →
∃ k : ℕ, (k : ℝ) ≤ C * (n + 1) *
(1 / ε + Real.log (n + 1) + Real.log (Real.log (2 * m))) ∧
IsRelaxedOpt (liftPts a) (p k) ((n : ℝ) / (n + 1) * ε) ∧
(momentMatrix (liftPts a) (p k)).PosDef ∧
(AffineMap.homothety (∑ j, aggr (p k) j • a j) ((1 + ε) * (n : ℝ))⁻¹) ''
lemma5Ellipsoid a (aggr (p k)) ε ⊆ convexHull ℝ (Set.range a) ∧
convexHull ℝ (Set.range a) ⊆ lemma5Ellipsoid a (aggr (p k)) ε := by sorry
end KhachiyanRound.BCD
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.