×

Computing Lyapunov functions using deep neural networks. (English) Zbl 1507.68267

Summary: We propose a deep neural network architecture and associated loss functions for a training algorithm for computing approximate Lyapunov functions of systems of nonlinear ordinary differential equations. Under the assumption that the system admits a compositional Lyapunov function, we prove that the number of neurons needed for an approximation of a Lyapunov function with fixed accuracy grows only polynomially in the state dimension, i.e., the proposed approach is able to overcome the curse of dimensionality. We show that nonlinear systems satisfying a small-gain condition admit compositional Lyapunov functions. Numerical examples in up to ten space dimensions illustrate the performance of the training scheme.

MSC:

68T07 Artificial neural networks and deep learning
34D20 Stability of solutions to ordinary differential equations

Software:

TensorFlow; DGM
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Abadi, A. Agarwal, P. Barham, E. Brevdo and Z. Chen, et al., TensorFlow: Large-scale machine learning on heterogeneous systems, 2015., Available from: https://www.tensorflow.org/.
[2] M. Abu-Khalaf; F. L. Lewis, Nearly optimal control laws for nonlinear systems with saturating actuators using a neural network HJB approach, Automatica J. IFAC, 41, 779-791 (2005) · Zbl 1087.49022 · doi:10.1016/j.automatica.2004.11.034
[3] J. Anderson; A. Papachristodoulou, Advances in computational Lyapunov analysis using sum-of-squares programming, Discrete Contin. Dyn. Syst. Ser. B, 20, 2361-2381 (2015) · Zbl 1334.37105 · doi:10.3934/dcdsb.2015.20.2361
[4] J. Berner; P. Grohs; A. Jentzen, Analysis of the generalization error: Empirical risk minimization over deep artificial neural networks overcomes the curse of dimensionality in the numerical approximation of Black-Scholes partial differential equations, SIAM J. Math. Data Sci., 2, 631-657 (2020) · Zbl 1480.60191 · doi:10.1137/19M125649X
[5] L. Bottou, Large-scale machine learning with stochastic gradient descent, in Proceedings of COMPSTAT’2010, Physica-Verlag/Springer, Heidelberg, 2010, 177-186. · Zbl 1436.68293
[6] L. Bottou; F. E. Curtis; J. Nocedal, Optimization methods for large-scale machine learning, SIAM Rev., 60, 223-311 (2018) · Zbl 1397.65085 · doi:10.1137/16M1080173
[7] F. Camilli, L. Grüne and F. Wirth, A regularization of Zubov’s equation for robust domains of attraction, in Nonlinear Control in the Year 2000, Lect. Notes Control Inf. Sci., 258, NCN, Springer, London, 2001, 277-289. · Zbl 1239.93048
[8] F. Camilli, L. Grüne and F. Wirth, Domains of attraction of interconnected systems: A Zubov method approach, European Control Conference (ECC), Budapest, Hungary, 2009.
[9] G. Cybenko, Approximation by superpositions of a sigmoidal function, Math. Control Signals Systems, 2, 303-314 (1989) · Zbl 0679.94019 · doi:10.1007/BF02551274
[10] J. Darbon, G. P. Langlois and T. Meng, Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures, Res. Math. Sci., 7 (2020), 50pp. · Zbl 1445.35119
[11] S. Dashkovskiy; H. Ito; F. Wirth, On a small gain theorem for ISS networks in dissipative Lyapunov form, Eur. J. Control, 17, 357-365 (2011) · Zbl 1237.93160 · doi:10.3166/ejc.17.357-365
[12] S. N. Dashkovskiy; B. S. Rüffer; F. R. Wirth, Small gain theorems for large scale systems and construction of ISS Lyapunov functions, SIAM J. Control Optim., 48, 4089-4118 (2010) · Zbl 1202.93008 · doi:10.1137/090746483
[13] W. E.; J. Han; A. Jentzen, Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations, Commun. Math. Stat., 5, 349-380 (2017) · Zbl 1382.65016 · doi:10.1007/s40304-017-0117-6
[14] P. Giesl; S. Hafstein, Computation of Lyapunov functions for nonlinear discrete time systems by linear programming, J. Difference Equ. Appl., 20, 610-640 (2014) · Zbl 1319.39010 · doi:10.1080/10236198.2013.867341
[15] P. Giesl; S. Hafstein, Review on computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20, 2291-2331 (2015) · Zbl 1337.37001 · doi:10.3934/dcdsb.2015.20.2291
[16] P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Mathematics, 1904, Springer, Berlin, 2007.
[17] L. Grüne, Overcoming the curse of dimensionality for approximating Lyapunov functions with deep neural networks under a small-gain condition, preprint, arXiv: 2001.08423.
[18] S. Hafstein, C. M. Kellett and H. Li, Continuous and piecewise affine Lyapunov functions using the Yoshizawa construction, American Control Conference, Portland, OR, 2014.
[19] S. F. Hafstein, An algorithm for constructing Lyapunov functions, Electronic Journal of Differential Equations, Monograph, 8, Texas State University-San Marcos, Department of Mathematics, San Marcos, TX, 2007, 100pp. · Zbl 1131.37021
[20] W. Hahn, Stability of Motion, Die Grundlehren der mathematischen Wissenschaften, 138, Springer-Verlag New York, Inc., New York, 1967. · Zbl 0189.38503
[21] J. Han; A. Jentzen; W. E., Solving high-dimensional partial differential equations using deep learning, Proc. Natl. Acad. Sci. USA, 115, 8505-8510 (2018) · Zbl 1416.35137 · doi:10.1073/pnas.1718942115
[22] K. Hornik; M. Stinchcombe; H. White, Multilayer feedforward networks are universal approximators, Neural Networks, 2, 359-366 (1989) · Zbl 1383.92015 · doi:10.1016/0893-6080(89)90020-8
[23] C. Huré; H. Pham; X. Warin, Deep backward schemes for high-dimensional nonlinear PDEs, Math. Comp., 89, 1547-1579 (2020) · Zbl 1440.60063 · doi:10.1090/mcom/3514
[24] M. Hutzenthaler, A. Jentzen and T. Kruse, Overcoming the curse of dimensionality in the numerical approximation of parabolic partial differential equations with gradient-dependent nonlinearities, preprint, arXiv: 1912.02571. · Zbl 1471.65169
[25] M. Hutzenthaler, A. Jentzen, T. Kruse and T. A. Nguyen, A proof that rectified deep neural networks overcome the curse of dimensionality in the numerical approximation of semilinear heat equations, SN Partial Differ. Equ. Appl., 10 (2020). · Zbl 1455.65200
[26] Z.-P. Jiang; A. R. Teel; L. Praly, Small-gain theorem for ISS systems and applications, Math. Control Signals Systems, 7, 95-120 (1994) · Zbl 0836.93054 · doi:10.1007/BF01211469
[27] Z.-P. Jiang; I. M. Y. Mareels; Y. Wang, A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems, Automatica J. IFAC, 32, 1211-1215 (1996) · Zbl 0857.93089 · doi:10.1016/0005-1098(96)00051-9
[28] H. K. Khalil, Nonlinear Systems, Prentice-Hall, 1996.
[29] S. Mohammad Khansari-Zadeh; A. Billard, Learning control Lyapunov function to ensure stability of dynamical system-based robot reaching motions, Robotics and Autonomous Systems, 62, 752-765 (2014) · doi:10.1016/j.robot.2014.03.001
[30] N. E. Kirin; R. A. Nelepin; V. N. \(Ba \begin{document}{\rm{\mathord{\buildrel{\lower3pt\hbox{\)\scriptscriptstyle\smile \(}} \over i} }} \end{document}\) daev, Construction of the attraction region by Zubov’s method, Differ. Equations, 17, 871-880 (1982) · Zbl 0486.34045
[31] F. L. Lewis, S. Jagannathan and A. Yeşildirek, Neural Network Control of Robot Manipulators and Nonlinear Systems, Taylor and Francis, 1998.
[32] H. Li, Computation of Lyapunov Functions and Stability of Interconnected Systems, Ph.D dissertation, Universität Bayreuth, 2015.
[33] Y. Long and M. M. Bayoumi, Feedback stabilization: Control Lyapunov functions modelled by neural networks, Proceedings of the 32nd IEEE Conference on Decision and Control, San Antonio, TX, 1993.
[34] H. N. Mhaskar, Neural networks for optimal approximation of smooth and analytic functions, Neural Comput., 8, 164-177 (1996) · doi:10.1162/neco.1996.8.1.164
[35] N. Noroozi, P. Karimaghaee, F. Safaei and H. Javadi, Generation of Lyapunov functions by neural networks, Proceedings of the World Congress on Engineering. Vol I, London, UK, 2008.
[36] V. Petridis and S. Petridis, Construction of neural network based Lyapunov functions, Proceedings of the International Joint Conference on Neural Networks, Vancouver, Canada, 2006, 5059-5065.
[37] T. Poggio; H. Mhaskar; L. Rosaco; B. Miranda; Q. Liao, Why and when can deep - but not shallow - networks avoid the curse of dimensionality: A review, Int. J. Automat. Computing, 14, 503-519 (2017) · doi:10.1007/s11633-017-1054-2
[38] C. Reisinger and Y. Zhang, Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems, Anal. Appl. (Singap.), 18 (2020), 951-999. · Zbl 1456.82804
[39] S. M. Richards, F. Berkenkamp and A. Krause, The Lyapunov neural network: Adaptive stability certification for safe learning of dynamical systems, Proceedings of the 2nd Conference on Robot Learning - CoRL 2018, Zürich, Switzerland, 2018. Available from: arXiv: 1808.00924.
[40] B. S. Rüffer, Monotone Systems, Graphs, and Stability of Large-Scale Interconnected Systems, Ph.D dissertation, Universität Bremen, Germany, 2007.
[41] G. Serpen, Empirical approximation for Lyapunov functions with artificial neural nets, Proc. International Joint Conference on Neural Networks, Montreal, Que., Canada, 2005.
[42] J. Sirignano; K. Spiliopoulos, DGM: A deep learning algorithm for solving partial differential equations, J. Comput. Phys., 375, 1339-1364 (2018) · Zbl 1416.65394 · doi:10.1016/j.jcp.2018.08.029
[43] E. D. Sontag, Smooth stabilization implies coprime factorization, IEEE Trans. Automat. Control, 34, 435-443 (1989) · Zbl 0682.93045 · doi:10.1109/9.28018
[44] E. D. Sontag, Feedback stabilization using two-hidden-layer nets, IEEE Trans. Neural Networks, 3, 981-990 (1992) · doi:10.1109/72.165599
[45] V. I. Zubov, Methods of A.M. Lyapunov and Their Application, P. Noordhoff Ltd, Groningen, 1964. · Zbl 0115.30204
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.