Abstract
The notion of Lyapunov function plays a key role in the design and verification of dynamical systems, as well as hybrid and cyber-physical systems. In this paper, to analyze the asymptotic stability of a dynamical system, we generalize standard Lyapunov functions to relaxed Lyapunov functions (RLFs), by considering higher order Lie derivatives. Furthermore, we present a method for automatically discovering polynomial RLFs for polynomial dynamical systems (PDSs). Our method is relatively complete in the sense that it is able to discover all polynomial RLFs with a given predefined template for any PDS. Therefore it can also generate all polynomial RLFs for the PDS by enumerating all polynomial templates.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agrachev A.A., Liberzon D.: Lie-algebraic stability criteria for switched systems. SIAM J. Control Optim. 40, 253–269 (2001)
Ahmadi, A.A., Parrilo, P.A.: On higher order derivatives of Lyapunov functions. In: American Control Conference 2011, pp. 1313–1314 (2011)
Brown, C.W.: QEPCAD. http://www.usna.edu/Users/cs/qepcad/B/QEPCAD.html
Butz A.: Higher order derivatives of Lyapunov functions. IEEE Trans. Automat. Contr. 14, 111–112 (1969)
Chen, Y., Xia, B., Yang, L., Zhan, N.: Generating polynomial invariants with DISCOVERER and QEPCAD. In: Jones, C., Liu, Z., Woodcock, J. (eds.) Formal Methods and Hybrid Real-Time Systems, LNCS, vol. 4700, pp. 67–82. Springer, Berlin (2007)
Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 2nd edn. Springer, Berlin (1997)
Davenport J.H., Heintz J.: Real quantifier elimination is doubly exponential. J. Symb. Comput. 5(1-2), 29–35 (1988)
Dolzmann, A., Seidl, A., Sturm, T.: Redlog User Manual (Nov 2006), http://redlog.dolzmann.de/downloads/, edition 3.1, for Redlog Version 3.06 (Reduce 3.8)
Gao B., Zhang W.: A weaker criterion of asymptotic stability. Comput. Math. Appl. 56(7), 1693–1698 (2008)
Giesl P.: Construction of a local and global Lyapunov function using radial basis functions. IMA J. Appl. Math. 73(5), 782–802 (2008)
Gurvits L.: Stability of discrete linear inclusion. Linear Algebra Appl. 231, 47–85 (1995)
Haddad W.M., Chellaboina V.: Nonlinear Dynamical Systems and Control: A Lyapunov-Based Approach. Princeton University Press, New Jersey (2008)
Jiang L.: On the asymptotic stability of equilibrium. J. Math. Anal. Appl. 301(2), 378–383 (2005)
Johansson M., Rantzer A.: Computation of piecewise quadratic Lyapunov functions for hybrid systems. . IEEE Trans Automat. Contr. 43, 555–559 (1998)
Khalil H.K.: Nonlinear Systems, 3rd edn. Prentice Hall, UK (2001)
Liberzon D., Hespanha J.P., Morse A.: Stability of switched systems: a Lie-algebraic condition. Syst. Control Lett. 37(3), 117–122 (1999)
Liu, J., Zhan, N., Zhao, H.: Computing semi-algebraic invariants for polynomial dynamical systems. In: EMSOFT’11, pp. 97–106. ACM press, New York (2011)
Maplesoft: Maple 14 User Manual. http://www.maplesoft.com/documentation_center/
Matrosov, V.M.: Method of vector Lyapunov functions of interconnected systems with distributed parameters. Avtovmatika i Telemekhanika. 33, 63–75 (1972) (in Russian)
Meigoli, V., Nikravesh, S.K.Y.: Application of higher order derivatives of Lyapunov functions in stability analysis of nonlinear homogeneous systems. In: IMECS’09 (2009). http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.149.3130
Nersesov, S.G., Haddad, W.M.: On the stability and control of nonlinear dynamical systems via vector Lyapunov functions. In: IEEE CDC’04, vol. 4, pp. 4107–4112 (2004)
Niu W., Wang D.: Algebraic approaches to stability analysis of biological systems. Math. Comput. Sci. 1, 507–539 (2008)
Papachristodoulou A., Prajna S.: Analysis of non-polynomial systems using the sums of squares decomposition. Positive Polynomials in Control 312, 23–43 (2005)
Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.3194 (2001)
Pettersson, S., Lennartson, B.: LMI for stability and robustness of hybrid systems. In: American Control Conference 1997, vol. 3, pp. 1714–1718 (1997)
Prajna, S., Papachristodoulou, A.: Analysis of switched and hybrid systems—beyond piecewise quadratic methods. In: American Control Conference 2003, vol. 4, pp. 2779 – 2784 (2003)
Ratschan, S., She, Z.: Providing a basin of attraction to a target region by computation of Lyapunov-like functions. In: IEEE ICCC’06, pp. 1–5 (2006)
She, Z., Xia, B., Xiao, R.: A semi-algebraic approach for the computation of Lyapunov functions. In: CI’06. pp. 7–12 (2006)
Shim, H., Noh, D.J., Seo, J.H.: Common Lyapunov function for exponentially stable nonlinear systems. In: 4th SIAM Conference on Control and its Applications (1998)
Slotine J.J., Li W.: Applied Nonlinear Control. Prentice Hall, New Jersey (1991)
Tabuada P.: Verification and Control of Hybrid Systems: A Symbolic Approach. Springer, Berlin (2009)
Tan, W., Packard, A.: Searching for control Lyapunov functions using sums of squares programming. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.1320
Tarski A.: A Decision Method for Elementary Algebra and Geometry. University of California Press, Berkeley (1951)
Vu L., Liberzon D.: Common Lyapunov functions for families of commuting nonlinear systems. Syst. Control Lett. 54(5), 405–416 (2005)
Wang, D., Xia, B.: Stability analysis of biological systems with real solution classification. In: ISSAC’05, pp. 354–361. ACM press, New York (2005)
Xia B.: DISCOVERER: a tool for solving semi-algebraic systems. ACM Commun. Comput. Algebra 41, 102–103 (2007)
Yang L.: Recent advances on determining the number of real roots of parametric polynomials. J. Symb. Comput. 28(1–2), 225–242 (1999)
Yang, L., Xia, B.: Real solution classifications of a class of parametric semi-algebraic systems. In: Algorithmic Algebra and Logic—Proceedings of the A3L 2005, pp. 281–289 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is supported in part by the projects NSFC-91118007, NSFC-60970031, NSFC-60736017, NSFC-61202131, YIGH-405070, cstc2011ggB40027, cstc2012ggB40004 and the PEARL project (041/2007/A3) from FDCT (Macau).
Rights and permissions
About this article
Cite this article
Liu, J., Zhan, N. & Zhao, H. Automatically Discovering Relaxed Lyapunov Functions for Polynomial Dynamical Systems. Math.Comput.Sci. 6, 395–408 (2012). https://doi.org/10.1007/s11786-012-0133-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11786-012-0133-6