Algebraic Riccati equations (AREs) arise in various models related to control theory, especially in linear-quadratic optimal control design. The deterministic/classical ones are considered for the deterministic linear time-invariant systems, including discrete-time algebraic Riccati equations (DAREs)

\[ X=A^{\T }XA+Q-(A^{\T }XB+L)(R+B^{\T }XB)^{-1}(B^{\T }XA+L^{\T }), \]

and continuous-time algebraic Riccati equations (CAREs)

\[ A^{\T }X+XA+Q-(XB+L)R^{-1}(B^{\T }X+L^{\T })=0. \]

During many years, people have developed rich theoretical results and numerical methods for the DAREs and CAREs. See [22, 21, 18, 3, 16, 2] to obtain an overview for both theories and algorithms.

In comparison, the stochastic/rational ones are considered for the stochastic linear time-invariant systems, including stochastic discrete-time algebraic Riccati equations (SDAREs)

\begin{align*} X=&A_{0}^{\T }XA_{0} + \sum _{i=1}^{r-1} A_i^{\T }XA_i+Q \\ &-(A_{0}^{\T }XB_{0}+\sum _{i=1}^{r-1} A_i^{\T }XB_i+L) (B_{0}^{\T }XB_{0}+\sum _{i=1}^{r-1} B_i^{\T }XB_i+R)^{-1}(B_{0}^{\T }XA_{0}+\sum _{i=1}^{r-1} B_i^{\T }XA_i+L^{\T }), \end{align*} and stochastic continuous-time algebraic Riccati equations (SCAREs)

\begin{align*} &A_{0}^{\T }X+XA_{0} + \sum _{i=1}^{r-1} A_i^{\T }XA_i+Q \\\qquad &-(XB_{0}+\sum _{i=1}^{r-1} A_i^{\T }XB_i+L) (\sum _{i=1}^{r-1} B_i^{\T }XB_i+R)^{-1}(B_{0}^{\T }X+\sum _{i=1}^{r-1} B_i^{\T }XA_i+L^{\T })=0. \end{align*} Here \(r-1\) is the number of stochastic processes involved in the stochastic systems dealt with, and it is easy to check that for the case \(r=1\) SDAREs and SCAREs degenerate to DAREs and CAREs respectively. Due to the complicated forms, we may recognize it would be much more difficult to analyze their properties and obtain their solutions. There are still literature, e.g., [6, 7, 8], discussing the stochastic linear systems and the induced stochastic AREs.

As we can see, the stochastic AREs are still algebraic, and it is quite natural to ask whether algebraic methods could be developed to solve them. However, limited by lack of clear algebraic structures, to the best of the authors’ knowledge, nearly all of the existing algorithms are based on the differentiability or continuity of the equations, such as Newton’s method [6, 5], modified Newton’s method [12, 19, 4], Lyapunov/Stein iterations [9, 20, 24], comparison theorem based method [10, 11], LMI’s (linear matrix inequality) method [23, 17], and homotopy method [25].

The key to the problem is the algebraic structures behind the equations. In this talk, we will build up a simple and clear algebraic interpretation of SDAREs and SCAREs with the help of the so-called left semi-tensor product. In the analysis we find out the Toeplitz structure and the symplectic structure appearing in the equations, and illustrate the fact that the fixed point iteration and the doubling iteration are also valid for them. The algebraic structures found here will shed light on the theoretical analysis and numerical algorithms design, and strongly imply that stochastic AREs are almost as easy as deterministic ones.

As an example, we show how to propose a RADI-type method for large-scale stochastic continuous-time algebraic Riccati equations with sparse and low-rank matrices (\(A_i\) are large-scale and sparse, and \(B_i\) and \(Q-LR^{-1}L^{\T }\) are low-rank), based on revealed algebraic structure and motivated by the relation illustrated in [13] between the algebraic structure and the efficient RADI method [1] for CAREs. Unlike many existing methods for large-scale problems such as Newton-type methods and homotopy method, it calculates the residual at a low cost and does not require a stabilizing initial approximation, which can often be challenging to find. Numerical experiments are provided to demonstrate its efficiency.

This talk is based on [13, 14, 15].

References

• [1]  P. Benner, Z. Bujanović, P. Kürschner, and J. Saak, “RADI: a low-rank ADI-type algorithm for large-scale algebraic Riccati equations,” Numer. Math., vol. 138, pp. 301–330, 2018.

• [2]  ——, “A numerical comparison of different solvers for large-scale, continuous-time algebraic Riccati equations and LQR problems,” SIAM J. Sci. Comput., vol. 42, no. 2, pp. A957–A996, 2020.

• [3]  D. A. Bini, B. Iannazzo, and B. Meini, Numerical Solution of Algebraic Riccati Equations, ser. Fundamentals of Algorithms. Philadelphia: SIAM Publications, 2012, vol. 9.

• [4]  E. K.-w. Chu, T. Li, W.-W. Lin, and C.-Y. Weng, “A modified newton’s method for rational riccati equations arising in stochastic control,” in 2011 International Conference on Communications, Computing and Control Applications (CCCA), 2011, pp. 1–6.

• [5]  T. Damm and D. Hinrichsen, “Newton’s method for a rational matrix equation occurring in stochastic control,” Linear Algebra Appl., vol. 332-334, pp. 81–109, 2001.

• [6]  T. Damm, Rational Matrix Equations in Stochastic Control. Berlin/Heidelberg, Germany: Springer-Verlag, 2004.

• [7]  V. Dragan, T. Morozan, and A.-M. Stoica, Mathematical Methods in Robust Control of Discrete-Time Linear Stochastic Systems. New York, NY, USA: Springer-Verlag, 2010.

• [8]  ——, Mathematical Methods in Robust Control of Linear Stochastic Systems, 2nd ed. New York, NY, USA: Springer-Verlag, 2013.

• [9]  H.-Y. Fan, P. C.-Y. Weng, and E. K. wah Chu, “Smith method for generalized Lyapunov/Stein and rational Riccati equations in stochastic control,” Numer. Alg., vol. 71, pp. 245–272, 2016.

• [10]  G. Freiling and A. Hochhaus, “Properties of the solutions of ration matrix difference equations,” Computers Math. Appl., vol. 45, pp. 1137–1154, 2003.

• [11]  ——, “On a class of rational matrix differential equations arising in stochastic control,” Linear Algebra Appl., vol. 379, pp. 43–68, 2004.

• [12]  C.-H. Guo, “Iterative solution of a matrix Riccati equation arising in stochastic control,” Oper. Theory: Adv. Appl., vol. 130, pp. 209–221, 2001.

• [13]  Z.-C. Guo and X. Liang, “The intrinsic Toeplitz structure and its applications in algebraic Riccati equations,” Numer. Alg., vol. 93, pp. 227–267, 2023.

• [14]  ——, “Stochastic algebraic Riccati equations are almost as easy as deterministic ones theoretically,” SIAM J. Matrix Anal. Appl., vol. 44, no. 4, pp. 1749–1770, 2023.

• [15]  ——, “An RADI-type method for stochastic continuous-time algebraic Riccati equations,” 2024, 21 pages.

• [16]  T.-M. Huang, R.-C. Li, and W.-W. Lin, Structure-Preserving Doubling Algorithms for Nonlinear Matrix Equations, ser. Fundamentals of Algorithms. Philadelphia: SIAM, 2018, vol. 14.

• [17]  H. Iiduka and I. Yamada, “Computational method for solving a stochastic linear-quadratic control problem given an unsolvable stochastic algebraic Riccati equation,” SIAM J. Control Optim., vol. 50, no. 4, pp. 2173–2192, 2012.

• [18]  V. Ionescu, C. Oară, and M. Weiss, Generalized Riccati Theory and Robust Control: A Popov Function Approach. Chichester, UK: John Wiley & Sons, 1999.

• [19]  I. G. Ivanov, “Iterations for solving a rational Riccati equations arising in stochastic control,” Computers Math. Appl., vol. 53, pp. 977–988, 2007.

• [20]  ——, “Properties of Stein (Lyapunov) iterations for solving a general Riccati equation,” Nonlinear Anal., vol. 67, pp. 1155–1166, 2007.

• [21]  P. Lancaster and L. Rodman, Algebraic Riccati Equations. New York: The clarendon Press, Oxford Sciece Publications, 1995.

• [22]  V. L. Mehrmann, “The autonomous linear quadratic control problems,” in Lecture Notes in Control and Information Sciences. Berlin: Springer-Verlag, 1991, vol. 163.

• [23]  M. A. Rami and X. Y. Zhou, “Linear matrix inequalities, Riccati equations, and indefinite stochastic linear quadratic controls,” IEEE Trans. Automat. Control, vol. 45, no. 6, pp. 1131–1143, 2000.

• [24]  N. Takahashi, M. Kono, T. Suzuki, and O. Sato, “A numerical solution of the stochastic discrete algebraic Riccati equation,” J. Archaeological Sci., vol. 13, pp. 451–454, 2009.

• [25]  L. Zhang, H.-Y. Fan, E. K. wah Chu, and Y. Wei, “Homotopy for rational Riccati equations arising in stochastic optimal control,” SIAM J. Sci. Comput., vol. 37, no. 1, pp. B103–B125, 2015.