Theorem 1, p. 17 — with fixed-frequency restarts on an α-sharp problem, dist(z^{n,0}, Z⋆) ≤ βⁿ dist(z^{0,0}, Z⋆)
ProvedRestartPD.Fixed.theorem_1Assume the standing assumptions of (1): , closed and convex, differentiable, convex in and concave in , and . Let be a semi-norm, and let the base primal-dual algorithm satisfy Property 3 with constants . Let and , and run Algorithm 1 from with the fixed-frequency restart rule (29): restart every
inner steps, . Suppose (1) is -sharp on with
Then for every outer iteration ,
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 and every run. The restart length is the natural number (Nat.ceil). is assumed (a sharpness constant is positive, and divides by ). replaces the page's "non-empty feasible region and bounded optimal value". Sharpness is assumed only on and only for radii in , as in Definition 1.
import Mathlib import Definitions.Def_RestartPD_Fixed_Algorithms
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.