Lemma 2 — stationarity exactly when the full direction vanishes
ProvedTsengCGD.Global.lemma2composite-optimizationcoordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be positive definite. The full-coordinate quadratic direction vanishes precisely at stationary points of :
This characterization turns a variational first-order condition into a residual test for the exact subproblem.
Formalization Note Stationarity includes and uses the one-sided derivative of the extended-valued objective. The Lean predicate uses the equivalent nonnegative lower-limit condition; directions leaving have value . The standing assumptions of (1) are explicit.
Preamble
import Mathlib import Definitions.Def_TsengCGD_Global_Basic
Formal statement
namespace TsengCGD.Global
open Filter Topology Finset Matrix
open scoped RealInnerProductSpace
theorem lemma2 {n : ℕ} (f : Vec n → ℝ) (D : Set (Vec n)) (P : Vec n → ℝ)
(c : ℝ) (hs : Standing f D P c)
(x : Vec n) (hx : x ∈ D) (H : Matrix (Fin n) (Fin n) ℝ) (hH : H.PosDef) :
IsStationary f D P c x ↔ dH f D P c H x Finset.univ = 0 := by sorry
end TsengCGD.Global
Source
Tseng and Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B 117 (2009), p. 394, Lemma 2, https://doi.org/10.1007/s10107-007-0170-0
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.