Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1(e) — every cluster point is stationary under generalized Gauss–Seidel selection

Disproved
TsengCGD.Global.theorem1_e

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

composite-optimizationcoordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider a CGD run for Fc=f+cPF_c=f+cPFc​=f+cP under Assumption 1. The steps use the Armijo rule with inf⁡kαinitk>0\inf_k\alpha^k_{\mathrm{init}}>0infk​αinitk​>0. Suppose every TTT consecutive coordinate sets cover all coordinates, PPP is block-separable with respect to each chosen set Jk\mathcal J^kJk, and sup⁡kαk<∞\sup_k\alpha^k<\inftysupk​αk<∞. Then

xˉ a cluster point of {xk}⟹Fc′(xˉ;v)≥0for every v∈Rn.\bar x\text{ a cluster point of }\{x^k\} \quad\Longrightarrow\quad F_c'(\bar x;v)\ge0\quad\text{for every }v\in\mathbb R^n.xˉ a cluster point of {xk}⟹Fc′​(xˉ;v)≥0for every v∈Rn.

Thus every accumulation point satisfies the full directional first-order condition, despite the changing coordinate blocks and nonsmooth penalty.

Formalization Note The standing assumptions of (1), exact subproblem minimizers, first accepted Armijo trial, and the ranges of all line-search parameters are explicit. MapClusterPt encodes a cluster point without assuming the full run converges. Stationarity covers all directions, not only the current block. The upper bound on accepted steps is a finite real bound.

Preamble
import Mathlib
import Definitions.Def_TsengCGD_Global_Basic
Formal statement
namespace TsengCGD.Global

open Filter Topology Finset Matrix
open scoped RealInnerProductSpace

theorem theorem1_e {n : ℕ} (f : Vec n → ℝ) (D : Set (Vec n)) (P : Vec n → ℝ)
    (c : ℝ) (hs : Standing f D P c)
    (J : ℕ → Finset (Fin n)) (H : ℕ → Matrix (Fin n) (Fin n) ℝ)
    (x d : ℕ → Vec n) (α αinit : ℕ → ℝ) (β σ γ lam lamBar : ℝ)
    (hrun : IsCGDRun f D P c J H x d α)
    (harm : IsArmijo f D P c β σ γ αinit H x d α)
    (hA1 : Assumption1 H lam lamBar)
    (hinit : ∃ a : ℝ, 0 < a ∧ ∀ k, a ≤ αinit k)
    (hGS : GaussSeidel J) (hsep : ∀ k, BlockSeparable D P (J k))
    (hsup : ∃ A : ℝ, ∀ k, α k ≤ A) :
    ∀ xbar : Vec n, MapClusterPt xbar atTop x → IsStationary f D P c xbar := 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. 399, Theorem 1(e), https://doi.org/10.1007/s10107-007-0170-0
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