Strict volume decrease under the central-cut ellipsoid update
ProvedLinearOptimization.ellipsoid_update_volume_ltconvex-geometrylinear-optimization
Let , let be an ellipsoid with symmetric positive definite, and let be nonzero. Let and be the central-cut updates
The updated ellipsoid has strictly smaller volume:
This is the quantitative volume-shrinkage component of Theorem 8.1 used to bound the number of ellipsoid-method iterations.
Preamble
import Definitions.Def_LinearOptimization_EllipsoidMethod open Matrix MeasureTheory
Formal statement
theorem LinearOptimization.ellipsoid_update_volume_lt {n : ℕ} (hn : 2 ≤ n)
(z : Fin n → ℝ) (D : Matrix (Fin n) (Fin n) ℝ) (hD : D.PosDef)
(a : Fin n → ℝ) (ha : a ≠ 0) :
volume (ellipsoid (ellipsoidUpdateCenter z D a)
(ellipsoidUpdateMatrix D a)) <
ENNReal.ofReal (Real.exp (-(1 : ℝ) / (2 * ((n : ℝ) + 1)))) *
volume (ellipsoid z D) := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 8.1, p. 366, proof in Section 8.2, pp. 366–369