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

Approximation of Lyapunov functions from noisy data

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.

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.   Google Scholar
[2]

N. Bhatia, On asymptotic stability in dynamical systems, Math. Systems Theory, 1 (1967), 113-127.  doi: 10.1007/BF01705521.  Google Scholar

[3]

N. Bhatia and G. Szegö, Stability Theory of Dynamical Systems, Grundlehren der mathematischen Wissenschaften, 161, Springer, Berlin, 1970.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

F. CamilliL. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

L. Evans, Partial Differential Equations, vol. 19 of Graduate Studies in Mathematics, AMS, Providence, Rhode Island, 1998.  Google Scholar

[12]

T. EvgeniouM. Pontil and T. Poggio, Regularization networks and support vector machines, Adv. Comput. Math., 13 (2000), 1-50.  doi: 10.1023/A:1018946025316.  Google Scholar

[13]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Mathematics. Springer Berlin Heidelberg, 2007.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

W. Hahn, Theorie und Anwendung der direkten Methode von Ljapunov, Ergebnisse der Mathematik und ihrer Grenzgebiete 22, Springer, Berlin, 1959.  Google Scholar

[20]

W. Hahn, Stability of Motion, Springer, New York, 1967.  Google Scholar

[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. Google Scholar

[22]

Y. LinE. 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.  Google Scholar

[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.  Google Scholar

[24]

J. L. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721.  doi: 10.2307/1969558.  Google Scholar

[25]

F. J. NarcowichJ. 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.  Google Scholar

[26]

R. Opfer, Multiscale kernels, Adv. Comput. Math., 25 (2006), 357-380.  doi: 10.1007/s10444-004-7622-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

S. Smale and D.-X. Zhou, Online learning with Markov sampling, Anal. Appl., 7 (2009), 87-113.  doi: 10.1142/S0219530509001293.  Google Scholar

[35]

G. Voronoi, Recherches sur les parallelodres primitives, J. Reine Angew. Math., 134 (1908), 198-287.  doi: 10.1515/crll.1908.134.198.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[38] H. Wendland, Scattered Data Approximation, Cambridge Monogr. Appl. Comput. Math., Cambridge University Press, Cambridge, UK, 2005.   Google Scholar
[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.  Google Scholar

show all references

References:
[1] R. A. Adams, Sobolev Spaces, Adademic Press, New York, 1975.   Google Scholar
[2]

N. Bhatia, On asymptotic stability in dynamical systems, Math. Systems Theory, 1 (1967), 113-127.  doi: 10.1007/BF01705521.  Google Scholar

[3]

N. Bhatia and G. Szegö, Stability Theory of Dynamical Systems, Grundlehren der mathematischen Wissenschaften, 161, Springer, Berlin, 1970.  Google Scholar

[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. Google Scholar

[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). Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

F. CamilliL. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[11]

L. Evans, Partial Differential Equations, vol. 19 of Graduate Studies in Mathematics, AMS, Providence, Rhode Island, 1998.  Google Scholar

[12]

T. EvgeniouM. Pontil and T. Poggio, Regularization networks and support vector machines, Adv. Comput. Math., 13 (2000), 1-50.  doi: 10.1023/A:1018946025316.  Google Scholar

[13]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Mathematics. Springer Berlin Heidelberg, 2007.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

W. Hahn, Theorie und Anwendung der direkten Methode von Ljapunov, Ergebnisse der Mathematik und ihrer Grenzgebiete 22, Springer, Berlin, 1959.  Google Scholar

[20]

W. Hahn, Stability of Motion, Springer, New York, 1967.  Google Scholar

[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. Google Scholar

[22]

Y. LinE. 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.  Google Scholar

[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.  Google Scholar

[24]

J. L. Massera, On Liapounoff's conditions of stability, Ann. of Math., 50 (1949), 705-721.  doi: 10.2307/1969558.  Google Scholar

[25]

F. J. NarcowichJ. 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.  Google Scholar

[26]

R. Opfer, Multiscale kernels, Adv. Comput. Math., 25 (2006), 357-380.  doi: 10.1007/s10444-004-7622-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

S. Smale and D.-X. Zhou, Online learning with Markov sampling, Anal. Appl., 7 (2009), 87-113.  doi: 10.1142/S0219530509001293.  Google Scholar

[35]

G. Voronoi, Recherches sur les parallelodres primitives, J. Reine Angew. Math., 134 (1908), 198-287.  doi: 10.1515/crll.1908.134.198.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[38] H. Wendland, Scattered Data Approximation, Cambridge Monogr. Appl. Comput. Math., Cambridge University Press, Cambridge, UK, 2005.   Google Scholar
[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.  Google Scholar

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 2.  Errors between $ f_1 $ and $ {f}^1_{{\bf z},\lambda} $
Figure 3.  Errors between $ f_2 $ and $ {f}^2_{{\bf z},\lambda} $
Figure 4.  Lyapunov function using Algorithm 2 with 360 points
Figure 5.  Lyapunov function using Algorithm 2 with 1520 points
Figure 6.  Orbital derivative of the Lyapunov function with respect to the original system using Algorithm 2 with 360 points
Figure 7.  Orbital derivative of the Lyapunov function with respect to the original system using Algorithm 2 with 1520 points
[1]

Peter Giesl. Construction of a global Lyapunov function using radial basis functions with a single operator. Discrete & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049

[6]

Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33

[7]

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

[8]

Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453

[9]

Antonio Cañada, Salvador Villegas. Lyapunov inequalities for partial differential equations at radial higher eigenvalues. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 111-122. doi: 10.3934/dcds.2013.33.111

[10]

Jeremy Levesley, Xinping Sun, Fahd Jarad, Alexander Kushpel. Interpolation of exponential-type functions on a uniform grid by shifts of a basis function. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020403

[11]

Weidong Zhao, Jinlei Wang, Shige Peng. Error estimates of the $\theta$-scheme for backward stochastic differential equations. Discrete & Continuous Dynamical Systems - B, 2009, 12 (4) : 905-924. doi: 10.3934/dcdsb.2009.12.905

[12]

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 & Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225

[13]

M. P. de Oliveira. On 3-graded Lie algebras, Jordan pairs and the canonical kernel function. Electronic Research Announcements, 2003, 9: 142-151.

[14]

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

[15]

Łukasz Struski, Jacek Tabor. Expansivity implies existence of Hölder continuous Lyapunov function. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3575-3589. doi: 10.3934/dcdsb.2017180

[16]

Peter Giesl. Construction of a finite-time Lyapunov function by meshless collocation. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2387-2412. doi: 10.3934/dcdsb.2012.17.2387

[17]

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 & Continuous Dynamical Systems - B, 2019, 24 (8) : 4247-4269. doi: 10.3934/dcdsb.2019080

[18]

Piermarco Cannarsa, Peter R. Wolenski. Semiconcavity of the value function for a class of differential inclusions. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 453-466. doi: 10.3934/dcds.2011.29.453

[19]

Sun Yi, Patrick W. Nelson, A. Galip Ulsoy. Delay differential equations via the matrix lambert w function and bifurcation analysis: application to machine tool chatter. Mathematical Biosciences & Engineering, 2007, 4 (2) : 355-368. doi: 10.3934/mbe.2007.4.355

[20]

Juan Li, Wenqiang Li. Controlled reflected mean-field backward stochastic differential equations coupled with value function and related PDEs. Mathematical Control & Related Fields, 2015, 5 (3) : 501-516. doi: 10.3934/mcrf.2015.5.501

 Impact Factor: 

Article outline

Figures and Tables

[Back to Top]