The discrete-time Riccati equation is the central object of linear-quadratic optimal control — the design equation behind LQR/LQG controllers in every modern control stack. Proposition 4.4.1 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005, §4.1) packages its asymptotic theory: under controllability and observability the Riccati iteration converges to the unique positive semidefinite solution of the algebraic Riccati equation and the resulting closed loop is stable. Alongside it, Lemma 4.2.1 of §4.2 develops K-convexity, the analytical engine behind Scarf's optimality of inventory policies — a foundational result of operations research. Neither the Riccati asymptotics nor K-convexity exists in Mathlib.
Matrices , , , . The Riccati operator (BertsekasRiccatiMap)
is controllable if has rank (BertsekasControllablePair); is observable if is controllable (BertsekasObservablePair). Separately, is -convex (BertsekasKConvex, Def. 4.2.1) if for all , , .
with — BertsekasDP.riccati_convergence_stability (goal). Milestones: Lemma 4.2.1(a)–(d) (kconvex_of_convex, kconvex_combination, kconvex_expectation, kconvex_sS_structure), culminating in the structure theorem for continuous coercive -convex functions.
The Riccati result is the mathematical license behind steady-state LQR design: it guarantees the design equation has one meaningful solution, that iterating the finite-horizon recursion finds it, and that the resulting feedback is stabilizing. Formally it would seed a Mathlib-adjacent theory of matrix fixed-point iterations, positive semidefinite order, and spectral-radius stability. The K-convexity milestones are self-contained real analysis, each of independent reuse value for inventory theory; part (d) is the engine of -policy optimality. All results are classical and proved in the book; the formal work is new.
The Riccati proof interleaves monotonicity of on the psd cone, boundedness from controllability (a steering argument), positivity from observability, and stability extracted from the fixed-point identity via a Lyapunov argument — several pieces of matrix analysis (psd order, congruence, Schur-type manipulations, spectral radius vs. convergence of powers) that must be built or located in Mathlib. The naive route of diagonalizing fails: nothing is symmetric about . For Lemma 4.2.1(d), the difficulty is that is not convex: the minimizer structure must come from the K-convexity inequality applied at carefully chosen points, plus continuity and coercivity.
Real matrices over Fin n; Matrix.PosSemidef/PosDef; matrix inverse is Mathlib's total inverse (zero on singular input — harmless here since along the relevant iterates, which the proof must establish); convergence in the entrywise topology; eigenvalues via spectrum ℂ of the complexified matrix, all strictly inside the unit circle. Rank-based controllability exactly as Def. 4.1.1. K-convexity is stated for all real ; note is forced whenever it is satisfiable (), and the expectation milestone is stated for finitely supported disturbances (integrability automatic).
namespace BertsekasDP
theorem riccati_convergence_stability {n m q : ℕ}
(A : Matrix (Fin n) (Fin n) ℝ) (B : Matrix (Fin n) (Fin m) ℝ)
(Q : Matrix (Fin n) (Fin n) ℝ) (R : Matrix (Fin m) (Fin m) ℝ)
(C : Matrix (Fin q) (Fin n) ℝ)
(hQ : Q = Cᵀ * C) (hQpsd : Q.PosSemidef) (hR : R.PosDef)
(hctrb : BertsekasControllablePair A B)
(hobs : BertsekasObservablePair A C) :
∃ P : Matrix (Fin n) (Fin n) ℝ, P.PosDef ∧
BertsekasRiccatiMap A B Q R P = P ∧
(∀ P' : Matrix (Fin n) (Fin n) ℝ, P'.PosSemidef →
BertsekasRiccatiMap A B Q R P' = P' → P' = P) ∧
(∀ P₀ : Matrix (Fin n) (Fin n) ℝ, P₀.PosSemidef →
Filter.Tendsto (fun k => (BertsekasRiccatiMap A B Q R)^[k] P₀)
Filter.atTop (nhds P)) ∧
(∀ z ∈ spectrum ℂ
((A + B * (-((Bᵀ * P * B + R)⁻¹ * Bᵀ * P * A))).map
(algebraMap ℝ ℂ)),
‖z‖ < 1) := by sorry
end BertsekasDPProposition 4.4.1 (asymptotic behavior of the Riccati equation and closed-loop stability). Let be , be , let be positive semidefinite symmetric with , and let be positive definite symmetric. Assume that is controllable and that is observable. Then there is a positive definite symmetric matrix such that:
This is the mathematical warrant for steady-state LQR design: it says the design equation has exactly one meaningful solution, that iterating the finite-horizon recursion finds it, and that the resulting constant feedback law stabilizes the system. Without part 4 one could compute a gain that minimizes cost over a finite horizon yet drives the state to infinity as the horizon grows.
Formalization Note Positive semidefiniteness and definiteness are Mathlib's (symmetry included). Uniqueness is asserted within the positive semidefinite cone only; nothing is claimed about indefinite fixed points. Convergence is entrywise, equivalently in any matrix norm. Eigenvalues are taken as the spectrum of the complexified matrix, so the bound is on the complex modulus. Matrix inverses are Mathlib's total inverse; part of the proof burden is showing is invertible where it is used.
No open leaves. Every sub-goal is proved or awaiting decomposition.