Proposition 5, p. 11 — ρ_r(z) is non-increasing in r ∈ [0, ∞)
ProvedRestartPD.Fixed.prop_5monotonicitynormalized-duality-gapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , be convex, let be convex in on and concave in on , and let be any semi-norm. For every , the normalized duality gap is non-increasing on :
Monotonicity in the radius makes an honest limit and lets a bound on at one radius control all smaller radii.
Formalization Note Values are in . Only the convexity hypotheses of (1) are assumed. The page says "for any fixed "; is assumed, since for the ball may be empty for small and .
Preamble
import Mathlib import Definitions.Def_RestartPD_Fixed_Problem
Formal statement
namespace RestartPD.Fixed
/-- Proposition 5, p. 11: for a fixed `z ∈ Z`, `r ↦ ρ_r(z)` is non-increasing on `[0, ∞)`. -/
theorem prop_5 {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) :
AntitoneOn (fun r : ℝ => rho L X Y p r z) (Set.Ici 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 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.