# American Institute of Mathematical Sciences

October  2012, 32(10): 3539-3565. doi: 10.3934/dcds.2012.32.3539

## Existence of piecewise linear Lyapunov functions in arbitrary dimensions

 1 Department of Mathematics, University of Sussex, Falmer BN1 9QH, United Kingdom 2 School of Science and Engineering, Reykjavik University, Menntavegi 1, IS-101 Reykjavik, Iceland

Received  May 2011 Revised  October 2011 Published  May 2012

Lyapunov functions are an important tool to determine the basin of attraction of exponentially stable equilibria in dynamical systems. In Marinósson (2002), a method to construct Lyapunov functions was presented, using finite differences on finite elements and thus transforming the construction problem into a linear programming problem. In Hafstein (2004), it was shown that this method always succeeds in constructing a Lyapunov function, except for a small, given neighbourhood of the equilibrium.
For two-dimensional systems, this local problem was overcome by choosing a fan-like triangulation around the equilibrium. In Giesl/Hafstein (2010) the existence of a piecewise linear Lyapunov function was shown, and in Giesl/Hafstein (2012) it was shown that the above method with a fan-like triangulation always succeeds in constructing a Lyapunov function, without any local exception. However, the previous papers only considered two-dimensional systems. This paper generalises the existence of piecewise linear Lyapunov functions to arbitrary dimensions.
Citation: Peter Giesl, Sigurdur Hafstein. Existence of piecewise linear Lyapunov functions in arbitrary dimensions. Discrete & Continuous Dynamical Systems, 2012, 32 (10) : 3539-3565. doi: 10.3934/dcds.2012.32.3539
##### References:
 [1] R. Baier, L. Grüne and S. Hafstein, Linear programming based Lyapunov function computation for differential inclusions, Discrete Contin. Dyn. Syst. Ser. B, 17 (2012), 33-56. doi: 10.3934/dcdsb.2012.17.33.  Google Scholar [2] R. Bartels and G. Stewart, Algorithm 432: Solution of the matrix equation $AX + XB = C$, Comm. ACM, 15 (1972), 820-826. doi: 10.1145/361573.361582.  Google Scholar [3] F. Clarke, "Optimization and Nonsmooth Analysis,'' Second edition, Classics in Applied Mathematics, 5, SIAM, Philadephia, PA, 1990.  Google Scholar [4] A. Garcia and O. Agamennoni, Attraction and stability of nonlinear ODE's using continuous piecewise linear approximations,, submitted., ().   Google Scholar [5] P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions,'' Lecture Notes in Mathematics, 1904, Springer, Berlin, 2007.  Google Scholar [6] P. Giesl and S. Hafstein, Existence of piecewise affine Lyapunov functions in two dimensions, J. Math. Anal. Appl., 371 (2010), 233-248. 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, J. Math. Anal. Appl., 388 (2012), 463-479. doi: 10.1016/j.jmaa.2011.10.047.  Google Scholar [8] 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.  Google Scholar [9] S. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dynamical Systems, 20 (2005), 281-299. doi: 10.1080/14689360500164873.  Google Scholar [10] S. Hafstein, "An Algorithm for Constructing Lyapunov Functions,'' Electron. J. Differential Equ. Monogr., 8, Texas State Univ.-San Marcos, Dep. of Mathematics, San Marcos, TX, 2007. Available from: http://ejde.math.txstate.edu/.  Google Scholar [11] T. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization, Automatica J. IFAC, 36 (2000), 1617-1626. doi: 10.1016/S0005-1098(00)00088-1.  Google Scholar [12] M. Johansson and A. Rantzer, On the computation of piecewise quadratic Lyapunov functions, in "Proceedings of the 36th IEEE Conference on Decision and Control,'' 1997. Google Scholar [13] P. Julian, "A High-Level Canonical Piecewise Linear Representation: Theory and Applications,'' Ph.D. thesis, Universidad Nacional del Sur, Bahia Blanca, Argentina, 1999.  Google Scholar [14] P. Julián, J. Guivant and A. Desages, A parametrization of piecewise linear Lyapunov function via linear programming. Multiple model approaches to modelling and control, Int. Journal of Control, 72 (1999), 702-715.  Google Scholar [15] H. K. Khalil, "Nonlinear Systems,'' 3rd edition, Prentice Hall, New Jersey, 2002. Google Scholar [16] S. Marinósson, "Stability Analysis of Nonlinear Systems with Linear Programming: A Lyapunov Functions Based Approach,'' Ph.D. thesis, Gerhard-Mercator-University, Duisburg, Germany, 2002. Google Scholar [17] S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dynamical Systems, 17 (2002), 137-150. doi: 10.1080/0268111011011847.  Google Scholar [18] 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,'' (2002), 3482-3487. Google Scholar [19] P. Parrilo, "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,'' Ph.D. thesis, Caltech, Pasadena, USA, 2000. Google Scholar [20] M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions, IEEE Trans. Automatic Control, 54 (2009), 979-987. doi: 10.1109/TAC.2009.2017116.  Google Scholar [21] V. Zubov, "Methods of A. M. Lyapunov and Their Application,'' Translation prepared under the auspices of the United States Atomic Energy Commission, edited by Leo F. Boron, P. Noordhoff Ltd, Groningen, 1964.  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 Contin. Dyn. Syst. Ser. B, 17 (2012), 33-56. doi: 10.3934/dcdsb.2012.17.33.  Google Scholar [2] R. Bartels and G. Stewart, Algorithm 432: Solution of the matrix equation $AX + XB = C$, Comm. ACM, 15 (1972), 820-826. doi: 10.1145/361573.361582.  Google Scholar [3] F. Clarke, "Optimization and Nonsmooth Analysis,'' Second edition, Classics in Applied Mathematics, 5, SIAM, Philadephia, PA, 1990.  Google Scholar [4] A. Garcia and O. Agamennoni, Attraction and stability of nonlinear ODE's using continuous piecewise linear approximations,, submitted., ().   Google Scholar [5] P. Giesl, "Construction of Global Lyapunov Functions Using Radial Basis Functions,'' Lecture Notes in Mathematics, 1904, Springer, Berlin, 2007.  Google Scholar [6] P. Giesl and S. Hafstein, Existence of piecewise affine Lyapunov functions in two dimensions, J. Math. Anal. Appl., 371 (2010), 233-248. 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, J. Math. Anal. Appl., 388 (2012), 463-479. doi: 10.1016/j.jmaa.2011.10.047.  Google Scholar [8] 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.  Google Scholar [9] S. Hafstein, A constructive converse Lyapunov theorem on asymptotic stability for nonlinear autonomous ordinary differential equations, Dynamical Systems, 20 (2005), 281-299. doi: 10.1080/14689360500164873.  Google Scholar [10] S. Hafstein, "An Algorithm for Constructing Lyapunov Functions,'' Electron. J. Differential Equ. Monogr., 8, Texas State Univ.-San Marcos, Dep. of Mathematics, San Marcos, TX, 2007. Available from: http://ejde.math.txstate.edu/.  Google Scholar [11] T. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization, Automatica J. IFAC, 36 (2000), 1617-1626. doi: 10.1016/S0005-1098(00)00088-1.  Google Scholar [12] M. Johansson and A. Rantzer, On the computation of piecewise quadratic Lyapunov functions, in "Proceedings of the 36th IEEE Conference on Decision and Control,'' 1997. Google Scholar [13] P. Julian, "A High-Level Canonical Piecewise Linear Representation: Theory and Applications,'' Ph.D. thesis, Universidad Nacional del Sur, Bahia Blanca, Argentina, 1999.  Google Scholar [14] P. Julián, J. Guivant and A. Desages, A parametrization of piecewise linear Lyapunov function via linear programming. Multiple model approaches to modelling and control, Int. Journal of Control, 72 (1999), 702-715.  Google Scholar [15] H. K. Khalil, "Nonlinear Systems,'' 3rd edition, Prentice Hall, New Jersey, 2002. Google Scholar [16] S. Marinósson, "Stability Analysis of Nonlinear Systems with Linear Programming: A Lyapunov Functions Based Approach,'' Ph.D. thesis, Gerhard-Mercator-University, Duisburg, Germany, 2002. Google Scholar [17] S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming, Dynamical Systems, 17 (2002), 137-150. doi: 10.1080/0268111011011847.  Google Scholar [18] 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,'' (2002), 3482-3487. Google Scholar [19] P. Parrilo, "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,'' Ph.D. thesis, Caltech, Pasadena, USA, 2000. Google Scholar [20] M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions, IEEE Trans. Automatic Control, 54 (2009), 979-987. doi: 10.1109/TAC.2009.2017116.  Google Scholar [21] V. Zubov, "Methods of A. M. Lyapunov and Their Application,'' Translation prepared under the auspices of the United States Atomic Energy Commission, edited by Leo F. Boron, P. Noordhoff Ltd, Groningen, 1964.  Google Scholar
 [1] Shimin Li, Jaume Llibre. On the limit cycles of planar discontinuous piecewise linear differential systems with a unique equilibrium. Discrete & Continuous Dynamical Systems - B, 2019, 24 (11) : 5885-5901. doi: 10.3934/dcdsb.2019111 [2] Ábel Garab. Unique periodic orbits of a delay differential equation with piecewise linear feedback function. Discrete & Continuous Dynamical Systems, 2013, 33 (6) : 2369-2387. doi: 10.3934/dcds.2013.33.2369 [3] Zhichuan Zhu, Bo Yu, Li Yang. Globally convergent homotopy method for designing piecewise linear deterministic contractual function. Journal of Industrial & Management Optimization, 2014, 10 (3) : 717-741. doi: 10.3934/jimo.2014.10.717 [4] Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33 [5] Massimiliano Tamborrino. Approximation of the first passage time density of a Wiener process to an exponentially decaying boundary by two-piecewise linear threshold. Application to neuronal spiking activity. Mathematical Biosciences & Engineering, 2016, 13 (3) : 613-629. doi: 10.3934/mbe.2016011 [6] Łukasz Struski, Jacek Tabor. Expansivity implies existence of Hölder continuous Lyapunov function. Discrete & Continuous Dynamical Systems - B, 2017, 22 (9) : 3575-3589. doi: 10.3934/dcdsb.2017180 [7] Prof. Dr.rer.nat Widodo. Topological entropy of shift function on the sequences space induced by expanding piecewise linear transformations. Discrete & Continuous Dynamical Systems, 2002, 8 (1) : 191-208. doi: 10.3934/dcds.2002.8.191 [8] Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049 [9] Claudio Buzzi, Claudio Pessoa, Joan Torregrosa. Piecewise linear perturbations of a linear center. Discrete & Continuous Dynamical Systems, 2013, 33 (9) : 3915-3936. doi: 10.3934/dcds.2013.33.3915 [10] Michal Málek, Peter Raith. Stability of the distribution function for piecewise monotonic maps on the interval. Discrete & Continuous Dynamical Systems, 2018, 38 (5) : 2527-2539. doi: 10.3934/dcds.2018105 [11] Magnus Aspenberg, Viviane Baladi, Juho Leppänen, Tomas Persson. On the fractional susceptibility function of piecewise expanding maps. Discrete & Continuous Dynamical Systems, 2022, 42 (2) : 679-706. doi: 10.3934/dcds.2021133 [12] Serafin Bautista, Yeison Sánchez. Sectional-hyperbolic Lyapunov stable sets. Discrete & Continuous Dynamical Systems, 2020, 40 (4) : 2011-2016. doi: 10.3934/dcds.2020103 [13] Ciprian D. Coman. Dissipative effects in piecewise linear dynamics. Discrete & Continuous Dynamical Systems - B, 2003, 3 (2) : 163-177. doi: 10.3934/dcdsb.2003.3.163 [14] Tomás Caraballo, M. J. Garrido-Atienza, B. Schmalfuss. Existence of exponentially attracting stationary solutions for delay evolution equations. Discrete & Continuous Dynamical Systems, 2007, 18 (2&3) : 271-293. doi: 10.3934/dcds.2007.18.271 [15] Jian Hou, Liwei Zhang. A barrier function method for generalized Nash equilibrium problems. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1091-1108. doi: 10.3934/jimo.2014.10.1091 [16] De-Jun Feng, Antti Käenmäki. Equilibrium states of the pressure function for products of matrices. Discrete & Continuous Dynamical Systems, 2011, 30 (3) : 699-708. doi: 10.3934/dcds.2011.30.699 [17] Wenjie Li, Lihong Huang, Jinchen Ji. Globally exponentially stable periodic solution in a general delayed predator-prey model under discontinuous prey control strategy. Discrete & Continuous Dynamical Systems - B, 2020, 25 (7) : 2639-2664. doi: 10.3934/dcdsb.2020026 [18] Jianfeng Lv, Yan Gao, Na Zhao. The viability of switched nonlinear systems with piecewise smooth Lyapunov functions. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1825-1843. doi: 10.3934/jimo.2020048 [19] 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 [20] Marat Akhmet, Duygu Aruğaslan. Lyapunov-Razumikhin method for differential equations with piecewise constant argument. Discrete & Continuous Dynamical Systems, 2009, 25 (2) : 457-466. doi: 10.3934/dcds.2009.25.457

2020 Impact Factor: 1.392