Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems. (English) Zbl 1212.65245
Summary: We study large-scale, continuous-time linear time-invariant control systems with a sparse or structured state matrix and a relatively small number of inputs and outputs. The main contributions of this paper are numerical algorithms for the solution of large algebraic Lyapunov and Riccati equations and linear-quadratic optimal control problems, which arise from such systems. First, we review an alternating direction implicit iteration-based method to compute approximate low-rank Cholesky factors of the solution matrix of large-scale Lyapunov equations, and we propose a refined version of this algorithm. Second, a combination of this method with a variant of Newton’s method (in this context also called Kleinman iteration) results in an algorithm for the solution of large-scale Riccati equations. Third, we describe an implicit version of this algorithm for the solution of linear-quadratic optimal control problems, which computes the feedback directly without solving the underlying algebraic Riccati equation explicitly. Our algorithms are efficient with respect to both memory and computation. In particular, they can be applied to problems of very large scale, where square, dense matrices of the system order cannot be stored in the computer memory. We study the performance of our algorithms in numerical experiments.
MSC:
| 65K10 | Numerical optimization and variational techniques |
| 65F30 | Other matrix algorithms (MSC2010) |
| 15A24 | Matrix equations and identities |
| 93C05 | Linear systems in control theory |
| 65F50 | Computational methods for sparse matrices |
| 65H10 | Numerical computation of solutions to systems of equations |
| 49N10 | Linear-quadratic optimal control problems |
| 49N35 | Optimal feedback synthesis |
| 93B52 | Feedback control |
Keywords:
Lyapunov equation; algebraic Riccati equation; linear-quadratic optimal control; Newton’s method; low-rank approximation; control system; sparse matrix; large-scale, continuous-time linear time-invariant control systems; algorithms; alternating direction implicit iteration method; Cholesky factors; Kleinman iteration; feedback; numerical experimentsReferences:
| [1] | Penzl T. Lyapack users guide. Technical Report SFB393/00-33, Sonderforschungsbereich 393Numerische Simulation auf massiv parallelen Rechnern, TU Chemnitz, FRG 2000. Available from: http://www.tu-chemnitz.de/sfb393/sfb00pr.html. |
| [2] | Abou-Kandil, Matrix Riccati Equations in Control and Systems Theory (2003) · Zbl 1027.93001 · doi:10.1007/978-3-0348-8081-7 |
| [3] | Datta, Numerical Methods for Linear Control Systems (2004) |
| [4] | Mehrmann, The Autonomous Linear Quadratic Control Problem, Theory and Numerical Solution (1991) · Zbl 0746.93001 · doi:10.1007/BFb0039443 |
| [5] | Petkov, Computational Methods for Linear Control Systems (1991) |
| [6] | Sima, Algorithms for Linear-Quadratic Optimization, Pure and Applied Mathematics 200 (1996) · Zbl 0863.65038 |
| [7] | Banks, The linear regulator problem for parabolic systems, SIAM Journal on Control and Optimization 22 pp 684– (1984) · Zbl 0548.49017 |
| [8] | Ito, Finite-dimensional compensators for infinite-dimensional systems via Galerkin-type approximation, SIAM Journal on Control and Optimization 28 pp 1251– (1990) · Zbl 0733.93031 |
| [9] | Lasiecka, Differential and Algebraic Riccati Equations with Application to Boundary/Point Control Problems: Continuous Theory and Approximation Theory (1991) · Zbl 0754.93038 · doi:10.1007/BFb0006880 |
| [10] | Morris, Design of finite-dimensional controllers for infinite-dimensional systems by approximation, Journal of Mathematical Systems, Estimation, and Control 4 pp 1– (1994) · Zbl 0813.93032 |
| [11] | Freund, Applied and Computational Control, Signals, and Circuits 1 pp 435– (1999) · doi:10.1007/978-1-4612-0571-5_9 |
| [12] | Freund, Krylov-subspace methods for reduced-order modeling in circuit simulation, Journal of Computational and Applied Mathematics 123 (1-2) pp 395– (2000) · Zbl 0964.65082 |
| [13] | Gawronski, Balanced Control of Flexible Structures (1996) · Zbl 0839.93004 · doi:10.1007/3-540-76017-2 |
| [14] | Papadopoulos P, Laub A, Ianculescu G, Ly J, Kenney C, Pandey P. Optimal control study for the space station solar dynamic power module. Proceedings of the Conference on Decision and Control CDC-1991, Brighton, 1991; 2224-2229. |
| [15] | Anderson, Optimal Control-Linear Quadratic Methods (1990) |
| [16] | Lancaster, The Algebraic Riccati Equation (1995) · Zbl 0836.15005 |
| [17] | Banks, A numerical algorithm for optimal feedback gains in high dimensional linear quadratic regulator problems, SIAM Journal on Control and Optimization 29 (3) pp 499– (1991) · Zbl 0736.65043 |
| [18] | Kalman, Contributions to the theory of optimal control, Boletin Sociedad Matematica Mexicana 5 pp 102– (1960) · Zbl 0112.06303 |
| [19] | Pinch, Optimal Control and the Calculus of Variations (1993) |
| [20] | Durrazi, Numerical solution of discrete quadratic optimal control problems by Hestenes’ method, Supplemento ai Rendiconti del Circolo Matematico di Palermo, Series II 58 pp 133– (1999) |
| [21] | Saberi, H2 Optimal Control (1995) |
| [22] | Green, Balanced stochastic realization, Linear Algebra and its Applications 98 pp 211– (1988) · Zbl 0642.93054 |
| [23] | Varga, On computing high accuracy solutions of a class of Riccati equations, Control-Theory and Advanced Technology 10 (4) pp 2005– (1995) |
| [24] | Doyle, State-space solutions to standard H2 and H control problems, IEEE Transactions on Automatic Control 34 pp 831– (1989) |
| [25] | Green, Linear Robust Control (1995) |
| [26] | Zhou, Robust and Optimal Control (1996) |
| [27] | Laub, A Schur method for solving algebraic Riccati equations, IEEE Transactions on Automatic Control AC-24 pp 913– (1979) · Zbl 0424.65013 |
| [28] | Byers, Solving the algebraic Riccati equation with the matrix sign function, Linear Algebra and its Applications 85 pp 267– (1987) · Zbl 0611.65027 |
| [29] | Gardiner, A generalization of the matrix-sign-function solution for algebraic Riccati equations, International Journal of Control 44 pp 823– (1986) · Zbl 0598.15012 |
| [30] | Roberts, Linear model reduction and solution of the algebraic Riccati equation by use of the sign function, International Journal of Control 32 pp 677– (1980) · Zbl 0463.93050 |
| [31] | Ammar, A multishift algorithm for the numerical solution of algebraic Riccati equations, Electronic Transactions on Numerical Analysis 1 pp 33– (1993) · Zbl 0809.65040 |
| [32] | Bunse-Gerstner, A symplectic QR-like algorithm for the solution of the real algebraic Riccati equation, IEEE Transactions on Automatic Control AC-31 pp 1104– (1986) · Zbl 0616.65048 |
| [33] | Byers, A Hamiltonian QR-algorithm, SIAM Journal on Scientific and Statistical Computing 7 pp 212– (1986) |
| [34] | Benner, Computational methods for linear-quadratic optimization, Supplemento ai Rendiconti del Circolo Matematico di Palermo, Series II 58 pp 21– (1999) · Zbl 0930.65075 |
| [35] | Benner, An implicitly restarted symplectic Lanczos method for the Hamiltonian eigenvalue problem, Linear Algebra and its Applications 263 pp 75– (1997) · Zbl 0884.65028 |
| [36] | Ferng, The shift-inverted J-Lanczos algorithm for the numerical solutions of large sparse algebraic Riccati equations, Computers and Mathematics with Applications 33 (10) pp 23– (1997) · Zbl 0889.65034 |
| [37] | Hodel A, Poolla K. Heuristic approaches to the solution of very large sparse Lyapunov and algebraic Riccati equations. Proceedings of the 27th IEEE Conference on Decision and Control, Austin, TX, 1988; 2217-2222. |
| [38] | Jaimoukha, Krylov subspace methods for solving large Lyapunov equations, SIAM Journal on Numerical Analysis 31 pp 227– (1994) · Zbl 0798.65060 |
| [39] | Benner, An exact line search method for solving generalized continuous-time algebraic Riccati equations, IEEE Transactions on Automatic Control 43 (1) pp 101– (1998) · Zbl 0908.93026 |
| [40] | Blackburn, Solution of the algebraic matrix Riccati equation via Newton-Raphson iteration, AIAA Journal 6 pp 951– (1968) · Zbl 0164.45202 |
| [41] | Kleinman, On an iterative technique for Riccati equation computations, IEEE Transactions on Automatic Control AC-13 pp 114– (1968) |
| [42] | Pandey P. Quasi-Newton methods for solving algebraic Riccati equations. Proceedings of the American Control Conference, Chicago, IL, 1992; 654-658. |
| [43] | Rosen, A multi-level technique for the approximate solution of operator Lyapunov and algebraic Riccati equations, SIAM Journal on Numerical Analysis 32 (2) pp 514– (1995) · Zbl 0857.65047 |
| [44] | Zečević, Solution of Lyapunov and Riccati equations in a multiprocessor environment, Nonlinear Analysis, Theory, Methods and Applications 30 (5) pp 2815– (1997) · Zbl 0891.65045 |
| [45] | Hammarling S. Newton’s method for solving the algebraic Riccati equation. NPL Report DITC 12/82, National Physical Laboratory, Teddington, Middlesex, U.K., 1982. · Zbl 0492.65017 |
| [46] | Hammarling, Numerical solution of the stable, non-negative definite Lyapunov equation, IMA Journal on Numerical Analysis 2 pp 303– (1982) · Zbl 0492.65017 |
| [47] | Gajić, Lyapunov Matrix Equation in System Stability and Control (1995) |
| [48] | Mullis, Synthesis of minimum roundoff noise fixed point digital filters, IEEE Transactions on Circuits and Systems CAS-23 (9) pp 551– (1976) · Zbl 0342.93066 |
| [49] | Moore, Principal component analysis in linear systems: controllability, observability, and model reduction, IEEE Transactions on Automatic Control AC-26 pp 17– (1981) · Zbl 0464.93022 |
| [50] | Glover, All optimal Hankel-norm approximations of linear multivariable systems and their L norms, International Journal on Control 39 pp 1115– (1984) · Zbl 0543.93036 |
| [51] | Lancaster, Explicit solutions of linear matrix equation, SIAM Review 12 pp 544– (1970) · Zbl 0209.06502 |
| [52] | Lancaster, The Theory of Matrices (1985) · Zbl 0578.62099 |
| [53] | Bartels, Solution of the matrix equation AX+ XB=C : Algorithm 432, Communications of the ACM 15 pp 820– (1972) · Zbl 1372.65121 |
| [54] | Smith, Matrix equation XA+ BX=C, SIAM Journal on Applied Mathematics 16 (1) pp 198– (1968) |
| [55] | Baur, Factorized solution of Lyapunov equations based on hierarchical matrix arithmetic, Computing 78 (3) pp 211– (2006) · Zbl 1111.65039 |
| [56] | Grasedyck, Solution of large scale algebraic matrix Riccati equations by use of hierarchical matrices, Computing 70 pp 121– (2003) · Zbl 1239.65026 |
| [57] | Benner, Solving stable generalized Lyapunov equations with the matrix sign function, Numerical Algorithms 20 (1) pp 75– (1999) · Zbl 0940.65035 |
| [58] | Gardiner, Parallel algorithms for algebraic Riccati equations, International Journal on Control 54 (6) pp 1317– (1991) · Zbl 0763.93036 |
| [59] | Peaceman, The numerical solution of elliptic and parabolic differential equations, Journal of the Society for Industrial and Applied Mathematics 3 pp 28– (1955) · Zbl 0067.35801 |
| [60] | Wachspress, Iterative solution of the Lyapunov matrix equation, Applied Mathematics Letters 107 pp 87– (1988) · Zbl 0631.65037 |
| [61] | Antoulas, On the decay rate of Hankel singular values and related issues, Systems and Control Letters 46 (5) pp 323– (2002) · Zbl 1003.93024 |
| [62] | Grasedyck, Existence of a low rank or H-matrix approximant to the solution of a Sylvester equation, Numerical Linear Algebra with Applications 11 pp 371– (2004) · Zbl 1164.65381 |
| [63] | Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case, Systems and Control Letters 40 pp 139– (2000) · Zbl 0977.93034 |
| [64] | Hodel, Numerical solution of the Lyapunov equation by approximate power iteration, Linear Algebra and its Applications 236 pp 205– (1996) · Zbl 0848.65033 |
| [65] | Hu, Krylov-subspace methods for the Sylvester equation, Linear Algebra and its Applications 172 pp 283– (1992) · Zbl 0777.65028 |
| [66] | Saad, Signal Processing, Scattering, Operator Theory and Numerical Methods pp 503– (1990) |
| [67] | Golub, Matrix Computations (1996) |
| [68] | Gudmundsson, Approximate solution of large sparse Lyapunov equations, IEEE Transactions on Automatic Control 39 pp 1110– (1994) · Zbl 0816.93041 |
| [69] | Ellner, Alternating direction implicit iteration for systems with complex spectra, SIAM Journal on Numerical Analysis 28 (3) pp 859– (1991) · Zbl 0737.65027 |
| [70] | Starke G. Rationale Minimierungsprobleme in der komplexen Ebene im Zusammenhang mit der Bestimmmung optimaler ADI-Parameter. Dissertation, Fakultät für Mathematik, Universität Karlsruhe, Germany, 1993 (in German). |
| [71] | Wachspress E. The ADI model problem 1995. Available from the author. · Zbl 1277.65022 |
| [72] | Li JR, Wang F, White J. An efficient Lyapunov equation-based approach for generating reduced-order models of interconnect. Proceedings of the 36th IEEE/ACM Design Automation Conference, New Orleans, LA, 1999. |
| [73] | Penzl, A cyclic low rank Smith method for large sparse Lyapunov equations, SIAM Journal on Scientific Computing 21 (4) pp 1401– (2000) · Zbl 0958.65052 |
| [74] | Li, Low rank solution of Lyapunov equations, SIAM Journal on Matrix Analysis and Applications 24 (1) pp 260– (2002) · Zbl 1016.65024 |
| [75] | Davis, Circulant Matrices (1979) |
| [76] | Duff, Direct Methods for Sparse Matrices (1989) |
| [77] | Cuthill, Sparse Matrices and their Applications (1972) |
| [78] | Saak J. Effiziente numerische Lösung eines Optimalsteuerungsproblems für die Abkühlung von Stahlprofilen. Diplomarbeit, Fachbereich 3/Mathematik und Informatik, Universität Bremen, Bremen, September 2003. |
| [79] | Hackbusch, Multigrid Methods and Applications (1985) · doi:10.1007/978-3-662-02427-0 |
| [80] | Stüben, Multigrid (1999) |
| [81] | Calvetti, Application of ADI iterative methods to the restoration of noisy images, SIAM Journal on Matrix Analysis and Applications 17 pp 165– (1996) · Zbl 0849.65101 |
| [82] | Penzl, Algorithms for model reduction of large dynamical systems, Linear Algebra with Applications 415 (2-3) pp 322– (2006) · Zbl 1092.65053 |
| [83] | Hochbruck, Preconditioned Krylov subspace methods for Lyapunov matrix equations, SIAM Journal on Matrix Analysis and Applications 16 (1) pp 156– (1995) · Zbl 0827.65048 |
| [84] | Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM Journal on Scientific Computing 29 pp 1268– (2007) · Zbl 1146.65038 |
| [85] | Tröltzsch, Fast solution of optimal control problems in the selective cooling of steel, Zeitschrift fur Angewandte Mathematik und Mechanik 81 pp 447– (2001) · Zbl 0993.49024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
