Lemma 5(b) — the Armijo descent condition (23) holds for
ProvedTsengCGD.Linear.lemma5_bcoordinate-descentline-searchnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider problem (1): with , proper, convex, lower semicontinuous and continuously differentiable on an open set containing . Let , , nonempty, , and .
Suppose is -Lipschitz on for some (condition (22)) and with . Then for every the descent condition
holds whenever (read as when ).
The lemma gives a stepsize, independent of , at which the Armijo test (9) always passes; it is what makes the Armijo stepsizes bounded away from zero in Theorem 1(f).
Formalization Note The step range is stated as and , which is the paper's range for and for ; the literal Lean min 1 (… / L) would be at . The conclusion includes , so that both sides of (23) are finite. is stated as for all .
Preamble
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic open Filter Topology Finset Matrix open scoped RealInnerProductSpace
Formal statement
namespace TsengCGD.Linear
theorem lemma5_b {n : ℕ} (f : TsengCGD.Global.Vec n → ℝ) (D : Set (TsengCGD.Global.Vec n)) (P : TsengCGD.Global.Vec n → ℝ) (c : ℝ)
(hs : TsengCGD.Global.Standing f D P c) (x : TsengCGD.Global.Vec n) (hx : x ∈ D) (H : Matrix (Fin n) (Fin n) ℝ)
(hH : H.PosDef) (J : Finset (Fin n)) (hJ : J.Nonempty) (d : TsengCGD.Global.Vec n)
(hd : TsengCGD.Global.IsDir f D P c H x J d) (γ : ℝ) (hγ0 : 0 ≤ γ) (hγ1 : γ < 1)
(L : ℝ) (hL : GradLipOn f D L) (lam : ℝ) (hlam : 0 < lam)
(hHlam : ∀ z : TsengCGD.Global.Vec n, lam * ‖z‖ ^ 2 ≤ TsengCGD.Global.qf H z)
(σ : ℝ) (hσ0 : 0 < σ) (hσ1 : σ < 1)
(α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) (hαL : α * L ≤ 2 * lam * (1 - σ + σ * γ)) :
x + α • d ∈ D ∧ TsengCGD.Global.Fc f P c (x + α • d) - TsengCGD.Global.Fc f P c x ≤ σ * α * TsengCGD.Global.Delta f P c γ H x d := by sorry
end TsengCGD.Linear
Source
Tseng and Yun, A coordinate gradient descent method for nonsmooth separable minimization, Math. Program. Ser. B 117 (2009), pp. 397–398, Lemma 5(b), (22), (23)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.