§4.4.2, p. 31 — component separability: the x-update splits into n scalar minimizations
ProvedBoydADMM.Prox.component_separableadmmdecompositionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1separability
Let with , let with diagonal, let and . Then is an -update,
if and only if, for every , the scalar minimizes
over . For this is the scalar problem (up to the constant ).
This is what the book calls component separability: the -minimization is carried out by independent scalar minimizations. Soft thresholding (§4.4.3) is the case .
Formalization Note The book does not write the scalar problems out; we write them explicitly, dropping the constant , which does not affect minimizers. The are real-valued, as on the page.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Prox_Basic open Matrix
Formal statement
namespace BoydADMM.Prox
theorem component_separable {n p : ℕ} (f : Fin n → ℝ → ℝ) (A : Matrix (Fin p) (Fin n) ℝ)
(d : Fin n → ℝ) (hdiag : Aᵀ * A = Matrix.diagonal d) (ρ : ℝ) (hρ : 0 < ρ)
(v : EuclideanSpace ℝ (Fin p)) (x : EuclideanSpace ℝ (Fin n)) :
IsXUpdate Set.univ (fun y => ∑ i, f i (y i)) ρ A v x ↔
∀ i, ∀ t : ℝ,
f i (x i) + (ρ / 2) * (d i * x i ^ 2 - 2 * (Matrix.toEuclideanLin Aᵀ v) i * x i) ≤
f i t + (ρ / 2) * (d i * t ^ 2 - 2 * (Matrix.toEuclideanLin Aᵀ v) i * t) := 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. 31, §4.4.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.