Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5(a) — variational inequality for the step x′=x+αdx' = x + \alpha dx′=x+αd under block-separability

Proved
TsengCGD.Linear.lemma5_a

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

coordinate-descentnonsmooth-optimizationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Consider problem (1): Fc=f+cPF_c=f+cPFc​=f+cP with c>0c>0c>0, PPP proper, convex, lower semicontinuous and fff continuously differentiable on an open set containing dom⁡P\operatorname{dom}PdomP. Let x∈dom⁡Px\in\operatorname{dom}Px∈domP, H≻0nH\succ0_nH≻0n​, J⊆N\mathcal J\subseteq\mathcal NJ⊆N nonempty, d=dH(x;J)d=d_H(x;\mathcal J)d=dH​(x;J) the direction (6), g=∇f(x)g=\nabla f(x)g=∇f(x), and γ∈[0,1)\gamma\in[0,1)γ∈[0,1); put Δ=gTd+γdTHd+cP(x+d)−cP(x)\Delta=g^Td+\gamma d^THd+cP(x+d)-cP(x)Δ=gTd+γdTHd+cP(x+d)−cP(x).

Suppose PPP is block-separable with respect to J\mathcal JJ, P(x)=PJ(xJ)+PJC(xJC)P(x)=P_{\mathcal J}(x_{\mathcal J})+P_{\mathcal J^C}(x_{\mathcal J^C})P(x)=PJ​(xJ​)+PJC​(xJC​). Then for every xˉ∈ℜn\bar x\in\Re^nxˉ∈ℜn, every α∈(0,1]\alpha\in(0,1]α∈(0,1] and x′=x+αdx'=x+\alpha dx′=x+αd,

(g+Hd)JT(x′−xˉ)J+cPJ(xJ′)−cPJ(xˉJ) ≤ (α−1)[(1−γ)dTHd+Δ].(g+Hd)_{\mathcal J}^T(x'-\bar x)_{\mathcal J}+cP_{\mathcal J}(x'_{\mathcal J})-cP_{\mathcal J}(\bar x_{\mathcal J})\ \le\ (\alpha-1)\big[(1-\gamma)d^THd+\Delta\big].(g+Hd)JT​(x′−xˉ)J​+cPJ​(xJ′​)−cPJ​(xˉJ​) ≤ (α−1)[(1−γ)dTHd+Δ].

This inequality compares a partial step with an arbitrary point on the block J\mathcal JJ; it is the per-block estimate that the linear convergence proof of Theorem 2(b) sums over a Gauss–Seidel cycle.

Formalization Note The left side involves the particular summand PJP_{\mathcal J}PJ​, so the statement holds for every decomposition (20) of PPP; a decomposition is given by two proper convex lsc functions on ℜn\Re^nℜn, one depending only on xJx_{\mathcal J}xJ​ (with its own effective domain), the other only on xJCx_{\mathcal J^C}xJC​. When xˉJ∉dom⁡PJ\bar x_{\mathcal J}\notin\operatorname{dom}P_{\mathcal J}xˉJ​∈/domPJ​ the left side is −∞-\infty−∞ and the inequality is empty, so xˉ\bar xxˉ ranges over dom⁡PJ\operatorname{dom}P_{\mathcal J}domPJ​. ddd is any minimizer of (6) (it is unique). Coordinates are 0-based; dTHdd^THddTHd is the quadratic form of the matrix HHH.

Preamble
import Mathlib
import Definitions.Def_TsengCGD_Linear_Basic
open Filter Topology Finset Matrix
open scoped RealInnerProductSpace
Formal statement
namespace TsengCGD.Linear

theorem lemma5_a {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)
    (DJ : Set (TsengCGD.Global.Vec n)) (PJ : TsengCGD.Global.Vec n → ℝ) (DJC : Set (TsengCGD.Global.Vec n)) (PJC : TsengCGD.Global.Vec n → ℝ)
    (hw : TsengCGD.Global.IsBlockSepWitness D P J DJ PJ DJC PJC)
    (xbar : TsengCGD.Global.Vec n) (hxbar : xbar ∈ DJ) (α : ℝ) (hα0 : 0 < α) (hα1 : α ≤ 1) :
    (∑ j ∈ J, (gradient f x j + (H *ᵥ WithLp.ofLp d) j) * ((x + α • d) j - xbar j))
        + c * PJ (x + α • d) - c * PJ xbar
      ≤ (α - 1) * ((1 - γ) * TsengCGD.Global.qf H d + 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), p. 397, Lemma 5(a)
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