§7.2: after the first iteration and
ProvedBoydADMM.Consensus.general_dual_sums_zeroadmmconsensusdual-variablesp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be any run of general form consensus ADMM (§7.2) with , and assume for every global index . Then, for every and every :
- the dual entries attached to sum to zero:
- the -update is plain local averaging:
Formalization Note "After the first iteration" is read as (the run starts at an arbitrary ). The hypothesis is implicit in the book. The run's -update is the argmin of the page's -objective, so item 2 is derived, not assumed.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- §7.2, p. 55: along every run of general form consensus ADMM with `ρ > 0` and every
`k_g ≥ 1`, after the first iteration (`k ≥ 1`) the dual entries attached to each global index
sum to zero, `∑_{G(i,j)=g} (y_i^k)_j = 0`, and the `z`-update is plain local averaging,
`z_g^{k+1} = (1/k_g) ∑_{G(i,j)=g} (x_i^{k+1})_j`. -/
theorem general_dual_sums_zero {n N : ℕ} {nl : Fin N → ℕ}
(G : (i : Fin N) → Fin (nl i) → Fin n) (hG : ∀ g, 1 ≤ kg G g) (ρ : ℝ) (hρ : 0 < ρ)
(Cf : (i : Fin N) → Set (EuclideanSpace ℝ (Fin (nl i))))
(f : (i : Fin N) → EuclideanSpace ℝ (Fin (nl i)) → ℝ)
(x : ℕ → (i : Fin N) → EuclideanSpace ℝ (Fin (nl i))) (z : ℕ → EuclideanSpace ℝ (Fin n))
(y : ℕ → (i : Fin N) → EuclideanSpace ℝ (Fin (nl i)))
(hrun : IsGeneralConsensusADMMRun G Cf f ρ x z y) :
(∀ k, 1 ≤ k → ∀ g, ∑ p ∈ entriesOf G g, y k p.1 p.2 = 0) ∧
(∀ k, 1 ≤ k → ∀ g,
z (k + 1) g = (1 / (kg G g : ℝ)) * ∑ p ∈ entriesOf G g, x (k + 1) p.1 p.2) := 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. 55, §7.2 (∑_{𝒢(i,j)=g} (y_i^k)_j = 0 after the first iteration; simplified z-update)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.