Proposition 6, p. 11 — the primal-dual gap at z is zero iff ρ_r(z) = 0
ProvedRestartPD.Fixed.prop_6normalized-duality-gapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dual-gap
Let , be convex, let be convex in on and concave in on , and let be any semi-norm. For every and every ,
Since a point has zero primal-dual gap exactly when it solves (1), the normalized duality gap at any radius detects solutions.
Formalization Note Both sides are extended reals. Only the convexity hypotheses of (1) are assumed; is assumed, as on the page, where is evaluated at feasible points.
Preamble
import Mathlib import Definitions.Def_RestartPD_Fixed_Problem
Formal statement
namespace RestartPD.Fixed
/-- Proposition 6, p. 11: for `z ∈ Z` and `r ∈ [0, ∞)`, the primal-dual gap (3) at `z` is zero
if and only if `ρ_r(z) = 0`. -/
theorem prop_6 {n m : ℕ} (L : Primal n → Dual m → ℝ) (X : Set (Primal n)) (Y : Set (Dual m))
(hX : Convex ℝ X) (hY : Convex ℝ Y)
(hLx : ∀ y ∈ Y, ConvexOn ℝ X (fun x => L x y))
(hLy : ∀ x ∈ X, ConcaveOn ℝ Y (fun y => L x y))
(p : Seminorm ℝ (E n m)) (z : E n m) (hz : z ∈ X ×ˢ Y) (r : ℝ) (hr : 0 ≤ r) :
pdGap L X Y z = 0 ↔ rho L X Y p r z = 0 := by sorry
end RestartPD.Fixed
Source
Applegate, Hinder, Lu & Lubin, Faster First-Order Primal-Dual Methods for Linear Programming using Restarts and Sharpness, arXiv:2105.12715v4, p. 11, Proposition 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.