Table 1: the simplex support function is the largest coordinate
ProvedJaggiFW.Sparsity.support_simplexfrank-wolfep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1simplexsupport-function
Let and . The unit simplex is the convex hull of the unit basis vectors (the atoms of this row), and its support function is attained and equals the largest coordinate of :
This identifies the linear subproblem used by a Frank–Wolfe step on the simplex.
Formalization Note The statement asserts an attaining coordinate and an attained maximum on the simplex. The table's algorithmic cost is outside the mathematical claim.
Preamble
import Mathlib import Definitions.Def_JaggiFW_Sparsity_Setting
Formal statement
namespace JaggiFW.Sparsity
/-- The simplex row of Table 1, PDF p. 6. -/
theorem support_simplex {n : ℕ} (hn : 0 < n) (y : Fin n → ℝ) :
stdSimplex ℝ (Fin n) = convexHull ℝ (Set.range fun i : Fin n => (Pi.single i 1 : Fin n → ℝ)) ∧
∃ i : Fin n, (∀ j, y j ≤ y i) ∧
IsGreatest ((fun s => ∑ j, s j * y j) '' stdSimplex ℝ (Fin n)) (y i) := by sorry
end JaggiFW.Sparsity
Source
Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, ICML 2013 (JMLR W&CP 28), PDF p. 6, Table 1, simplex row
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.