Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

详细信息    查看全文

• 作者：Hung-Yuan Fan ; Peter Chang-Yi Weng ; Eric King-Wah Chu
• 关键词：Algebraic Riccati equation ; Bilinear model order reduction ; Generalized Lyapunov equation ; Generalized Stein equation ; Large ; scale problem ; Newton’s method ; Rational Riccati equation ; Smith method ; Stochastic Algebraic Riccati equation ; Stochastic optimal control ; 15A24 ; 65F99 ; 93C05 ; 93E20 ; 93E25
• 刊名：Numerical Algorithms
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：71
• 期：2
• 页码：245-272
• 全文大小：464 KB
• 参考文献：1.Abou-kandil, H., Freiling, G., Ionescu, V., Jank, G.: Matrix Riccati Equations in Control and Systems Theory. Basel, Birkhäuser Verlag (2003)CrossRef MATH
  2.Bai, Z., Skoogh, D.: A projection method for model reduction of bilinear dynamical systems. Lin. Alg. Applic. 415, 406–425 (2006)CrossRef MathSciNet MATH
  3.Benner, P., Breiten, T.: Low rank methods for a class of generalized Lyapunov equations and related issues. Numer. Math. 124, 441–470 (2013)CrossRef MathSciNet MATH
  4.Benner, P., Damm, T.: Lyapunov equations, energy functionals, and model order reduction of bilinear and stochastic systems. SIAM J. Contr. Optim. 49, 686–711 (2011)CrossRef MathSciNet MATH
  5.Benner, P., Fassbender, H.: On the numerical solution of large-scale sparse discrete-time Riccati equations. Adv. Comput. Maths. 35, 119–147 (2011)CrossRef MathSciNet MATH
  6.Benner, P., Laub, A., Mehrmann, V.: Benchmarks for the numerical solution of algebraic Riccati equations. IEEE Contr. Syst. Magazine 17, 18–28 (1995)CrossRef
  7.Benner, P., Saak, J.: A semi-discretized heat transfer model for optimal cooling of steel profiles, in Dimension Reduction of Large-Scale Systems, ed. P. Benner, V. Mehrmann and D.C. Sorensen, Lecture Notes in Computational Science and Engineering, Springer-Verlag, Berlin/Heidelberg, Germany, 45 353356. (2005)
  8.Benner, P., Saak, J.: A Newton-Galerkin-ADI Method for Large-Scale Algebraic Riccati Equations , Applied Linear Algebra, GAMM Workshop Applied and Numerical Linear Algebra, Novi Sad May 27 2010 (2010). http://​ala2010.​pmf.​uns.​ac.​rs/​presentations/​4g1220pb.​pdf
  9.Benner, P., Saak, J.: A Galerkin-Newton-ADI method for solving large-scale algebraic Riccati equations, DFG Priority Programme 1253 Optimization with Partial Differential Equations, Preprint SPP1253-090, January (2010)
  10.Benner, P., Saak, J.: Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey. GAMM Mitteilungen 36, 32–52 (2013)CrossRef MathSciNet MATH
  11.Bini, D.A., Iannazzo, b., meini, b.: Numerical Solution of Algebraic Riccati Equations , SIAM Philadelphia (2012)
  12.Brandts, J.: The Riccati algorithm for eigenvalues and invariant subspaces of matrices with inexpensive actions. Lin. Alg. Appl. 358, 335–365 (2003)CrossRef MathSciNet MATH
  13.Chu, E.K.W., Fan, H.Y., Lin, W.W.: A structure-preserving doubling algorithm for continuous-time algebraic R iccati equations. Linear Algebra Appl. 396, 55–80 (2005)CrossRef MathSciNet MATH
  14.Chu, E.K.W., Fan, H.Y., Lin, W.W., Wang, C.S.: A structure-preserving doubling algorithm for periodic discrete-time algebraic Riccati equations. Int. J. Control 77, 767–788 (2004)CrossRef MathSciNet MATH
  15.Chu, E.K.W., Li, T., Lin, W.W., Weng, P.C.Y.: A modified Newton’s method for rational Riccati equations arising in stochastic control, 2011 International Conference on Communications, Computing and Control Applications (CCCA’11) Tunisia, 3–5 March (2011)
  16.Chu, E.K.W., Weng, P.C.Y.: Large-scale discrete-time algebraic Riccati equations — doubling algorithm and error analysis. J. Comp. Appl. Maths. 277, 115–126 (2015)CrossRef MathSciNet MATH
  17.Damm, T.: Rational Matrix Equations in Stochastic Control, vol. 297. Springer Verlag, Berlin (2004)
  18.Damm, T.: Direct methods and ADI-preconditioned Krylov subspace methods for generalized Lyapunov equations. Numer. Lin. Alg. Applic. 15, 853–871 (2008)CrossRef MathSciNet MATH
  19.Damm, T., Hinrichsen, D.: Newton’s method for a rational matrix equation occurring in stochastic control. Lin. Algebra Applic. 332-334, 81–109 (2001)CrossRef MathSciNet
  20.Dragan, V., Morozan, T., Stoica, A. M.: Mathematical Methods in Robust Control of Discrete-Time Linear Stochastic Systems. Springer, New York (2010)CrossRef MATH
  21.Fan, H.Y., Weng, P.C.Y., Chu, E.K.W.: Numerical solution to generalized Lyapunov, Stein and rational Riccati equations in stochastic control, Technical Report , NCTS, National Tsing Hua University, Hsinchu, Taiwan. (http://​www.​mat.​cts.​nthu.​edu.​tw/​publish/​publish.​php?​class=​102 ) (2013)
  22.Freiling, G.: A survey of nonsymmetric Riccati equations. Lin. Algebra Applic 351–352, 243–270 (2002)CrossRef MathSciNet
  23.Freiling, G., Hochhaus, A.: Basic properties of a class of rational matrix differential equations, Proc, European Control Conf. Porto (2001)
  24.Freiling, G., Hochhaus, A.: Properties of the solutions of rational matrix difference equations. Comput. Math. Applic. 45, 1137–1154 (2003)CrossRef MathSciNet MATH
  25.Freiling, G., Hochhaus, A.: On a class of rational matrix differential equations arising in stochastic control. Lin. Algebra Applic. 379, 43–68 (2004)CrossRef MathSciNet MATH
  26.Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th. Johns Hopkins University Press. Baltimore, MD (2013)
  27.Guo, C.H.: Iterative solution of a matrix Riccati equation arising in stochastic control. Oper. Theory. Adv. Appl. 130, 209–221 (2001)
  28.Guo, C.H.: Iterative methods inearly perturbed algebraic matrix Riccati equation arising in stochastic control. Numer. Funct. Anal. Optim. 34, 516–529 (2013)CrossRef MathSciNet MATH
  29.Heyouni, M., Jbilou, K.: An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equations. Elect. Trans. Numer. Anal. 33, 53–62 (2009)MathSciNet
  30.Ivanov, I.G.: Iterations for solving a rational Riccati equations arising in stochastic control. Comput. Math. Applic. 53, 977–988 (2007)CrossRef MATH
  31.Ivanov, I.G.: Properties of Stein (Lyapunov) iterations for solving a general Riccati equation. Nonlinear Anal. 67, 1155–1166 (2007)CrossRef MathSciNet MATH
  32.Jaimoukha, I.M., kasenally, E.M.: Krylov subspace methods for solving large Lyapunov equations. SIAM J. Numer. Anal. 31, 227–251 (1994)CrossRef MathSciNet MATH
  33.Jbilou, K.: Block Krylov subspace methods for large continuous-time algebraic Riccati equations. Numer Algorithms 34, 339–353 (2003)CrossRef MathSciNet MATH
  34.Jbilou, K.: An Arnoldi based algorithm for large algebraic Riccati equations. Appl. Math. Lett. 19, 437–444 (2006)CrossRef MathSciNet MATH
  35.Jbilou, K.: Low rank approximate solutions to large Sylvester matrix equations. Appl. Math. Comput. 177, 365–376 (2006)CrossRef MathSciNet MATH
  36.Kressner, D., Sirković, P.: Greedy low-rank methods for solving general linear matrix equations, Technical Report École Polytechnique Fédérale de Lausanne, February (2014). http://​sma.​epfl.​ch/​anchpcommon/​publications/​KS_​GLRM.​pdf
  37.Lancaster, P., Rodman, L.: Algebraic Riccati Equations. Clarendon Press, Oxford (1995)MATH
  38.Li, T., Chu, E.K.W., Lin, W.W., Weng, C.Y.: Solving large-scale continuous-time algebraic Riccati equations by doubling. J. Compur. Appl. Math. 237, 373–383 (2013)CrossRef MathSciNet MATH
  39.Li, T., Weng, P.C.Y., Chu, E.K.W., Lin, W.W.: Large-scale Stein and Lyapunov equations, Smith method, and applications . Numer. Alg. 63, 727–752 (2013)CrossRef MathSciNet MATH
  40.Lin, W.W., Xu, S.F.: Convergence analysis of structure-preserving doubling algorithms for Riccati-type matrix equations. SIAM J. Matrix Anal. Appl. 28, 26–39 (2006)CrossRef MathSciNet MATH
  41.Mathworks, MATLAB User’s Guide (2012)
  42.Mehrmann, V.L.: The Autonomous Linear Quadratic Control Problem, vol. 163. Springer Verlag, Berlin (1991)CrossRef
  43.Saak, J.: Efficient Numerical Solution of Large Scale Algebraic Matrix Equations in PDE Control and Model Order Reduction , Dr. rer. nat. Dissertation, Chemnitz University of Technology, Germany (2009)
  44.Saak, J., Mena, H., Benner, P.: Matrix Equation Sparse Solvers (MESS): A MATLAB Toolbox for the Solution of Sparse Large-Scale Matrix Equations. Chemnitz University of Technology, Germany (2010)
  45.Schneider, H., Positive operators and an inertia theorem. Numer. Math 7, 11–17 (1965)CrossRef MathSciNet MATH
  46.Simoncini, V.: A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29, 1268–1288 (2007)CrossRef MathSciNet MATH
  47.Simoncini, V.: Computational methods for linear matrix equations, Technical Report, January , available from (2014). http://​www.​dm.​unibo.​it/​~simoncin/​public_​matrixeq_​rev.​pdf
  48.Weng, P.C.Y., Fan, H.Y., Chu, E.K.W.: Low-rank approximation to the solution of a nonsymmetric algebraic Riccati equation from transport theory. Appl. Math. Comput. 219, 729–740 (2012)CrossRef MathSciNet MATH
  49.Wonham, W.M.: On a matrix Riccati equation of stochastic control. SIAM J. Control 6, 681–797 (1968)CrossRef MathSciNet MATH
  50.Wonham, W.M.: Erratum: On a matrix Riccati equation of stochastic control. SIAM J. Control 7, 365 (1969)CrossRef MathSciNet
  51.Zhou, B., Lam, J., Duan, G.R.: On Smith-type iterative algorithms for the Stein matrix equation. Appl. Maths. Letts. 22, 1038–1044 (2009)CrossRef MathSciNet MATH
  
• 作者单位：Hung-Yuan Fan (1)
  Peter Chang-Yi Weng (2)
  Eric King-Wah Chu (3)
  
  1. Department of Mathematics, National Taiwan Normal University, Taipei, 116, Taiwan
  2. Institute of Statistical Science, Academia Sinica, Taipei, 115, Taiwan
  3. School of Mathematical Sciences, Monash University, Building 28, Monash, 3800, VIC, Australia
  
• 刊物类别：Computer Science
• 刊物主题：Numeric Computing
  Algorithms
  Mathematics
  Algebra
  Theory of Computation
  
• 出版者：Springer U.S.
• ISSN：1572-9265

文摘

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n 3) computational complexity per iteration and an O(n 2) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n 6) complexity or the slower modified Newton’s methods of O(n 3) complexity. The convergence and error analysis will be considered and numerical examples provided. Keywords Algebraic Riccati equation Bilinear model order reduction Generalized Lyapunov equation Generalized Stein equation Large-scale problem Newton’s method Rational Riccati equation Smith method Stochastic Algebraic Riccati equation Stochastic optimal control