Proposition 8, p. 17 — under Property 3, ‖z̄ᵗ − z⁰‖ = 0 forces z̄ᵗ ∈ Z⋆
ProvedRestartPD.Fixed.prop_8normalized-duality-gapp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1restarts
Assume the standing assumptions of (1) and let the base algorithm satisfy Property 3 with constants . Let , let be an output sequence of the algorithm started at , and let . If
This removes the degenerate case , where sharpness (defined only for ) says nothing, from the proofs of Theorems 1 and 2.
Formalization Note The page concludes "". With a semi-norm, does not give ; what the proof establishes and what Theorem 1 uses is , which is what is stated.
Preamble
import Mathlib import Definitions.Def_RestartPD_Fixed_Algorithms
Formal statement
namespace RestartPD.Fixed
/-- Proposition 8, p. 17: under Property 3, if `‖z̄ᵗ − z⁰‖ = 0` for an output `z̄ᵗ` (`t ≥ 1`) of a
run from `z⁰ ∈ Z`, then `z̄ᵗ ∈ Z⋆`. (The page also writes `z̄ᵗ = z⁰`, which a semi-norm does not
give; only the membership is stated.) -/
theorem prop_8 {n m : ℕ} (L : Primal n → Dual m → ℝ) (X : Set (Primal n)) (Y : Set (Dual m))
(hP : IsPDProblem L X Y) (p : Seminorm ℝ (E n m))
(Runs : E n m → Set (ℕ → E n m)) (q C : ℝ) (h3 : Property3 L X Y p Runs q C)
(z0 : E n m) (hz0 : z0 ∈ X ×ˢ Y) (zb : ℕ → E n m) (hzb : zb ∈ Runs z0)
(t : ℕ) (ht : 1 ≤ t) (hzero : p (zb t - z0) = 0) :
zb t ∈ Zstar L X Y := 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. 17, Proposition 8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.