§2 — the linear subproblem computes the gap
ProvedJaggiFW.PrimalDual.gap_eq_of_linear_minimizerduality-gapfrank-wolfelinear-minimizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a compact domain, let , and suppose that minimizes the linearized objective over . Then the duality gap is attained at :
Thus an exact Frank–Wolfe linear subproblem returns a numerical optimality certificate along with its atom.
Formalization Note The paper's standing convexity and continuous-differentiability assumptions are omitted because this identity uses only the linear derivative at . The chosen point makes the real supremum nonempty, and compactness bounds it.
Preamble
import Mathlib import Definitions.Def_JaggiFW_PrimalDual_Setting
Formal statement
namespace JaggiFW.PrimalDual
/-- The exact linear subproblem computes the gap, page 2 after equation (2). -/
theorem gap_eq_of_linear_minimizer {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
(D : Set E) (hDc : IsCompact D) (f : E → ℝ)
(x s : E) (hx : x ∈ D) (hs : s ∈ D)
(hsmin : ∀ ŝ ∈ D, fderiv ℝ f x s ≤ fderiv ℝ f x ŝ) :
dualityGap f D x = fderiv ℝ f x (x - s) := by sorry
end JaggiFW.PrimalDual
Source
Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, ICML 2013 (JMLR W&CP 28), https://proceedings.mlr.press/v28/jaggi13.html, PDF p. 2, §2 “The Duality Gap and Certificates”, paragraph beginning “While the value”
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.