§6.5, p. 47 — first-order condition: is the X-update iff
ProvedBoydADMM.L1.covsel_first_order_conditionadmmcovariance-selectionoptimality-conditionsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let with and symmetric, and let . Consider
on the cone of symmetric positive definite matrices. For ,
This is the book's statement that "the first-order optimality condition is that the gradient should vanish, together with the implicit constraint ": the vanishing gradient is necessary and, because is convex, sufficient for to solve the X-minimization.
Formalization Note stand for . The symmetry of (an empirical covariance) and of (the ADMM iterates are symmetric when started symmetric) is made an explicit hypothesis; without it the gradient over symmetric matrices is only the symmetric part of . is Matrix.PosDef, which includes symmetry. is the sum of squared entries.
Preamble
import Mathlib import Definitions.Def_BoydADMM_L1_CovSel open Matrix
Formal statement
namespace BoydADMM.L1
/-- §6.5, p. 47: for symmetric `S` and `Z − U` and `ρ > 0`, a positive definite `X` minimizes
`Tr(SX) − log det X + (ρ/2)‖X − Z + U‖_F²` over the positive definite matrices if and only if
the gradient vanishes, `S − X⁻¹ + ρ(X − Z + U) = 0`. -/
theorem covsel_first_order_condition {n : ℕ} (S Z U : Matrix (Fin n) (Fin n) ℝ) (ρ : ℝ)
(hρ : 0 < ρ) (hS : S.IsSymm) (hZU : (Z - U).IsSymm)
(X : Matrix (Fin n) (Fin n) ℝ) (hX : X.PosDef) :
(∀ X' : Matrix (Fin n) (Fin n) ℝ, X'.PosDef →
covselXObjective S Z U ρ X ≤ covselXObjective S Z U ρ X') ↔
S - X⁻¹ + ρ • (X - Z + U) = 0 := by sorry
end BoydADMM.L1
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. 47, §6.5 (first-order optimality condition)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.