(3.4)–(3.5), p. 11 — on (3.1), x₁^{k+1} is given by (3.4) and L(x₂, x₃, μ)^{k+1} = R(x₂, x₃, μ)^k with μ = λ/β
ProvedExtADMM.Diverge.eq_3_4_3_5admmlinear-recursionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1splitting-methods
Let be column vectors such that the matrix is nonsingular, and consider the linear system (3.1), with , as an instance of problem (1.1). Let and let be any run of the direct extension of ADMM (1.5) on it. Put . Then for every ,
and
with the matrices of (3.6) and of (3.7).
The point is that neither nor involves : in the scaled variables the iteration is the same linear map for every penalty parameter. This is what makes the divergence of the example hold for every at once.
Formalization Note. The run is any sequence satisfying the minimiser conditions of (1.5); no particular minimiser is chosen. is never read. has components , indexed in Lean.
Preamble
import Mathlib import Definitions.Def_ExtADMM_Diverge_Setting open Matrix Filter Topology
Formal statement
namespace ExtADMM.Diverge
/-- (3.4)–(3.5), p. 11. For the linear system (3.1) with columns `a₁, a₂, a₃ ∈ ℝ³` such that
`[A₁, A₂, A₃]` is nonsingular, and any `β > 0`, every run of the direct extension of ADMM (1.5)
satisfies, for every `k`, the closed form (3.4) of `x₁^{k+1}` and the recursion (3.5)
`L (x₂^{k+1}, x₃^{k+1}, μ^{k+1}) = R (x₂ᵏ, x₃ᵏ, μᵏ)` in the variables `μ = λ/β`. -/
theorem eq_3_4_3_5 (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 : ℕ) :
x1 (k+1) 0 = (1 / (a1 ⬝ᵥ a1)) *
(-(a1 ⬝ᵥ a2) * x2 k 0 - (a1 ⬝ᵥ a3) * x3 k 0 + a1 ⬝ᵥ (β⁻¹ • lam k)) ∧
Lmat a2 a3 *ᵥ stateVec β (x2 (k+1)) (x3 (k+1)) (lam (k+1)) =
Rmat a1 a2 a3 *ᵥ stateVec β (x2 k) (x3 k) (lam k) := 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.3)–(3.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.