Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.2 for state feedback — the gradient method stays in S0\mathcal S_0S0​, reaches stationarity, and converges linearly to the optimal gain

Proved
FatkhullinPolyak.Discrete.gradient_method_slqr_linear_rate

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

gradient-methodlinear-convergencelqrp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1state-feedback

Consider state feedback, C=IC=IC=I (so r=nr=nr=n), with Q,R,Σ≻0Q,R,\Sigma\succ0Q,R,Σ≻0, B≠0B\ne0B=0 and a stabilizing gain K0∈SK_0\in\mathcal SK0​∈S. Let K∗∈SK_*\in\mathcal SK∗​∈S be an optimal gain, f(K∗)≤f(K)f(K_*)\le f(K)f(K∗​)≤f(K) for all K∈SK\in\mathcal SK∈S. Let L>0L>0L>0 be a Lipschitz constant of the gradient (3.3) on S0\mathcal S_0S0​:

∥∇f(K)−∇f(K′)∥F≤L∥K−K′∥F(K,K′∈S0).\|\nabla f(K)-\nabla f(K')\|_F\le L\|K-K'\|_F\qquad(K,K'\in\mathcal S_0).∥∇f(K)−∇f(K′)∥F​≤L∥K−K′∥F​(K,K′∈S0​).

Let (γj)(\gamma_j)(γj​) be real step sizes and Kj+1=Kj−γj∇f(Kj)K_{j+1}=K_j-\gamma_j\nabla f(K_j)Kj+1​=Kj​−γj​∇f(Kj​) the gradient method (4.4) from K0K_0K0​.

  1. If 0<γj≤2/L0<\gamma_j\le2/L0<γj​≤2/L for all jjj, then every KjK_jKj​ lies in S0\mathcal S_0S0​ and
f(Kj+1)≤f(Kj)−γj(1−Lγj2)∥∇f(Kj)∥F2for all j.(4.5)f(K_{j+1})\le f(K_j)-\gamma_j\Big(1-\frac{L\gamma_j}{2}\Big)\|\nabla f(K_j)\|_F^2\qquad\text{for all }j. \tag{4.5}f(Kj+1​)≤f(Kj​)−γj​(1−2Lγj​​)∥∇f(Kj​)∥F2​for all j.(4.5)
  1. If 0<ε1≤γj≤2/L−ε20<\varepsilon_1\le\gamma_j\le2/L-\varepsilon_20<ε1​≤γj​≤2/L−ε2​ for all jjj, with ε2>0\varepsilon_2>0ε2​>0, then ∇f(Kj)→0\nabla f(K_j)\to0∇f(Kj​)→0,
min⁡0≤j≤k∥∇f(Kj)∥F2≤f(K0)c1k(k≥1),c1=ε1ε2L2,\min_{0\le j\le k}\|\nabla f(K_j)\|_F^2\le\frac{f(K_0)}{c_1k}\quad(k\ge1),\qquad c_1=\frac{\varepsilon_1\varepsilon_2L}{2},0≤j≤kmin​∥∇f(Kj​)∥F2​≤c1​kf(K0​)​(k≥1),c1​=2ε1​ε2​L​,

and the iterates converge to K∗K_*K∗​ at a linear rate: there are c≥0c\ge0c≥0 and 0≤q<10\le q<10≤q<1 with

∥Kj−K∗∥F≤c qjfor all j.(4.6)\|K_j-K_*\|_F\le c\,q^j\qquad\text{for all }j. \tag{4.6}∥Kj​−K∗​∥F​≤cqjfor all j.(4.6)

This is the main convergence theorem of the paper for the discrete gradient method: although fff is non-convex and defined only on the stabilizing set, the method with constant-order steps converges globally and linearly to the optimal state-feedback gain.

Formalization Note The paper's LLL is the constant (3.8), which is false as printed (see Theorem 3.15 in this mission). The proof (Appendix D.2) uses only that ∇f\nabla f∇f is LLL-Lipschitz on S0\mathcal S_0S0​ (the definition of LLL-smoothness in §3.6), so LLL is any such constant. Invariance of S0\mathcal S_0S0​ is a conclusion, not a hypothesis. The minimum is over j∈{0,…,k}j\in\{0,\dots,k\}j∈{0,…,k} and requires k≥1k\ge1k≥1. In (4.6) the paper uses the spectral norm; the Frobenius norm is used here, which is equivalent up to a factor absorbed in ccc. The constants c,qc,qc,q may depend on all the data, the step sequence and ε1,ε2\varepsilon_1,\varepsilon_2ε1​,ε2​, as in the paper. K∗K_*K∗​ is taken as a hypothesis; its existence is Corollary 3.10.

Preamble
import Mathlib
import Definitions.Def_FatkhullinPolyak_Discrete_LQR

open Filter Topology
Formal statement
namespace FatkhullinPolyak.Discrete

/-- Theorem 4.2 (pp. 10–11) for state feedback `C = I`, with `L` any Lipschitz constant of `∇f`
on `S₀` (the paper's `L`-smoothness, §3.6; the explicit (3.8) is false). For the gradient method
(4.4) from `K₀ ∈ S`, with `K⋆ ∈ S` a minimum point of `f` on `S`:
(i) if `0 < γⱼ ≤ 2/L` for all `j`, every iterate stays in `S₀` and (4.5) holds;
(ii) if `0 < ε₁ ≤ γⱼ ≤ 2/L − ε₂`, `ε₂ > 0`, then `∇f(Kⱼ) → 0`,
`min_{0≤j≤k} ‖∇f(Kⱼ)‖_F² ≤ f(K₀)/(c₁k)` for `k ≥ 1` with `c₁ = ε₁ε₂L/2`, and the iterates
converge linearly to `K⋆`: (4.6) `‖Kⱼ − K⋆‖_F ≤ c qʲ` for some `c ≥ 0`, `0 ≤ q < 1`. -/
theorem gradient_method_slqr_linear_rate {n m : ℕ} (A : Matrix (Fin n) (Fin n) ℝ) (B : Matrix (Fin n) (Fin m) ℝ)
    (Q : Matrix (Fin n) (Fin n) ℝ) (R : Matrix (Fin m) (Fin m) ℝ)
    (Sig : Matrix (Fin n) (Fin n) ℝ)
    (hQ : Q.PosDef) (hR : R.PosDef) (hSig : Sig.PosDef) (hB : B ≠ 0)
    (K₀ : Matrix (Fin m) (Fin n) ℝ) (hK₀ : K₀ ∈ stabSet A B (1 : Matrix (Fin n) (Fin n) ℝ))
    (Kstar : Matrix (Fin m) (Fin n) ℝ) (hKstar : Kstar ∈ stabSet A B (1 : Matrix (Fin n) (Fin n) ℝ))
    (hopt : ∀ K ∈ stabSet A B (1 : Matrix (Fin n) (Fin n) ℝ), lqrCost A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig Kstar ≤ lqrCost A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K)
    (L : ℝ) (hLpos : 0 < L)
    (hL : ∀ K ∈ sublevel A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀, ∀ K' ∈ sublevel A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀,
      frobNorm (lqrGrad A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K - lqrGrad A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K') ≤ L * frobNorm (K - K'))
    (γ : ℕ → ℝ) :
    ((∀ j, 0 < γ j ∧ γ j ≤ 2 / L) →
      (∀ j, gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ j ∈ sublevel A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀) ∧
      ∀ j, lqrCost A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig (gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ (j + 1)) ≤
        lqrCost A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig (gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ j)
          - γ j * (1 - L * γ j / 2) *
            frobNorm (lqrGrad A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig (gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ j)) ^ 2) ∧
    (∀ ε₁ ε₂ : ℝ, 0 < ε₁ → 0 < ε₂ → (∀ j, ε₁ ≤ γ j ∧ γ j ≤ 2 / L - ε₂) →
      Tendsto (fun j => frobNorm (lqrGrad A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig (gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ j)))
        atTop (𝓝 0) ∧
      (∀ k : ℕ, 1 ≤ k →
        (Finset.range (k + 1)).inf' ⟨0, by simp⟩
            (fun j => frobNorm (lqrGrad A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig (gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ j)) ^ 2)
          ≤ lqrCost A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ / (ε₁ * ε₂ * L / 2 * k)) ∧
      ∃ c q : ℝ, 0 ≤ c ∧ 0 ≤ q ∧ q < 1 ∧
        ∀ j, frobNorm (gradIter A B (1 : Matrix (Fin n) (Fin n) ℝ) Q R Sig K₀ γ j - Kstar) ≤ c * q ^ j) := by sorry

end FatkhullinPolyak.Discrete
Source
Fatkhullin, Polyak, Optimizing Static Linear Feedback: Gradient Method, arXiv:2004.09875v2, pp. 10–11, Theorem 4.2, (4.4)–(4.6), case C = I; proof in Appendix D.2, p. 19
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

For natural numbers n,mn, mn,m, the statement fixes real matrices A∈Rn×nA \in \mathbb{R}^{n\times n}A∈Rn×n, B∈Rn×mB \in \mathbb{R}^{n\times m}B∈Rn×m, Q∈Rn×nQ \in \mathbb{R}^{n\times n}Q∈Rn×n, R∈Rm×mR \in \mathbb{R}^{m\times m}R∈Rm×m and Σ∈Rn×n\Sigma \in \mathbb{R}^{n\times n}Σ∈Rn×n. It assumes QQQ, RRR and Σ\SigmaΣ are positive definite (Mathlib's notion, which includes symmetry) and that B≠0B \neq 0B=0. It uses several objects from an imported definitions file whose code is not shown here, so this read-back cannot unfold them. It refers to them only by name. In each of them the third argument is always the n×nn\times nn×n identity matrix III:

  • S:=stabSet(A,B,I)\mathcal{S} := \mathrm{stabSet}(A,B,I)S:=stabSet(A,B,I), a set of m×nm\times nm×n real matrices.
  • f(K):=lqrCost(A,B,I,Q,R,Σ,K)f(K) := \mathrm{lqrCost}(A,B,I,Q,R,\Sigma,K)f(K):=lqrCost(A,B,I,Q,R,Σ,K), a real number for each m×nm\times nm×n matrix KKK.
  • ∇f(K):=lqrGrad(A,B,I,Q,R,Σ,K)\nabla f(K) := \mathrm{lqrGrad}(A,B,I,Q,R,\Sigma,K)∇f(K):=lqrGrad(A,B,I,Q,R,Σ,K), an m×nm\times nm×n matrix.
  • S0:=sublevel(A,B,I,Q,R,Σ,K0)\mathcal{S}_0 := \mathrm{sublevel}(A,B,I,Q,R,\Sigma,K_0)S0​:=sublevel(A,B,I,Q,R,Σ,K0​), a set of m×nm\times nm×n matrices.
  • ∥M∥F:=frobNorm(M)\|M\|_F := \mathrm{frobNorm}(M)∥M∥F​:=frobNorm(M), a real number.
  • Kj:=gradIter(A,B,I,Q,R,Σ,K0,γ,j)K_j := \mathrm{gradIter}(A,B,I,Q,R,\Sigma,K_0,\gamma,j)Kj​:=gradIter(A,B,I,Q,R,Σ,K0​,γ,j), an m×nm\times nm×n matrix for each j∈Nj \in \mathbb{N}j∈N.

Nothing in the statement itself says what these objects are or how they relate to each other. For example, it does not say that S0⊆S\mathcal{S}_0 \subseteq \mathcal{S}S0​⊆S, what KjK_jKj​ is computed from, or what fff is outside S\mathcal{S}S.

Hypotheses. Besides the ones above:

  • K0∈SK_0 \in \mathcal{S}K0​∈S and K⋆∈SK^\star \in \mathcal{S}K⋆∈S.
  • K⋆K^\starK⋆ minimizes fff over S\mathcal{S}S, meaning f(K⋆)≤f(K)f(K^\star) \le f(K)f(K⋆)≤f(K) for every K∈SK \in \mathcal{S}K∈S.
  • L>0L > 0L>0 is a real number with
∥∇f(K)−∇f(K′)∥F≤L ∥K−K′∥Ffor all K,K′∈S0.\|\nabla f(K) - \nabla f(K')\|_F \le L\,\|K - K'\|_F \quad \text{for all } K, K' \in \mathcal{S}_0.∥∇f(K)−∇f(K′)∥F​≤L∥K−K′∥F​for all K,K′∈S0​.
  • γ:N→R\gamma : \mathbb{N} \to \mathbb{R}γ:N→R is an arbitrary real sequence (the step sizes γj\gamma_jγj​).

Conclusion. Two statements hold together.

(i) Suppose 0<γj≤2/L0 < \gamma_j \le 2/L0<γj​≤2/L for every jjj. Then Kj∈S0K_j \in \mathcal{S}_0Kj​∈S0​ for every j∈Nj \in \mathbb{N}j∈N, and for every jjj:

f(Kj+1)≤f(Kj)−γj(1−Lγj2)∥∇f(Kj)∥F2.f(K_{j+1}) \le f(K_j) - \gamma_j\left(1 - \frac{L\gamma_j}{2}\right)\|\nabla f(K_j)\|_F^2 .f(Kj+1​)≤f(Kj​)−γj​(1−2Lγj​​)∥∇f(Kj​)∥F2​.

(ii) Let ε1>0\varepsilon_1 > 0ε1​>0 and ε2>0\varepsilon_2 > 0ε2​>0 be any reals with ε1≤γj≤2/L−ε2\varepsilon_1 \le \gamma_j \le 2/L - \varepsilon_2ε1​≤γj​≤2/L−ε2​ for every jjj. Then all three of the following hold:

  1. ∥∇f(Kj)∥F→0\|\nabla f(K_j)\|_F \to 0∥∇f(Kj​)∥F​→0 as j→∞j \to \inftyj→∞.
  2. For every integer k≥1k \ge 1k≥1:
min⁡0≤j≤k∥∇f(Kj)∥F2  ≤  f(K0)ε1ε2L2⋅k.\min_{0 \le j \le k} \|\nabla f(K_j)\|_F^2 \;\le\; \frac{f(K_0)}{\frac{\varepsilon_1\varepsilon_2 L}{2}\cdot k}.0≤j≤kmin​∥∇f(Kj​)∥F2​≤2ε1​ε2​L​⋅kf(K0​)​.

The minimum is over the k+1k+1k+1 indices j=0,1,…,kj = 0, 1, \dots, kj=0,1,…,k. 3. There exist reals c≥0c \ge 0c≥0 and qqq with 0≤q<10 \le q < 10≤q<1 such that ∥Kj−K⋆∥F≤c qj\|K_j - K^\star\|_F \le c\,q^j∥Kj​−K⋆∥F​≤cqj for every j∈Nj \in \mathbb{N}j∈N.

  • ccc and qqq are only claimed to exist. They may depend on everything above, including ε1\varepsilon_1ε1​, ε2\varepsilon_2ε2​ and γ\gammaγ.
  • No formula for them is given.

Degenerate cases.

  • n=0n = 0n=0 or m=0m = 0m=0. The only n×mn\times mn×m matrix is the zero matrix, so the hypothesis B≠0B \neq 0B=0 cannot hold. The whole statement is then vacuously true, so it has content only when n≥1n \ge 1n≥1 and m≥1m \ge 1m≥1.
  • Unsatisfiable step-size conditions. In (ii), if ε1>2/L−ε2\varepsilon_1 > 2/L - \varepsilon_2ε1​>2/L−ε2​, no sequence γ\gammaγ satisfies the condition, and (ii) is vacuous for that pair (ε1,ε2)(\varepsilon_1, \varepsilon_2)(ε1​,ε2​).
    • The same happens in (i) and (ii) whenever the fixed γ\gammaγ breaks the stated bounds at even one index.
  • Divisions. Because L>0L > 0L>0, the quantity 2/L2/L2/L is an ordinary positive number. Because ε1,ε2,L>0\varepsilon_1, \varepsilon_2, L > 0ε1​,ε2​,L>0 and k≥1k \ge 1k≥1, the denominator in the gradient bound is strictly positive, so no division by zero occurs. The bound for k=0k = 0k=0 is not claimed.
  • q=0q = 0q=0. This choice is allowed, with q0=1q^0 = 1q0=1. The rate bound then says ∥K0−K⋆∥F≤c\|K_0 - K^\star\|_F \le c∥K0​−K⋆∥F​≤c and Kj=K⋆K_j = K^\starKj​=K⋆ for every j≥1j \ge 1j≥1.
  • The hypotheses themselves. The Lipschitz hypothesis and the minimality of K⋆K^\starK⋆ are stated only through the unshown definitions of fff, ∇f\nabla f∇f, S\mathcal{S}S, S0\mathcal{S}_0S0​ and ∥⋅∥F\|\cdot\|_F∥⋅∥F​. Whether they can be satisfied, or hold vacuously (for example, if S\mathcal{S}S or S0\mathcal{S}_0S0​ turned out to be empty or a single point), cannot be determined from the code shown.
  • The sign of f(K0)f(K_0)f(K0​). No hypothesis says f(K0)≥0f(K_0) \ge 0f(K0​)≥0 or says anything about the sign of fff.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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