Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, p. 17 — with fixed-frequency restarts on an α-sharp problem, dist(z^{n,0}, Z⋆) ≤ βⁿ dist(z^{0,0}, Z⋆)

Proved
RestartPD.Fixed.theorem_1

by mikedeng1 · Oct 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

linear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1primal-dualrestartssharpness

Assume the standing assumptions of (1): XXX, YYY closed and convex, LLL differentiable, convex in xxx and concave in yyy, and Z⋆≠∅Z^\star \neq \emptysetZ⋆=∅. Let ∥⋅∥\|\cdot\|∥⋅∥ be a semi-norm, and let the base primal-dual algorithm satisfy Property 3 with constants q,C>0q, C > 0q,C>0. Let α>0\alpha > 0α>0 and β∈(0,1)\beta \in (0, 1)β∈(0,1), and run Algorithm 1 from z0,0∈Zz^{0,0} \in Zz0,0∈Z with the fixed-frequency restart rule (29): restart every

t⋆=⌈2C(q+2)αβ⌉t^\star = \left\lceil \frac{2C(q+2)}{\alpha\beta} \right\rceilt⋆=⌈αβ2C(q+2)​⌉

inner steps, zn+1,0=zˉn,t⋆z^{n+1,0} = \bar z^{n,t^\star}zn+1,0=zˉn,t⋆. Suppose (1) is α\alphaα-sharp on WR(z0,0)W_R(z^{0,0})WR​(z0,0) with

R=q+21−βdist⁡(z0,0,Z⋆).R = \frac{q+2}{1-\beta} \operatorname{dist}(z^{0,0}, Z^\star).R=1−βq+2​dist(z0,0,Z⋆).

Then for every outer iteration n≥0n \ge 0n≥0,

dist⁡(zn,0,Z⋆)≤βndist⁡(z0,0,Z⋆).(31)\operatorname{dist}(z^{n,0}, Z^\star) \le \beta^n \operatorname{dist}(z^{0,0}, Z^\star). \tag{31}dist(zn,0,Z⋆)≤βndist(z0,0,Z⋆).(31)

With PDHG, EGM, PPM or ADMM as the base algorithm and the LP sharpness of Lemma 5, this gives linear convergence of restarted primal-dual methods for linear programming.

Formalization Note The base algorithm is the set of its admissible output sequences from each start; Property 3 holds for every start in ZZZ and every run. The restart length is the natural number ⌈2C(q+2)/(αβ)⌉\lceil 2C(q+2)/(\alpha\beta) \rceil⌈2C(q+2)/(αβ)⌉ (Nat.ceil). α>0\alpha > 0α>0 is assumed (a sharpness constant is positive, and t⋆t^\start⋆ divides by α\alphaα). Z⋆≠∅Z^\star \neq \emptysetZ⋆=∅ replaces the page's "non-empty feasible region and bounded optimal value". Sharpness is assumed only on WR(z0,0)W_R(z^{0,0})WR​(z0,0) and only for radii in (0,diam⁡(WR(z0,0))](0, \operatorname{diam}(W_R(z^{0,0}))](0,diam(WR​(z0,0))], as in Definition 1.

Preamble
import Mathlib
import Definitions.Def_RestartPD_Fixed_Algorithms
Formal statement
namespace RestartPD.Fixed

/-- Theorem 1 (Fixed frequency restarts), p. 17: if the base algorithm satisfies Property 3 with
`q, C`, the problem is `α`-sharp on `W_R(z^{0,0})` with `R = ((q + 2)/(1 − β)) dist(z^{0,0}, Z⋆)`,
and Algorithm 1 restarts every `t⋆ = ⌈2C(q + 2)/(αβ)⌉` inner steps (29), then
`dist(z^{n,0}, Z⋆) ≤ βⁿ dist(z^{0,0}, Z⋆)` for every `n ≥ 0` (31). -/
theorem theorem_1 {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)
    (α β : ℝ) (hα : 0 < α) (hβ : β ∈ Set.Ioo (0 : ℝ) 1)
    (z : ℕ → E n m) (zb : ℕ → ℕ → E n m) (hz0 : z 0 ∈ X ×ˢ Y)
    (hrun : IsFixedRestartRun Runs (Nat.ceil (2 * C * (q + 2) / (α * β))) z zb)
    (hsharp : IsSharpOn L X Y p α
      (Wball X Y p ((q + 2) / (1 - β) * distZ L X Y p (z 0)) (z 0))) :
    ∀ k : ℕ, distZ L X Y p (z k) ≤ β ^ k * distZ L X Y p (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. 17, Theorem 1 (31)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me