Approximation of Lyapunov functions from noisy data

Peter Giesl; Boumediene Hamzi; Martin Rasmussen; Kevin Webster

doi:10.3934/jcd.2020003

Previous Article
Geometrical properties of the mean-median map
JCD Home
This Issue
Next Article
Evaluating the accuracy of the dynamic mode decomposition

June 2020, 7(1): 57-81. doi: 10.3934/jcd.2020003

Approximation of Lyapunov functions from noisy data

Peter Giesl ^1, , Boumediene Hamzi ^2, , Martin Rasmussen ^2, and Kevin Webster ^2,

1.	Department of Mathematics, University of Sussex, Falmer, BN1 9QH, UK
2.	Department of Mathematics, Imperial College London, London SW7 2AZ, UK

Received May 2017 Revised October 2019 Published December 2019

Fund Project: B. Hamzi was supported by Marie Curie Fellowships. M. Rasmussen was supported by an EPSRC Career Acceleration Fellowship EP/I004165/1 and K.N. Webster was supported by the EPSRC Grant EP/L00187X/1 and a Marie Skł odowska-Curie Individual Fellowship Grant Number 660616

Methods have previously been developed for the approximation of Lyapunov functions using radial basis functions. However these methods assume that the evolution equations are known. We consider the problem of approximating a given Lyapunov function using radial basis functions where the evolution equations are not known, but we instead have sampled data which is contaminated with noise. We propose an algorithm in which we first approximate the underlying vector field, and use this approximation to then approximate the Lyapunov function. Our approach combines elements of machine learning/statistical learning theory with the existing theory of Lyapunov function approximation. Error estimates are provided for our algorithm.

Keywords: Lyapunov function, differential equations, radial basis function, error estimates, reproducing kernel Hilbert space.

Mathematics Subject Classification: 37B25, 65N15, 37M99.

Citation: Peter Giesl, Boumediene Hamzi, Martin Rasmussen, Kevin Webster. Approximation of Lyapunov functions from noisy data. Journal of Computational Dynamics, 2020, 7 (1) : 57-81. doi: 10.3934/jcd.2020003

References:

[1]	R. A. Adams, Sobolev Spaces, Adademic Press, New York, 1975.
[2]	N. Bhatia, On asymptotic stability in dynamical systems, Math. Systems Theory, 1 (1967), 113-127. doi: 10.1007/BF01705521.
[3]	N. Bhatia and G. Szegö, Stability Theory of Dynamical Systems, Grundlehren der mathematischen Wissenschaften, 161, Springer, Berlin, 1970.
[4]	J. Bouvrie and B. Hamzi, Balanced reduction of nonlinear control systems in reproducing kernel hilbert space, in Proc. 48th Annual Allerton Conference on Communication, Control, and Computing, (2010), 294–301, http://arXiv.org/abs/1011.2952.
[5]	J. Bouvrie and B. Hamzi, Empirical estimators for the controllability energy and invariant measure of stochastically forced nonlinear systems, in Proc. of the 2012 American Control Conference, (2012), (long version at http://arXiv.org/abs/1204.0563).
[6]	J. Bouvrie and B. Hamzi, Kernel methods for the approximation of some key quantities of nonlinear systems, in Journal of Computational Dynamics, 4 (2017), http://arXiv.org/abs/1204.0563.
[7]	J. Bouvrie and B. Hamzi, Kernel methods for the approximation of nonlinear systems, in SIAM J. Control & Optimization, 55 (2017), http://arXiv.org/abs/1108.2903.
[8]	F. Camilli, L. Grüne and F. Wirth, A generalization of Zubov's method to perturbed systems, SIAM J. Control Optim., 40 (2001), 496-515. doi: 10.1137/S036301299936316X.
[9]	F. Cucker and S. Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc., 39 (2001), 1-49. doi: 10.1090/S0273-0979-01-00923-5.
[10]	F. Cucker and S. Smale, Best choices for regularisation parameters in learning theory, Found. Comput. Math., 2 (2002), 413-428. doi: 10.1007/s102080010030.
[11]	L. Evans, Partial Differential Equations, vol. 19 of Graduate Studies in Mathematics, AMS, Providence, Rhode Island, 1998.
[12]	T. Evgeniou, M. Pontil and T. Poggio, Regularization networks and support vector machines, Adv. Comput. Math., 13 (2000), 1-50. doi: 10.1023/A:1018946025316.
[13]	P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Mathematics. Springer Berlin Heidelberg, 2007.
[14]	P. Giesl and S. Hafstein, Computation and verification of Lyapunov functions, SIAM J. Appl. Dyn. Syst., 14 (2015), 1663-1698. doi: 10.1137/140988802.
[15]	P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions, Discrete and Continuous Dynamical Systems Series B, 20 (2015), 2291-2331. doi: 10.3934/dcdsb.2015.20.2291.
[16]	P. Giesl and H. Wendland, Meshless collocation: Error estimates with application to dynamical systems, SIAM J. Num. Anal., 45 (2007), 1723-1741. doi: 10.1137/060658813.
[17]	L. Grüne, Asymptotic Behavior of Dynamical and Control Systems Under Perturbation and Discretization, Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2002. doi: 10.1007/b83677.
[18]	S. Hafstein, An Algorithm for Constructing Lyapunov Functions, Electronic Journal of Differential Equations. Monograph, 8. Texas State UniversityCSan Marcos, Department of Mathematics, San Marcos, TX, 2007.
[19]	W. Hahn, Theorie und Anwendung der direkten Methode von Ljapunov, Ergebnisse der Mathematik und ihrer Grenzgebiete 22, Springer, Berlin, 1959.
[20]	W. Hahn, Stability of Motion, Springer, New York, 1967.
[21]	A. M. Lyapunov, Problème général de la stabilité du mouvement, Ann. Fac. Sci. Toulouse, 9 (1907), 203–474. Translation of the Russian version, published 1893 in Comm. Soc. math. Kharkow. Newly printed: Ann. of math. Stud. 17, Princeton, 1949.
[22]	Y. Lin, E. D. Sontag and Y. Wang, A smooth converse Lyapunov theorem for robust stability, SIAM J. Control Optim., 34 (1996), 124-160. doi: 10.1137/S0363012993259981.
[23]	C. Kellett, Classical converse theorems in Lyapunov's second method, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2333-2360. doi: 10.3934/dcdsb.2015.20.2333.
[24]	J. L. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721. doi: 10.2307/1969558.
[25]	F. J. Narcowich, J. D. Ward and H. Wendland, Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting, Mathematics of Computation, 74 (2005), 743-763. doi: 10.1090/S0025-5718-04-01708-9.
[26]	R. Opfer, Multiscale kernels, Adv. Comput. Math., 25 (2006), 357-380. doi: 10.1007/s10444-004-7622-3.
[27]	R. Opfer, Tight frame expansions of multiscale reproducing kernels in Sobolev spaces, Appl. Comput. Harmon. Anal., 20 (2006), 357-374. doi: 10.1016/j.acha.2005.05.003.
[28]	A. Papachristodoulou and S. Prajna, On the Construction of Lyapunov Functions Using the Sum of Squares Decomposition, Proceedings of the 41st IEEE Conference on Decision and Control, 2002. doi: 10.1109/CDC.2002.1184414.
[29]	G. Pagès, A space quantization method for numerical integration, J. Comp. Appl. Math., 89 (1998), 1-38. doi: 10.1016/S0377-0427(97)00190-8.
[30]	R. Rifkin and R. A. Lippert, ., Notes on Regularized Least-Squares, CBCL Paper 268/AI Technical Report 2007-019, Massachusetts Institute of Technology, Cambridge, MA, May, 2007.
[31]	S. Smale and D.-X. Zhou, Shannon Sampling and Function Reconstruction from Point Values, Bull. Amer. Math. Soc., 41 (2004), 279-305. doi: 10.1090/S0273-0979-04-01025-0.
[32]	S. Smale and D.-X. Zhou, Shannon sampling II: Connections to learning theory, Appl. Comput. Harmon. Anal., 19 (2005), 285-302. doi: 10.1016/j.acha.2005.03.001.
[33]	S. Smale and D.-X. Zhou, Learning theory estimates via their integral operators and their approximations, Constr. Approx., 26 (2007), 153-172. doi: 10.1007/s00365-006-0659-y.
[34]	S. Smale and D.-X. Zhou, Online learning with Markov sampling, Anal. Appl., 7 (2009), 87-113. doi: 10.1142/S0219530509001293.
[35]	G. Voronoi, Recherches sur les parallelodres primitives, J. Reine Angew. Math., 134 (1908), 198-287. doi: 10.1515/crll.1908.134.198.
[36]	F. Wesley Wilson and Jr ., Smoothing derivatives of functions and applications, Trans. Amer. Math. Soc., 139 (1969), 413-428. doi: 10.1090/S0002-9947-1969-0251747-9.
[37]	H. Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Adv. Comput. Math., 4 (1995), 389-396. doi: 10.1007/BF02123482.
[38]	H. Wendland, Scattered Data Approximation, Cambridge Monogr. Appl. Comput. Math., Cambridge University Press, Cambridge, UK, 2005.
[39]	H. Wendland and C. Rieger, Approximate interpolation with applications to selecting smoothing parameters, Numer. Math., 101 (2005), 729-748. doi: 10.1007/s00211-005-0637-y.

show all references

References:

[1]	R. A. Adams, Sobolev Spaces, Adademic Press, New York, 1975.
[2]	N. Bhatia, On asymptotic stability in dynamical systems, Math. Systems Theory, 1 (1967), 113-127. doi: 10.1007/BF01705521.
[3]	N. Bhatia and G. Szegö, Stability Theory of Dynamical Systems, Grundlehren der mathematischen Wissenschaften, 161, Springer, Berlin, 1970.
[4]	J. Bouvrie and B. Hamzi, Balanced reduction of nonlinear control systems in reproducing kernel hilbert space, in Proc. 48th Annual Allerton Conference on Communication, Control, and Computing, (2010), 294–301, http://arXiv.org/abs/1011.2952.
[5]	J. Bouvrie and B. Hamzi, Empirical estimators for the controllability energy and invariant measure of stochastically forced nonlinear systems, in Proc. of the 2012 American Control Conference, (2012), (long version at http://arXiv.org/abs/1204.0563).
[6]	J. Bouvrie and B. Hamzi, Kernel methods for the approximation of some key quantities of nonlinear systems, in Journal of Computational Dynamics, 4 (2017), http://arXiv.org/abs/1204.0563.
[7]	J. Bouvrie and B. Hamzi, Kernel methods for the approximation of nonlinear systems, in SIAM J. Control & Optimization, 55 (2017), http://arXiv.org/abs/1108.2903.
[8]	F. Camilli, L. Grüne and F. Wirth, A generalization of Zubov's method to perturbed systems, SIAM J. Control Optim., 40 (2001), 496-515. doi: 10.1137/S036301299936316X.
[9]	F. Cucker and S. Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc., 39 (2001), 1-49. doi: 10.1090/S0273-0979-01-00923-5.
[10]	F. Cucker and S. Smale, Best choices for regularisation parameters in learning theory, Found. Comput. Math., 2 (2002), 413-428. doi: 10.1007/s102080010030.
[11]	L. Evans, Partial Differential Equations, vol. 19 of Graduate Studies in Mathematics, AMS, Providence, Rhode Island, 1998.
[12]	T. Evgeniou, M. Pontil and T. Poggio, Regularization networks and support vector machines, Adv. Comput. Math., 13 (2000), 1-50. doi: 10.1023/A:1018946025316.
[13]	P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Mathematics. Springer Berlin Heidelberg, 2007.
[14]	P. Giesl and S. Hafstein, Computation and verification of Lyapunov functions, SIAM J. Appl. Dyn. Syst., 14 (2015), 1663-1698. doi: 10.1137/140988802.
[15]	P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions, Discrete and Continuous Dynamical Systems Series B, 20 (2015), 2291-2331. doi: 10.3934/dcdsb.2015.20.2291.
[16]	P. Giesl and H. Wendland, Meshless collocation: Error estimates with application to dynamical systems, SIAM J. Num. Anal., 45 (2007), 1723-1741. doi: 10.1137/060658813.
[17]	L. Grüne, Asymptotic Behavior of Dynamical and Control Systems Under Perturbation and Discretization, Lecture Notes in Mathematics. Springer-Verlag, Berlin, 2002. doi: 10.1007/b83677.
[18]	S. Hafstein, An Algorithm for Constructing Lyapunov Functions, Electronic Journal of Differential Equations. Monograph, 8. Texas State UniversityCSan Marcos, Department of Mathematics, San Marcos, TX, 2007.
[19]	W. Hahn, Theorie und Anwendung der direkten Methode von Ljapunov, Ergebnisse der Mathematik und ihrer Grenzgebiete 22, Springer, Berlin, 1959.
[20]	W. Hahn, Stability of Motion, Springer, New York, 1967.
[21]	A. M. Lyapunov, Problème général de la stabilité du mouvement, Ann. Fac. Sci. Toulouse, 9 (1907), 203–474. Translation of the Russian version, published 1893 in Comm. Soc. math. Kharkow. Newly printed: Ann. of math. Stud. 17, Princeton, 1949.
[22]	Y. Lin, E. D. Sontag and Y. Wang, A smooth converse Lyapunov theorem for robust stability, SIAM J. Control Optim., 34 (1996), 124-160. doi: 10.1137/S0363012993259981.
[23]	C. Kellett, Classical converse theorems in Lyapunov's second method, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2333-2360. doi: 10.3934/dcdsb.2015.20.2333.
[24]	J. L. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721. doi: 10.2307/1969558.
[25]	F. J. Narcowich, J. D. Ward and H. Wendland, Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting, Mathematics of Computation, 74 (2005), 743-763. doi: 10.1090/S0025-5718-04-01708-9.
[26]	R. Opfer, Multiscale kernels, Adv. Comput. Math., 25 (2006), 357-380. doi: 10.1007/s10444-004-7622-3.
[27]	R. Opfer, Tight frame expansions of multiscale reproducing kernels in Sobolev spaces, Appl. Comput. Harmon. Anal., 20 (2006), 357-374. doi: 10.1016/j.acha.2005.05.003.
[28]	A. Papachristodoulou and S. Prajna, On the Construction of Lyapunov Functions Using the Sum of Squares Decomposition, Proceedings of the 41st IEEE Conference on Decision and Control, 2002. doi: 10.1109/CDC.2002.1184414.
[29]	G. Pagès, A space quantization method for numerical integration, J. Comp. Appl. Math., 89 (1998), 1-38. doi: 10.1016/S0377-0427(97)00190-8.
[30]	R. Rifkin and R. A. Lippert, ., Notes on Regularized Least-Squares, CBCL Paper 268/AI Technical Report 2007-019, Massachusetts Institute of Technology, Cambridge, MA, May, 2007.
[31]	S. Smale and D.-X. Zhou, Shannon Sampling and Function Reconstruction from Point Values, Bull. Amer. Math. Soc., 41 (2004), 279-305. doi: 10.1090/S0273-0979-04-01025-0.
[32]	S. Smale and D.-X. Zhou, Shannon sampling II: Connections to learning theory, Appl. Comput. Harmon. Anal., 19 (2005), 285-302. doi: 10.1016/j.acha.2005.03.001.
[33]	S. Smale and D.-X. Zhou, Learning theory estimates via their integral operators and their approximations, Constr. Approx., 26 (2007), 153-172. doi: 10.1007/s00365-006-0659-y.
[34]	S. Smale and D.-X. Zhou, Online learning with Markov sampling, Anal. Appl., 7 (2009), 87-113. doi: 10.1142/S0219530509001293.
[35]	G. Voronoi, Recherches sur les parallelodres primitives, J. Reine Angew. Math., 134 (1908), 198-287. doi: 10.1515/crll.1908.134.198.
[36]	F. Wesley Wilson and Jr ., Smoothing derivatives of functions and applications, Trans. Amer. Math. Soc., 139 (1969), 413-428. doi: 10.1090/S0002-9947-1969-0251747-9.
[37]	H. Wendland, Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Adv. Comput. Math., 4 (1995), 389-396. doi: 10.1007/BF02123482.
[38]	H. Wendland, Scattered Data Approximation, Cambridge Monogr. Appl. Comput. Math., Cambridge University Press, Cambridge, UK, 2005.
[39]	H. Wendland and C. Rieger, Approximate interpolation with applications to selecting smoothing parameters, Numer. Math., 101 (2005), 729-748. doi: 10.1007/s00211-005-0637-y.

Figure 1. Domains and sets used in the statement and proof of Theorem 2.1. The dotted lines show the boundary of the set $ \mathcal{D} = \Omega\setminus B_{\varepsilon}(\overline{x}) $ where the Lyapunov functions are approximated. We also have $ \Omega_V,\Omega_T\subset A(\overline{x}) $

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2. Errors between $ f_1 $ and $ {f}^1_{{\bf z},\lambda} $

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3. Errors between $ f_2 $ and $ {f}^2_{{\bf z},\lambda} $

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4. Lyapunov function using Algorithm 2 with 360 points

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5. Lyapunov function using Algorithm 2 with 1520 points

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6. Orbital derivative of the Lyapunov function with respect to the original system using Algorithm 2 with 360 points

Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7. Orbital derivative of the Lyapunov function with respect to the original system using Algorithm 2 with 1520 points

Figure Options

Download full-size image

Download as PowerPoint slide

[1]	Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete and Continuous Dynamical Systems - B, 2007, 7 (1) : 101-124. doi: 10.3934/dcdsb.2007.7.101
[2]	Martin D. Buhmann, Slawomir Dinew. Limits of radial basis function interpolants. Communications on Pure and Applied Analysis, 2007, 6 (3) : 569-585. doi: 10.3934/cpaa.2007.6.569
[3]	Kaitlyn (Voccola) Muller. A reproducing kernel Hilbert space framework for inverse scattering problems within the Born approximation. Inverse Problems and Imaging, 2019, 13 (6) : 1327-1348. doi: 10.3934/ipi.2019058
[4]	Ali Akgül, Mustafa Inc, Esra Karatas. Reproducing kernel functions for difference equations. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1055-1064. doi: 10.3934/dcdss.2015.8.1055
[5]	Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete and Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049
[6]	Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete and Continuous Dynamical Systems - S, 2021, 14 (10) : 3337-3349. doi: 10.3934/dcdss.2020443
[7]	Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33
[8]	Mahmoud M. El-Borai. On some fractional differential equations in the Hilbert space. Conference Publications, 2005, 2005 (Special) : 233-240. doi: 10.3934/proc.2005.2005.233
[9]	Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete and Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453
[10]	Antonio Cañada, Salvador Villegas. Lyapunov inequalities for partial differential equations at radial higher eigenvalues. Discrete and Continuous Dynamical Systems, 2013, 33 (1) : 111-122. doi: 10.3934/dcds.2013.33.111
[11]	Jeremy Levesley, Xinping Sun, Fahd Jarad, Alexander Kushpel. Interpolation of exponential-type functions on a uniform grid by shifts of a basis function. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2399-2416. doi: 10.3934/dcdss.2020403
[12]	Weidong Zhao, Jinlei Wang, Shige Peng. Error estimates of the $\theta$-scheme for backward stochastic differential equations. Discrete and Continuous Dynamical Systems - B, 2009, 12 (4) : 905-924. doi: 10.3934/dcdsb.2009.12.905
[13]	Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems and Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048
[14]	Markus Dick, Martin Gugat, Günter Leugering. A strict $H^1$-Lyapunov function and feedback stabilization for the isothermal Euler equations with friction. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225
[15]	Ali Akgül. A new application of the reproducing kernel method. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2041-2053. doi: 10.3934/dcdss.2020261
[16]	M. P. de Oliveira. On 3-graded Lie algebras, Jordan pairs and the canonical kernel function. Electronic Research Announcements, 2003, 9: 142-151.
[17]	Quyen Tran, Harbir Antil, Hugo Díaz. Optimal control of parameterized stationary Maxwell's system: Reduced basis, convergence analysis, and a posteriori error estimates. Mathematical Control and Related Fields, 2022 doi: 10.3934/mcrf.2022003
[18]	Andrei Korobeinikov, Philip K. Maini. A Lyapunov function and global properties for SIR and SEIR epidemiological models with nonlinear incidence. Mathematical Biosciences & Engineering, 2004, 1 (1) : 57-60. doi: 10.3934/mbe.2004.1.57
[19]	Łukasz Struski, Jacek Tabor. Expansivity implies existence of Hölder continuous Lyapunov function. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3575-3589. doi: 10.3934/dcdsb.2017180
[20]	Hjörtur Björnsson, Sigurdur Hafstein, Peter Giesl, Enrico Scalas, Skuli Gudmundsson. Computation of the stochastic basin of attraction by rigorous construction of a Lyapunov function. Discrete and Continuous Dynamical Systems - B, 2019, 24 (8) : 4247-4269. doi: 10.3934/dcdsb.2019080

Impact Factor:

Tools

Metrics

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

American Institute of Mathematical Sciences

Approximation of Lyapunov functions from noisy data

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Approximation of Lyapunov functions from noisy data

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors