(7.13): with fixed,
ProvedBoydADMM.Consensus.sharing_fixed_average_solutionadmmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1sharing
Let and , and fix (the value of the average ). The problem
over has the unique solution
In the sharing -update, with fixed the term is constant and the factor does not change the minimizers, so this is exactly the book's "minimizing over with fixed".
Formalization Note The book says "has the solution"; uniqueness is also stated.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- (7.13), §7.3, p. 57: with the average `z̄ = w` fixed, the problem of minimizing
`∑_i ‖z_i − a_i‖²` over `(z_1, …, z_N)` subject to `(1/N)∑_i z_i = w` has the unique solution
`z_i = a_i + w − ā`. (With `z̄` fixed, the term `g(N z̄)` of the book's objective is constant and
the factor `ρ/2 > 0` does not change the minimizers.) -/
theorem sharing_fixed_average_solution {n N : ℕ} (hN : 0 < N)
(a z : Fin N → EuclideanSpace ℝ (Fin n)) (w : EuclideanSpace ℝ (Fin n)) :
(avg z = w ∧ ∀ z' : Fin N → EuclideanSpace ℝ (Fin n), avg z' = w →
∑ i, ‖z i - a i‖ ^ 2 ≤ ∑ i, ‖z' i - a i‖ ^ 2) ↔
∀ i, z i = a i + w - avg a := 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, (7.13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.