Lemma 1, p. 310 — Σⱼ pⱼwⱼ(p) = n for every p ∈ S_F
ProvedKhachiyanRound.BCD.lemma_1d-optimal-designleveragep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be a point of the unit simplex with , where . With ,
The -weighted average of the leverages is exactly the dimension. In particular , so the accuracy is nonnegative, and the identity is the complementary-slackness ingredient of the Kiefer–Wolfowitz conditions.
Formalization Note The page states the lemma in §2, whose standing assumptions are central symmetry (2.1), full dimension (2.2) and ; the lemma uses none of them, and the Lean statement drops all three.
Preamble
import Mathlib import Definitions.Def_LinearOptimization_Ellipsoid import Definitions.Def_KhachiyanRound_BCD_Setting open scoped Pointwise
Formal statement
namespace KhachiyanRound.BCD
theorem lemma_1 {ι : Type*} [Fintype ι] {n : ℕ} (a : ι → Fin n → ℝ)
(p : ι → ℝ) (hp : p ∈ SF a) :
∑ j, p j * w a p j = (n : ℝ) := by sorry
end KhachiyanRound.BCD
Source
Khachiyan, Rounding of polytopes in the real number model of computation, Math. Oper. Res. 21 (1996), p. 310, Lemma 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.