Computing Lyapunov functions using deep neural networks

Lars Grüne

doi:10.3934/jcd.2021006

Article Contents

2021, Volume 8, Issue 2: 131-152. Doi: 10.3934/jcd.2021006

This issue Previous Article Next Article Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm

Computing Lyapunov functions using deep neural networks

Lars Grüne

Mathematical Institute, University of Bayreuth, 95440 Bayreuth, Germany

Received: September 2020

Revised: November 2020

Early access: December 2020

Published: April 2021

Abstract / Introduction Full Text(HTML) Figure(8) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary:68T07;34D20;Secondary:93D09.

Citation:

FullText(HTML)

Figure 1. Neural network with $ 1 $ and $ 2 $ hidden layers

Download: Full-size image PowerPoint slide

Figure 2. Neural network for Lyapunov functions, $ f\in F_1^{d_{\max}} $

Download: Full-size image PowerPoint slide

Figure 3. Neural network for Lyapunov functions, $ f\in F_2^{d_{\max}} $

Download: Full-size image PowerPoint slide

Figure 5. Attempt to compute a Lyapunov function $ W(\cdot;\theta^*) $ (solid) with its orbital derivative $ DW(\cdot;\theta^*)f $ (mesh) for Ex. (12) with loss function (9)

Download: Full-size image PowerPoint slide

Figure 4. Approximate Lyapunov function $ W(\cdot;\theta^*) $ (solid) and its orbital derivative $ DW(\cdot;\theta^*)f $ (mesh) for Example (12) computed with loss function (11)

Download: Full-size image PowerPoint slide

Figure 6. Approximate Lyapunov function $ W(\cdot;\theta^*) $ (solid) and its orbital derivative $ DW(\cdot;\theta^*)f $ (mesh) for Example (13) on $ (x_2,x_8) $-plane

Download: Full-size image PowerPoint slide

Figure 7. Approximate Lyapunov function $ W(\cdot;\theta^*) $ (solid) and its orbital derivative $ DW(\cdot;\theta^*)f $ (mesh) for Example (13) on $ (x_9,x_{10}) $-plane

Download: Full-size image PowerPoint slide

Figure 8. Value of approximate Lyapunov function $ W(x(t);\theta^*) $ along trajectories for initial values $ x_0 = (1,1,1,1,1,1,1,1,1,1)^T $, $ (0,1,0,1,0,1,0,1,0,1)^T $, $ (1,0,0,0,0,0,0,0,0,0)^T $ (left to right)

Download: Full-size image PowerPoint slide

Related Papers

Cited by

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 and F. L. Lewis, Nearly optimal control laws for nonlinear systems with saturating actuators using a neural network HJB approach, Automatica J. IFAC, 41 (2005), 779-791. doi: 10.1016/j.automatica.2004.11.034.
[3]	J. Anderson and A. Papachristodoulou, Advances in computational Lyapunov analysis using sum-of-squares programming, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2361-2381. doi: 10.3934/dcdsb.2015.20.2361.
[4]	J. Berner, P. Grohs and 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 (2020), 631-657. 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. doi: 10.1007/978-3-7908-2604-3_16.
[6]	L. Bottou, F. E. Curtis and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Rev., 60 (2018), 223-311. 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. doi: 10.1007/BFb0110220.
[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. doi: 10.23919/ECC.2009.7074385.
[9]	G. Cybenko, Approximation by superpositions of a sigmoidal function, Math. Control Signals Systems, 2 (1989), 303-314. 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. doi: 10.1007/s40687-020-00215-6.
[11]	S. Dashkovskiy, H. Ito and F. Wirth, On a small gain theorem for ISS networks in dissipative Lyapunov form, Eur. J. Control, 17 (2011), 357-365. doi: 10.3166/ejc.17.357-365.
[12]	S. N. Dashkovskiy, B. S. Rüffer and F. R. Wirth, Small gain theorems for large scale systems and construction of ISS Lyapunov functions, SIAM J. Control Optim., 48 (2010), 4089-4118. doi: 10.1137/090746483.
[13]	W. E, J. Han and A. Jentzen, Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations, Commun. Math. Stat., 5 (2017), 349-380. doi: 10.1007/s40304-017-0117-6.
[14]	P. Giesl and S. Hafstein, Computation of Lyapunov functions for nonlinear discrete time systems by linear programming, J. Difference Equ. Appl., 20 (2014), 610-640. doi: 10.1080/10236198.2013.867341.
[15]	P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2291-2331. 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. doi: 10.1007/978-3-540-69909-5.
[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. doi: 10.1109/ACC.2014.6858660.
[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.
[20]	W. Hahn, Stability of Motion, Die Grundlehren der mathematischen Wissenschaften, 138, Springer-Verlag New York, Inc., New York, 1967. doi: 10.1007/978-3-642-50085-5.
[21]	J. Han, A. Jentzen and W. E, Solving high-dimensional partial differential equations using deep learning, Proc. Natl. Acad. Sci. USA, 115 (2018), 8505-8510. doi: 10.1073/pnas.1718942115.
[22]	K. Hornik, M. Stinchcombe and H. White, Multilayer feedforward networks are universal approximators, Neural Networks, 2 (1989), 359-366. doi: 10.1016/0893-6080(89)90020-8.
[23]	C. Huré, H. Pham and X. Warin, Deep backward schemes for high-dimensional nonlinear PDEs, Math. Comp., 89 (2020), 1547-1579. 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.
[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). doi: 10.1007/s42985-019-0006-9.
[26]	Z.-P. Jiang, A. R. Teel and L. Praly, Small-gain theorem for ISS systems and applications, Math. Control Signals Systems, 7 (1994), 95-120. doi: 10.1007/BF01211469.
[27]	Z.-P. Jiang, I. M. Y. Mareels and Y. Wang, A Lyapunov formulation of the nonlinear small-gain theorem for interconnected ISS systems, Automatica J. IFAC, 32 (1996), 1211-1215. doi: 10.1016/0005-1098(96)00051-9.
[28]	H. K. Khalil, Nonlinear Systems, Prentice-Hall, 1996.
[29]	S. Mohammad Khansari-Zadeh and A. Billard, Learning control Lyapunov function to ensure stability of dynamical system-based robot reaching motions, Robotics and Autonomous Systems, 62 (2014), 752-765. doi: 10.1016/j.robot.2014.03.001.
[30]	N. E. Kirin, R. A. Nelepin and V. N. Ba${\rm{\mathord{\buildrel{\lower3pt\hbox{$\scriptscriptstyle\smile$}} \over i} }}$daev, Construction of the attraction region by Zubov's method, Differ. Equations, 17 (1982), 871-880.
[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. doi: 10.1109/CDC.1993.325708.
[34]	H. N. Mhaskar, Neural networks for optimal approximation of smooth and analytic functions, Neural Comput., 8 (1996), 164-177. 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 and Q. Liao, Why and when can deep - but not shallow - networks avoid the curse of dimensionality: A review, Int. J. Automat. Computing, 14 (2017), 503-519. 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. doi: 10.1142/S0219530520500116.
[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. doi: 10.1109/IJCNN.2005.1555943.
[42]	J. Sirignano and K. Spiliopoulos, DGM: A deep learning algorithm for solving partial differential equations, J. Comput. Phys., 375 (2018), 1339-1364. doi: 10.1016/j.jcp.2018.08.029.
[43]	E. D. Sontag, Smooth stabilization implies coprime factorization, IEEE Trans. Automat. Control, 34 (1989), 435-443. doi: 10.1109/9.28018.
[44]	E. D. Sontag, Feedback stabilization using two-hidden-layer nets, IEEE Trans. Neural Networks, 3 (1992), 981-990. doi: 10.1109/72.165599.
[45]	V. I. Zubov, Methods of A.M. Lyapunov and Their Application, P. Noordhoff Ltd, Groningen, 1964.