§2 — linearization and primal-error certificate
ProvedJaggiFW.PrimalDual.gap_ge_primal_errorconvexityduality-gapfrank-wolfep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a compact convex domain, let be a convex, continuously differentiable objective, and let minimize on . At every feasible , the linearization at lies below . Consequently, the duality gap bounds the primal error:
The gap is therefore a certificate for the quality of a feasible iterate, even when the optimal value is unknown.
Formalization Note The derivative pairing is written as on a real normed space. Convexity is required on ; continuous differentiability is kept from the paper's standing assumptions.
Preamble
import Mathlib import Definitions.Def_JaggiFW_PrimalDual_Setting
Formal statement
namespace JaggiFW.PrimalDual
/-- The linearization inequality and the certificate following equation (2), page 2. -/
theorem gap_ge_primal_error {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
(D : Set E) (hDc : IsCompact D) (hDconv : Convex ℝ D)
(f : E → ℝ) (hfC1 : ContDiff ℝ 1 f) (hfconv : ConvexOn ℝ D f)
(xstar : E) (hxstar : xstar ∈ D) (hmin : ∀ y ∈ D, f xstar ≤ f y) :
(∀ x ∈ D, ∀ s ∈ D, f x + fderiv ℝ f x (s - x) ≤ f s) ∧
(∀ x ∈ D, f x - f xstar ≤ dualityGap f D x) := 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 following (2)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.