Lemma 2.3, p. 247 — a half-ellipsoid fits in an ellipsoid of volume ≤ exp(−1/(2n))·vol(E₀), explicitly (2.5)–(2.6) for n ≥ 2
ProvedConvexOptAlg.Ellipsoid.lemma_2_3convex-optimizationellipsoid-methodp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1volume
Let with and symmetric positive definite, and let , . Then:
- there exists an ellipsoid , symmetric positive definite, with
- for one can take
this is symmetric positive definite and satisfies (2.3) and (2.4).
This is the geometric step of the ellipsoid method: one cut through the center of the current ellipsoid shrinks the volume of the localizing ellipsoid by the factor .
Formalization Note is Lebesgue measure on Fin n → ℝ, with values in ; ellipsoids are the published LinearOptimization.ellipsoid. "Ellipsoid" in part 1 means a positive definite shape matrix. The published, proved LinearOptimization.ellipsoid_update_halfspace_volume gives (2.3) and positive definiteness for (2.5)–(2.6) with , but only the weaker volume factor ; the book's factor is kept here.
Preamble
import Mathlib import Definitions.Def_ConvexOptAlg_Ellipsoid_Defs
Formal statement
namespace ConvexOptAlg.Ellipsoid
open Matrix MeasureTheory
/-- **Lemma 2.3** (Bubeck, arXiv:1405.4980v2, p. 247). Let `E₀ = {x : (x − c₀)⊤H₀⁻¹(x − c₀) ≤ 1}`
with `H₀` symmetric positive definite, and let `w ≠ 0`.
(i) There is an ellipsoid `E` (center `c`, symmetric positive definite matrix `H`) containing
the half-ellipsoid `{x ∈ E₀ : w⊤(x − c₀) ≤ 0}` (2.3) with `vol(E) ≤ exp(−1/(2n)) vol(E₀)` (2.4).
(ii) For `n ≥ 2` one can take `c = c₀ − (1/(n+1)) H₀w/√(w⊤H₀w)` (2.5) and
`H = (n²/(n²−1)) (H₀ − (2/(n+1)) H₀ww⊤H₀/(w⊤H₀w))` (2.6): this `H` is positive definite and
`E` satisfies (2.3) and (2.4). Volume is Lebesgue measure on `ℝⁿ = Fin n → ℝ`. -/
theorem lemma_2_3 {n : ℕ} (c0 : Fin n → ℝ) (H0 : Matrix (Fin n) (Fin n) ℝ) (hH0 : H0.PosDef)
(w : Fin n → ℝ) (hw : w ≠ 0) :
(∃ (c : Fin n → ℝ) (H : Matrix (Fin n) (Fin n) ℝ), H.PosDef ∧
LinearOptimization.ellipsoid c0 H0 ∩ {x | w ⬝ᵥ (x - c0) ≤ 0} ⊆
LinearOptimization.ellipsoid c H ∧
volume (LinearOptimization.ellipsoid c H) ≤
ENNReal.ofReal (Real.exp (-(1 : ℝ) / (2 * (n : ℝ)))) *
volume (LinearOptimization.ellipsoid c0 H0)) ∧
(2 ≤ n →
(((n : ℝ) ^ 2 / ((n : ℝ) ^ 2 - 1)) •
(H0 - ((2 : ℝ) / ((n : ℝ) + 1)) • (w ⬝ᵥ (H0 *ᵥ w))⁻¹ •
(H0 * vecMulVec w w * H0))).PosDef ∧
LinearOptimization.ellipsoid c0 H0 ∩ {x | w ⬝ᵥ (x - c0) ≤ 0} ⊆
LinearOptimization.ellipsoid
(c0 - ((1 : ℝ) / ((n : ℝ) + 1)) • (Real.sqrt (w ⬝ᵥ (H0 *ᵥ w)))⁻¹ • (H0 *ᵥ w))
(((n : ℝ) ^ 2 / ((n : ℝ) ^ 2 - 1)) •
(H0 - ((2 : ℝ) / ((n : ℝ) + 1)) • (w ⬝ᵥ (H0 *ᵥ w))⁻¹ •
(H0 * vecMulVec w w * H0))) ∧
volume (LinearOptimization.ellipsoid
(c0 - ((1 : ℝ) / ((n : ℝ) + 1)) • (Real.sqrt (w ⬝ᵥ (H0 *ᵥ w)))⁻¹ • (H0 *ᵥ w))
(((n : ℝ) ^ 2 / ((n : ℝ) ^ 2 - 1)) •
(H0 - ((2 : ℝ) / ((n : ℝ) + 1)) • (w ⬝ᵥ (H0 *ᵥ w))⁻¹ •
(H0 * vecMulVec w w * H0)))) ≤
ENNReal.ofReal (Real.exp (-(1 : ℝ) / (2 * (n : ℝ)))) *
volume (LinearOptimization.ellipsoid c0 H0)) := by sorry
end ConvexOptAlg.Ellipsoid
Source
Bubeck, arXiv:1405.4980v2, Lemma 2.3, eqs. (2.3)–(2.6), p. 247
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.