# American Institute of Mathematical Sciences

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] Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190 [2] Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136 [3] Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008 [4] Jaume Llibre, Luci Any Roberto. On the periodic solutions of a class of Duffing differential equations. Discrete & Continuous Dynamical Systems - A, 2013, 33 (1) : 277-282. doi: 10.3934/dcds.2013.33.277 [5] Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203 [6] Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450 [7] Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200 [8] Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192 [9] Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175 [10] Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 [11] Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027 [12] Gelasio Salaza, Edgardo Ugalde, Jesús Urías. Master--slave synchronization of affine cellular automaton pairs. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 491-502. doi: 10.3934/dcds.2005.13.491 [13] Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056 [14] Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 [15] Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 [16] Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055 [17] W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 [18] Gheorghe Craciun, Abhishek Deshpande, Hyejin Jenny Yeon. Quasi-toric differential inclusions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2343-2359. doi: 10.3934/dcdsb.2020181 [19] Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094 [20] Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

Impact Factor: