§7.2: the general form consensus -update is local averaging
ProvedBoydADMM.Consensus.general_z_update_local_averageadmmconsensusp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Consider general form consensus (§7.2) with the index map , , and assume every global entry is copied at least once: for every . Fix (standing for ) and (standing for ). Then minimizes
if and only if, for every global index ,
So each global entry is the average of the local entries that copy it.
Formalization Note The book writes the sum in the -update as ; is a typo for . The hypothesis is implicit in the book (otherwise does not appear in the objective and the formula divides by zero). Indices are 0-based in Lean.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- §7.2, p. 55: in general form consensus, if every global component is copied at least once
(`k_g ≥ 1` for every `g`), then `z` minimizes the `z`-update objective
`∑_i (−y_i^{kT} z̃_i + (ρ/2)‖x_i^{k+1} − z̃_i‖²)` over `z ∈ ℝⁿ` iff every component is the local
average `z_g = ∑_{G(i,j)=g} ((x_i^{k+1})_j + (1/ρ)(y_i^k)_j) / k_g`. Here `x`, `y` stand for
`x^{k+1}`, `y^k`. -/
theorem general_z_update_local_average {n N : ℕ} {nl : Fin N → ℕ}
(G : (i : Fin N) → Fin (nl i) → Fin n) (hG : ∀ g, 1 ≤ kg G g) (ρ : ℝ) (hρ : 0 < ρ)
(x y : (i : Fin N) → EuclideanSpace ℝ (Fin (nl i))) (z : EuclideanSpace ℝ (Fin n)) :
(∀ z' : EuclideanSpace ℝ (Fin n),
∑ i, (-⟪y i, ztil G z i⟫_ℝ + (ρ / 2) * ‖x i - ztil G z i‖ ^ 2) ≤
∑ i, (-⟪y i, ztil G z' i⟫_ℝ + (ρ / 2) * ‖x i - ztil G z' i‖ ^ 2)) ↔
∀ g, z g = (∑ p ∈ entriesOf G g, (x p.1 p.2 + (1 / ρ) * y p.1 p.2)) / (kg G g : ℝ) := 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 (z-update of general form consensus ADMM; the book prints ∑_{i=1}^m for ∑_{i=1}^N)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.