Lemma 3 — comparison of directions under two quadratic matrices
ProvedTsengCGD.Global.lemma3composite-optimizationcoordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be nonempty, and let be positive definite. Set , , and . Lemma 3 bounds the change of direction by
If , the second conclusion is
Together these estimates control the direction when the quadratic model changes.
Formalization Note The extreme eigenvalues are represented by Rayleigh quotient extrema on vectors supported in . Generalized quotients represent 's spectrum. The nonempty block and positive-definite matrices make their defining sets nonempty and bounded; the square-root arguments are nonnegative.
Preamble
import Mathlib import Definitions.Def_TsengCGD_Global_Basic
Formal statement
namespace TsengCGD.Global
open Filter Topology Finset Matrix
open scoped RealInnerProductSpace
theorem lemma3 {n : ℕ} (f : Vec n → ℝ) (D : Set (Vec n)) (P : Vec n → ℝ)
(c : ℝ) (hs : Standing f D P c)
(x : Vec n) (hx : x ∈ D) (J : Finset (Fin n)) (hJ : J.Nonempty)
(H Ht : Matrix (Fin n) (Fin n) ℝ) (hH : H.PosDef) (hHt : Ht.PosDef) :
let d := dH f D P c H x J
let dt := dH f D P c Ht x J
‖dt‖ ≤
((1 + genMax H Ht J +
Real.sqrt (1 - 2 * genMin H Ht J + (genMax H Ht J) ^ 2)) / 2) *
(lamMax H J / lamMin Ht J) * ‖d‖ ∧
((∀ u : Vec n, SupportedOn J u → u ≠ 0 → qf Ht u < qf H u) →
‖d‖ ≤ Real.sqrt (lamMax (H - Ht) J / lamMin (H - Ht) J) * ‖dt‖) := 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 3, equations (18)–(19), 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.