(3.8)–(3.9), p. 11 — on (3.1), (x₂ᵏ, x₃ᵏ, μᵏ) = Mᵏ(x₂⁰, x₃⁰, μ⁰) with M = L⁻¹R
ProvedExtADMM.Diverge.eq_3_8admmlinear-recursionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1splitting-methods
Let be such that is nonsingular, let , and let be any run of the direct extension of ADMM (1.5) on the linear system (3.1). With and (3.9), for every
So the extended ADMM on (3.1) is a fixed linear iteration on , independent of , and its behaviour is governed by the powers of .
Formalization Note. is lower triangular with , which is nonzero under the nonsingularity hypothesis, so is the genuine inverse. The page writes the identity as applied to the starting point; the Lean states it for every as , which is the same family of identities together with the trivial case .
Preamble
import Mathlib import Definitions.Def_ExtADMM_Diverge_Setting open Matrix Filter Topology
Formal statement
namespace ExtADMM.Diverge
/-- (3.8)–(3.9), p. 11. For the linear system (3.1) with `[A₁, A₂, A₃]` nonsingular and any
`β > 0`, every run of (1.5) satisfies
`(x₂ᵏ, x₃ᵏ, μᵏ) = Mᵏ (x₂⁰, x₃⁰, μ⁰)` with `M = L⁻¹R` and `μ = λ/β`. -/
theorem eq_3_8 (a1 a2 a3 : Fin 3 → ℝ) (hA : (colMat a1 a2 a3).det ≠ 0)
(β : ℝ) (hβ : 0 < β)
(x1 x2 x3 : ℕ → Fin 1 → ℝ) (lam : ℕ → Fin 3 → ℝ)
(hrun : (instance31 a1 a2 a3).IsRun15 β x1 x2 x3 lam) (k : ℕ) :
stateVec β (x2 k) (x3 k) (lam k) =
(Mmat a1 a2 a3 ^ k) *ᵥ stateVec β (x2 0) (x3 0) (lam 0) := by sorry
end ExtADMM.Diverge
Source
Chen, He, Ye & Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., DOI 10.1007/s10107-014-0826-5 (authors' version of January 22, 2014), p. 11, (3.8)–(3.9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.