§7.3 (goal): the sharing -update reduces to one -variable problem plus (7.13), and the dual variables agree (7.14)
ProvedBoydADMM.Consensus.sharing_z_update_reductionLet , and let be the shared objective of the sharing problem (7.11)–(7.12).
- Reduction of the -update. For any (in ADMM, ), a tuple minimizes the -variable problem
if and only if its average minimizes the -variable problem
and for every (7.13).
- The dual variables agree (7.14). Along every run of the scaled sharing ADMM (p. 56), for every and every ,
In particular all are equal, so a single dual variable suffices.
This is what makes sharing ADMM practical: the -update needs only the averages , and one problem in variables.
Formalization Note Each extended-real-valued function of the book is encoded by its effective domain (a set) and its finite values on it (a real function); a minimization of a sum containing is a minimization over . The -variable problem is minimized over tuples with and the -variable one over with . The book states only that the -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 or is needed. The book's "" refers to a vector of . (7.14) is derived for every run, not built into the definition of the run.
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.