Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§7.3 (goal): the sharing zzz-update reduces to one nnn-variable problem plus (7.13), and the dual variables agree (7.14)

Proved
BoydADMM.Consensus.sharing_z_update_reduction

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

admmdistributed-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1sharing

Let N≥1N\ge1N≥1, ρ>0\rho>0ρ>0 and let g:Rn→R∪{+∞}g:\mathbb R^n\to\mathbb R\cup\{+\infty\}g:Rn→R∪{+∞} be the shared objective of the sharing problem (7.11)–(7.12).

  1. Reduction of the zzz-update. For any a1,…,aN∈Rna_1,\dots,a_N\in\mathbb R^na1​,…,aN​∈Rn (in ADMM, ai=uik+xik+1a_i=u_i^k+x_i^{k+1}ai​=uik​+xik+1​), a tuple (z1,…,zN)(z_1,\dots,z_N)(z1​,…,zN​) minimizes the NnNnNn-variable problem
g(∑i=1Nzi)+(ρ/2)∑i=1N∥zi−ai∥22g\Big(\sum_{i=1}^N z_i\Big)+(\rho/2)\sum_{i=1}^N\|z_i-a_i\|_2^2g(i=1∑N​zi​)+(ρ/2)i=1∑N​∥zi​−ai​∥22​

if and only if its average zˉ=1N∑izi\bar z=\frac1N\sum_i z_izˉ=N1​∑i​zi​ minimizes the nnn-variable problem

g(Nzˉ)+(ρ/2)∑i=1N∥zˉ−aˉ∥22g(N\bar z)+(\rho/2)\sum_{i=1}^N\|\bar z-\bar a\|_2^2g(Nzˉ)+(ρ/2)i=1∑N​∥zˉ−aˉ∥22​

and zi=ai+zˉ−aˉz_i=a_i+\bar z-\bar azi​=ai​+zˉ−aˉ for every iii (7.13).

  1. The dual variables agree (7.14). Along every run xik,zik,uikx_i^k, z_i^k, u_i^kxik​,zik​,uik​ of the scaled sharing ADMM (p. 56), for every k≥0k\ge0k≥0 and every iii,
uik+1=uˉk+xˉk+1−zˉk+1.u_i^{k+1}=\bar u^k+\bar x^{k+1}-\bar z^{k+1}.uik+1​=uˉk+xˉk+1−zˉk+1.

In particular all uik+1u_i^{k+1}uik+1​ are equal, so a single dual variable suffices.

This is what makes sharing ADMM practical: the zzz-update needs only the averages xˉk+1\bar x^{k+1}xˉk+1, uˉk\bar u^kuˉk and one problem in nnn variables.

Formalization Note Each extended-real-valued function φ:Rn→R∪{+∞}\varphi:\mathbb R^n\to\mathbb R\cup\{+\infty\}φ:Rn→R∪{+∞} of the book is encoded by its effective domain dom⁡φ\operatorname{dom}\varphidomφ (a set) and its finite values on it (a real function); a minimization of a sum containing φ\varphiφ is a minimization over dom⁡φ\operatorname{dom}\varphidomφ. The NnNnNn-variable problem is minimized over tuples with ∑izi∈dom⁡g\sum_i z_i\in\operatorname{dom}g∑i​zi​∈domg and the nnn-variable one over zˉ\bar zzˉ with Nzˉ∈dom⁡gN\bar z\in\operatorname{dom}gNzˉ∈domg. The book states only that the zzz-update "can be computed by" solving the reduced problem and applying (7.13); the equivalence stated here contains that direction and its converse. No convexity of fif_ifi​ or ggg is needed. The book's "u∈Rmu\in\mathbf R^mu∈Rm" refers to a vector of Rn\mathbb R^nRn. (7.14) is derived for every run, not built into the definition of the run.

Preamble
import Mathlib
import Definitions.Def_BoydADMM_Consensus_Model

open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus

/-- §7.3, p. 57 (goal). Let `g` have effective domain `Cg`, `ρ > 0`, `N ≥ 1`.

(1) For any `a_1, …, a_N ∈ ℝⁿ`, `(z_1, …, z_N)` solves the sharing `z`-update
`minimize g(∑_i z_i) + (ρ/2)∑_i ‖z_i − a_i‖²` (over `∑_i z_i ∈ dom g`) iff its average `z̄` solves
the `n`-variable problem `minimize g(N z̄) + (ρ/2)∑_{i=1}^N ‖z̄ − ā‖²` (over `N z̄ ∈ dom g`) and
`z_i = a_i + z̄ − ā` for every `i` (7.13).

(2) Along every run of sharing ADMM, (7.14) holds: `u_i^{k+1} = ū^k + x̄^{k+1} − z̄^{k+1}` for every
`k` and `i`; in particular all `u_i^{k+1}` are equal. -/
theorem sharing_z_update_reduction {n N : ℕ} (hN : 0 < N) (ρ : ℝ) (hρ : 0 < ρ)
    (Cg : Set (EuclideanSpace ℝ (Fin n))) (g : EuclideanSpace ℝ (Fin n) → ℝ) :
    (∀ a z : Fin N → EuclideanSpace ℝ (Fin n),
      ((∑ i, z i) ∈ Cg ∧ ∀ z' : Fin N → EuclideanSpace ℝ (Fin n), (∑ i, z' i) ∈ Cg →
          sharingZObj g ρ a z ≤ sharingZObj g ρ a z') ↔
        ((N : ℝ) • avg z ∈ Cg ∧
          (∀ w : EuclideanSpace ℝ (Fin n), (N : ℝ) • w ∈ Cg →
            g ((N : ℝ) • avg z) + (ρ / 2) * ∑ _i : Fin N, ‖avg z - avg a‖ ^ 2 ≤
              g ((N : ℝ) • w) + (ρ / 2) * ∑ _i : Fin N, ‖w - avg a‖ ^ 2) ∧
          ∀ i, z i = a i + avg z - avg a)) ∧
    (∀ (Cf : Fin N → Set (EuclideanSpace ℝ (Fin n))) (f : Fin N → EuclideanSpace ℝ (Fin n) → ℝ)
      (x z u : ℕ → Fin N → EuclideanSpace ℝ (Fin n)),
      IsSharingADMMRun Cf f Cg g ρ x z u →
        ∀ k i, u (k + 1) i = avg (u k) + avg (x (k + 1)) - avg (z (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. 57, §7.3 (reduction of the z-update to one n-variable problem, (7.13), (7.14))
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me