Parallel projection ADMM reduces to project-and-average
ProvedBoydADMM.Constrained.parallel_projection_simplificationLet and , and let be nonempty closed convex sets. Start the parallel projection ADMM iteration from arbitrary and . Then the average dual variable vanishes after every update, for , and for . From the same run therefore satisfies
If , these two simplified updates already hold for every . Thus the simplified algorithm describes the iterates of the displayed three-update method, with its initial step and index ranges made explicit.
Formalization Note Projection is relational and the theorem ranges over every run; it does not assume the vanishing dual average. The book's intermediate formula prints where the iteration requires . It also says the first step projects onto the sets ; these are the of §5.1.2.
import Mathlib import Definitions.Def_BoydADMM_Constrained_Run
namespace BoydADMM.Constrained
/-- §5.1.2, p. 36: every parallel projection ADMM run reduces to project-and-average
after its dual average has vanished. The index ranges keep the arbitrary initial state. -/
theorem parallel_projection_simplification {N n : ℕ} (hN : 0 < N)
(A : Fin N → Set (Vec n))
(hAne : ∀ i, (A i).Nonempty) (hAclosed : ∀ i, IsClosed (A i))
(hAconvex : ∀ i, Convex ℝ (A i))
(ρ : ℝ) (hρ : 0 < ρ)
(x : ℕ → Blocks N n) (z : ℕ → Vec n) (u : ℕ → Blocks N n)
(hrun : IsParallelRun A x z u) :
(∀ k, avg (u (k + 1)) = 0) ∧
(∀ k, 1 ≤ k → z (k + 1) = avg (x (k + 1))) ∧
(∀ k, 2 ≤ k → ∀ i,
RandomGradFree.Nonsmooth.IsMetricProjection (A i)
(avg (x k) - u k i) (x (k + 1) i) ∧
u (k + 1) i = u k i + (x (k + 1) i - avg (x (k + 1)))) ∧
(avg (u 0) = 0 → ∀ k, 1 ≤ k → ∀ i,
RandomGradFree.Nonsmooth.IsMetricProjection (A i)
(avg (x k) - u k i) (x (k + 1) i) ∧
u (k + 1) i = u k i + (x (k + 1) i - avg (x (k + 1)))) := by sorry
end BoydADMM.Constrained
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.