June  2015, 2(2): 227-246. doi: 10.3934/jcd.2015004

Computing continuous and piecewise affine lyapunov functions for nonlinear systems

1. 

School of Science and Engineering, Reykjavik University, Menntavegi 1, Reykjavik, IS-101

2. 

School of Electrical Engineering and Computer Science, University of Newcastle, Callaghan, New South Wales 2308

3. 

School of Mathematics and Physics, Chinese University of Geosciences (Wuhan), 430074, Wuhan

Received  June 2015 Revised  March 2016 Published  May 2016

We present a numerical technique for the computation of a Lyapunov function for nonlinear systems with an asymptotically stable equilibrium point. The proposed approach constructs a partition of the state space, called a triangulation, and then computes values at the vertices of the triangulation using a Lyapunov function from a classical converse Lyapunov theorem due to Yoshizawa. A simple interpolation of the vertex values then yields a Continuous and Piecewise Affine (CPA) function. Verification that the obtained CPA function is a Lyapunov function is shown to be equivalent to verification of several simple inequalities. Numerical examples are presented demonstrating different aspects of the proposed method.
Citation: Sigurdur F. Hafstein, Christopher M. Kellett, Huijuan Li. Computing continuous and piecewise affine lyapunov functions for nonlinear systems. Journal of Computational Dynamics, 2015, 2 (2) : 227-246. doi: 10.3934/jcd.2015004
References:
[1]

R. Baier, L. Grüne and S. Hafstein, Linear programming based Lyapunov function computation for differential inclusions,, Discrete and Continuous Dynamical Systems Series B, 17 (2012), 33.  doi: 10.3934/dcdsb.2012.17.33.  Google Scholar

[2]

H. Ban and W. Kalies, A computational approach to Conley's decomposition theorem,, Journal of Computational and Nonlinear Dynamics, 1 (2006), 312.  doi: 10.1115/1.2338651.  Google Scholar

[3]

J. Björnsson, P. Giesl and S. Hafstein, Algorithmic verification of approximations to complete Lyapunov functions,, In Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, (2014), 1181.   Google Scholar

[4]

J. Björnsson, P. Giesl, S. Hafstein, C. M. Kellett and H. Li, Computation of continuous and piecewise affine Lyapunov functions by numerical approximations of the Massera construction,, In Proceedings of the 53rd IEEE Conference on Decision and Control, (2014), 5506.   Google Scholar

[5]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions,, Number 1904 in Lecture Notes in Mathematics. Springer, (1904).   Google Scholar

[6]

P. Giesl and S. Hafstein, Existence of piecewise affine Lyapunov functions in two dimensions,, J. Math. Anal. Appl., 371 (2010), 233.  doi: 10.1016/j.jmaa.2010.05.009.  Google Scholar

[7]

P. Giesl and S. Hafstein, Construction of Lyapunov functions for nonlinear planar systems by linear programming,, Journal of Mathematical Analysis and Applications, 388 (2012), 463.  doi: 10.1016/j.jmaa.2011.10.047.  Google Scholar

[8]

P. Giesl and S. Hafstein, Existence of piecewise affine Lyapunov functions in arbitrary dimensions,, Discrete and Contin. Dyn. Syst., 32 (2012), 3539.  doi: 10.3934/dcds.2012.32.3539.  Google Scholar

[9]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems,, Journal of Mathematical Analysis and Applications, 410 (2014), 292.  doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[10]

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

[11]

P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions,, Discrete and Continuous Dynamical Systems Series B, 20 (2015), 2291.  doi: 10.3934/dcdsb.2015.20.2291.  Google Scholar

[12]

S. Hafstein, An Algorithm for Constructing Lyapunov Functions,, Electronic Journal of Differential Equations Mongraphs, (2007).   Google Scholar

[13]

S. Hafstein, C. M. Kellett and H. Li, Continuous and piecewise affine Lyapunov functions using the Yoshizawa construction,, In Proceedings of the American Control Conference, (2014), 548.  doi: 10.1109/ACC.2014.6858660.  Google Scholar

[14]

W. Hahn, Stability of Motion,, Springer-Verlag, (1967).   Google Scholar

[15]

T. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization,, Automatica, 36 (2000), 1617.  doi: 10.1016/S0005-1098(00)00088-1.  Google Scholar

[16]

W. Kalies, K. Mischaikow and R. VanderVorst, An algorithmic approach to chain recurrence,, Foundations of Computational Mathematics, 5 (2005), 409.  doi: 10.1007/s10208-004-0163-9.  Google Scholar

[17]

C. M. Kellett, A compendium of comparsion function results,, Mathematics of Controls, 26 (2014), 339.  doi: 10.1007/s00498-014-0128-8.  Google Scholar

[18]

C. M. Kellett, Classical converse theorems in Lyapunov's second method,, Discrete and Continuous Dynamical Systems Series B, 20 (2015), 2333.  doi: 10.3934/dcdsb.2015.20.2333.  Google Scholar

[19]

J. Kurzweil, On the inversion of Ljapunov's second theorem on stability of motion,, Chechoslovak Mathematics Journal, 81 (1956), 217.   Google Scholar

[20]

H. Li, S. Hafstein and C. M. Kellett, Computation of continuous and piecewise affine Lyapunov functions for discrete-time systems,, J Differ Equ Appl, 21 (2015), 486.  doi: 10.1080/10236198.2015.1025069.  Google Scholar

[21]

A. M. Lyapunov, The general problem of the stability of motion,, Math. Soc. of Kharkov, 55 (1992), 521.  doi: 10.1080/00207179208934253.  Google Scholar

[22]

S. Marinosson, Lyapunov function construction for ordinary differential equations with linear programming,, Dynamical Systems, 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar

[23]

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

[24]

A. Papachristodoulou and S. Prajna, The construction of Lyapunov functions using the sum of squares decomposition,, In Proceedings of the 41st IEEE Conference on Decision and Control, 3 (2002), 3482.  doi: 10.1109/CDC.2002.1184414.  Google Scholar

[25]

M. Peet and A. Papachristodoulou, A converse sum of squares Lyapunov result with a degree bound,, IEEE Transactions on Automatic Control, 57 (2012), 2281.  doi: 10.1109/TAC.2012.2190163.  Google Scholar

[26]

N. Rouche, P. Habets and M. Laloy, Stability Theory by Liapunov's Direct Method,, Springer-Verlag, (1977).   Google Scholar

[27]

E. D. Sontag, Comments on integral variants of ISS,, Systems and Control Letters, 34 (1998), 93.  doi: 10.1016/S0167-6911(98)00003-6.  Google Scholar

[28]

A. R. Teel and L. Praly, A smooth Lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions,, ESAIM Control Optim. Calc. Var., 5 (2000), 313.  doi: 10.1051/cocv:2000113.  Google Scholar

[29]

T. Yoshizawa, On the stability of solutions of a system of differential equations,, Memoirs of the College of Science, 29 (1955), 27.   Google Scholar

[30]

T. Yoshizawa, Stability Theory by Liapunov's Second Method,, Mathematical Society of Japan, (1966).   Google Scholar

show all references

References:
[1]

R. Baier, L. Grüne and S. Hafstein, Linear programming based Lyapunov function computation for differential inclusions,, Discrete and Continuous Dynamical Systems Series B, 17 (2012), 33.  doi: 10.3934/dcdsb.2012.17.33.  Google Scholar

[2]

H. Ban and W. Kalies, A computational approach to Conley's decomposition theorem,, Journal of Computational and Nonlinear Dynamics, 1 (2006), 312.  doi: 10.1115/1.2338651.  Google Scholar

[3]

J. Björnsson, P. Giesl and S. Hafstein, Algorithmic verification of approximations to complete Lyapunov functions,, In Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, (2014), 1181.   Google Scholar

[4]

J. Björnsson, P. Giesl, S. Hafstein, C. M. Kellett and H. Li, Computation of continuous and piecewise affine Lyapunov functions by numerical approximations of the Massera construction,, In Proceedings of the 53rd IEEE Conference on Decision and Control, (2014), 5506.   Google Scholar

[5]

P. Giesl, Construction of Global Lyapunov Functions Using Radial Basis Functions,, Number 1904 in Lecture Notes in Mathematics. Springer, (1904).   Google Scholar

[6]

P. Giesl and S. Hafstein, Existence of piecewise affine Lyapunov functions in two dimensions,, J. Math. Anal. Appl., 371 (2010), 233.  doi: 10.1016/j.jmaa.2010.05.009.  Google Scholar

[7]

P. Giesl and S. Hafstein, Construction of Lyapunov functions for nonlinear planar systems by linear programming,, Journal of Mathematical Analysis and Applications, 388 (2012), 463.  doi: 10.1016/j.jmaa.2011.10.047.  Google Scholar

[8]

P. Giesl and S. Hafstein, Existence of piecewise affine Lyapunov functions in arbitrary dimensions,, Discrete and Contin. Dyn. Syst., 32 (2012), 3539.  doi: 10.3934/dcds.2012.32.3539.  Google Scholar

[9]

P. Giesl and S. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems,, Journal of Mathematical Analysis and Applications, 410 (2014), 292.  doi: 10.1016/j.jmaa.2013.08.014.  Google Scholar

[10]

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

[11]

P. Giesl and S. Hafstein, Review on computational methods for Lyapunov functions,, Discrete and Continuous Dynamical Systems Series B, 20 (2015), 2291.  doi: 10.3934/dcdsb.2015.20.2291.  Google Scholar

[12]

S. Hafstein, An Algorithm for Constructing Lyapunov Functions,, Electronic Journal of Differential Equations Mongraphs, (2007).   Google Scholar

[13]

S. Hafstein, C. M. Kellett and H. Li, Continuous and piecewise affine Lyapunov functions using the Yoshizawa construction,, In Proceedings of the American Control Conference, (2014), 548.  doi: 10.1109/ACC.2014.6858660.  Google Scholar

[14]

W. Hahn, Stability of Motion,, Springer-Verlag, (1967).   Google Scholar

[15]

T. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization,, Automatica, 36 (2000), 1617.  doi: 10.1016/S0005-1098(00)00088-1.  Google Scholar

[16]

W. Kalies, K. Mischaikow and R. VanderVorst, An algorithmic approach to chain recurrence,, Foundations of Computational Mathematics, 5 (2005), 409.  doi: 10.1007/s10208-004-0163-9.  Google Scholar

[17]

C. M. Kellett, A compendium of comparsion function results,, Mathematics of Controls, 26 (2014), 339.  doi: 10.1007/s00498-014-0128-8.  Google Scholar

[18]

C. M. Kellett, Classical converse theorems in Lyapunov's second method,, Discrete and Continuous Dynamical Systems Series B, 20 (2015), 2333.  doi: 10.3934/dcdsb.2015.20.2333.  Google Scholar

[19]

J. Kurzweil, On the inversion of Ljapunov's second theorem on stability of motion,, Chechoslovak Mathematics Journal, 81 (1956), 217.   Google Scholar

[20]

H. Li, S. Hafstein and C. M. Kellett, Computation of continuous and piecewise affine Lyapunov functions for discrete-time systems,, J Differ Equ Appl, 21 (2015), 486.  doi: 10.1080/10236198.2015.1025069.  Google Scholar

[21]

A. M. Lyapunov, The general problem of the stability of motion,, Math. Soc. of Kharkov, 55 (1992), 521.  doi: 10.1080/00207179208934253.  Google Scholar

[22]

S. Marinosson, Lyapunov function construction for ordinary differential equations with linear programming,, Dynamical Systems, 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar

[23]

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

[24]

A. Papachristodoulou and S. Prajna, The construction of Lyapunov functions using the sum of squares decomposition,, In Proceedings of the 41st IEEE Conference on Decision and Control, 3 (2002), 3482.  doi: 10.1109/CDC.2002.1184414.  Google Scholar

[25]

M. Peet and A. Papachristodoulou, A converse sum of squares Lyapunov result with a degree bound,, IEEE Transactions on Automatic Control, 57 (2012), 2281.  doi: 10.1109/TAC.2012.2190163.  Google Scholar

[26]

N. Rouche, P. Habets and M. Laloy, Stability Theory by Liapunov's Direct Method,, Springer-Verlag, (1977).   Google Scholar

[27]

E. D. Sontag, Comments on integral variants of ISS,, Systems and Control Letters, 34 (1998), 93.  doi: 10.1016/S0167-6911(98)00003-6.  Google Scholar

[28]

A. R. Teel and L. Praly, A smooth Lyapunov function from a class-$\mathcal{KL}$ estimate involving two positive semidefinite functions,, ESAIM Control Optim. Calc. Var., 5 (2000), 313.  doi: 10.1051/cocv:2000113.  Google Scholar

[29]

T. Yoshizawa, On the stability of solutions of a system of differential equations,, Memoirs of the College of Science, 29 (1955), 27.   Google Scholar

[30]

T. Yoshizawa, Stability Theory by Liapunov's Second Method,, Mathematical Society of Japan, (1966).   Google Scholar

[1]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006

[2]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378

[3]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331

[4]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

[5]

Bimal Mandal, Aditi Kar Gangopadhyay. A note on generalization of bent boolean functions. Advances in Mathematics of Communications, 2021, 15 (2) : 329-346. doi: 10.3934/amc.2020069

[6]

Andreas Koutsogiannis. Multiple ergodic averages for tempered functions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1177-1205. doi: 10.3934/dcds.2020314

[7]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[8]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098

[9]

Yu Zhou, Xinfeng Dong, Yongzhuang Wei, Fengrong Zhang. A note on the Signal-to-noise ratio of $ (n, m) $-functions. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020117

[10]

Tahir Aliyev Azeroğlu, Bülent Nafi Örnek, Timur Düzenli. Some results on the behaviour of transfer functions at the right half plane. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020106

[11]

Meenakshi Rana, Shruti Sharma. Combinatorics of some fifth and sixth order mock theta functions. Electronic Research Archive, 2021, 29 (1) : 1803-1818. doi: 10.3934/era.2020092

[12]

Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020125

[13]

Tomasz Szostok. Inequalities of Hermite-Hadamard type for higher order convex functions, revisited. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020296

[14]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

[15]

Tuoc Phan, Grozdena Todorova, Borislav Yordanov. Existence uniqueness and regularity theory for elliptic equations with complex-valued potentials. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1071-1099. doi: 10.3934/dcds.2020310

[16]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, 2021, 14 (1) : 115-148. doi: 10.3934/krm.2020051

[17]

Isabeau Birindelli, Françoise Demengel, Fabiana Leoni. Boundary asymptotics of the ergodic functions associated with fully nonlinear operators through a Liouville type theorem. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020395

[18]

Arthur Fleig, Lars Grüne. Strict dissipativity analysis for classes of optimal control problems involving probability density functions. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020053

[19]

Chunming Tang, Maozhi Xu, Yanfeng Qi, Mingshuo Zhou. A new class of $ p $-ary regular bent functions. Advances in Mathematics of Communications, 2021, 15 (1) : 55-64. doi: 10.3934/amc.2020042

[20]

Sugata Gangopadhyay, Constanza Riera, Pantelimon Stănică. Gowers $ U_2 $ norm as a measure of nonlinearity for Boolean functions and their generalizations. Advances in Mathematics of Communications, 2021, 15 (2) : 241-256. doi: 10.3934/amc.2020056

 Impact Factor: 

Metrics

  • PDF downloads (71)
  • HTML views (0)
  • Cited by (6)

[Back to Top]