Ellipsoid method correctness in iterations
ProvedLinearOptimization.ellipsoid_method_correctalgorithm-correctnesscomplexityellipsoid-methodlinear-programming
(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 .
Preamble
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. -/
Formal statement
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
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 8.2, p. 372