(32), proof of Theorem 1, p. 17 — one restart contracts dist(·, Z⋆) by β inside W_R(z^{0,0})
ProvedRestartPD.Fixed.eq_32linear-convergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1restartssharpness
Assume the standing assumptions of (1). Let the base algorithm satisfy Property 3 with constants , let and , and let , be a run of Algorithm 1 from with the fixed-frequency rule
Let and suppose (1) is -sharp on . If both and lie in , then
This is the contraction step of the induction in Theorem 1: sharpness at radius , Property 3 and the choice of combine into a factor .
Formalization Note The display (32) ends with "", which is the induction hypothesis; that last step is left to Theorem 1. Both and are assumed in because the radius used in the sharpness inequality must not exceed ; the proof has both facts from the induction.
Preamble
import Mathlib import Definitions.Def_RestartPD_Fixed_Algorithms
Formal statement
namespace RestartPD.Fixed
/-- (32), proof of Theorem 1, p. 17: in a fixed-frequency restart run with
`t⋆ = ⌈2C(q + 2)/(αβ)⌉`, on a problem that is `α`-sharp on `W_R(z^{0,0})`,
`R = ((q + 2)/(1 − β)) dist(z^{0,0}, Z⋆)`, if `z^{N,0}` and `z^{N+1,0}` lie in `W_R(z^{0,0})` then
`dist(z^{N+1,0}, Z⋆) ≤ β dist(z^{N,0}, Z⋆)`. -/
theorem eq_32 {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)))
(N : ℕ)
(hN : z N ∈ Wball X Y p ((q + 2) / (1 - β) * distZ L X Y p (z 0)) (z 0))
(hN1 : z (N + 1) ∈ Wball X Y p ((q + 2) / (1 - β) * distZ L X Y p (z 0)) (z 0)) :
distZ L X Y p (z (N + 1)) ≤ β * distZ L X Y p (z N) := 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, proof of Theorem 1, (32)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.