Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author: T. Breiten

    * Corresponding author: T. Breiten 
Abstract Full Text(HTML) Figure(11) / Table(1) Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
     | Show Table
    DownLoad: CSV
  • [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. AhmedG. MatthiesL. 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. BennerZ. 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. BennerS. DolgovA. 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. BennerA. 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. FeitzingerT. 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. GrasedyckD. 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. HackbuschB. 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. LangH. 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. MenaA. OstermannL.-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. ZhangX. YangI. OseledetsG. 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. 
  • 加载中




Article Metrics

HTML views(748) PDF downloads(735) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint