Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
ConvexOptAlg.Ellipsoid.lemma_2_3

by mikedeng1 · Oct 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-optimizationellipsoid-methodp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-bookp2o-v1volume

Let E0={x∈Rn:(x−c0)⊤H0−1(x−c0)≤1}\mathcal E_0=\{x\in\mathbb R^n:(x-c_0)^\top H_0^{-1}(x-c_0)\le 1\}E0​={x∈Rn:(x−c0​)⊤H0−1​(x−c0​)≤1} with c0∈Rnc_0\in\mathbb R^nc0​∈Rn and H0H_0H0​ symmetric positive definite, and let w∈Rnw\in\mathbb R^nw∈Rn, w≠0w\ne0w=0. Then:

  1. there exists an ellipsoid E={x:(x−c)⊤H−1(x−c)≤1}\mathcal E=\{x:(x-c)^\top H^{-1}(x-c)\le 1\}E={x:(x−c)⊤H−1(x−c)≤1}, HHH symmetric positive definite, with
E⊃{x∈E0:w⊤(x−c0)≤0}(2.3)andvol(E)≤exp⁡(−12n)vol(E0)(2.4);\mathcal E\supset\{x\in\mathcal E_0: w^\top(x-c_0)\le0\}\quad(2.3)\qquad\text{and}\qquad \mathrm{vol}(\mathcal E)\le\exp\Big(-\frac1{2n}\Big)\mathrm{vol}(\mathcal E_0)\quad(2.4);E⊃{x∈E0​:w⊤(x−c0​)≤0}(2.3)andvol(E)≤exp(−2n1​)vol(E0​)(2.4);
  1. for n≥2n\ge2n≥2 one can take
c=c0−1n+1H0ww⊤H0w(2.5),H=n2n2−1(H0−2n+1H0ww⊤H0w⊤H0w)(2.6):c=c_0-\frac1{n+1}\frac{H_0w}{\sqrt{w^\top H_0w}}\quad(2.5),\qquad H=\frac{n^2}{n^2-1}\Big(H_0-\frac2{n+1}\frac{H_0ww^\top H_0}{w^\top H_0w}\Big)\quad(2.6):c=c0​−n+11​w⊤H0​w​H0​w​(2.5),H=n2−1n2​(H0​−n+12​w⊤H0​wH0​ww⊤H0​​)(2.6):

this HHH is symmetric positive definite and E\mathcal EE 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 exp⁡(−1/(2n))\exp(-1/(2n))exp(−1/(2n)).

Formalization Note vol\mathrm{vol}vol is Lebesgue measure on Fin n → ℝ, with values in [0,∞][0,\infty][0,∞]; 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 a=−wa=-wa=−w, but only the weaker volume factor exp⁡(−1/(2(n+1)))\exp(-1/(2(n+1)))exp(−1/(2(n+1))); the book's factor exp⁡(−1/(2n))\exp(-1/(2n))exp(−1/(2n)) 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
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me