Ellipsoid method correctness in iterations
ProvedLinearOptimization.ellipsoid_method_correct(Theorem 8.2, p. 372, GOAL — correctness of the ellipsoid method) Let be a bounded polyhedron that is either empty or full-dimensional and for which the prior information , , , is available: , , and either or .
Then the ellipsoid method decides correctly whether is nonempty or not, i.e., if [no center of an admissible run lies in ], then is empty, where
Equivalently: if is nonempty, every admissible run of the ellipsoid method reaches a feasible center for some .
import Definitions.Def_LinearOptimization_EllipsoidMethod
open Matrix MeasureTheory
/-- **Bertsimas & Tsitsiklis, Theorem 8.2 (p. 372).** Correctness of the ellipsoid method: if
`P = {x | Ax ≥ b}` is bounded and either empty or full-dimensional,
`P ⊆ E(x₀, r²I)`, `Vol(E(x₀, r²I)) ≤ V`, `Vol(P) > v` unless `P = ∅`,
and an admissible run started at `(x₀, r²I)` has no feasible center
before `t* = ⌈2(n+1) log(V/v)⌉`, then `P` is empty. -/
theorem LinearOptimization.ellipsoid_method_correct {m n : ℕ} (hn : 2 ≤ n)
(A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(x0 : Fin n → ℝ) (r v V : ℝ) (hr : 0 < r) (hv : 0 < v)
(hbdd : IsBoundedSet (polyhedron A b))
(hdim : polyhedron A b = ∅ ∨ IsFullDimensional (polyhedron A b))
(hcover : polyhedron A b ⊆ ellipsoidBall x0 r)
(hV : volume (ellipsoidBall x0 r) ≤ ENNReal.ofReal V)
(hvol : polyhedron A b ≠ ∅ →
ENNReal.ofReal v < volume (polyhedron A b))
(tstar : ℕ)
(htstar : tstar = ⌈2 * ((n : ℝ) + 1) * Real.log (V / v)⌉₊)
(x : ℕ → Fin n → ℝ) (D : ℕ → Matrix (Fin n) (Fin n) ℝ)
(hx0 : x 0 = x0)
(hD0 : D 0 = r ^ 2 • (1 : Matrix (Fin n) (Fin n) ℝ))
(hrun : IsEllipsoidRun A b x D tstar)
(hmiss : ∀ t < tstar, x t ∉ polyhedron A b) :
polyhedron A b = ∅ := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix , a real system , a point , and reals , , (no sign assumed on ). Let . Hypotheses: is bounded; is empty or has positive Lebesgue volume; , where is the closed ball of radius (well-defined since ); ; if then ; (natural-number ceiling, clamped to for nonpositive arguments); sequences , with as stated and ; the pair is an ellipsoid run up to (for each with , some strictly violated row () satisfies and ); and for every (so the step condition is actually triggered at each such ). Conclusion: . Notes: no positive-definiteness of the is hypothesized beyond ; (e.g. ) makes the run and miss hypotheses vacuous, yet the emptiness conclusion is still asserted; nothing is concluded about feasibility ever being detected — the theorem only converts " consecutive infeasible centers" into emptiness of .
Confirmed by the mission captain (proposal self-audit).