Lemma 3 — a three-step linear recursion with block-bounded perturbations has summable terms
ProvedBotNguyenADMM.KL.lemma_3nonconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1real-sequences
Let and satisfy, for every ,
where , and componentwise. Assume there is with for all . Then for every , and for every and every ,
It closes the proof of Theorem 14, applied with and .
Preamble
import Mathlib open Filter Topology
Formal statement
namespace BotNguyenADMM.KL
/-- Lemma 3 (p. 6). Let `aᵏ ∈ ℝᴺ₊` and `δ_k ∈ ℝ` satisfy
`⟨𝟙, aᵏ⁺¹⟩ ≤ ⟨c₀, aᵏ⟩ + ⟨c₁, aᵏ⁻¹⟩ + ⟨c₂, aᵏ⁻²⟩ + δ_k` for all `k ≥ 2` (9), where `c₀ ∈ ℝᴺ`,
`c₁, c₂ ∈ ℝᴺ₊` and `c₀ + c₁ + c₂ < 𝟙` componentwise, and let `δ̄ ≥ 0` bound every block sum
`∑_{k=K̲}^{K̄} δ_k` with `K̄ ≥ K̲ ≥ 2`. Then every coordinate sequence `(a_iᵏ)_k` is summable and
(10) holds for every `i` and every `K̄ ≥ K̲ ≥ 2`. -/
theorem lemma_3 (N : ℕ) (a : ℕ → Fin N → ℝ) (ha : ∀ k i, 0 ≤ a k i) (δ : ℕ → ℝ)
(c₀ c₁ c₂ : Fin N → ℝ) (hc₁ : ∀ i, 0 ≤ c₁ i) (hc₂ : ∀ i, 0 ≤ c₂ i)
(hc : ∀ i, c₀ i + c₁ i + c₂ i < 1)
(h9 : ∀ k, 2 ≤ k → ∑ i, a (k + 1) i ≤
∑ i, c₀ i * a k i + ∑ i, c₁ i * a (k - 1) i + ∑ i, c₂ i * a (k - 2) i + δ k)
(δbar : ℝ) (hδbar : 0 ≤ δbar)
(hδ : ∀ Klo Khi : ℕ, 2 ≤ Klo → Klo ≤ Khi → ∑ k ∈ Finset.Icc Klo Khi, δ k ≤ δbar) :
(∀ i, Summable (fun k => a k i)) ∧
∀ (i : Fin N) (Klo Khi : ℕ), 2 ≤ Klo → Klo ≤ Khi →
∑ k ∈ Finset.Icc Klo Khi, a k i ≤
(∑ j, ((1 - c₀ j - c₁ j) * a Klo j + (1 - c₀ j) * a (Klo + 1) j + a (Klo + 2) j)
+ δbar) / (1 - c₀ i - c₁ i - c₂ i) := by sorry
end BotNguyenADMM.KL
Source
Boţ and Nguyen, The proximal ADMM in the nonconvex setting, arXiv:1801.01994v2, p. 6, Lemma 3, (9)–(10)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.