§4.1, p. 26 — the proximity operator of the indicator of C is Π_C, for every ρ > 0
ProvedBoydADMM.Prox.prox_indicator_eq_projectionadmmp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1projectionproximal-operator
Let be a closed, nonempty, convex set and let . Let be the indicator function of ( on , off ). Then:
- the Euclidean projection exists and is unique: there is exactly one with for all ;
- for every penalty , a point is an -update
if and only if .
In particular independently of the choice of . This is the reason that constraint sets in ADMM are handled by projections.
Formalization Note The indicator function is encoded as the domain with the zero function. The book says "This holds independently of the choice of "; we state it for every , the book's standing assumption on (p. 14); at every point of would be a minimizer.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Prox_Basic open Matrix
Formal statement
namespace BoydADMM.Prox
theorem prox_indicator_eq_projection {n : ℕ} (C : Set (EuclideanSpace ℝ (Fin n)))
(hC_closed : IsClosed C) (hC_convex : Convex ℝ C) (hC_ne : C.Nonempty)
(v : EuclideanSpace ℝ (Fin n)) :
(∃! x, IsProjection C v x) ∧
∀ ρ : ℝ, 0 < ρ → ∀ x, IsProx C (fun _ => 0) ρ v x ↔ IsProjection C v x := by sorry
end BoydADMM.Prox
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. 26, §4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.