Proof of Theorem 1, first display, p. 17 — if (31) holds for n ≤ N then z^{N+1,0} ∈ W_R(z^{0,0})
ProvedRestartPD.Fixed.thm1_partial_suminductionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1restarts
Let the base algorithm satisfy Property 3 with constants , let , let , and let , be a run of Algorithm 1 restarting every inner steps from . If for some
then
and therefore with .
This is the step of the induction in Theorem 1 that keeps the outer iterates inside the set on which sharpness is assumed.
Formalization Note The restart length is any ; this step does not use its value. The standing assumptions of (1) are not needed and not assumed.
Preamble
import Mathlib import Definitions.Def_RestartPD_Fixed_Algorithms
Formal statement
namespace RestartPD.Fixed
/-- Proof of Theorem 1, first display, p. 17: in a fixed-frequency restart run, if (31) holds for
all `n ≤ N`, then `‖z^{N+1,0} − z^{0,0}‖ ≤ ((q + 2)/(1 − β)) dist(z^{0,0}, Z⋆)`, i.e.
`z^{N+1,0} ∈ W_R(z^{0,0})`. -/
theorem thm1_partial_sum {n m : ℕ} (L : Primal n → Dual m → ℝ) (X : Set (Primal n))
(Y : Set (Dual m)) (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β : β ∈ Set.Ioo (0 : ℝ) 1)
(tstar : ℕ) (htstar : 1 ≤ tstar)
(z : ℕ → E n m) (zb : ℕ → ℕ → E n m) (hz0 : z 0 ∈ X ×ˢ Y)
(hrun : IsFixedRestartRun Runs tstar z zb)
(N : ℕ) (hind : ∀ k ≤ N, distZ L X Y p (z k) ≤ β ^ k * distZ L X Y p (z 0)) :
p (z (N + 1) - z 0) ≤ (q + 2) / (1 - β) * distZ L X Y p (z 0) ∧
z (N + 1) ∈ Wball X Y p ((q + 2) / (1 - β) * distZ L X Y p (z 0)) (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, proof of Theorem 1, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.