Theorem 4.2 for state feedback — the gradient method stays in , reaches stationarity, and converges linearly to the optimal gain
ProvedFatkhullinPolyak.Discrete.gradient_method_slqr_linear_rateConsider state feedback, (so ), with , and a stabilizing gain . Let be an optimal gain, for all . Let be a Lipschitz constant of the gradient (3.3) on :
Let be real step sizes and the gradient method (4.4) from .
- If for all , then every lies in and
- If for all , with , then ,
and the iterates converge to at a linear rate: there are and with
This is the main convergence theorem of the paper for the discrete gradient method: although 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 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 is -Lipschitz on (the definition of -smoothness in §3.6), so is any such constant. Invariance of is a conclusion, not a hypothesis. The minimum is over and requires . In (4.6) the paper uses the spectral norm; the Frobenius norm is used here, which is equivalent up to a factor absorbed in . The constants may depend on all the data, the step sequence and , as in the paper. is taken as a hypothesis; its existence is Corollary 3.10.
import Mathlib import Definitions.Def_FatkhullinPolyak_Discrete_LQR open Filter Topology
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For natural numbers , the statement fixes real matrices , , , and . It assumes , and are positive definite (Mathlib's notion, which includes symmetry) and that . 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 identity matrix :
- , a set of real matrices.
- , a real number for each matrix .
- , an matrix.
- , a set of matrices.
- , a real number.
- , an matrix for each .
Nothing in the statement itself says what these objects are or how they relate to each other. For example, it does not say that , what is computed from, or what is outside .
Hypotheses. Besides the ones above:
- and .
- minimizes over , meaning for every .
- is a real number with
- is an arbitrary real sequence (the step sizes ).
Conclusion. Two statements hold together.
(i) Suppose for every . Then for every , and for every :
(ii) Let and be any reals with for every . Then all three of the following hold:
- as .
- For every integer :
The minimum is over the indices . 3. There exist reals and with such that for every .
- and are only claimed to exist. They may depend on everything above, including , and .
- No formula for them is given.
Degenerate cases.
- or . The only matrix is the zero matrix, so the hypothesis cannot hold. The whole statement is then vacuously true, so it has content only when and .
- Unsatisfiable step-size conditions. In (ii), if , no sequence satisfies the condition, and (ii) is vacuous for that pair .
- The same happens in (i) and (ii) whenever the fixed breaks the stated bounds at even one index.
- Divisions. Because , the quantity is an ordinary positive number. Because and , the denominator in the gradient bound is strictly positive, so no division by zero occurs. The bound for is not claimed.
- . This choice is allowed, with . The rate bound then says and for every .
- The hypotheses themselves. The Lipschitz hypothesis and the minimality of are stated only through the unshown definitions of , , , and . Whether they can be satisfied, or hold vacuously (for example, if or turned out to be empty or a single point), cannot be determined from the code shown.
- The sign of . No hypothesis says or says anything about the sign of .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.