Article Contents
Article Contents

# Solving differential Riccati equations: A nonlinear space-time method using tensor trains

• * Corresponding author: T. Breiten
• Differential Riccati equations are at the heart of many applications in control theory. They are time-dependent, matrix-valued, and in particular nonlinear equations that require special methods for their solution. Low-rank methods have been used heavily for computing a low-rank solution at every step of a time-discretization. We propose the use of an all-at-once space-time solution leading to a large nonlinear space-time problem for which we propose the use of a Newton–Kleinman iteration. Approximating the space-time problem in a higher-dimensional low-rank tensor form requires fewer degrees of freedom in the solution and in the operator, and gives a faster numerical method. Numerical experiments demonstrate a storage reduction of up to a factor of 100.

Mathematics Subject Classification: Primary: 15A24, 65H10, 15A69, 93A15.

 Citation:

• Figure 1.  1D heat equation with $n = 1000$ and $n_t = 2000$. Left. Controlled and desired states. Right. Singular values of solutions

Figure 2.  Left. Control and observation domains. Right. Singular values of matrix unfoldings

Figure 3.  Storage reduction by tensor truncation from $P(\cdot)$ to $\tilde{P}(\cdot)$

Figure 4.  Left. Control domains. Right. Observation domains

Figure 6.  Left. Desired state $x_d(\xi_1,\xi_2,t_f)$. Right. Controlled state $x(\xi_1,\xi_2,t_f)$

Figure 5.  Left. Change in Newton iterates. Right. TT ranks of $\mathbf{p}_i$ during Newton iteration, $r_1$ (solid lines) and $r_2$ (dashed lines)

Figure 7.  Left. Change in Newton iterates. Right. TT ranks of $\mathbf{p}_i$ during Newton iteration, $r_1$ (solid lines) and $r_2$ (dashed lines)

Figure 8.  Left. Desired state $x_d(\xi_1,\xi_2,t_f)$. Right. Controlled state $x(\xi_1,\xi_2,t_f)$

Figure 9.  Left. Change in Newton iterates. Right. TT ranks of $\mathbf{p}_i$ during Newton iteration

Figure 10.  Left. Desired state $x_d(\xi_1,\xi_2,t_f)$. Right. Controlled state $x(\xi_1,\xi_2,t_f)$

Figure 11.  Relative error w.r.t. to the "true" solution from $\mathtt{ode23}$

Table 1.  Computing times and storage for $n_t = 100$ and $n_t = 1000$

 Time ($s$) Memory (MB) Time ($s$) Memory (MB) $\mathtt{ode23}$ 731 2048 894 20480 $\mathtt{tt}$ 6142 14.61 11940 18.6 $\mathtt{MMESS (split)}$ 6.5 74.32 86 916 $\mathtt{MMESS (BDF)}$ 48 115.3 172 1045 $\mathtt{RKSM-DRE}$ 12 29.44 153 273
•  [1] H. Abou-Kandil, G. Freiling, V. Ionescu and G. Jank, Matrix Riccati Equations, Systems Control: Foundations Applications, Birkhäuser Verlag, Basel, 2003, URL https://doi.org/10.1007/978-3-0348-8081-7, In Control and Systems Theory. doi: 10.1007/978-3-0348-8081-7. [2] N. Ahmed, G. Matthies, L. Tobiska and H. Xie, Discontinuous Galerkin time stepping with local projection stabilization for transient convection–diffusion-reaction problems, Computer Methods in Applied Mechanics and Engineering, 200 (2011), 1747-1756.  doi: 10.1016/j.cma.2011.02.003. [3] J. Ballani and L. Grasedyck, A projection method to solve linear systems in tensor format, Numerical Linear Algebra with Applications, 20 (2013), 27-43.  doi: 10.1002/nla.1818. [4] R. Bellman, Dynamic programming, Courier Corporation, 2013. [5] P. Benner, Z. Bujanović, P. Kürschner and J. Saak, RADI: A low-rank ADI-type algorithm for large scale algebraic Riccati equations, Numerische Mathematik, 138 (2018), 301-330.  doi: 10.1007/s00211-017-0907-5. [6] P. Benner, Z. Bujanović, P. Kürschner and J. Saak, A numerical comparison of different solvers for large-scale, continuous-time algebraic Riccati equations and LQR problems, SIAM Journal on Scientific Computing, 42 (2020), A957–A996. doi: 10.1137/18M1220960. [7] P. Benner, S. Dolgov, A. Onwunta and M. Stoll, Low-rank solvers for unsteady Stokes-Brinkman optimal control problem with random data, Computer Methods in Applied Mechanics and Engineering, 304 (2016), 26-54.  doi: 10.1016/j.cma.2016.02.004. [8] P. Benner and H. Mena, BDF methods for large-scale differential Riccati equations, in in Proceedings of Mathematical Theory of Network and Systems, MTNS, 2004. [9] P. Benner and H. Mena, Rosenbrock methods for solving Riccati differential equations, IEEE Transactions on Automatic Control, 58 (2013), 2950-2956.  doi: 10.1109/TAC.2013.2258495. [10] P. Benner, A. Onwunta and M. Stoll, Low rank solution of unsteady diffusion equations with stochastic coefficients, SIAM Journal on Uncertainty Quantification, 3 (2015), 622-649.  doi: 10.1137/130937251. [11] 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. [12] A. Brooks and T. Hughes, Streamline upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations, Computer Methods in Applied Mechanics and Engineering, 32 (1982), 199-259.  doi: 10.1016/0045-7825(82)90071-8. [13] S. Dolgov and B. Khoromskij, Two-level QTT-Tucker format for optimized tensor calculus, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 593-623.  doi: 10.1137/120882597. [14] S. Dolgov and M. Stoll, Low-rank solutions to an optimization problem constrained by the Navier-Stokes equations, SIAM Journal on Scientific Computing, 39 (2017), A255–A280. doi: 10.1137/15M1040414. [15] S. Dolgov, TT-GMRES: solution to a linear system in the structured tensor format, Russian Journal of Numerical Analysis and Mathematical Modelling, 28 (2013), 149-172.  doi: 10.1515/rnam-2013-0009. [16] S. Dolgov and D. Savostyanov, Alternating minimal energy methods for linear systems in higher dimensions, SIAM Journal on Scientific Computing, 36 (2014), A2248–A2271. doi: 10.1137/140953289. [17] D. Donoho et al., High-dimensional data analysis: The curses and blessings of dimensionality, AMS Math Challenges Lecture, 1 (2000), 32. [18] F. Feitzinger, T. Hylla and E. Sachs, Inexact Kleinman–Newton method for Riccati equations, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 272-288.  doi: 10.1137/070700978. [19] C. Fu and J. Pfaendtner, Lifting the curse of dimensionality on enhanced sampling of reaction networks with parallel bias metadynamics, Journal of Chemical Theory and Computation, 14 (2018), 2516-2525. [20] L. Grasedyck and W. Hackbusch, A multigrid method to solve large scale Sylvester equations, SIAM Journal on Matrix Analysis and Applications, 29 (2007), 870-894.  doi: 10.1137/040618102. [21] L. Grasedyck, D. Kressner and C. Tobler, A literature survey of low-rank tensor approximation techniques, GAMM-Mitteilungen, 36 (2013), 53-78.  doi: 10.1002/gamm.201310004. [22] W. Hackbusch, Tensor Spaces And Numerical Tensor Calculus, Springer–Verlag, Berlin, 2012. doi: 10.1007/978-3-642-28027-6. [23] W. Hackbusch, B. N. Khoromskij and E. E. Tyrtyshnikov, Approximate iterations for structured matrices, Numerische Mathematik, 109 (2008), 365-383.  doi: 10.1007/s00211-008-0143-0. [24] E. Hansen and T. Stillfjord, Convergence analysis for splitting of the abstract differential Riccati equation, SIAM Journal on Numerical Analysis, 52 (2014), 3128-3139.  doi: 10.1137/130935501. [25] R. Herzog and E. Sachs, Preconditioned conjugate gradient method for optimal control problems with control and state constraints, SIAM Journal on Matrix Analysis and Applications, 31 (2010), 2291–2317, URL https://doi.org/10.1137/090779127. doi: 10.1137/090779127. [26] M. Hinze, Optimal and Instantaneous Control of the Instationary Navier-Stokes Equations, Habilitation, Technisches Universität Dresden, 2002. [27] S. Holtz, T. Rohwedder and R. Schneider, The alternating linear scheme for tensor optimization in the tensor train format, SIAM Journal on Scientific Computing, 34 (2012), A683–A713. doi: 10.1137/100818893. [28] B. Khoromskij and V. Khoromskaia, Multigrid accelerated tensor approximation of function related multidimensional arrays, SIAM Journal on Scientific Computing, 31 (2009), 3002-3026.  doi: 10.1137/080730408. [29] G. Kirsten and V. Simoncini, Order reduction methods for solving large-scale differential matrix Riccati equations, accepted SIAM Journal on Scientific Computing. doi: 10.1137/19M1264217. [30] T. Kolda and B. Bader, Tensor decompositions and applications, SIAM Review, 51 (2009), 455-500.  doi: 10.1137/07070111X. [31] A. Koskela and H. Mena, Analysis of Krylov subspace approximation to large scale differential Riccati equations, arXiv preprint arXiv: 1705.07507. [32] D. Kressner and C. Tobler, Krylov subspace methods for linear systems with tensor product structure, SIAM Journal on Matrix Analysis and Applications, 31 (2010), 1688-1714.  doi: 10.1137/090756843. [33] N. Lang, Numerical Methods for Large-Scale Linear Time-Varying Control Systems and Related Differential Matrix Equations, PhD thesis, Technische Universität Chemnitz, 2018. [34] N. Lang, H. Mena and J. Saak, On the benefits of the $LDL^T$ factorization for large-scale differential matrix equation solvers, Linear Algebra and its Applications, 480 (2015), 44-71.  doi: 10.1016/j.laa.2015.04.006. [35] 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. [36] H. Mena, A. Ostermann, L.-M. Pfurtscheller and C. Piazzola, Numerical low-rank approximation of matrix differential equations, Journal of Computational and Applied Mathematics, 340 (2018), 602-614.  doi: 10.1016/j.cam.2018.01.035. [37] M. R. Opmeer, Decay of singular values of the Gramians of infinite-dimensional systems, in 2015 European Control Conference (ECC), 2015, 1183–1188. [38] I. Oseledets, DMRG approach to fast linear algebra in the TT-format, Computational Methods in Applied Mathematics, 11 (2011), 382-393.  doi: 10.2478/cmam-2011-0021. [39] I. Oseledets, Tensor-train decomposition, SIAM Journal on Scientific Computing, 33 (2011), 2295-2317.  doi: 10.1137/090752286. [40] I. Oseledets, S. Dolgov, V. Kazeev, D. Savostyanov, O. Lebedeva, P. Zhlobich, T. Mach and L. Song, TT-Toolbox, URL https://github.com/oseledets/TT-Toolbox, https://github.com/oseledets/TT-Toolbox. [41] I. Oseledets and E. Tyrtyshnikov, Breaking the curse of dimensionality, or how to use SVD in many dimensions, SIAM Journal on Scientific Computing, 31 (2009), 3744-3759.  doi: 10.1137/090748330. [42] J. Pearson, M. Stoll and A. Wathen, Preconditioners for state-constrained optimal control problems with Moreau-Yosida penalty function, Numerical Linear Algebra with Applications, 21 (2014), 81–97, URL https://doi.org/10.1002/nla.1863. doi: 10.1002/nla.1863. [43] J. Saak, M. Köhler and P. Benner, M-M.E.S.S.-2.0 – The matrix equations sparse solvers library, See also: www.mpi-magdeburg.mpg.de/projects/mess. doi: 10.5281/zenodo.3368844. [44] C. Schillings and C. Schwab, Sparse, adaptive Smolyak quadratures for Bayesian inverse problems, Inverse Problems, 29 (2013), 065011. doi: 10.1088/0266-5611/29/6/065011. [45] C. Silvestre and A. Pascoal, Depth control of the INFANTE AUV using gain-scheduled reduced order output feedback, Control Engineering Practice, 15 (2007), 883-895. [46] V. Simoncini, Analysis of the rational Krylov subspace projection method for large-scale algebraic Riccati equations, SIAM Journal on Matrix Analysis and Applications, 37 (2016), 1655-1674.  doi: 10.1137/16M1059382. [47] T. Stillfjord, Singular value decay of operator-valued differential Lyapunov and Riccati equations, SIAM Journal on Control and Optimization, 56 (2018), 3598-3618.  doi: 10.1137/18M1178815. [48] M. Stoll and T. Breiten, A low-rank in time approach to PDE-constrained optimization, SIAM Journal on Scientific Computing, 37 (2015), 1-19.  doi: 10.1137/130926365. [49] C. Tobler, Low-rank Tensor Methods for Linear Systems and Eigenvalue Problems, PhD thesis, Diss., Eidgenössische Technische Hochschule ETH Zürich, Nr. 20320, 2012. [50] F. Tröltzsch, Optimale Steuerung Partieller Differentialgleichungen, Vieweg+Teubner Verlag, 2005. [51] B. Vandereycken and S. Vandewalle, Local Fourier analysis for tensor-product multigrid, in AIP Conference Proceedings, AIP, 1168 (2009), 354–356. [52] C. d. Villemagne and R. E. Skelton, Model reductions using a projection formulation, International Journal of Control, 46 (1987), 2141-2169.  doi: 10.1080/00207178708934040. [53] Z. Zhang, X. Yang, I. Oseledets, G. Karniadakis and L. Daniel, Enabling high-dimensional hierarchical uncertainty quantification by ANOVA and tensor-train decomposition, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 34 (2015), 63-76.

Figures(11)

Tables(1)