Ellipsoid update: the half-ellipsoid is covered with volume ratio
ProvedLinearOptimization.ellipsoid_update_halfspace_volumeconvex-geometryellipsoid-methodvolume
(Theorem 8.1, p. 366 — the key geometric result behind the ellipsoid method) Let be an ellipsoid in (; see design_note), and let be a nonzero -vector. Consider the halfspace and let
The matrix is symmetric and positive definite and thus is an ellipsoid. Moreover,
- (a) ,
- (b) .
Preamble
import Definitions.Def_LinearOptimization_EllipsoidMethod
open Matrix MeasureTheory
/-- **Bertsimas & Tsitsiklis, Theorem 8.1 (p. 366).** Half-ellipsoid covered by a strictly
smaller ellipsoid: `D̄` is positive definite (and symmetric),
`E(z, D) ∩ {x | a'x ≥ a'z} ⊆ E(z̄, D̄)`, and
`Vol(E(z̄, D̄)) < e^{−1/(2(n+1))} · Vol(E(z, D))`. -/
Formal statement
theorem LinearOptimization.ellipsoid_update_halfspace_volume {n : ℕ} (hn : 2 ≤ n)
(z : Fin n → ℝ) (D : Matrix (Fin n) (Fin n) ℝ) (hD : D.PosDef)
(a : Fin n → ℝ) (ha : a ≠ 0) :
(ellipsoidUpdateMatrix D a).PosDef ∧
ellipsoid z D ∩ {x | a ⬝ᵥ z ≤ a ⬝ᵥ x} ⊆
ellipsoid (ellipsoidUpdateCenter z D a) (ellipsoidUpdateMatrix D a) ∧
volume (ellipsoid (ellipsoidUpdateCenter z D a)
(ellipsoidUpdateMatrix D a)) <
ENNReal.ofReal (Real.exp (-(1 : ℝ) / (2 * ((n : ℝ) + 1)))) *
volume (ellipsoid z D) := by
sorry
Source
Bertsimas & Tsitsiklis, Introduction to Linear Optimization, Athena Scientific, 1997, Theorem 8.1, p. 366
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.