Appendix B, p. 40 — on the cycle's pieces, (ε_{k+2}, ε_{k+1}) = P (ε_{k+1}, ε_k)
ProvedIQCAlg.HeavyBall.perturbation_recursionheavy-balllimit-cyclelinearizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real sequence satisfying (B.1) for every , let be the 3-cycle of (B.3), and let . Fix and assume that lies on the same linear piece of (4.11) as : if then , and if then . Then
Near the cycle the nonlinear recursion is therefore a linear time-invariant recursion for the perturbation, which is what the remaining steps of the argument analyse.
Formalization Note The same-piece condition is stated, as on the page, by membership of the iterate in the piece of its limit point; it is needed only at index , the argument of in (B.1).
Preamble
import Mathlib import Definitions.Def_IQCAlg_HeavyBall_Setting
Formal statement
namespace IQCAlg.HeavyBall
/-- Perturbation recursion, p. 40: if `x` satisfies (B.1) and the iterate `x_{k+1}` lies on
the same piece of (4.11) as `x⋆_{k+1}`, then `(ε_{k+2}, ε_{k+1}) = P (ε_{k+1}, ε_k)`, i.e.
`ε_{k+2} = −(4/3) ε_{k+1} − (4/9) ε_k`. -/
theorem perturbation_recursion (x : ℕ → ℝ) (hx : IsB1Traj x) (k : ℕ)
(hpiece : (cyc (k + 1) < 1 → x (k + 1) < 1) ∧ (2 < cyc (k + 1) → 2 < x (k + 1))) :
![eps x (k + 2), eps x (k + 1)] = Pm.mulVec ![eps x (k + 1), eps x k] := by sorry
end IQCAlg.HeavyBall
Source
Lessard, Recht & Packard, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, arXiv:1408.3595v7, p. 40, perturbation recursion (the display defining P)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.