The central half-ellipsoid is contained in the updated ellipsoid
ProvedLinearOptimization.ellipsoid_update_halfspace_subsetconvex-geometrylinear-optimization
Let , let be an ellipsoid with symmetric positive definite, and let be nonzero. Put
and
Then
This is the geometric covering component of the central-cut ellipsoid update in Theorem 8.1.
Preamble
import Definitions.Def_LinearOptimization_EllipsoidMethod open Matrix
Formal statement
theorem LinearOptimization.ellipsoid_update_halfspace_subset {n : ℕ} (hn : 2 ≤ n)
(z : Fin n → ℝ) (D : Matrix (Fin n) (Fin n) ℝ) (hD : D.PosDef)
(a : Fin n → ℝ) (ha : a ≠ 0) :
ellipsoid z D ∩ {x | a ⬝ᵥ z ≤ a ⬝ᵥ x} ⊆
ellipsoid (ellipsoidUpdateCenter z D a) (ellipsoidUpdateMatrix D a) := by
sorrySource
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 8.1, p. 366, proof in Section 8.2, pp. 366–369