(4.1), p. 26 — for quadratic f, x⁺ = (P + ρAᵀA)⁻¹(ρAᵀv − q)
ProvedBoydADMM.Prox.quadratic_xUpdateLet with (symmetric positive semidefinite), , . Let , , and assume that is invertible. Then:
- the coefficient matrix is positive definite;
- for every , the -update over all of is unique and is the affine function of
So computing an -update with a quadratic objective term amounts to solving one linear system with a positive definite coefficient matrix, which is what makes factorization caching (§4.2.3) and the matrix inversion lemma (§4.2.4) useful.
Formalization Note is P.PosSemidef (which includes symmetry). "Assuming is invertible" is the explicit hypothesis IsUnit (P + ρ • (Aᵀ * A)). The claim " is given by (4.1)" is stated as an equivalence: is a minimizer if and only if equals the right-hand side of (4.1), which gives both existence and uniqueness. The positive definiteness, stated by the book in the next sentence, is the first conjunct.
import Mathlib import Definitions.Def_BoydADMM_Prox_Basic open Matrix
namespace BoydADMM.Prox
theorem quadratic_xUpdate {n p : ℕ} (P : Matrix (Fin n) (Fin n) ℝ) (hP : P.PosSemidef)
(q : EuclideanSpace ℝ (Fin n)) (r : ℝ) (A : Matrix (Fin p) (Fin n) ℝ) (ρ : ℝ) (hρ : 0 < ρ)
(hinv : IsUnit (P + ρ • (Aᵀ * A))) :
(P + ρ • (Aᵀ * A)).PosDef ∧
∀ (v : EuclideanSpace ℝ (Fin p)) (x : EuclideanSpace ℝ (Fin n)),
IsXUpdate Set.univ (quadObj P q r) ρ A v x ↔
x = Matrix.toEuclideanLin (P + ρ • (Aᵀ * A))⁻¹
(ρ • Matrix.toEuclideanLin Aᵀ v - q) := by sorry
end BoydADMM.Prox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.