Lemma 1 — descent estimate and quadratic-direction bound
ProvedTsengCGD.Global.lemma1composite-optimizationcoordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , let be a nonempty coordinate set, and let be positive definite. If is the exact minimizer of the coordinate quadratic subproblem and , then, for ,
and
The first inequality relates the actual objective to the model direction; the second provides its quantitative descent bound.
Formalization Note The standing assumptions of (1) are explicit. The line segment belongs to , so the displayed objective is finite. The remainder is a function with from the right; the statement holds for every exact minimizer.
Preamble
import Mathlib import Definitions.Def_TsengCGD_Global_Basic
Formal statement
namespace TsengCGD.Global
open Filter Topology Finset Matrix
open scoped RealInnerProductSpace
theorem lemma1 {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 : Matrix (Fin n) (Fin n) ℝ) (hH : H.PosDef)
(d : Vec n) (hd : IsDir f D P c H x J d) :
(∃ r : ℝ → ℝ, Tendsto (fun a => r a / a) (𝓝[>] (0 : ℝ)) (𝓝 0) ∧
∀ a ∈ Set.Ioc (0 : ℝ) 1,
x + a • d ∈ D ∧
Fc f P c (x + a • d) ≤
Fc f P c x + a * (⟪gradient f x, d⟫ + c * P (x + d) - c * P x) + r a) ∧
⟪gradient f x, d⟫ + c * P (x + d) - c * P x ≤ -qf H d := 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. 391, Lemma 1, equations (7)–(8), 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.