Consensus ADMM: the -update is
ProvedBoydADMM.Consensus.consensus_z_update_averageadmmconsensusp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Consider global variable consensus with agents and . Fix (the new local iterates ) and (the dual variables ). The -update of ADMM minimizes the augmented Lagrangian
over . Its minimizer is unique and equals the average step:
This is why the central collector of consensus ADMM only has to average.
Formalization Note The book states the algorithm with the averaging formula (p. 49) and rewrites it with overlines (p. 50); the statement here is the underlying fact that this formula is the exact (and unique) minimizer of in . The terms are constants in and are kept as in . The hypotheses and are implicit in the book.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- §7.1, pp. 49–50: the consensus `z`-update, the minimization of
`L_ρ(x^{k+1}, z, y^k)` over `z ∈ ℝⁿ`, has the unique solution `z = x̄^{k+1} + (1/ρ) ȳ^k`. The
terms `f_i(x_i^{k+1})` of `L_ρ` do not depend on `z` and are kept. -/
theorem consensus_z_update_average {n N : ℕ} (hN : 0 < N) (ρ : ℝ) (hρ : 0 < ρ)
(f : Fin N → EuclideanSpace ℝ (Fin n) → ℝ)
(x y : Fin N → EuclideanSpace ℝ (Fin n)) (z : EuclideanSpace ℝ (Fin n)) :
(∀ z' : EuclideanSpace ℝ (Fin n),
∑ i, (f i (x i) + ⟪y i, x i - z⟫_ℝ + (ρ / 2) * ‖x i - z‖ ^ 2) ≤
∑ i, (f i (x i) + ⟪y i, x i - z'⟫_ℝ + (ρ / 2) * ‖x i - z'‖ ^ 2)) ↔
z = avg x + (1 / ρ) • avg y := by sorry
end BoydADMM.Consensus
Source
Boyd, Parikh, Chu, Peleato, Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn. 3(1) (2011), pp. 49–50, §7.1 (ADMM for (7.1) and its simplification z^{k+1} = x̄^{k+1} + (1/ρ)ȳ^k)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.