Remark 5.1, p. 174 — the strong convexity inequality of Proposition 5.1(a) remains true for all x, y ∈ Δ
ProvedBeckTeboulleMD.EMDA.remark_5_1entropyp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1strong-convexityunit-simplex
Let and with .
- For with the same support ( for every ),
where the terms with are . 2. is -strongly convex on all of with respect to : for and with ,
The remark extends Proposition 5.1(a) from the relative interior to the closed simplex, which is what is needed to apply Theorems 4.1 and 4.2 with and .
Formalization Note When the supports differ, the left side of (1) is on the page and "there is nothing to prove"; in Lean , so that case is excluded by the support hypothesis rather than stated with a junk value. Part (2) is the remark's conclusion read through Proposition 5.1(a)'s " is 1-strongly convex", written out with .
Preamble
import Mathlib import Definitions.Def_BeckTeboulleMD_EMDA_Setting
Formal statement
namespace BeckTeboulleMD.EMDA
/-- Remark 5.1, p. 174: the strong convexity inequality of Proposition 5.1(a) remains true on the
whole simplex `Δ` (with `0 ln 0 = 0`): (i) `∑_j (x_j − y_j) ln(x_j / y_j) ≥ ‖x − y‖₁²` for `x, y ∈ Δ`
with the same support (otherwise the left side is `+∞` on the page); (ii) `ψ_e` is `1`-strongly
convex on `Δ` with respect to `‖·‖₁`. -/
theorem remark_5_1 {n : ℕ} :
(∀ x ∈ stdSimplex ℝ (Fin n), ∀ y ∈ stdSimplex ℝ (Fin n), (∀ j, x j = 0 ↔ y j = 0) →
(∑ j, |x j - y j|) ^ 2 ≤ ∑ j, (x j - y j) * Real.log (x j / y j)) ∧
(∀ x ∈ stdSimplex ℝ (Fin n), ∀ y ∈ stdSimplex ℝ (Fin n), ∀ a b : ℝ,
0 ≤ a → 0 ≤ b → a + b = 1 →
entropy (a • x + b • y)
≤ a * entropy x + b * entropy y - a * b * (1 / 2 * (∑ j, |x j - y j|) ^ 2)) := by sorry
end BeckTeboulleMD.EMDA
Source
Beck & Teboulle, Mirror descent and nonlinear projected subgradient methods for convex optimization, Oper. Res. Lett. 31 (2003), p. 174, Remark 5.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.