(B.4), p. 40 — ε²_{k+8} < (1/2)(ε²_{k+1} + ε²_k) while the iterates stay on the cycle's pieces
ProvedIQCAlg.HeavyBall.eq_B_4contractionheavy-balllimit-cyclep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let satisfy (B.1), let be its perturbation from the cycle (B.3), and fix . Assume that each of lies on the same linear piece of (4.11) as the corresponding (if then ; if then ), and that . Then
This is the eight-step contraction of the perturbation that drives the tail argument.
Formalization Note Two departures from the printed (B.4), both disclosed. (i) The page's strict inequality fails when (it would read ), so is assumed. (ii) The page's middle terms involve , which would need the same-piece condition at as well; the statement keeps only the outer inequality, which needs the condition at (since is the second entry of ).
Preamble
import Mathlib import Definitions.Def_IQCAlg_HeavyBall_Setting
Formal statement
namespace IQCAlg.HeavyBall
/-- (B.4), p. 40: if `x` satisfies (B.1), the iterates `x_{k+1}, …, x_{k+7}` lie on the same
pieces of (4.11) as the cycle, and `(ε_{k+1}, ε_k) ≠ 0`, then
`ε²_{k+8} < (1/2)(ε²_{k+1} + ε²_k)`. -/
theorem eq_B_4 (x : ℕ → ℝ) (hx : IsB1Traj x) (k : ℕ)
(hpiece : ∀ j : ℕ, 1 ≤ j → j ≤ 7 →
(cyc (k + j) < 1 → x (k + j) < 1) ∧ (2 < cyc (k + j) → 2 < x (k + j)))
(hne : eps x k ≠ 0 ∨ eps x (k + 1) ≠ 0) :
eps x (k + 8) ^ 2 < 1 / 2 * (eps x (k + 1) ^ 2 + eps x k ^ 2) := by sorry
end IQCAlg.HeavyBall
Source
Lessard, Recht & Packard, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, arXiv:1408.3595v7, p. 40, (B.4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.