Ellipsoid update: the half-ellipsoid is covered with volume ratio
ProvedLinearOptimization.ellipsoid_update_halfspace_volume(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) .
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))`. -/
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
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Fix , a center , a positive definite real matrix , and a vector . Write (matrix-inverse convention: for singular ; here is invertible), , and . The theorem asserts three conjuncts: (i) is positive definite; (ii) the half-ellipsoid (the side where is at least its value at the center) is contained in ; (iii) the Lebesgue volume of is strictly less than times the volume of , the inequality stated in with the constant embedded via . No normalization of is assumed, and excludes the degenerate prefactor cases .
Confirmed by the mission captain (proposal self-audit).