Remark before Theorem 2.4, p. 250 — a point of X leaves E_t only if c_t ∈ X, and then its value exceeds f(c_t)
ProvedConvexOptAlg.Ellipsoid.cut_keeps_XLet , , and let be a run of the ellipsoid method on with objective , started from the Euclidean ball of center and radius . Fix such that the oracle answers are all nonzero, and write . If lies in but not in , then
This is the ellipsoid-method analogue of (2.2) for the center of gravity method: a cut never removes a point of unless it is a value cut at a center in , and such a cut removes only points that are worse than that center.
Formalization Note The page states only "at step one can remove a point in from the current ellipsoid only if "; the second conclusion is the inequality of (2.2) that "the exact same argument" of Theorem 2.1 uses. The nonzero answers guarantee that every , , is a genuine update.
import Mathlib import Definitions.Def_ConvexOptAlg_Ellipsoid_Defs
namespace ConvexOptAlg.Ellipsoid
/-- The remark before Theorem 2.4 (Bubeck, arXiv:1405.4980v2, §2.2, p. 250): at step `t` of the
ellipsoid method a point of `X` can be removed from the current ellipsoid only if `c_t ∈ X`, and
then (as in (2.2), p. 246) its value exceeds `f(c_t)`. Formally: in a run with `n ≥ 2`, `R > 0`
and nonzero oracle answers `w_0, …, w_t`, every `x ∈ X` lying in `E_t` but not in `E_{t+1}`
satisfies `c_t ∈ X` and `f(c_t) < f(x)`, where
`E_s = {x : (x − c_s)⊤H_s⁻¹(x − c_s) ≤ 1}`. -/
theorem cut_keeps_X {n : ℕ} (hn : 2 ≤ n) (X : Set (Fin n → ℝ)) (f : (Fin n → ℝ) → ℝ)
(R : ℝ) (hR : 0 < R) (c0 : Fin n → ℝ) (c : ℕ → Fin n → ℝ)
(H : ℕ → Matrix (Fin n) (Fin n) ℝ) (w : ℕ → Fin n → ℝ)
(hrun : IsEllipsoidRun X f R c0 c H w) (t : ℕ) (hw : ∀ s ≤ t, w s ≠ 0)
(x : Fin n → ℝ) (hxX : x ∈ X) (hxt : x ∈ LinearOptimization.ellipsoid (c t) (H t))
(hxt1 : x ∉ LinearOptimization.ellipsoid (c (t + 1)) (H (t + 1))) :
c t ∈ X ∧ f (c t) < f x := by sorry
end ConvexOptAlg.Ellipsoid
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.