Theorem 20 for Algorithm 1 with — rates for the proximal ADMM iterates when
OpenBotNguyenADMM.Rates.theorem_20_prox_mu1_zeroThis is Theorem 20 of Boţ–Nguyen restricted to Algorithm 1 (the proximal ADMM) with metric bound , i.e. for all .
Suppose Assumption 2 holds for Algorithm 1 with , and let be a bounded sequence generated by Algorithm 1 that converges to . Suppose that the Section 3 regularized augmented Lagrangian
satisfies the Łojasiewicz property (70) at with constant and exponent . Then:
- if , then for all large ;
- if , there are , and such that for every
- if , there are and such that for every
The paper's Assumption 1/2 allows , so this case is covered by the paper's Theorem 20. It is exactly the case in which vanishes: then carries no term, and the constants , and used in Lemmas 17 and 19 degenerate. For Algorithm 2, and for Algorithm 1 with , one has , and Theorem 20 follows from Theorem 18 and Lemma 19.
Formalization Note Same formal setting and conventions as BotNguyenADMM.Rates.theorem_20 (the limit and the Łojasiewicz property are packaged in LojAt; any valid bounds lam, μ₂ may be used), with the extra hypotheses v = prox and μ₁ = 0.
import Mathlib import Definitions.Def_BotNguyenADMM_Rates_Setting import Definitions.Def_BotNguyenADMM_Rates_Lojasiewicz open Filter Topology open scoped InnerProductSpace RealInnerProductSpace open NonconvexSplitting.Shared
namespace BotNguyenADMM.Rates
/-- **Theorem 20, case of Algorithm 1 with `μ₁ = 0`** (Boţ–Nguyen, arXiv:1801.01994v2, p. 28).
The statement of Theorem 20 for Algorithm 1 (`v = prox`) with the metric bound `μ₁ = 0`, i.e. the
case where the constant `C₁ = 4T₀μ₁²/r` vanishes and the constants `C₁₇`, `C₁₉`, `C₂₀` used in
the paper's proof (Lemmas 17 and 19) degenerate. -/
theorem theorem_20_prox_mu1_zero
{n m : ℕ} (v : BotNguyenADMM.KL.Variant) (g : BotNguyenADMM.KL.E m → EReal) (h : BotNguyenADMM.KL.E n → ℝ) (A : BotNguyenADMM.KL.E n →L[ℝ] BotNguyenADMM.KL.E m)
(L r ρ lam μ₁ μ₂ : ℝ) (M₁ : ℕ → BotNguyenADMM.KL.E n →L[ℝ] BotNguyenADMM.KL.E n) (M₂ : ℕ → BotNguyenADMM.KL.E m →L[ℝ] BotNguyenADMM.KL.E m)
(hv : v = BotNguyenADMM.KL.Variant.prox) (hμ₁ : μ₁ = 0)
(hA2 : Assumption2 v g h A L r ρ lam μ₁ μ₂ M₁ M₂)
(x : ℕ → BotNguyenADMM.KL.E n) (z y : ℕ → BotNguyenADMM.KL.E m) (hrun : IsRun v g h A r ρ M₁ M₂ x z y)
(hbx : Bornology.IsBounded (Set.range x)) (hbz : Bornology.IsBounded (Set.range z))
(hby : Bornology.IsBounded (Set.range y))
(xh : BotNguyenADMM.KL.E n) (zh yh : BotNguyenADMM.KL.E m) (CL θ : ℝ)
(hloj : LojAt v g h A L r ρ lam μ₁ x z y xh zh yh CL θ) :
(θ = 0 → ∃ K : ℕ, ∀ k ≥ K, x k = xh ∧ z k = zh ∧ y k = yh) ∧
(0 < θ ∧ θ ≤ 1 / 2 → ∃ k₀ : ℕ, 1 ≤ k₀ ∧
∃ C01 C02 C03 Qhat : ℝ, 0 < C01 ∧ 0 < C02 ∧ 0 < C03 ∧ 0 ≤ Qhat ∧ Qhat < 1 ∧
∀ k ≥ k₀, ‖x k - xh‖ ≤ C01 * Qhat ^ k ∧ ‖y k - yh‖ ≤ C02 * Qhat ^ k ∧
‖z k - zh‖ ≤ C03 * Qhat ^ k) ∧
(1 / 2 < θ ∧ θ < 1 → ∃ k₀ : ℕ, 3 ≤ k₀ ∧
∃ C11 C12 C13 : ℝ, 0 < C11 ∧ 0 < C12 ∧ 0 < C13 ∧
∀ k ≥ k₀, ‖x k - xh‖ ≤ C11 * ((k : ℝ) - 1) ^ (-((1 - θ) / (2 * θ - 1))) ∧
‖y k - yh‖ ≤ C12 * ((k : ℝ) - 1) ^ (-((1 - θ) / (2 * θ - 1))) ∧
‖z k - zh‖ ≤ C13 * ((k : ℝ) - 2) ^ (-((1 - θ) / (2 * θ - 1)))) := by sorry
end BotNguyenADMM.Rates