December  2021, 26(12): 6027-6046. doi: 10.3934/dcdsb.2020378

System specific triangulations for the construction of CPA Lyapunov functions

1. 

Department of Mathematics, University of Sussex, Falmer BN1 9QH, United Kingdom

2. 

Faculty of Physical Sciences, University of Iceland, 107 Reykjavik, Iceland

Received  September 2020 Published  December 2021 Early access  December 2020

Fund Project: The research in this paper was partly supported by the Icelandic Research Fund (Ranní s) grant number 163074-052, Complete Lyapunov functions: Efficient numerical computation

Recently, a transformation of the vertices of a regular triangulation of $ {\mathbb {R}}^n $ with vertices in the lattice $ \mathbb{Z}^n $ was introduced, which distributes the vertices with approximate rotational symmetry properties around the origin. We prove that the simplices of the transformed triangulation are $ (h, d) $-bounded, a type of non-degeneracy particularly useful in the numerical computation of Lyapunov functions for nonlinear systems using the CPA (continuous piecewise affine) method. Additionally, we discuss and give examples of how this transformed triangulation can be used together with a Lyapunov function for a linearization to compute a Lyapunov function for a nonlinear system with the CPA method using considerably fewer simplices than when using a regular triangulation.

Citation: Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete and Continuous Dynamical Systems - B, 2021, 26 (12) : 6027-6046. doi: 10.3934/dcdsb.2020378
References:
[1]

S. AlbertssonP. GieslS. Gudmundsson and S. Hafstein, Simplicial complex with approximate rotational symmetry: A general class of simplicial complexes, J. Comput. Appl. Math., 363 (2020), 413-425.  doi: 10.1016/j.cam.2019.06.019.

[2]

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.

[3]

J. Björnsson, S. Gudmundsson and S. Hafstein, Class library in C++ to compute Lyapunov functions for nonlinear systems, In Proceedings of MICNON, 1st Conference on Modelling, Identification and Control of Nonlinear Systems, no. 0155, 2015,788–793.

[4]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Math., vol. 1904, Springer, Berlin, 2007.

[5]

P. Giesl and S. Hafstein, Implementation of a fan-like triangulation for the CPA method to compute Lyapunov functions, In Proceedings of the 2014 American Control Conference, Portland, OR, 2014, 2989–2994. doi: 10.1016/j.jmaa.2013.08.014.

[6]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems, J. Math. Anal. Appl., 410 (2014), 292-306.  doi: 10.1016/j.jmaa.2013.08.014.

[7]

P. Giesl and S. Hafstein, Computation and verification of Lyapunov functions, SIAM J. Appl. Dyn. Syst., 14 (2015), 1663-1698.  doi: 10.1137/140988802.

[8]

P. Giesl and S. Hafstein, Review of computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2291-2331.  doi: 10.3934/dcdsb.2015.20.2291.

[9] G. Golub and C. van Loan, Matrix Computations, 4th edition, John Hopkins University Press, Baltimore, MD, 2013. 
[10]

S. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete Contin. Dyn. Syst., 10 (2004), 657-678.  doi: 10.3934/dcds.2004.10.657.

[11]

S. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dyn. Syst., 20 (2005), 281-299.  doi: 10.1080/14689360500164873.

[12]

S. Hafstein, Implementation of simplicial complexes for CPA functions in C++11 using the armadillo linear algebra library, In Proceedings of the 3rd International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH), Reykjavik, Iceland, 2013, 49–57.

[13]

S. Hafstein, Simulation and Modeling Methodologies, Technologies and Applications, volume 873 of Advances in Intelligent Systems and Computing, chapter Fast Algorithms for Computing Continuous Piecewise Affine Lyapunov Functions, Springer, 2019,274–299.

[14]

S. Hafstein and A. Valfells, Study of dynamical systems by fast numerical computation of Lyapunov functions, In Proceedings of the 14th International Conference on Dynamical Systems: Theory and Applications (DSTA), Mathematical and Numerical Aspects of Dynamical System Analysis, 2017,220–240.

[15]

W. Hahn, Stability of Motion, Springer-Verlag New York, Inc., New York, 1967.

[16]

R. Kamyar and M. Peet, Polynomial optimization with applications to stability analysis and control – alternatives to sum of squares, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2383-2417.  doi: 10.3934/dcdsb.2015.20.2383.

[17]

H. Khalil, Nonlinear Systems, 3rd edition, Pearson, 2002.

[18]

A. M. Lyapunov, The general problem of the stability of motion, Internat. J. Control, 55 (1992), 521-790.  doi: 10.1080/00207179208934253.

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150.  doi: 10.1080/0268111011011847.

[20]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimiza, Ph.D thesis, California Institute of Technology, Pasadena, California, 2000.

[21]

S. Ratschan and Z. She, Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions, SIAM J. Control Optim., 48 (2010), 4377-4394.  doi: 10.1137/090749955.

[22]

S. Sastry, Nonlinear Systems: Analysis, Stability, and Control, Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-3108-8.

[23]

J. Sherman and W. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics, 21 (1950), 124-127.  doi: 10.1214/aoms/1177729893.

[24]

G. Valmorbida and J. Anderson, Region of attraction estimation using invariant sets and rational Lyapunov functions, Automatica J. IFAC, 75 (2017), 37-45.  doi: 10.1016/j.automatica.2016.09.003.

[25]

A. Vannelli and M. Vidyasagar, Maximal Lyapunov functions and domains of attraction for autonomous nonlinear systems, Automatica J. IFAC, 21 (1985), 69-80.  doi: 10.1016/0005-1098(85)90099-8.

[26]

M. Vidyasagar, Nonlinear System Analysis, 2nd edition, Classics in Applied Mathematics, vol. 42, SIAM, Philadelphia, PA, 2002. doi: 10.1137/1.9780898719185.

[27]

T. Yoshizawa, Stability Theory by Liapunov's Second Method, Publications of the Mathematical Society of Japan, No. 9. The Mathematical Society of Japan, Tokyo, 1966.

[28]

V. I. Zubov, Methods of A. M. Lyapunov and Their Application, P. Noordhoff Ltd., Groningen, 1964.

show all references

References:
[1]

S. AlbertssonP. GieslS. Gudmundsson and S. Hafstein, Simplicial complex with approximate rotational symmetry: A general class of simplicial complexes, J. Comput. Appl. Math., 363 (2020), 413-425.  doi: 10.1016/j.cam.2019.06.019.

[2]

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.

[3]

J. Björnsson, S. Gudmundsson and S. Hafstein, Class library in C++ to compute Lyapunov functions for nonlinear systems, In Proceedings of MICNON, 1st Conference on Modelling, Identification and Control of Nonlinear Systems, no. 0155, 2015,788–793.

[4]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions, Lecture Notes in Math., vol. 1904, Springer, Berlin, 2007.

[5]

P. Giesl and S. Hafstein, Implementation of a fan-like triangulation for the CPA method to compute Lyapunov functions, In Proceedings of the 2014 American Control Conference, Portland, OR, 2014, 2989–2994. doi: 10.1016/j.jmaa.2013.08.014.

[6]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems, J. Math. Anal. Appl., 410 (2014), 292-306.  doi: 10.1016/j.jmaa.2013.08.014.

[7]

P. Giesl and S. Hafstein, Computation and verification of Lyapunov functions, SIAM J. Appl. Dyn. Syst., 14 (2015), 1663-1698.  doi: 10.1137/140988802.

[8]

P. Giesl and S. Hafstein, Review of computational methods for Lyapunov functions, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2291-2331.  doi: 10.3934/dcdsb.2015.20.2291.

[9] G. Golub and C. van Loan, Matrix Computations, 4th edition, John Hopkins University Press, Baltimore, MD, 2013. 
[10]

S. Hafstein, A constructive converse Lyapunov theorem on exponential stability, Discrete Contin. Dyn. Syst., 10 (2004), 657-678.  doi: 10.3934/dcds.2004.10.657.

[11]

S. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dyn. Syst., 20 (2005), 281-299.  doi: 10.1080/14689360500164873.

[12]

S. Hafstein, Implementation of simplicial complexes for CPA functions in C++11 using the armadillo linear algebra library, In Proceedings of the 3rd International Conference on Simulation and Modeling Methodologies, Technologies and Applications (SIMULTECH), Reykjavik, Iceland, 2013, 49–57.

[13]

S. Hafstein, Simulation and Modeling Methodologies, Technologies and Applications, volume 873 of Advances in Intelligent Systems and Computing, chapter Fast Algorithms for Computing Continuous Piecewise Affine Lyapunov Functions, Springer, 2019,274–299.

[14]

S. Hafstein and A. Valfells, Study of dynamical systems by fast numerical computation of Lyapunov functions, In Proceedings of the 14th International Conference on Dynamical Systems: Theory and Applications (DSTA), Mathematical and Numerical Aspects of Dynamical System Analysis, 2017,220–240.

[15]

W. Hahn, Stability of Motion, Springer-Verlag New York, Inc., New York, 1967.

[16]

R. Kamyar and M. Peet, Polynomial optimization with applications to stability analysis and control – alternatives to sum of squares, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015), 2383-2417.  doi: 10.3934/dcdsb.2015.20.2383.

[17]

H. Khalil, Nonlinear Systems, 3rd edition, Pearson, 2002.

[18]

A. M. Lyapunov, The general problem of the stability of motion, Internat. J. Control, 55 (1992), 521-790.  doi: 10.1080/00207179208934253.

[19]

S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dyn. Syst., 17 (2002), 137-150.  doi: 10.1080/0268111011011847.

[20]

P. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimiza, Ph.D thesis, California Institute of Technology, Pasadena, California, 2000.

[21]

S. Ratschan and Z. She, Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions, SIAM J. Control Optim., 48 (2010), 4377-4394.  doi: 10.1137/090749955.

[22]

S. Sastry, Nonlinear Systems: Analysis, Stability, and Control, Springer-Verlag, New York, 1999. doi: 10.1007/978-1-4757-3108-8.

[23]

J. Sherman and W. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics, 21 (1950), 124-127.  doi: 10.1214/aoms/1177729893.

[24]

G. Valmorbida and J. Anderson, Region of attraction estimation using invariant sets and rational Lyapunov functions, Automatica J. IFAC, 75 (2017), 37-45.  doi: 10.1016/j.automatica.2016.09.003.

[25]

A. Vannelli and M. Vidyasagar, Maximal Lyapunov functions and domains of attraction for autonomous nonlinear systems, Automatica J. IFAC, 21 (1985), 69-80.  doi: 10.1016/0005-1098(85)90099-8.

[26]

M. Vidyasagar, Nonlinear System Analysis, 2nd edition, Classics in Applied Mathematics, vol. 42, SIAM, Philadelphia, PA, 2002. doi: 10.1137/1.9780898719185.

[27]

T. Yoshizawa, Stability Theory by Liapunov's Second Method, Publications of the Mathematical Society of Japan, No. 9. The Mathematical Society of Japan, Tokyo, 1966.

[28]

V. I. Zubov, Methods of A. M. Lyapunov and Their Application, P. Noordhoff Ltd., Groningen, 1964.

Figure 1.  Left: The triangulation $ {\mathcal T}^\text{ std}_{K} $, $ K = 4 $, with a triangle fan at the origin. Right: The transformed approximately rotationally symmetric triangulation $ {\mathcal T}_{\Phi, K} $
Figure 2.  The vertices of the triangulations of Figure 1, right, are mapped by the linear transformation $ {\bf x} \mapsto P^{-\frac{1}{2}} {\bf x} $, where $ P^{-\frac{1}{2}} $ is a symmetric and positive definite matrix. This triangulation is adapted to the structure of the system with a local Lyapunov function $ V( {\bf x}) = {\bf x}^\text{T}P {\bf x} $
Figure 3.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.3 $ using a rectangular grid. Right: The rectangular grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures
Figure 4.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.3 $ using a transformed grid. Right: The transformed grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures. Note that the triangulation is much better adapted to the shape of the level-sets than when using a rectangular grid as in Figure 3
Figure 5.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.4 $ using a rectangular grid. Right: The rectangular grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures
Figure 6.  Left: CPA Lyapunov function for system (3.1) with $ \alpha = 0.5 $ and $ \beta = -0.4 $ using a transformed grid. Right: The transformed grid, with a triangle fan at the origin, used for the computation. Level-sets of the Lyapunov function are drawn in red on both figures. Note that the triangulation is much better adapted to the shape of the level-sets than when using a rectangular grid as in Figure 5. Both the area covered by the triangle fan, in both cases with $ 64 $ triangles, as well as the area covered overall are much larger than when using the rectangular grid, see Figure 5
[1]

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

[2]

Andrey Kochergin. A Besicovitch cylindrical transformation with Hölder function. Electronic Research Announcements, 2015, 22: 87-91. doi: 10.3934/era.2015.22.87

[3]

Martin Gugat, Günter Leugering, Ke Wang. Neumann boundary feedback stabilization for a nonlinear wave equation: A strict $H^2$-lyapunov function. Mathematical Control and Related Fields, 2017, 7 (3) : 419-448. doi: 10.3934/mcrf.2017015

[4]

Hongming Yang, C. Y. Chung, Xiaojiao Tong, Pingping Bing. Research on dynamic equilibrium of power market with complex network constraints based on nonlinear complementarity function. Journal of Industrial and Management Optimization, 2008, 4 (3) : 617-630. doi: 10.3934/jimo.2008.4.617

[5]

Justyna Szpond, Grzegorz Malara. The containment problem and a rational simplicial arrangement. Electronic Research Announcements, 2017, 24: 123-128. doi: 10.3934/era.2017.24.013

[6]

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

[7]

Ł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

[8]

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

[9]

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

[10]

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

[11]

Kanji Inui, Hikaru Okada, Hiroki Sumi. The Hausdorff dimension function of the family of conformal iterated function systems of generalized complex continued fractions. Discrete and Continuous Dynamical Systems, 2020, 40 (2) : 753-766. doi: 10.3934/dcds.2020060

[12]

Jianquan Li, Yicang Zhou, Jianhong Wu, Zhien Ma. Complex dynamics of a simple epidemic model with a nonlinear incidence. Discrete and Continuous Dynamical Systems - B, 2007, 8 (1) : 161-173. doi: 10.3934/dcdsb.2007.8.161

[13]

Tsuyoshi Kajiwara, Toru Sasaki, Yasuhiro Takeuchi. Construction of Lyapunov functions for some models of infectious diseases in vivo: From simple models to complex models. Mathematical Biosciences & Engineering, 2015, 12 (1) : 117-133. doi: 10.3934/mbe.2015.12.117

[14]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[15]

Zhiyou Wu, Fusheng Bai, Guoquan Li, Yongjian Yang. A new auxiliary function method for systems of nonlinear equations. Journal of Industrial and Management Optimization, 2015, 11 (2) : 345-364. doi: 10.3934/jimo.2015.11.345

[16]

Yves Edel, Alexander Pott. A new almost perfect nonlinear function which is not quadratic. Advances in Mathematics of Communications, 2009, 3 (1) : 59-81. doi: 10.3934/amc.2009.3.59

[17]

Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial and Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911

[18]

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

[19]

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

[20]

Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048

2020 Impact Factor: 1.327

Metrics

  • PDF downloads (267)
  • HTML views (417)
  • Cited by (0)

Other articles
by authors

[Back to Top]