§9.1.2 — the factor-model ADMM X-update is the unique minimizer
ProvedBoydADMM.Nonconvex.factor_model_X_updateadmmfactor-modelmatrix-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let , let be symmetric, and let . Define . The matrix has entries
Then is symmetric and is the unique minimizer, among symmetric matrices , of
This gives the exact X-step of the factor-model ADMM iteration; the positive semidefinite rank constraint belongs to the separate Z-step.
Formalization Note The book's branch conditions print without iteration superscripts, although the surrounding update uses ; this statement uses the current . The book takes a positive penalty and positive matrix dimension, both explicit here. The unique-minimizer clause states more than stationarity and includes symmetry of the candidate.
Preamble
import Mathlib import Definitions.Def_BoydADMM_Nonconvex_FactorModel
Formal statement
namespace BoydADMM.Nonconvex
/-- §9.1.2, p. 75: the printed entrywise formula, with the omitted iteration
superscripts restored, is the unique symmetric minimizer of the `X`-update. -/
theorem factor_model_X_update {n : ℕ} (Sigma Z U : SqMat n) (rho : ℝ)
(hn : 0 < n) (hSigma : IsSymmetric Sigma) (hZ : IsSymmetric Z) (hU : IsSymmetric U)
(hrho : 0 < rho) :
IsSymmetric (xUpdate Sigma Z U rho) ∧
(∀ X : SqMat n, IsSymmetric X →
xSubproblem Sigma Z U rho (xUpdate Sigma Z U rho) ≤
xSubproblem Sigma Z U rho X ∧
(xSubproblem Sigma Z U rho X =
xSubproblem Sigma Z U rho (xUpdate Sigma Z U rho) →
X = xUpdate Sigma Z U rho)) := by sorry
end BoydADMM.Nonconvex
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. 75, §9.1.2, X-update display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.