Theorem 4.9.1 — Löwner–Fritz John: unique extremal ellipsoids of a solid, within factor n (√n if symmetric)
ProvedModernConvex.Ellipsoids.lowner_fritz_johnLet be a solid, i.e. a closed and bounded convex set with nonempty interior. Volumes are normalized, so the unit Euclidean ball has volume . For a full-dimensional ellipsoid ( square, ) and , the concentric ellipsoid times larger (in linear sizes) is .
- There is exactly one largest-volume full-dimensional ellipsoid contained in . If , then
If is central-symmetric, then already . 2. There is exactly one smallest-volume full-dimensional ellipsoid containing . If , then
If is central-symmetric, then already .
This is the classical existence, uniqueness and rounding theorem for extremal ellipsoids. In §4.9 it supplies the "true" smallest-volume ellipsoid against which the semidefinite approximations are measured.
Formalization Note "Exists and is uniquely defined" is ∃! over sets that are largest (resp. smallest) volume full-dimensional ellipsoids. The rounding claims are stated for every representation of (resp. ) with . The scaled set does not depend on the representation. Central symmetry means symmetry about some point. Volume is Lebesgue measure divided by the measure of the unit Euclidean ball. The book leaves the proof to Exercise 4.71. The degenerate case , which the book does not consider, holds trivially.
import Mathlib import Definitions.Def_ModernConvex_Ellipsoids_Ellipsoid open Matrix
namespace ModernConvex.Ellipsoids
/-- Ben-Tal–Nemirovski, Theorem 4.9.1 (Löwner–Fritz John), p. 259. Let `S ⊂ ℝⁿ` be a solid. Then
(i) there exists and is uniquely defined the largest volume full-dimensional ellipsoid `E_in`
contained in `S`; the concentric to `E_in` `n` times larger ellipsoid contains `S`, and if `S` is
central-symmetric already the `√n` times larger one does;
(ii) there exists and is uniquely defined the smallest volume full-dimensional ellipsoid `E_out`
containing `S`; the concentric to `E_out` `n` times smaller ellipsoid is contained in `S`, and if
`S` is central-symmetric already the `√n` times smaller one is.
"Concentric, `r` times larger" ellipsoid of `E = {Au + c | uᵀu ≤ 1}` is `{(rA)u + c | uᵀu ≤ 1}`. -/
theorem lowner_fritz_john {n : ℕ} (S : Set (Fin n → ℝ)) (hS : IsSolid S) :
((∃! E : Set (Fin n → ℝ), IsMaxVolInscribed S E) ∧
∀ (A : Matrix (Fin n) (Fin n) ℝ) (c : Fin n → ℝ), A.det ≠ 0 →
IsMaxVolInscribed S (ellipsoid A c) →
S ⊆ ellipsoid ((n : ℝ) • A) c ∧
(IsCentralSymmetric S → S ⊆ ellipsoid (Real.sqrt n • A) c)) ∧
((∃! E : Set (Fin n → ℝ), IsMinVolCircumscribed S E) ∧
∀ (A : Matrix (Fin n) (Fin n) ℝ) (c : Fin n → ℝ), A.det ≠ 0 →
IsMinVolCircumscribed S (ellipsoid A c) →
ellipsoid ((1 / (n : ℝ)) • A) c ⊆ S ∧
(IsCentralSymmetric S → ellipsoid ((1 / Real.sqrt n) • A) c ⊆ S)) := by sorry
end ModernConvex.Ellipsoids
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let and let be a solid: closed, bounded, convex and with nonempty interior. The following terms are used:
- .
- A full-dimensional ellipsoid is a set with a square real matrix, .
- , Lebesgue outer measure normalized so that the Euclidean unit ball has volume .
- is a maximum-volume inscribed ellipsoid of when is a full-dimensional ellipsoid, , and for every full-dimensional ellipsoid .
- is a minimum-volume circumscribed ellipsoid of when is a full-dimensional ellipsoid, , and for every full-dimensional ellipsoid .
- is central-symmetric when there is some point (not tied to any ellipsoid) with .
The statement asserts the conjunction of two parts.
(i) Inscribed ellipsoid.
- There is exactly one set that is a maximum-volume inscribed ellipsoid of .
- For every real with and every such that is a maximum-volume inscribed ellipsoid of :
and, if is central-symmetric, .
(ii) Circumscribed ellipsoid.
- There is exactly one set that is a minimum-volume circumscribed ellipsoid of .
- For every real with and every such that is a minimum-volume circumscribed ellipsoid of :
and, if is central-symmetric, .
Uniqueness is uniqueness of the set , not of the pair representing it.
Degenerate cases.
- : is a single point, and the only solid is that whole one-point space. Every ellipsoid is that point, and the empty matrix has determinant . The scalings , , and are all the empty matrix; in particular and evaluate to . All inclusions therefore hold between one-point sets.
- : all scaling factors equal .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.