A POD projection method for large-scale algebraic Riccati equations

Boris  Kramer; John  R.  Singler

doi:10.3934/naco.2016018

Article Contents

2016, Volume 6, Issue 4: 413-435. Doi: 10.3934/naco.2016018

This issue Previous Article Next Article Closed-form expression for the inverse of a class of tridiagonal matrices

A POD projection method for large-scale algebraic Riccati equations

Boris Kramer^1, and
John R. Singler^2,

1.
Department of Aeronautics and Astronautics, Massachusetts Institute of Technology,Cambridge, MA 02139
2.
Department of Mathematics and Statistics, Missouri University of Science and Technology, Rolla, MO 65409-0020

Received: February 2016

Revised: September 2016

Published: November 2016

Abstract Related Papers Cited by

Abstract

The solution of large-scale matrix algebraic Riccati equations is important for instance in control design and model reduction and remains an active area of research. We consider a class of matrix algebraic Riccati equations (AREs) arising from a linear system along with a weighted inner product. This problem class often arises from a spatial discretization of a partial differential equation system. We propose a projection method to obtain low rank solutions of AREs based on simulations of linear systems coupled with proper orthogonal decomposition. The method can take advantage of existing (black box) simulation code to generate the projection matrices. We also develop new weighted norm residual computations and error bounds. We present numerical results demonstrating that the proposed approach can produce highly accurate approximate solutions. We also briefly discuss making the proposed approach completely data-based so that one can use existing simulation codes without accessing system matrices.

Keywords:

Mathematics Subject Classification: Primary: 49; Secondary: 65.

Citation:

Related Papers

Cited by

References

[1]	I. Akhtar, J. Borggaard, M. Stoyanov and L. Zietsman, On commutation of reduction and control: linear feedback control of a von Kármán street, in 5th AIAA Flow Control Conference, (2010), 1-14.
[2]	L. Amodei and J.-M. Buchot, A stabilization algorithm of the Navier-Stokes equations based on algebraic Bernoulli equation, Numerical Linear Algebra with Applications, 19 (2012), 700-727.doi: 10.1002/nla.799.
[3]	A. C. Antoulas, Approximation of Large-Scale Dynamical Systems, Advances in Design and Control, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2005.doi: 10.1137/1.9780898718713.
[4]	W. F. Arnold and A. J. Laub, Generalized eigenproblem algorithms and software for algebraic Riccati equations, Proceedings of the IEEE, 72 (1984), 1746-1754.
[5]	J. A. Atwell, J. Borggaard and B. King, Reduced order controllers for Burgers' equation with a nonlinear observer, International Journal of Applied Mathematics and Computer Science, 11 (2001), 1311-1330.
[6]	J. A. Atwell and B. B. King, Proper orthogonal decomposition for reduced basis feedback controllers for parabolic equations, Math. Comput. Modelling, 33 (2001), 1-19.doi: 10.1016/S0895-7177(00)00225-9.
[7]	J. Baker, M. Embree and J. Sabino, Fast singular value decay for Lyapunov solutions with nonnormal coefficients, SIAM J. Matrix Anal. Appl., 36 (2015), 656-668.doi: 10.1137/140993867.
[8]	H. T. Banks, S. C. Beeler, G. M. Kepler and H. T. Tran, Reduced order modeling and control of thin film growth in an HPCVD reactor, SIAM J. Appl. Math., 62 (2002), 1251-1280.doi: 10.1137/S0036139901383280.
[9]	H. T. Banks, R. C. H. del Rosario and R. C. Smith, Reduced-order model feedback control design: numerical implementation in a thin shell model, IEEE Trans. Automat. Control, 45 (2000), 1312-1324.doi: 10.1109/9.867024.
[10]	H. T. Banks and K. Ito, A numerical algorithm for optimal feedback gains in high-dimensional linear quadratic regulator problems, SIAM J. Control Optim., 29 (1991), 499-515.doi: 10.1137/0329029.
[11]	C. A. Beattie, J. Borggaard, S. Gugercin and T. Iliescu, A domain decomposition approach to POD, in Proceedings of the 45th IEEE Conference on Decision and Control, 2006.
[12]	P. Benner, Balancing-related model reduction for parabolic control systems, in 1st IFAC Workshop on Control of Systems Governed by Partial Differential Equations, (2014), 257-262.
[13]	P. Benner, J.-R. Li and T. Penzl, Numerical solution of large-scale Lyapunov equations, Riccati equations, and linear-quadratic optimal control problems, Numer. Linear Algebra Appl., 15 (2008), 755-777.doi: 10.1002/nla.622.
[14]	P. Benner and J. Saak, A Galerkin-Newton-ADI method for solving large-scale algebraic Riccati equations, Preprint SPP1253-090, DFG Priority Programme 1253 Optimization with Partial Differential Equations, 2010, http://www.am.uni-erlangen.de/home/spp1253/wiki/images/2/28/Preprint-SPP1253-090.pdf.
[15]	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: 10.1002/gamm.201310003.
[16]	P. Benner and Z. Bujanović, On the solution of large-scale algebraic Riccati equations by using low-dimensional invariant subspaces, Linear Algebra and its Applications, 488 (2016), 430-459.doi: 10.1016/j.laa.2015.09.027.
[17]	P. Benner, J. Saak and M. M. Uddin, Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control, Numer. Algebra Control Optim., 6 (2016), 1-20.doi: 10.3934/naco.2016.6.1.
[18]	D. Bini, B. Iannazzo and B. Meini, Numerical Solution of Algebraic Riccati Equations, Fundamentals of algorithms, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, USA, 2012.
[19]	J. Borggaard and M. Stoyanov, An efficient long-time integrator for Chandrasekhar equations, in Proceedings of the 47th IEEE Conference on Decision and Control, (2008), 3983-3988.
[20]	J. A. Burns and K. P. Hulsing, Numerical methods for approximating functional gains in LQR boundary control problems, Math. Comput. Modelling, 33 (2001), 89-100. Computation and Control, VI (Bozeman, MT, 1998).doi: 10.1016/S0895-7177(00)00231-4.
[21]	J. A. Burns, E. W. Sachs and L. Zietsman, Mesh independence of Kleinman-Newton iterations for Riccati equations in Hilbert space, SIAM J. Control Optim., 47 (2008), 2663-2692.doi: 10.1137/060653962.
[22]	J. Burns, K. Ito and R. Powers, Chandrasekhar equations and computational algorithms for distributed parameter systems, in Proceedings of the 23rd IEEE Conference on Decision and Control., 23 (1984), 262-267.
[23]	J. A. Burns, Introduction to theCalculus of Variations and Control-With Modern Applications, CRC Press, Boca Raton, FL, 2014.
[24]	D. H. Chambers, R. J. Adrian, P. Moin, D. S. Stewart and H. J. Sung, Karhunen-Love expansion of Burgers model of turbulence, Phys. Fluids, 31 (1988), 2573-2582.
[25]	S. Chaturantabut and D. C. Sorensen, Discrete empirical interpolation for nonlinear model reduction, in Proceedings of the 48th IEEE Conference on Decision and Control, IEEE, (2009), 4316-4321.
[26]	K. K. Chen and C. W. Rowley, Fluid flow control applications of H₂ optimal actuator and sensor placement, in Proceedings of the American Control Conference, (2014), 4044-4049.
[27]	K. Chen and C. W. Rowley, H₂ optimal actuator and sensor placement in the linearised complex Ginzburg-Landau system, J. Fluid Mech., 681 (2011), 241-260.doi: 10.1017/jfm.2011.195.
[28]	N. Darivandi, K. Morris and A. Khajepour, An algorithm for LQ optimal actuator location, Smart Materials and Structures, 22 (2013), 035001.
[29]	B. T. Dickinson and J. R. Singler, Nonlinear model reduction using group proper orthogonal decomposition, Int. J. Numer. Anal. Model., 7 (2010), 356-372.
[30]	V. Druskin and L. Knizhnerman, Extended Krylov subspaces: approximation of the matrix square root and related functions, SIAM Journal on Matrix Analysis and Applications, 19 (1998), 755-771.doi: 10.1137/S0895479895292400.
[31]	M. Fahl, Computation of POD basis functions for fluid flows with Lanczos methods, Math. Comput. Modelling, 34 (2001), 91-107.doi: 10.1016/S0895-7177(01)00051-6.
[32]	J. S. Gibson and A. Adamian, Approximation theory for linear-quadratic-Gaussian optimal control of flexible structures, SIAM J. Control Optim., 29 (1991), 1-37.doi: 10.1137/0329001.
[33]	L. Giraud, J. Langou, M. Rozložník and J. van den Eshof, Rounding error analysis of the classical Gram-Schmidt orthogonalization process, Numer. Math., 101 (2005), 87-100.doi: 10.1007/s00211-005-0615-4.
[34]	G. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University, Press, Baltimore, MD, USA.
[35]	A. Hay, J. Borggaard and D. Pelletier, Local improvements to reduced-order models using sensitivity analysis of the proper orthogonal decomposition, J. Fluid Mech., 629 (2009), 41-72.doi: 10.1017/S0022112009006363.
[36]	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.
[37]	P. Holmes, J. L. Lumley, G. Berkooz and C. W. Rowley, Turbulence, Coherent Structures, Dynamical Systems and Symmetry, 2nd edition, Cambridge Monographs on Mechanics, Cambridge University Press, Cambridge, 2012.doi: 10.1017/CBO9780511919701.
[38]	I. Jaimoukha and E. Kasenally, Krylov subspace methods for solving large Lyapunov equations, SIAM J. Numer. Anal., 31 (1994), 227-251.doi: 10.1137/0731012.
[39]	K. Jbilou, Block Krylov subspace methods for large algebraic Riccati equations, Numerical Algorithms, 34 (2003), 339-353.doi: 10.1023/B:NUMA.0000005349.18793.28.
[40]	K. Jbilou, An Arnoldi based algorithm for large algebraic Riccati equations, Applied Mathematics Letters, 19 (2006), 437-444.doi: 10.1016/j.aml.2005.07.001.
[41]	K. Jbilou and A. Riquet, Projection methods for large Lyapunov matrix equations, Linear Algebra and its Applications, Special Issue on Order Reduction of Large-Scale Systems, 415 (2006), 344-358.doi: 10.1016/j.laa.2004.11.004.
[42]	T. Kailath, Some Chandrasekhar-type algorithms for quadratic regulators, in Proceedings of the 1972 IEEE Conference on Decision and Control and 11th Symposium on Adaptive Processes., vol. 11, (1972), 219-223.
[43]	D. Kasinathan and K. Morris, H_∞-optimal actuator location, IEEE Trans. Automat. Control, 58 (2013), 2522-2535.doi: 10.1109/TAC.2013.2266870.
[44]	C. Kenney, A. Laub and M. Wette, Error bounds for Newton refinement of solutions to algebraic Riccati equations, Mathematics of Control, Signals and Systems, 3 (1990), 211-224.doi: 10.1007/BF02551369.
[45]	B. Kramer, Solving algebraic Riccati equations via proper orthogonal decomposition, in Proceedings of the 19th IFAC World Congress, (2014), 7767-7772.
[46]	K. Kunisch and S. Volkwein, Galerkin proper orthogonal decomposition methods for a general equation in fluid dynamics, SIAM Journal on Numerical analysis, 40 (2002), 492-515.doi: 10.1137/S0036142900382612.
[47]	H. Kwakernaak and R. Sivan, Linear Optimal Control Systems, Wiley-Interscience, New York, 1972.
[48]	C. H. Lee and H. T. Tran, Reduced-order-based feedback control of the Kuramoto-Sivashinsky equation, J. Comput. Appl. Math., 173 (2005), 1-19.doi: 10.1016/j.cam.2004.02.021.
[49]	T. Li, E. K.-w. Chu, W.-W. Lin and P. C.-Y. Weng, Solving large-scale continuous-time algebraic Riccati equations by doubling, J. Comput. Appl. Math., 237 (2013), 373-383.doi: 10.1016/j.cam.2012.06.006.
[50]	Y. Lin and V. Simoncini, A new subspace iteration method for the algebraic Riccati equation, Numerical Linear Algebra with Applications, 22 (2015), 26-47.doi: 10.1002/nla.1936.
[51]	A. Lindquist, A new algorithm for optimal filtering of discrete-time stationary processes, SIAM Journal on Control, 12 (1974), 736-746.
[52]	M. Opmeer, Decay of singular values of the Gramians of infinite-dimensional systems, in In Proceedings of the European Control Conference, (2015), 1183-1188.
[53]	G. M. Oxberry, T. Kostova-Vassilevska, W. Arrighi and K. Chand, Limited-memory adaptive snapshot selection for proper orthogonal decomposition, International Journal for Numerical Methods in Engineering, 2016.
[54]	B. Peherstorfer and K. Willcox, Dynamic data-driven reduced-order models, Comput. Methods Appl. Mech. Engrg., 291 (2015), 21-41.doi: 10.1016/j.cma.2015.03.018.
[55]	J. Pralits and P. Luchini, Riccati-less optimal control of bluff-body wakes, in Seventh IUTAM Symposium on Laminar-Turbulent Transition, Springer Netherlands, (2010), 325-330.
[56]	C. Rowley, Model reduction for fluids, using balanced proper orthogonal decomposition, International Journal of Bifurcation and Chaos, 15 (2005), 997-1013.doi: 10.1142/S0218127405012429.
[57]	M. Rozložník, M. Tůma, A. Smoktunowicz and J. Kopal, Numerical stability of orthogonalization methods with a non-standard inner product, BIT, 52 (2012), 1035-1058.doi: 10.1007/s10543-012-0398-9.
[58]	Y. Saad, Numerical solution of large Lyapunov equations, in Signal Processing, Scattering and Operator Theory, and Numerical Methods (Amsterdam, 1989), vol. 5 of Progr. Systems Control Theory, Birkhäuser Boston, Boston, MA, (1990), 503-511.
[59]	O. Semeraro, J. O. Pralits, C. Rowley and D. Henningson, Riccati-less approach for optimal control and estimation: an application to two-dimensional boundary layers, Journal of Fluid Mechanics, 731 (2013), 394-417.doi: 10.1017/jfm.2013.352.
[60]	V. Simoncini, A new iterative method for solving large-scale Lyapunov matrix equations, SIAM J. Sci. Comput, 29 (2007), 1268-1288.doi: 10.1137/06066120X.
[61]	V. Simoncini, D. B. Szyld and M. Monsalve, On two numerical methods for the solution of large-scale algebraic Riccati equations, IMA J. Numer. Anal., 34 (2014), 904-920.doi: 10.1093/imanum/drt015.
[62]	J. R. Singler, Balanced POD for model reduction of linear PDE systems: convergence theory, Numer. Math., 121 (2012), 127-164.doi: 10.1007/s00211-011-0424-x.
[63]	J. R. Singler and B. A. Batten, Balanced POD for linear PDE robust control computations, Comp. Opt. and Appl., 53 (2012), 227-248.doi: 10.1007/s10589-011-9451-x.
[64]	J. Singler, Convergent snapshot algorithms for infinite-dimensional Lyapunov equations, IMA Journal of Numerical Analysis, 31 (2011), 1468-1496.doi: 10.1093/imanum/drq028.
[65]	L. Sirovich, Turbulence and the dynamics of coherent structures. I. Coherent structures, Quart. Appl. Math., 45 (1987), 561-571.
[66]	J. Sun, Residual bounds of approximate solutions of the algebraic Riccati equation, Numerische Mathematik, 76 (1997), 249-263.doi: 10.1007/s002110050262.
[67]	L. Trefethen and M. Embree, Spectra and Pseudospectra, Princeton University Press, Princeton, NJ, 2005.
[68]	E. Verriest, Low sensitivity design and optimal order reduction for the LQG-problem, in Proc. 24th Midwest Symp. Circ. Syst., Albuquerque, NM, USA, (1981), 365-369.
[69]	S. Volkwein, Proper orthogonal decomposition for linear-quadratic optimal control, Lecture Notes, University of Konstanz, 2013, http://www.math.uni-konstanz.de/numerik/personen/volkwein/teaching/scripts.php.
[70]	S. Volkwein, Proper orthogonal decomposition: Theory and reduced-order modelling, Lecture Notes, University of Konstanz, 2013, http://www.math.uni-konstanz.de/numerik/personen/volkwein/teaching/scripts.php.
[71]	E. Vugrin, On Approximation and Optimal Control of Nonnormal Distributed Parameter Systems, PhD thesis, Virginia Polytechnic Institute and State University, 2004, https://vtechworks.lib.vt.edu/handle/10919/27404.
[72]	W.-g. Wang, W.-c. Wang and R.-c. Li, Deflating irreducible singular M-matrix algebraic Riccati equations, Numer. Algebra Control Optim., 3 (2013), 491-518.doi: 10.3934/naco.2013.3.491.
[73]	X. Wang, W.-W. Li and L. Dai, On inexact Newton methods based on doubling iteration scheme for symmetric algebraic Riccati equations, J. Comput. Appl. Math., 260 (2014), 364-374.doi: 10.1016/j.cam.2013.09.074.
[74]	K. Willcox and J. Peraire, Balanced model reduction via the proper orthogonal decomposition, AIAA Journal, 40 (2015), 2323-2330.