Reduced basis approximation of large scale parametric algebraic Riccati equations

Schmidt, Andreas; Haasdonk, Bernard

ESAIM: Control, Optimisation and Calculus of Variations, Tome 24 (2018) no. 1, pp. 129-151.

The algebraic Riccati equation (ARE) is a matrix valued quadratic equation with many important applications in the field of control theory, such as feedback control, state estimation or ${\mathscr{H}}_{\infty }$-robust control. However, solving the ARE can get very expensive in applications that arise from semi-discretized partial differential equations. A further level of computational complexity is introduced by parameter dependent systems and the wish to obtain solutions rapidly for varying parameters. We thus propose the application of the reduced basis (RB) methodology to the parametric ARE by exploiting the well known low-rank structure of the solution matrices. We discuss a basis generation procedure and analyze the induced error by deriving a rigorous a posteriori error bound. We study the computational complexity of the whole procedure and give numerical examples that prove the efficiency of the approach in the context of linear quadratic (LQ) control.

Classification : 49N05, 34K35, 93B52, 65G99
Mots clés : Reduced basis method, optimal feedback control, algebraic riccati equation, low rank approximation

H. Abou-Kandil, G. Freiling, V. Ionescu and G. Jank, Matrix Riccati Equations in Control and Systems Theory. Springer Science + Business Media (2003). | MR | Zbl

A.C. Antoulas, Approximation of Large-Scale Dynamical Systems. SIAM Publications, Philadelphia, PA (2005). | MR | Zbl

A.C. Antoulas, D.C. Sorensen and Y. Zhou, On the decay rate of Hankel singular values and related issues. Systems & Control Letters 46 (2002) 323–342. | DOI | MR | Zbl

E. Bänsch, P. Benner, J. Saak and H.K. Weichelt, Riccati-based boundary feedback stabilization of incompressible Navier-Stokes flows. SIAM J. Sci. Comput. 37 (2015) A832–A858. | DOI | MR | Zbl

M. Barrault, Y. Maday, N.C. Nguyen and A.T. Patera, An “empirical interpolation” method: application to efficient reduced-basis discretization of partial differential equations. C. R. Acad. Sci., Series I 339 (2004) 667–672. | MR | Zbl

P. Benner and J. Saak, A semi-discretized heat transfer model for optimal cooling of steel profiles. In Dimension Reduction of Large-Scale Systems. Springer-Verlag (2005) 353–356. | Zbl

P. Benner and J. Saak, Numerical solution of large and sparse continuous time algebraic matrix Riccati and Lyapunov equations: a state of the art survey. GAMM-Mitteilungen 36 (2013) 32–52. | DOI | MR | Zbl

P. Benner and Z. Bujanovi, On the solution of large-scale algebraic Riccati equations by using low-dimensional invariant subspaces. Linear Algebra Appl. 488 (2016) 430–459. | DOI | MR | Zbl

J. Borggaard, M. Stoyanov and L. Zietsman, Linear feedback control of a von Kármán street by cylinder rotation. In Proc. of the 2010 American Control Conference. IEEE (2010) 5674–5681.

G. Caloz and J. Rappaz, Numerical analysis for nonlinear and bifurcation problems. In Techniques of Scientific Computing (Part 2), Vol. 5 of Handbook of Numerical Analysis. Elsevier (1997) 487–637. | MR

G. Dahlquist, Convergence and stability in the numerical integration of ordinary differential equations. Math. Scand. 4 (1956) 33–53. | DOI | MR | Zbl

M. Drohmann, B. Haasdonk and M. Ohlberger, Reduced basis approximation for nonlinear parametrized evolution equations based on empirical operator interpolation. SIAM J. Sci. Comput. 34 (2012) A937–A969. | DOI | MR | Zbl

A.R. Ghavimi and A.J. Laub, Backward error, sensitivity, and refinement of computed solutions of algebraic Riccati equations. Numer. Lin. Algebra Appl. 2 (1995) 29–49. | DOI | MR | Zbl

M.A. Grepl and A.T. Patera, A posteriori error bounds for reduced-basis approximations of parametrized parabolic partial differential equations. ESAIM: M2AN 39 (2005) 157–181. | DOI | Numdam | MR | Zbl

C. Großmann and H.G. Roos, Numerische Behandlung partieller Differentialgleichungen. Vieweg+Teubner Verlag (2005).

B. Haasdonk, Convergence rates of the POD–Greedy method. ESAIM: M2AN 47 (2013) 859–873. | DOI | Numdam | MR | Zbl

B. Haasdonk, Reduced basis methods for parametrized PDEs – a tutorial introduction for stationary and instationary problems. SimTech preprint, IANS, University of Stuttgart, Germany, 2014. Chapter in: Model Reduction and Approximation: Theory and Algorithms, edited by P. Benner, A. Cohen, M. Ohlberger and K. Willcox. SIAM, Philadelphia (2017). | MR

B. Haasdonk, M. Dihlmann and M. Ohlberger, A training set and multiple basis generation approach for parametrized model reduction based on adaptive grids in parameter space. Math. Comp. Model. Dyn. Systems 17 (2011) 423–442. | DOI | MR | Zbl

B. Haasdonk and M. Ohlberger, Reduced basis method for finite volume approximations of parametrized linear evolution equations. ESAIM: M2AN 42 (2008) 277–302. | DOI | Numdam | MR | Zbl

B. Haasdonk and M. Ohlberger, Efficient reduced models and a posteriori error estimation for parametrized dynamical systems by offline/online decomposition. Math. Comp. Model Dyn. 17 (2011) 145–161. | DOI | MR | Zbl

B. Haasdonk, M. Ohlberger and G. Rozza. A reduced basis method for evolution schemes with parameter-dependent explicit operators. ETNA, Electron. Trans. Numer. Anal. 32 (2008) 145–161. | MR | Zbl

E. Heinz, Beiträge zur Störungstheorie der Spektralzerleung. Math. Ann. 123 (1951) 415–438. | DOI | MR | Zbl

G. Hewer and C. Kenney, The sensitivity of the stable Lyapunov equation. SIAM J. Control Optimiz. 26 (1988) 321–344. | DOI | MR | Zbl

M. Heyouni and K. Jbilou, An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation. Electron. Trans. Numer. Anal. 33 (2009) 53–62. | MR | Zbl

D. Hinrichsen and A.J. Pritchard, Mathematical Systems Theory I: Modelling, State Space Analysis, Stability and Robustness. Springer (2005). | MR | Zbl

K. Hiramoto, H. Doki and G. Obinata, Optimal sensor/actuator placement for active vibration control using explicit solution of algebraic Riccati equations. J. Sound Vibration 229 (2000) 1057–1075. | DOI | MR | Zbl

D.B.P. Huynh, D.J. Knezevic, Y. Chen, J.S. Hesthaven and A.T. Patera, A natural-norm successive constraint method for inf-sup lower bounds. Comput. Methods Appl. Mech. Eng. 199 (2010) 1963–1975. | DOI | MR | Zbl

I.M. Jaimoukha and E.M. Kasenally, Krylov subspace methods for solving large Lyapunov equations. SIAM J. Numer. Anal. 31 (1994) 227–251. | DOI | MR | Zbl

K. Jbilou, Block Krylov subspace methods for large algebraic Riccati equations. Numer. Algorithms 34 (2003) 339–353. | DOI | MR | Zbl

K. Jbilou, An Arnoldi based algorithm for large algebraic Riccati equations. Appl. Math. Lett. 19 (2006) 437–444. | DOI | MR | Zbl

C. Johnson, Numerical solution of partial differential equations by the finite element method. Courier Corporation (1989). | MR | Zbl

R.E. Kalman and R.S. Bucy, New results in linear filtering and prediction theory. J. Basic Eng. 83 (1961) 95. | DOI | MR

R.E. Kalman, Contributions to the theory of optimal control. Bol. Soc. Mat. Mexicana 5 (1960) 102–119. | MR | Zbl

M. Kärcher and M.A. Grepl, A certified reduced basis method for parametrized elliptic optimal control problems. ESAIM: COCV 20 (2014) 416–441. | Numdam | MR | Zbl

C. Kenney and G. Hewer, The sensitivity of the algebraic and differential Riccati equations. SIAM J. Control Optimiz. 28 (1990) 50–69. | DOI | MR | Zbl

C. Kenney, A.J. Laub and M. Wette, Error bounds for Newton refinement of solutions to algebraic Riccati equations. Math. Control, Signals Systems 3 (1990) 211–224. | DOI | MR | Zbl

H. Kwakernaak and R. Sivan, Linear optimal control systems, Vol. 1. Wiley-interscience New York (1972). | MR | Zbl

P. Lancaster, Explicit solutions of linear matrix equations. SIAM Rev. 12 (1970) 544–566. | DOI | MR | Zbl

P. Lancaster and L. Rodman, Algebr. Riccati Equ. Oxford University Press (1995). | MR

J.-R. Li and J. White, Low rank solution of Lyapunov equations. SIAM J. Matrix Anal. Appl. 46 (2004) 693–713. | MR | Zbl

A. Manzoni and F. Negri, Heuristic strategies for the approximation of stability factors in quadratically nonlinear parametrized PDEs. Special Issue on Model Reduction of Parametrized Systems. Advances in Computational Mathematics (2015). | MR

D. Mustafa and K. Glover, Controller reduction by $H_{\infty }$ balanced truncation. IEEE Trans. Autom. Control 36 (1991) 668–682. | DOI | MR

F. Negri, G. Rozza, A. Manzoni and A. Quarteroni, Reduced basis method for parametrized elliptic optimal control problems. SIAM J. Scientific Comput. 35 (2013) A2316–A2340. | DOI | MR | Zbl

H. Panzer, T. Wolf and B. Lohmann, A strictly dissipative state space representation of second order systems. at – Automatisierungstechnik 60 (2012) 392–397. | DOI

A.T. Patera and G. Rozza, Reduced Basis Approximation and a Posteriori Error Estimation for Parametrized Partial Differential Equations. To appear in (tentative) MIT Pappalardo Graduate Monographs in Mechanical Engineering. MIT (2007).

T. Penzl, Numerical solution of generalized Lyapunov equations. Adv. Comput. Math. 8 (1998) 33–48. | DOI | MR | Zbl

T. Penzl, Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case. Syst. Control Lett. 40 (2000) 139–144. | DOI | MR | Zbl

G. Rozza, D.B.P. Huynh and A.T. Patera, Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations: application to transport and continuum mechanics. Arch. Comput. Meth. Eng. 15 (2008) 229–275. | DOI | MR | Zbl

Y. Saad and X.V. Gv, Numerical solution of large Lyapunov equations. In Proc. of MTNS-89 Signal Processing, Scattering and Operator Theory, and Numerical Methods. Birkhauser (1990) 503–511. | MR | Zbl

J. Saak, Efficient numerical solution of large scale algebraic matrix equations in PDE control and model order reduction. Ph.D. thesis, Chemnitz University of Technology (2009).

A. Schmidt, M. Dihlmann and B. Haasdonk, Basis generation approaches for a reduced basis linear quadratic regulator. In Proc. MATHMOD 2015 – 8th Vienna International Conference on Mathematical Modelling (2015) 713–718.

A. Schmidt and B. Haasdonk, Reduced basis method for H2 optimal feedback control problems. IFAC-PapersOnLine 49 (2016) 327–332, 2nd IFAC Workshop on Control of Systems Governed by Partial Differential Equations CPDE (2016). | DOI | MR

V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput. 29 (2007) 1268–1288. | DOI | MR | Zbl

V. Simoncini, Analysis of the rational krylov subspace projection method for large-scale algebraic Riccati equations. SIAM J. Matrix Anal. Appl. 37 (2016) 1655–1674. | DOI | MR | Zbl

G. Söderlind, The logarithmic norm. history and modern theory. BIT Numer. Math. 46 (2006) 631–652. | DOI | MR | Zbl

N.T. Son and T. Stykel, Solving parameter-dependent Lyapunov equations using reduced basis method with application to parametric model order reduction. Technical report, University of Augsburg (2015). | MR

T. Stykel, Analysis and numerical solution of generalized Lyapunov equations. Ph.D. thesis, Institut für Mathematik, Technische Universität, Berlin (2002). | Zbl

T. Stykel, Numerical solution and perturbation theory for generalized Lyapunov equations. Lin. Algebr. Appl. 349 (2002) 155–185. | DOI | MR | Zbl

J.-G. Sun, Residual bounds of approximate solutions of the algebraic Riccati equation. Numer. Math. 76 (1997) 249–263. | DOI | MR | Zbl

N. Truhar and K. Veselić, Bounds on the trace of a solution to the Lyapunov equation with a general stable matrix. Syst. Control Lett. 56 (2007) 493–503. | DOI | MR | Zbl

K. Veroy, C. Prud’homme, D.V. Rovas and A.T. Patera, A posteriori error bounds for reduced-basis approximation of parametrized noncoercive and nonlinear elliptic partial differential equations. In 16th AIAA Computational Fluid Dynamics Conference. American Institute of Aeronautics and Astronautics (2003) 2003–3847.

S. Volkwein, Model reduction using proper orthogonal decomposition. Lecture notes, University of Konstanz (2011).

H. Wendland, Scattered Data Approximation. Cambridge University Press (2004). Cambridge Books Online. | MR | Zbl

D. Wirtz, D.C. Sorensen and B. Haasdonk, A posteriori error estimation for DEIM reduced nonlinear dynamical systems. SIAM J. Scientific Comput.36 (2014) A311–A338. | MR | Zbl

Daniel Wirtz, Model Reduction for Nonlinear Systems: Kernel Methods and Error Estimation. epubli GmbH (2014).

K. Zhou, J.C. Doyle and K. Glover, Robust and Optimal Control. Prentice Hall (1996). | Zbl