Consensus ADMM: , and the simplified iteration
ProvedBoydADMM.Consensus.consensus_dual_average_zeroadmmconsensusdual-variablesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be any run of global variable consensus ADMM (§7.1) with agents and . Then:
- the dual variables have average zero after the first iteration: for every ;
- for every ;
- for every , minimizes over ;
- for every , .
Items 3–4 are the book's simplified algorithm, in which the global variable no longer appears:
Formalization Note The book says "after the first iteration" and then "using " without an index range. Since , the identity needs , i.e. for an arbitrary starting ; we state exactly these ranges. and are made explicit.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- §7.1, p. 50: along every run of global variable consensus ADMM with `N ≥ 1`, `ρ > 0`:
(1) `ȳ^{k+1} = 0` for every `k ≥ 0` (the dual variables have average zero after the first
iteration); (2) `z^k = x̄^k` for every `k ≥ 2`; and hence the simplified iteration holds:
(3) for `k ≥ 2`, `x_i^{k+1}` minimizes `f_i(x_i) + y_i^{kT}(x_i − x̄^k) + (ρ/2)‖x_i − x̄^k‖²` over
`dom f_i`, and (4) for `k ≥ 1`, `y_i^{k+1} = y_i^k + ρ(x_i^{k+1} − x̄^{k+1})`. -/
theorem consensus_dual_average_zero {n N : ℕ} (hN : 0 < N) (ρ : ℝ) (hρ : 0 < ρ)
(Cf : Fin N → Set (EuclideanSpace ℝ (Fin n))) (f : Fin N → EuclideanSpace ℝ (Fin n) → ℝ)
(x : ℕ → Fin N → EuclideanSpace ℝ (Fin n)) (z : ℕ → EuclideanSpace ℝ (Fin n))
(y : ℕ → Fin N → EuclideanSpace ℝ (Fin n)) (hrun : IsConsensusADMMRun Cf f ρ x z y) :
(∀ k, avg (y (k + 1)) = 0) ∧
(∀ k, 2 ≤ k → z k = avg (x k)) ∧
(∀ k, 2 ≤ k → ∀ i, ∀ x' ∈ Cf i,
f i (x (k + 1) i) + ⟪y k i, x (k + 1) i - avg (x k)⟫_ℝ +
(ρ / 2) * ‖x (k + 1) i - avg (x k)‖ ^ 2 ≤
f i x' + ⟪y k i, x' - avg (x k)⟫_ℝ + (ρ / 2) * ‖x' - avg (x k)‖ ^ 2) ∧
(∀ k, 1 ≤ k → ∀ i, y (k + 1) i = y k i + ρ • (x (k + 1) i - avg (x (k + 1)))) := 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), p. 50, §7.1 (ȳ^{k+1} = 0 and the simplified algorithm)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.