EDA, p. 174 — the EDA update is the SANP step (3.11) with ψ = ψ_e on X = Δ and stays in int Δ
ProvedBeckTeboulleMD.EMDA.eda_is_sanp_stepentropic-mirror-descentexponentiated-gradientmirror-descentp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1unit-simplex
Let (all , ), and , and define
Then , and minimises the SANP objective over the simplex:
With and , this says that the entropic descent algorithm (EDA) is exactly SANP (3.11) with and , and that its iterates remain in the relative interior of , so that Theorems 4.1 and 4.2 apply to it.
Formalization Note The page derives the EDA by "using the entropy function in (3.12)", that is, in SANP with a satisfying (3.12); this item states the resulting identification for one step. , and uses the derivative of at , which exists because has positive entries.
Preamble
import Mathlib import Definitions.Def_BeckTeboulleMD_EMDA_Setting
Formal statement
namespace BeckTeboulleMD.EMDA
/-- The EDA is SANP with `ψ_e` on `Δ`, p. 174: for `y` in the relative interior of `Δ`, a vector `z`
(the subgradient `f′(y)`) and `t > 0`, the point `w_j = y_j e^{−t z_j} / ∑_i y_i e^{−t z_i}` lies in
the relative interior of `Δ` and minimises `u ↦ ⟨u, z⟩ + (1/t) B_{ψ_e}(u, y)` over `Δ`. -/
theorem eda_is_sanp_step {n : ℕ} (y : Fin n → ℝ) (hy : y ∈ relIntSimplex n)
(z : Fin n → ℝ) (t : ℝ) (ht : 0 < t) :
(fun j => y j * Real.exp (-(t * z j)) / ∑ i, y i * Real.exp (-(t * z i))) ∈ relIntSimplex n ∧
∀ u ∈ stdSimplex ℝ (Fin n),
∑ j, (y j * Real.exp (-(t * z j)) / ∑ i, y i * Real.exp (-(t * z i))) * z j
+ (1 / t) * bregman (entropy (n := n))
(fun j => y j * Real.exp (-(t * z j)) / ∑ i, y i * Real.exp (-(t * z i))) y
≤ ∑ j, u j * z j + (1 / t) * bregman (entropy (n := n)) u y := 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, the entropic descent algorithm (EDA) and the sentence preceding it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.