American Institute of Mathematical Sciences

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

Computing continuous and piecewise affine lyapunov functions for nonlinear systems

Sigurdur F. Hafstein 1, , Christopher M. Kellett 2, and  Huijuan Li 3,

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.
Keywords: Lyapunov functions, continuous and piecewise affine functions, computational techniques stability theory, ordinary differential equations..
Mathematics Subject Classification: Primary: 93D05, 93D30, 93D20; Secondary: 93D1.
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]

Peter Giesl, Sigurdur Hafstein. Computational methods for Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : i-ii. doi: 10.3934/dcdsb.2015.20.8i
[2]

Luis Barreira, Claudia Valls. Stability of nonautonomous equations and Lyapunov functions. Discrete & Continuous Dynamical Systems - A, 2013, 33 (7) : 2631-2650. doi: 10.3934/dcds.2013.33.2631
[3]

Peter Giesl, Sigurdur Hafstein. Review on computational methods for Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2291-2331. doi: 10.3934/dcdsb.2015.20.2291
[4]

Volodymyr Pichkur. On practical stability of differential inclusions using Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (5) : 1977-1986. doi: 10.3934/dcdsb.2017116
[5]

Jean Mawhin, James R. Ward Jr. Guiding-like functions for periodic or bounded solutions of ordinary differential equations. Discrete & Continuous Dynamical Systems - A, 2002, 8 (1) : 39-54. doi: 10.3934/dcds.2002.8.39
[6]

Peter Giesl, Sigurdur Hafstein. Existence of piecewise linear Lyapunov functions in arbitrary dimensions. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3539-3565. doi: 10.3934/dcds.2012.32.3539
[7]

Frédéric Mazenc, Christophe Prieur. Strict Lyapunov functions for semilinear parabolic partial differential equations. Mathematical Control & Related Fields, 2011, 1 (2) : 231-250. doi: 10.3934/mcrf.2011.1.231
[8]

Huijuan Li, Junxia Wang. Input-to-state stability of continuous-time systems via finite-time Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019192
[9]

Yulan Lu, Minghui Song, Mingzhu Liu. Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 695-717. doi: 10.3934/dcdsb.2018203
[10]

Olaf Klein. On the representation of hysteresis operators acting on vector-valued, left-continuous and piecewise monotaffine and continuous functions. Discrete & Continuous Dynamical Systems - A, 2015, 35 (6) : 2591-2614. doi: 10.3934/dcds.2015.35.2591
[11]

Michael Schönlein. Asymptotic stability and smooth Lyapunov functions for a class of abstract dynamical systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 4053-4069. doi: 10.3934/dcds.2017172
[12]

Deqiong Ding, Wendi Qin, Xiaohua Ding. Lyapunov functions and global stability for a discretized multigroup SIR epidemic model. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 1971-1981. doi: 10.3934/dcdsb.2015.20.1971
[13]

Marat Akhmet, Duygu Aruğaslan. Lyapunov-Razumikhin method for differential equations with piecewise constant argument. Discrete & Continuous Dynamical Systems - A, 2009, 25 (2) : 457-466. doi: 10.3934/dcds.2009.25.457
[14]

Dag Lukkassen, Annette Meidell, Peter Wall. On the conjugate of periodic piecewise harmonic functions. Networks & Heterogeneous Media, 2008, 3 (3) : 633-646. doi: 10.3934/nhm.2008.3.633
[15]

F. M. G. Magpantay, A. R. Humphries. Generalised Lyapunov-Razumikhin techniques for scalar state-dependent delay differential equations. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 85-104. doi: 10.3934/dcdss.2020005
[16]

Ian D. Morris. Ergodic optimization for generic continuous functions. Discrete & Continuous Dynamical Systems - A, 2010, 27 (1) : 383-388. doi: 10.3934/dcds.2010.27.383
[17]

Xifeng Su, Lin Wang, Jun Yan. Weak KAM theory for HAMILTON-JACOBI equations depending on unknown functions. Discrete & Continuous Dynamical Systems - A, 2016, 36 (11) : 6487-6522. doi: 10.3934/dcds.2016080
[18]

Andrey V. Melnik, Andrei Korobeinikov. Lyapunov functions and global stability for SIR and SEIR models with age-dependent susceptibility. Mathematical Biosciences & Engineering, 2013, 10 (2) : 369-378. doi: 10.3934/mbe.2013.10.369
[19]

Luis Barreira, César Silva. Lyapunov exponents for continuous transformations and dimension theory. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 469-490. doi: 10.3934/dcds.2005.13.469
[20]

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

 Impact Factor: 

Tools

Metrics

  • PDF downloads (15)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences