(B.1)–(B.3), pp. 39–40 — α = 1/9, β = 4/9, and (p, q, r) is the unique solution of the linear system and a 3-cycle of (B.1)
ProvedIQCAlg.HeavyBall.eq_B_3counterexampleheavy-balllimit-cyclep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For and (so ), the Heavy-ball parameters of Proposition 1 are
so the update is (B.1): .
Let , , . Then:
- , and ;
- solves
and every real solution of this system equals ; 3. the period-3 sequence satisfies (B.1) with from (4.11) for every , i.e. the trajectory (B.2) with values (B.3) is a fixed point of (B.1).
This identifies the limit cycle that the Heavy-ball method approaches in the counterexample.
Preamble
import Mathlib import Definitions.Def_IQCAlg_HeavyBall_Setting
Formal statement
namespace IQCAlg.HeavyBall
/-- (B.1)–(B.3), pp. 39–40: Proposition 1's Heavy-ball tuning at `L = 25`, `m = 1` is
`α = 1/9`, `β = 4/9` (so the update is (B.1)); `p < 1`, `q < 1`, `r > 2`; `(p, q, r)` of (B.3)
solves the linear system of p. 39 and is its unique solution; and the period-3 sequence
`p, q, r, p, …` satisfies (B.1). -/
theorem eq_B_3 :
hbAlpha 25 1 = 1 / 9 ∧ hbBeta 25 1 = 4 / 9 ∧
pC < 1 ∧ qC < 1 ∧ 2 < rC ∧
(4 * pC + 12 * qC + 9 * rC = 0 ∧ 9 * pC + 4 * qC + 12 * rC = 24 ∧
12 * pC + 9 * qC + 4 * rC = 0) ∧
(∀ a b c : ℝ, 4 * a + 12 * b + 9 * c = 0 → 9 * a + 4 * b + 12 * c = 24 →
12 * a + 9 * b + 4 * c = 0 → a = pC ∧ b = qC ∧ c = rC) ∧
IsB1Traj cyc := by sorry
end IQCAlg.HeavyBall
Source
Lessard, Recht & Packard, Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints, arXiv:1408.3595v7, pp. 39–40, (B.1), (B.2), the linear system, (B.3) and the sentence after it; p. 6, Proposition 1, last row
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.