§7.1.1: for the indicator of the proximal step is the positive part
ProvedBoydADMM.Consensus.nonneg_prox_positive_partadmmconsensusp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1projection
Let , , and let be the indicator function of the nonnegative orthant (zero on , elsewhere). With , the proximal step
has the unique solution , that is,
Formalization Note The indicator is encoded by its domain with value there. The book prints ; the intended reading, forced by the proximal form of the -update displayed earlier on the same page, is , which is what is stated.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Consensus_Model open scoped BigOperators InnerProductSpace
Formal statement
namespace BoydADMM.Consensus
/-- §7.1.1, p. 52 (sign corrected): for `g` the indicator function of `ℝⁿ₊` (effective domain
`{z | z ≥ 0}`, value `0` there), the proximal step
`argmin_z (g(z) + (Nρ/2)‖z − x̄^{k+1} − (1/ρ)ȳ^k‖²)` has the unique solution
`z = (x̄^{k+1} + (1/ρ)ȳ^k)₊`, componentwise. The book prints `x̄^{k+1} − (1/ρ)ȳ^k`. -/
theorem nonneg_prox_positive_part {n N : ℕ} (hN : 0 < N) (ρ : ℝ) (hρ : 0 < ρ)
(x y : Fin N → EuclideanSpace ℝ (Fin n)) (z : EuclideanSpace ℝ (Fin n)) :
((∀ j, 0 ≤ z j) ∧ ∀ z' : EuclideanSpace ℝ (Fin n), (∀ j, 0 ≤ z' j) →
((N : ℝ) * ρ / 2) * ‖z - avg x - (1 / ρ) • avg y‖ ^ 2 ≤
((N : ℝ) * ρ / 2) * ‖z' - avg x - (1 / ρ) • avg y‖ ^ 2) ↔
∀ j, z j = max ((avg x + (1 / ρ) • avg y) j) 0 := 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. 52, §7.1.1 (example g = indicator of R^n_+; the book prints x̄^{k+1} − (1/ρ)ȳ^k, corrected to +)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.