Theorem 1(f) — under (22) the Armijo stepsizes are bounded away from 0, and if is bounded below then and
ProvedTsengCGD.Linear.theorem1_fcoordinate-descentline-searchnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Consider problem (1) with its standing assumptions. Let be generated by the CGD method under Assumption 1 (, ), with chosen by the Armijo rule (parameters , , ) and . If satisfies (22) for some , then
If moreover , then
where is (10).
This is the step of the global analysis that the linear convergence proof of Theorem 2(b) starts from: it makes the directions, and hence the residuals, vanish along the iterates.
Formalization Note "" and "" are stated as the existence of a positive lower bound. Since is nonincreasing (Theorem 1(a)), "" is stated as: the values are bounded below. The Armijo rule picks the first with (9). Iteration indices start at ; coordinates are 0-based.
Preamble
import Mathlib import Definitions.Def_TsengCGD_Linear_Basic open Filter Topology Finset Matrix open scoped RealInnerProductSpace
Formal statement
namespace TsengCGD.Linear
theorem theorem1_f {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) (J : ℕ → Finset (Fin n)) (H : ℕ → Matrix (Fin n) (Fin n) ℝ)
(x d : ℕ → TsengCGD.Global.Vec n) (α : ℕ → ℝ) (hrun : TsengCGD.Global.IsCGDRun f D P c J H x d α)
(lam lamBar : ℝ) (hA1 : TsengCGD.Global.Assumption1 H lam lamBar)
(β σ γ : ℝ) (αinit : ℕ → ℝ) (harm : TsengCGD.Global.IsArmijo f D P c β σ γ αinit H x d α)
(hinit : ∃ a > 0, ∀ k, a ≤ αinit k)
(L : ℝ) (hL : GradLipOn f D L) :
(∃ a > 0, ∀ k, a ≤ α k) ∧
(BddBelow (Set.range fun k => TsengCGD.Global.Fc f P c (x k)) →
Tendsto (fun k => TsengCGD.Global.Delta f P c γ (H k) (x k) (d k)) atTop (𝓝 0) ∧
Tendsto d atTop (𝓝 0)) := 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. 399–400, Theorem 1(f)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.