A Flexible and Accurate Solver for Continuous-Time Algebraic Riccati Equations | SN Computer Science Skip to main content
Springer Nature Link
Log in

A Flexible and Accurate Solver for Continuous-Time Algebraic Riccati Equations

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

The solution of algebraic Riccati equations (AREs) is a fundamental computation in optimal control and other domains. Most of the available ARE solvers are black-boxes, lacking the flexibility in choosing a solution method, or in setting values for options and parameters. However, the quality of a computed solution depends not only on the problem conditioning, but also on various decisions made by the solver designer. The purpose of this paper is to show how the accuracy of solutions can be improved as much as possible. The paper presents a flexible solver for continuous-time AREs (CAREs) that allows the user to choose among several structured solution methods, orthogonalization methods, and balancing options, and to set parameter values. Since no selection ensures the best results for all problems, it is sometimes useful to automatically explore various algorithmic pathways. The best solution found serves to initialize a Newton solver to further improve the accuracy of the results. Since this solver also offers several methods and options, it can itself be employed in an exploratory way. The combination of the flexible CARE solver with Newton solver has been used to solve the examples from the SLICOT CAREX benchmark collection, and for most of the systems from the COMPl\(_e\)ib collection. The relative errors, and relative and normalized residuals of the solutions computed by the combined solver can be of several orders of magnitude smaller than those obtained by the state-of-the-art MATLAB solvers. Often, the limiting precision of the computations is attained. The numerical results in extensive tests illustrate the very good performance of the proposed flexible and accurate solver.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Notes

  1. See https://github.com/SLICOT/SLICOT-Reference and http://www.slicot.org.

References

  1. The MathWorks, Inc.: MATLAB® Primer. R2016a. Natick; 2016.

  2. Van Dooren P. A generalized eigenvalue approach for solving Riccati equations. SIAM J Sci Stat Comput. 1981;2(2):121–35. https://doi.org/10.1137/0902010.

    Article  MathSciNet  MATH  Google Scholar 

  3. Bender DJ, Laub AJ. The linear-quadratic optimal regulator for descriptor systems. IEEE Trans Autom Control AC. 1987;32(8):672–88. https://doi.org/10.1016/0005-1098(87)90119-1.

    Article  MathSciNet  MATH  Google Scholar 

  4. Mehrmann V. The autonomous linear quadratic control problem. Theory and numerical solution. Lect. notes in control and information sciences, vol. 163. Berlin: Springer; 1991.

    Google Scholar 

  5. Lancaster P, Rodman L. The algebraic Riccati equation. Oxford: Oxford University Press; 1995.

    MATH  Google Scholar 

  6. Sima V. Algorithms for linear-quadratic optimization. Pure and applied mathematics: a series of monographs and textbooks, vol. 200. New York: Marcel Dekker, Inc.; 1996.

    Google Scholar 

  7. MathWorks®: Control System Toolbox\(^{\rm TM}\). The MathWorks, Inc., Natick; 2015.

  8. Benner P, Mehrmann V, Sima V, Van Huffel S, Varga A. SLICOT—a subroutine library in systems and control theory. In: Datta BN, editor. Applied and computational control, signals, and circuits, chapter 10, vol. 1. Boston: Birkhäuser; 1999. p. 499–539. https://doi.org/10.1007/978-1-4612-0571-5_10.

    Chapter  MATH  Google Scholar 

  9. Benner P, Kressner D, Sima V, Varga A. Die SLICOT-Toolboxen für Matlab. Automatisierungstechnik. 2010;58(1):15–25. https://doi.org/10.1524/auto.2010.0814.

    Article  Google Scholar 

  10. Raines III AC, Watkins DS. A class of Hamiltonian-symplectic methods for solving the algebraic Riccati equation. Technical report, Washington State University, Pullman, WA, 1992.

  11. Benner P, Byers R, Mehrmann V, Xu H. Numerical computation of deflating subspaces of skew Hamiltonian/Hamiltonian pencils. SIAM J Matrix Anal Appl. 2002;24(1):165–90. https://doi.org/10.1137/S0895479800367439.

    Article  MathSciNet  MATH  Google Scholar 

  12. Benner P, Byers R, Losse P, Mehrmann V, Xu H. Numerical solution of real skew-Hamiltonian/Hamiltonian eigenproblems. Technical report, Technische Universität Chemnitz, Chemnitz, November 2007.

  13. Xu H. On equivalence of pencils from discrete-time and continuous-time control. Linear Algebra Appl. 2006;414(1):97–124. https://doi.org/10.1016/j.laa.2005.09.015.

    Article  MathSciNet  MATH  Google Scholar 

  14. Anderson BDO, Moore JB. Linear optimal control. Englewood Cliffs: Prentice-Hall; 1971.

    Book  MATH  Google Scholar 

  15. Francis BA. A course in \(H_{\infty }\) control theory. Lect. notes in control and information sciences, vol. 88. New York: Springer; 1987.

    Google Scholar 

  16. Bini DA, Iannazzo B, Meini B. Numerical solution of algebraic Riccati equations. Philadelphia: SIAM; 2012.

    MATH  Google Scholar 

  17. Benner P. Theory and numerical solution of differential and algebraic Riccati equations. In: Benner P, Bollhöfer M, Kressner D, Mehl C, Stykel T, editors. Numerical algebra, matrix theory, differential-algebraic equations and control theory. Cham: Springer; 2015. p. 67–105. https://doi.org/10.1007/978-3-319-15260-8.

    Chapter  MATH  Google Scholar 

  18. Varga A. Solving fault diagnosis problems: linear synthesis techniques. Studies in systems decision and control, vol. 84. Berlin: Springer; 2017. https://doi.org/10.1007/978-3-319-51559-5.

    Book  MATH  Google Scholar 

  19. Laub AJ. A Schur method for solving algebraic Riccati equations. IEEE Trans Autom Control AC. 1979;24(6):913–21. https://doi.org/10.1109/CDC.1978.267893.

    Article  MathSciNet  MATH  Google Scholar 

  20. Arnold WF III, Laub AJ. Generalized eigenproblem algorithms and software for algebraic Riccati equations. Proc IEEE. 1984;72(12):1746–54. https://doi.org/10.1109/PROC.1984.13083.

    Article  Google Scholar 

  21. Kenney C, Laub AJ, Wette M. A stability-enhancing scaling procedure for Schur–Riccati solvers. Syst Control Lett. 1989;12:241–50. https://doi.org/10.1016/0167-6911(89)90056-X.

    Article  MathSciNet  MATH  Google Scholar 

  22. Bunse-Gerstner A, Mehrmann V. A symplectic QR like algorithm for the solution of the real algebraic Riccati equation. IEEE Trans Autom Control AC. 1986;31(12):1104–13. https://doi.org/10.1109/TAC.1986.1104186.

    Article  MathSciNet  MATH  Google Scholar 

  23. Sima V, Benner P. Solving SLICOT benchmarks for continuous-time algebraic Riccati equations by Hamiltonian solvers. In: Proceedings of the 2015 19th International Conference on System Theory, Control and Computing (ICSTCC 2015), October 14–16, 2015, Cheile Gradistei-Fundata Resort, Romania, 2015, p. 1–6. IEEE, Piscataway, NJ. https://doi.org/10.1109/ICSTCC.2015.7321260.

  24. Benner P, Sima V, Voigt M. Algorithm 961: Fortran 77 subroutines for the solution of skew-Hamiltonian/Hamiltonian eigenproblems. ACM Trans Math Softw (TOMS). 2016;42(3):1–26. https://doi.org/10.1145/2818313.

    Article  MathSciNet  Google Scholar 

  25. Roberts J. Linear model reduction and solution of the algebraic Riccati equation by the use of the sign function. Int J Control. 1980;32:667–87. https://doi.org/10.1080/00207178008922881.

    Article  MathSciNet  Google Scholar 

  26. Gardiner JD, Laub AJ. A generalization of the matrix sign function solution for algebraic Riccati equations. Int J Control. 1986;44:823–32. https://doi.org/10.1109/CDC.1985.268700.

    Article  MATH  Google Scholar 

  27. Byers R. Solving the algebraic Riccati equation with the matrix sign function. Linear Algebra Appl. 1987;85(1):267–79. https://doi.org/10.1016/0024-3795(87)90222-9.

    Article  MathSciNet  MATH  Google Scholar 

  28. Kleinman DL. On an iterative technique for Riccati equation computations. IEEE Trans Autom Control AC. 1968;13:114–5. https://doi.org/10.1109/TAC.1968.1098829.

    Article  Google Scholar 

  29. Benner, P.: Contributions to the numerical solution of algebraic Riccati equations and related eigenvalue problems. Dissertation, Fakultät für Mathematik, Technische Universität Chemnitz–Zwickau, D-09107 Chemnitz, Germany, 1997.

  30. Benner P, Byers R. An exact line search method for solving generalized continuous-time algebraic Riccati equations. IEEE Trans Autom Control. 1998;43(1):101–7. https://doi.org/10.1109/9.654908.

    Article  MathSciNet  MATH  Google Scholar 

  31. Guo C, Laub AJ. On a Newton-like method for solving algebraic Riccati equations. SIAM J Matrix Anal Appl. 2000;21(2):694–8. https://doi.org/10.1137/S0895479898348519.

    Article  MathSciNet  MATH  Google Scholar 

  32. Sima V, Benner P. A SLICOT implementation of a modified Newton’s method for algebraic Riccati equations. In: Proceedings of the 14th Mediterranean Conference on Control and Automation MED’06, June 28–30 2006, Ancona, Italy (CD-ROM). Omnipress, Madison, WI (2006). https://doi.org/10.1109/MED.2006.328740.

  33. Sima V, Benner P. Numerical investigation of Newton’s method for solving continuous-time algebraic Riccati equations. In: Ferrier J-L, Gusikhin O, Madani K, Sasiadek J, editors. Proceedings of the 11th International Conference on Informatics in Control, Automation and Robotics (ICINCO-2014), 1–3 September, 2014, Vienna, Austria, 2014, vol. 1, p. 404–9. SciTePress—Science and Technology Publications, Setúbal, Portugal. https://doi.org/10.5220/0005117004040409.

  34. Sima V, Benner P. Computational experience with a modified Newton solver for discrete-time algebraic Riccati equations. In: Gusikhin O, Madani K, editors. Informatics in control, automation and robotics. 15th International Conference, ICINCO 2018, Porto, Portugal, July 29–31, 2018, Revised Selected Papers. Lecture Notes in Electrical Engineering, 2019, vol. 613, p. 142–67. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-030-31993-9.

  35. Chu EK-W, Fan H-Y, Lin W-W. A structure-preserving doubling algorithm for continuous-time algebraic Riccati equations. Linear Algebra Appl. 2005;386:55–80. https://doi.org/10.1016/j.laa.2004.10.010.

    Article  MathSciNet  MATH  Google Scholar 

  36. Guo P-C. A modified large-scale structure-preserving doubling algorithm for a large-scale Riccati equation from transport theory. Numer Algorithms. 2016;71(3):541–52. https://doi.org/10.1007/s11075-015-0008-4.

    Article  MathSciNet  MATH  Google Scholar 

  37. Lanzon A, Feng Y, Anderson BDO, Rotkowitz M. Computing the positive stabilizing solution to algebraic Riccati equations with an indefinite quadratic term via a recursive method. IEEE Trans Autom Control AC. 2008;53(10):2280–91. https://doi.org/10.1109/TAC.2008.2006108.

    Article  MathSciNet  MATH  Google Scholar 

  38. Penzl T. LYAPACK users guide. Technical Report SFB393/00-33, Technische Universität Chemnitz, Sonderforschungsbereich 393, “Numerische Simulation auf massiv parallelen Rechnern”, Chemnitz (August 2000).

  39. Penzl T. Numerical solution of generalized Lyapunov equations. Adv Comput Math. 1998;8:33–48. https://doi.org/10.1023/A:1018979826766.

    Article  MathSciNet  MATH  Google Scholar 

  40. Benner P, Sima V. Solving algebraic Riccati equations with SLICOT. In: CD-ROM Proceedings of The 11th Mediterranean Conference on Control and Automation MED’03, June 18–20 2003, Rhodes, Greece; 2003.

  41. Van Huffel S, Sima V, Varga A, Hammarling S, Delebecque F. High-performance numerical software for control. IEEE Control Syst Mag. 2004;24(1):60–76. https://doi.org/10.1109/MCS.2004.1272746.

    Article  Google Scholar 

  42. Giftthaler M, Neunert M, Stäuble M, Buchli J. The Control Toolbox—an Open-Source C++ library for robotics, optimal and model predictive control. [Online]. 2018. https://doi.org/10.1109/SIMPAR.2018.8376281. Available: https://arxiv.org/abs/1801.04290.

  43. Sima V. An efficient Schur method to solve the stabilizing problem. IEEE Trans Autom Control AC. 1981;26(3):724–5. https://doi.org/10.1109/TAC.1981.1102700.

    Article  MathSciNet  MATH  Google Scholar 

  44. Varga A. A Schur method for pole assignment. IEEE Trans Autom Control AC. 1981;26(2):517–9. https://doi.org/10.1109/TAC.1981.1102605.

    Article  MathSciNet  MATH  Google Scholar 

  45. Hammarling SJ. Newton’s method for solving the algebraic Riccati equation. NPC Report DIIC 12/82, National Physics Laboratory, Teddington, Middlesex TW11 OLW, UK, 1982.

  46. Mehrmann V, Tan E. Defect correction methods for the solution of algebraic Riccati equations. IEEE Trans Autom Control AC. 1988;33(7):695–8. https://doi.org/10.1109/9.1282.

    Article  MathSciNet  MATH  Google Scholar 

  47. Ciubotaru BD, Staroswiecki M. Comparative study of matrix Riccati equation solvers for parametric faults accommodation. In: Proceedings of the 10th European Control Conference, 23-26 August 2009, Budapest, Hungary, 2009, p. 1371–6 . https://doi.org/10.23919/ECC.2009.7074597.

  48. Benner P, Mehrmann V, Xu H. A new method for computing the stable invariant subspace of a real Hamiltonian matrix. J Comput Appl Math. 1997;86(1):17–43. https://doi.org/10.1016/S0377-0427(97)00146-5.

    Article  MathSciNet  MATH  Google Scholar 

  49. Benner P, Mehrmann V, Xu H. A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils. Numer Math. 1998;78(3):329–58. https://doi.org/10.1007/s002110050315.

    Article  MathSciNet  MATH  Google Scholar 

  50. Bojanczyk AW, Golub G, Van Dooren P. The periodic Schur decomposition: algorithms and applications. In: Luk FT, editor. Proc. of the SPIE Conference Advanced Signal Processing Algorithms, Architectures, and Implementations III, 1992, vol. 1770, p. 31–42. https://doi.org/10.1117/12.130915.

  51. Sreedhar J, Van Dooren P. Periodic Schur form and some matrix equations. In: Helmke U, Mennicken R, Saurer J, editors. Systems and networks: mathematical theory and applications, Proceedings of the Symposium on the Mathematical Theory of Networks and Systems (MTNS’93), Regensburg, Germany, 2–6 August 1993, vol. 1. Weinheim, Berlin: Wiley-VCH; 1994. p. 339–62.

  52. Granat R, Kågström B, Kressner D. Computing periodic deflating subspaces associated with a specified set of eigenvalues. BIT Numer Math. 2007;47(4):763–91. https://doi.org/10.1007/s10543-007-0143-y.

    Article  MathSciNet  MATH  Google Scholar 

  53. Granat R, Kågström B, Kressner D. Matlab tools for solving periodic eigenvalue problems. IFAC Proc Vol. 2007;40(14):169–74. https://doi.org/10.3182/20070829-3-RU-4912.00029.

    Article  Google Scholar 

  54. Sima V, Gahinet P. Improving the convergence of the periodic QZ algorithm. In: Gusikhin O, Madani K, Zaytoon J, editors. Proceedings of the 16th International Conference on Informatics in Control, Automation and Robotics (ICINCO-2019), 29–31 July, 2019, Prague, Czech Republic, 2019, vol. 1, p. 261–268. SciTePress—Science and Technology Publications, Lda, Setúbal, Portugal. https://doi.org/10.5220/0007876902610268

  55. Sima V. Computation of initial transformation for implicit double step in the periodic QZ algorithm. In: Precup R-E, editor. Proceedings of the 2019 23th International Conference on System Theory, Control and Computing (ICSTCC), 9–11 October, 2019, Sinaia, Romania, p. 7–12. IEEE, Manhattan, New York; 2019. https://doi.org/10.1109/ICSTCC.2019.8885649.

  56. Sima V, Gahinet P. Using semi-implicit iterations in the periodic QZ algorithm. In: Gusikhin O, Madani K, Zaytoon J, editors. Proceedings of the 17th International Conference on Informatics in Control, Automation and Robotics (ICINCO-2020), 7–9 July, 2020, vol. 1: ICINCO, p. 35–46. SciTePress—Science and Technology Publications, Lda, Setúbal, Portugal. https://doi.org/10.5220/0009823300350046.

  57. Benner P. Symplectic balancing of Hamiltonian matrices. SIAM J Sci Comput. 2001;22(5):1885–904. https://doi.org/10.1137/S1064827500367993.

    Article  MathSciNet  MATH  Google Scholar 

  58. Sima V. Balancing skew-Hamiltonian/Hamiltonian pencils with applications in control engineering. In: Gusikhin O, Peaucelle D, Madani K, editors. Proceedings of the 13th International Conference on Informatics in Control, Automation and Robotics (ICINCO-2016), 29–31 July, 2016, Lisbon, Portugal, 2016, vol. 1, p. 177–84. SciTePress—Science and Technology Publications, Lda., Setúbal, Portugal. https://doi.org/10.5220/0005981201770184.

  59. Sima V, Benner P. Improved balancing for general and structured eigenvalue problems. In: Petre E, Brezovan M, editors. Proceedings of the 2016 20th Joint International Conference on System Theory, Control and Computing (ICSTCC 2016), October 13–15, 2016, Sinaia, Romania, 2016, p. 381–6. IEEE, Manhattan, New York. https://doi.org/10.1109/ICSTCC.2016.7790695.

  60. Sima V. A flexible structured solver for continuous-time algebraic Riccati equations. In: Gusikhin O, Nijmeijer H, Madani K, editors. ICINCO 2021 Proceedings of the 18th International Conference on Informatics in Control, Automation and Robotics, July 6-8, 2021, vol. 1, p. 78–89. SciTePress—Science and Technology Publications, Lda, Setúbal, Portugal. https://doi.org/10.5220/0010577700780089.

  61. Abels J, Benner P. CAREX—a collection of benchmark examples for continuous-time algebraic Riccati equations (Version 2.0). SLICOT Working Note 1999-14, 1999.

  62. Sima V. Computational experience with structure-preserving Hamiltonian solvers in optimal control. In: Ferrier J-L, Bernard A, Gusikhin O, Madani K, editors. Proceedings of the “8th International Conference on Informatics in Control, Automation and Robotics” (ICINCO 2011), Noordwijkerhout, The Netherlands, 28–31 July, 2011, vol. 1, p. 91–6. SciTePress—Science and Technology Publications, Setúbal, Portugal. https://doi.org/10.5220/0003534100910096.

  63. Leibfritz F, Lipinski W. Description of the benchmark examples in shape COMPleib. Technical report, Department of Mathematics, University of Trier, D-54286 Trier, Germany, 2003.

  64. Sima V. Structure-preserving computation of stable deflating subspaces. IFAC Proc Vol. 2010;43(10):249–54. https://doi.org/10.3182/20100826-3-TR-4015.00047.

    Article  Google Scholar 

  65. Sima V, Benner P. Pitfalls when solving eigenproblems with applications in control engineering. In: Filipe J, Madani K, Gusikhin OY, Sasiadek JZ, editors. Proceedings of the 12th International Conference on Informatics in Control, Automation and Robotics (ICINCO-2015), 21–23 July, 2015, Colmar, France, 2015, vol. 1, p. 171–8. SciTePress—Science and Technology Publications, Setúbal, Portugal. https://doi.org/10.5220/0005533301710178.

  66. Ward RC. Balancing the generalized eigenvalue problem. SIAM J Sci Stat Comput. 1981;2:141–52. https://doi.org/10.1137/0902012.

    Article  MathSciNet  MATH  Google Scholar 

  67. Anderson E, Bai Z, Bischof C, Blackford S, Demmel J, Dongarra J, Du Croz J, Greenbaum A, Hammarling S, McKenney A, Sorensen D. LAPACK users’ guide: third edition. Software \(\cdot \) Environments \(\cdot \) Tools. Philadelphia: SIAM; 1999.

    Book  MATH  Google Scholar 

  68. Sima V. Computational experience with a modified Newton solver for continuous-time algebraic Riccati equations. In: Ferrier J-L, Gusikhin O, Madani K, Sasiadek J, editors. Informatics in control, automation and robotics. Lecture notes in electrical engineering, vol. 325. Cham: Springer; 2015. p. 55–71. https://doi.org/10.1007/978-3-319-10891-9_3.

    Chapter  Google Scholar 

  69. Dongarra JJ, Du Croz J, Duff IS, Hammarling S. Algorithm 679: a set of level 3 basic linear algebra subprograms. ACM Trans Math Softw. 1990;16(1):1–17, 18–28. https://doi.org/10.1145/77626.77627.

    Article  MATH  Google Scholar 

  70. Van Huffel S, Sima V. SLICOT and control systems numerical software packages. In: Proceedings of the 2002 IEEE International Conference on Control Applications and IEEE International Symposium on Computer Aided Control System Design, CCA/CACSD 2002, September 18–20, 2002, Glasgow, Scotland, UK, 2002, p. 39–44. Omnipress, Madison, WI. https://doi.org/10.1109/CACSD.2002.1036926.

  71. Jónsson GF, Vavasis S. Solving polynomials with small leading coefficients. SIAM J Matrix Anal Appl. 2004;26(2):400–14. https://doi.org/10.1137/S0895479899365720.

    Article  MathSciNet  MATH  Google Scholar 

  72. Golub GH, Van Loan CF. Matrix computations. 4th ed. Baltimore: The Johns Hopkins University Press; 2013.

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technical Sciences Academy of Romania, Bucharest, Romania

    Vasile Sima

Authors
  1. Vasile Sima
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Vasile Sima.

Ethics declarations

Conflict of interest

The author declares that he has no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Informatics in Control, Automation and Robotics” guest edited by Kurosh Madani, Oleg Gusikhin and Henk Nijmeijer.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Sima, V. A Flexible and Accurate Solver for Continuous-Time Algebraic Riccati Equations. SN COMPUT. SCI. 4, 28 (2023). https://doi.org/10.1007/s42979-022-01430-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-022-01430-4

Keywords