# 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 - A, 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.  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.  doi: 10.1145/361573.361582.  Google Scholar [3] F. Clarke, "Optimization and Nonsmooth Analysis,'', Second edition, 5 (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 (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.  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.  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.  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.  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, (2007).   Google Scholar [11] T. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization,, Automatica J. IFAC, 36 (2000), 1617.  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, (1997).   Google Scholar [13] P. Julian, "A High-Level Canonical Piecewise Linear Representation: Theory and Applications,'', Ph.D. thesis, (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.   Google Scholar [15] H. K. Khalil, "Nonlinear Systems,'', 3rd edition, (2002).   Google Scholar [16] S. Marinósson, "Stability Analysis of Nonlinear Systems with Linear Programming: A Lyapunov Functions Based Approach,'', Ph.D. thesis, (2002).   Google Scholar [17] S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dynamical Systems, 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar [18] A. Papachristodoulou and S. Prajna, The construction of Lyapunov functions using the sum of squares decomposition,, in, (2002), 3482.   Google Scholar [19] P. Parrilo, "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,'', Ph.D. thesis, (2000).   Google Scholar [20] M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions,, IEEE Trans. Automatic Control, 54 (2009), 979.  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, (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.  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.  doi: 10.1145/361573.361582.  Google Scholar [3] F. Clarke, "Optimization and Nonsmooth Analysis,'', Second edition, 5 (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 (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.  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.  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.  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.  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, (2007).   Google Scholar [11] T. Johansen, Computation of Lyapunov functions for smooth nonlinear systems using convex optimization,, Automatica J. IFAC, 36 (2000), 1617.  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, (1997).   Google Scholar [13] P. Julian, "A High-Level Canonical Piecewise Linear Representation: Theory and Applications,'', Ph.D. thesis, (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.   Google Scholar [15] H. K. Khalil, "Nonlinear Systems,'', 3rd edition, (2002).   Google Scholar [16] S. Marinósson, "Stability Analysis of Nonlinear Systems with Linear Programming: A Lyapunov Functions Based Approach,'', Ph.D. thesis, (2002).   Google Scholar [17] S. Marinósson, Lyapunov function construction for ordinary differential equations with linear programming,, Dynamical Systems, 17 (2002), 137.  doi: 10.1080/0268111011011847.  Google Scholar [18] A. Papachristodoulou and S. Prajna, The construction of Lyapunov functions using the sum of squares decomposition,, in, (2002), 3482.   Google Scholar [19] P. Parrilo, "Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,'', Ph.D. thesis, (2000).   Google Scholar [20] M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions,, IEEE Trans. Automatic Control, 54 (2009), 979.  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, (1964).   Google Scholar
 [1] Mark F. Demers. Uniqueness and exponential mixing for the measure of maximal entropy for piecewise hyperbolic maps. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 217-256. doi: 10.3934/dcds.2020217 [2] Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444 [3] 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 [4] Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 [5] Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164 [6] Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443 [7] Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168 [8] Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320 [9] Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070 [10] Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 [11] Yichen Zhang, Meiqiang Feng. A coupled $p$-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075 [12] Ahmad Z. Fino, Wenhui Chen. A global existence result for two-dimensional semilinear strongly damped wave equation with mixed nonlinearity in an exterior domain. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5387-5411. doi: 10.3934/cpaa.2020243 [13] Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436 [14] Zhilei Liang, Jiangyu Shuai. Existence of strong solution for the Cauchy problem of fully compressible Navier-Stokes equations in two dimensions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020348 [15] Thabet Abdeljawad, Mohammad Esmael Samei. Applying quantum calculus for the existence of solution of $q$-integro-differential equations with three criteria. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020440 [16] Gongbao Li, Tao Yang. Improved Sobolev inequalities involving weighted Morrey norms and the existence of nontrivial solutions to doubly critical elliptic systems involving fractional Laplacian and Hardy terms. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020469

2019 Impact Factor: 1.338