§4.2.5, p. 29 — quadratic f restricted to {Fx = g}: the x-update solves the KKT system and is affine in v
ProvedBoydADMM.Prox.quadratic_affine_kktLet with , restricted to the affine set , where and are arbitrary. Let . Consider the scaled-form -update with and :
- For all , a point is such a minimizer if and only if there is solving the KKT system
- If the affine set is nonempty, then is an affine function of : there are a matrix and a vector such that for every , the minimizer of over is unique and equals .
So the update with an equality-constrained quadratic term again reduces to one linear system, the KKT system, whose coefficient matrix does not depend on .
Formalization Note The book says "the update involves solving the KKT system"; we state the equivalence between minimality and solvability of the KKT system for some multiplier (sufficiency is the direction the book uses; necessity holds because the constraints are linear). may have any rank, so need not be unique. Existence of a minimizer needs the affine set to be nonempty, which the book leaves implicit; it is a hypothesis of part 2 only.
import Mathlib import Definitions.Def_BoydADMM_Prox_Basic open Matrix
namespace BoydADMM.Prox
theorem quadratic_affine_kkt {n m : ℕ} (P : Matrix (Fin n) (Fin n) ℝ) (hP : P.PosSemidef)
(q : EuclideanSpace ℝ (Fin n)) (r : ℝ) (F : Matrix (Fin m) (Fin n) ℝ)
(g : EuclideanSpace ℝ (Fin m)) (ρ : ℝ) (hρ : 0 < ρ) :
(∀ (z u x : EuclideanSpace ℝ (Fin n)),
IsProx (affineSet F g) (quadObj P q r) ρ (z - u) x ↔
∃ ν : EuclideanSpace ℝ (Fin m),
Matrix.toEuclideanLin (P + ρ • (1 : Matrix (Fin n) (Fin n) ℝ)) x
+ Matrix.toEuclideanLin Fᵀ ν + (q - ρ • (z - u)) = 0 ∧
Matrix.toEuclideanLin F x - g = 0) ∧
((affineSet F g).Nonempty →
∃ (M : Matrix (Fin n) (Fin n) ℝ) (b : EuclideanSpace ℝ (Fin n)),
∀ (v x : EuclideanSpace ℝ (Fin n)),
IsProx (affineSet F g) (quadObj P q r) ρ v x ↔
x = Matrix.toEuclideanLin M v + b) := by sorry
end BoydADMM.Prox
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.