Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1(f) — under (22) the Armijo stepsizes are bounded away from 0, and if Fc(xk)F_c(x^k)Fc​(xk) is bounded below then Δk→0\Delta^k \to 0Δk→0 and dk→0d^k \to 0dk→0

Proved
TsengCGD.Linear.theorem1_f

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

coordinate-descentline-searchnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider problem (1) with its standing assumptions. Let {xk},{dk},{Hk}\{x^k\},\{d^k\},\{H^k\}{xk},{dk},{Hk} be generated by the CGD method under Assumption 1 (λˉI⪰Hk⪰λ‾I\bar\lambda I\succeq H^k\succeq\underline\lambda IλˉI⪰Hk⪰λ​I, 0<λ‾≤λˉ0<\underline\lambda\le\bar\lambda0<λ​≤λˉ), with {αk}\{\alpha^k\}{αk} chosen by the Armijo rule (parameters 0<β<10<\beta<10<β<1, 0<σ<10<\sigma<10<σ<1, 0≤γ<10\le\gamma<10≤γ<1) and inf⁡kαinitk>0\inf_k\alpha^k_{\rm init}>0infk​αinitk​>0. If fff satisfies (22) for some L≥0L\ge0L≥0, then

inf⁡kαk>0.\inf_k\alpha^k>0.kinf​αk>0.

If moreover lim⁡k→∞Fc(xk)>−∞\lim_{k\to\infty}F_c(x^k)>-\inftylimk→∞​Fc​(xk)>−∞, then

{Δk}→0and{dk}→0,\{\Delta^k\}\to0\quad\text{and}\quad\{d^k\}\to0,{Δk}→0and{dk}→0,

where Δk=∇f(xk)Tdk+γ dkTHkdk+cP(xk+dk)−cP(xk)\Delta^k=\nabla f(x^k)^Td^k+\gamma\,d^{kT}H^kd^k+cP(x^k+d^k)-cP(x^k)Δk=∇f(xk)Tdk+γdkTHkdk+cP(xk+dk)−cP(xk) 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 "inf⁡kαinitk>0\inf_k\alpha^k_{\rm init}>0infk​αinitk​>0" and "inf⁡kαk>0\inf_k\alpha^k>0infk​αk>0" are stated as the existence of a positive lower bound. Since Fc(xk)F_c(x^k)Fc​(xk) is nonincreasing (Theorem 1(a)), "lim⁡Fc(xk)>−∞\lim F_c(x^k)>-\inftylimFc​(xk)>−∞" is stated as: the values Fc(xk)F_c(x^k)Fc​(xk) are bounded below. The Armijo rule picks the first jjj with (9). Iteration indices start at 000; 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
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me