The indicator-function z-update is Euclidean projection
ProvedBoydADMM.Constrained.indicator_projectionadmmconvex-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1projections
Let be nonempty, closed and convex, let , and let . For a point , minimizing the indicator-function part of the scaled ADMM -update is equivalent to projecting onto :
This explains the projection update displayed for constrained optimization on page 33. The source writes .
Formalization Note The indicator is represented by restricting the minimization to . The conclusion uses the published nearest-point predicate; and the geometric properties of make the projection well defined.
Preamble
import Mathlib import Definitions.Def_RandomGradFree_Nonsmooth_IsMetricProjection import Definitions.Def_BoydADMM_Constrained_Geometry
Formal statement
namespace BoydADMM.Constrained
/-- §5, p. 33: the `z`-minimization with the indicator of `C` is Euclidean projection. -/
theorem indicator_projection {n : ℕ} (C : Set (Vec n))
(hCne : C.Nonempty) (hCclosed : IsClosed C) (hCconvex : Convex ℝ C)
(ρ : ℝ) (hρ : 0 < ρ) (v p : Vec n) (hp : p ∈ C) :
(∀ w ∈ C, (ρ / 2) * ‖v - p‖ ^ 2 ≤ (ρ / 2) * ‖v - w‖ ^ 2) ↔
RandomGradFree.Nonsmooth.IsMetricProjection C v p := by sorry
end BoydADMM.Constrained
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. 33, (5.1) and scaled z-update; https://doi.org/10.1561/2200000016
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.