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]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443

[2]

Liam Burrows, Weihong Guo, Ke Chen, Francesco Torella. Reproducible kernel Hilbert space based global and local image segmentation. Inverse Problems & Imaging, 2021, 15 (1) : 1-25. doi: 10.3934/ipi.2020048

[3]

Petr Čoupek, María J. Garrido-Atienza. Bilinear equations in Hilbert space driven by paths of low regularity. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 121-154. doi: 10.3934/dcdsb.2020230

[4]

Alberto Bressan, Wen Shen. A posteriori error estimates for self-similar solutions to the Euler equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 113-130. doi: 10.3934/dcds.2020168

[5]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463

[6]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296

[7]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117

[8]

Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021  doi: 10.3934/nhm.2021004

[9]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089

[10]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[11]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

[12]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021011

[13]

Madhurima Mukhopadhyay, Palash Sarkar, Shashank Singh, Emmanuel Thomé. New discrete logarithm computation for the medium prime case using the function field sieve. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020119

[14]

Kateřina Škardová, Tomáš Oberhuber, Jaroslav Tintěra, Radomír Chabiniok. Signed-distance function based non-rigid registration of image series with varying image intensity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1145-1160. doi: 10.3934/dcdss.2020386

[15]

Huiying Fan, Tao Ma. Parabolic equations involving Laguerre operators and weighted mixed-norm estimates. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5487-5508. doi: 10.3934/cpaa.2020249

[16]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377

[17]

Boris Andreianov, Mohamed Maliki. On classes of well-posedness for quasilinear diffusion equations in the whole space. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 505-531. doi: 10.3934/dcdss.2020361

[18]

Lorenzo Zambotti. A brief and personal history of stochastic partial differential equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 471-487. doi: 10.3934/dcds.2020264

[19]

Fabio Camilli, Giulia Cavagnari, Raul De Maio, Benedetto Piccoli. Superposition principle and schemes for measure differential equations. Kinetic & Related Models, 2021, 14 (1) : 89-113. doi: 10.3934/krm.2020050

[20]

Md. Masum Murshed, Kouta Futai, Masato Kimura, Hirofumi Notsu. Theoretical and numerical studies for energy estimates of the shallow water equations with a transmission boundary condition. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1063-1078. doi: 10.3934/dcdss.2020230

 Impact Factor: 

Metrics

  • PDF downloads (221)
  • HTML views (396)
  • Cited by (1)

[Back to Top]