×

Discovering polynomial Lyapunov functions for continuous dynamical systems. (English) Zbl 1338.37025

Summary: In this paper we analyze locally asymptotic stability of polynomial dynamical systems by discovering local Lyapunov functions beyond quadratic forms. We first derive an algebraizable sufficient condition for the existence of a polynomial Lyapunov function. Then we apply a real root classification based method step by step to under-approximate this derived condition as a semi-algebraic system such that the semi-algebraic system only involves the coefficients of the pre-assumed polynomial. Afterward, we compute a sample point in the corresponding semi-algebraic set for the coefficients resulting in a local Lyapunov function. Moreover, we test our approach on some examples using a prototype implementation and compare it with the generic quantifier elimination based method and the sum of squares based method. These computation and comparison results show the applicability and efficiency of our approach.

MSC:

37B25 Stability of topological dynamical systems
37C75 Stability theory for smooth dynamical systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Branicky, M. S., Multiple Lyapunov functions and other analysis tools for switched and hybrid systems, IEEE Trans. Automat. Control, 43, 4, 475-482 (1998) · Zbl 0904.93036
[2] Brown, C. W., Improved projection for cylindrical algebraic decomposition, J. Symbolic Comput., 32, 5, 447-465 (2001) · Zbl 0981.68186
[3] Brown, C. W., QEPCAD B: A system for computing with semi-algebraic sets via cylindrical algebraic decomposition, SIGSAM Bull., 38, 1, 23-24 (2004)
[4] Chen, C.; Lemaire, F.; Li, L.; Maza, M. Moreno; Pan, W.; Xie, Y., The ConstructibleSetTools and ParametricSystemTools modules of the RegularChains library in Maple, (Proc. of the International Conference on Computational Science and Applications (2008), IEEE Computer Society Press), 342-352 · Zbl 1344.13001
[5] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, J. Symbolic Comput., 12, 299-328 (1991) · Zbl 0754.68063
[6] Decarlo, R. A.; Branicky, M. S.; Pettersson, S., Perspective and results on the stability and stabilizability of hybrid systems, Proc. IEEE, 88, 7, 1069-1081 (2000)
[7] Dolzmann, A.; Sturm, T., REDLOG: Computer algebra meets computer logic, SIGSAM Bull., 31, 2, 2-9 (1997)
[8] Forsman, F., Construction of Lyapunov functions using Gröbner bases, (Proc. of the IEEE Conf. on Decision and Control (1991)), 798-799
[9] Gulwani, S.; Tiwari, A., Constraint-based approach for analysis of hybrid systems, (CAV 2008 (2008)), 190-203 · Zbl 1155.68437
[10] Hahn, W., Stability of Motion (1967), Springer · Zbl 0189.38503
[11] Hong, H.; Liska, R.; Steinberg, S., Testing stability by quantifier elimination, J. Symbolic Comput., 24, 2, 161-187 (1997) · Zbl 0886.65087
[12] Kahoui, M. El; Weber, A., Deciding Hopf bifurcations by quantifier elimination in a software-component architecture, J. Symbolic Comput., 30, 2, 161-179 (2000) · Zbl 0965.65137
[13] Khalil, H. K., Nonlinear Systems (2002), Prentice Hall
[14] Koc̈vara, M.; Stingl, M., PENBMI Userʼs Guide (2005), Available from
[15] Löfberg, J., Yalmip: A toolbox for modeling and optimization in MATLAB, (Proceedings of the CACSD Conference (2004)), Available from
[16] Pai, M. A., Power System Stability by Lyapunovʼs Method (1981), North-Holland Publishing Company
[17] Papachristodoulou, A.; Prajna, S., On the construction of Lyapunov functions using the sum of squares decomposition, (Proc. of the IEEE Conf. on Decision and Control (2002))
[18] Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems, Math. Program. Ser. B, 96, 2, 293-320 (2003) · Zbl 1043.14018
[19] Podelski, A.; Wagner, S., Model checking of hybrid systems: From reachability towards stability, (Hespanha, J.; Tiwari, A., Hybrid Systems: Computation and Control. Hybrid Systems: Computation and Control, Lecture Notes in Comput. Sci., vol. 3927 (2006), Springer), 507-521 · Zbl 1178.93077
[20] Prajna, S.; Papachristodoulou, A.; Parrilo, P. A., Introducing SOSTOOLS: A general purpose sum of squares programming solver, (Proc. of the IEEE Conf. on Decision and Control (2002))
[21] Ratschan, S.; She, Z., Safety verification of hybrid systems by constraint propagation-based abstraction refinement, ACM Trans. Embed. Comput. Syst., 6, 1 (2007), Article No. 8, pp. 1-23
[22] Ratschan, S.; She, Z., Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions, SIAM J. Control Optim., 48, 7, 4377-4394 (2010) · Zbl 1215.65188
[23] Reznick, B., Some concrete aspects of Hilbertʼs 17th problem, (Contemp. Math., vol. 253 (2000)), 251-272 · Zbl 0972.11021
[24] She, Z., Termination analysis of safety verification for non-linear robust hybrid systems, (Proceedings of the 8th International Conference on Informatics in Control, Automation and Robotics (2011), SciTePress), 251-261
[25] She, Z.; Xia, B.; Xiao, R.; Zheng, Z., A semi-algebraic approach for asymptotic stability analysis, Nonlinear Anal. Hybrid Syst., 3, 4, 588-596 (2009) · Zbl 1217.93153
[26] She, Z.; Xia, B.; Zheng, Z., Condition number based complexity estimate for solving polynomial systems, J. Comput. Appl. Math., 235, 8, 2670-2678 (2011) · Zbl 1211.65059
[27] She, Z.; Xue, B., Computing a basin of attraction to a target region by solving bilinear semi-definite problems, (Proceedings of the 13th International Workshop on Computer Algebra in Scientific Computing. Proceedings of the 13th International Workshop on Computer Algebra in Scientific Computing, Lecture Notes in Comput. Sci., vol. 6885 (2011), Springer), 333-344 · Zbl 1345.34107
[28] She, Z.; Xue, B., Algebraic analysis on asymptotic stability of switched hybrid systems, (Proceedings of the 15th International Conference on Hybrid Systems: Computation and Control (2012)), 187-196 · Zbl 1364.93689
[29] She, Z.; Xue, B.; Zheng, Z., Algebraic analysis on asymptotic stability of continuous dynamical systems, (Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation (2011)), 313-320 · Zbl 1323.68627
[30] She, Z.; Zheng, Z., Tightened reachability constraints for the verification of linear hybrid systems, Nonlinear Anal. Hybrid Syst., 2, 4, 1222-1231 (2008) · Zbl 1163.93006
[31] She, Z.; Zheng, Z., Condition number based complexity estimate for solving local extrema, J. Comput. Appl. Math., 230, 1, 233-242 (2009) · Zbl 1187.68723
[32] Strzeboński, A., Solving systems of strict polynomial inequalities, J. Symbolic Comput., 29, 3, 471-480 (2000) · Zbl 0962.68183
[33] Sturm, T.; Weber, A.; Abdel-Rahman, E. O.; Kahoui, M. El, Investigating algebraic and logical algorithms to solve Hopf bifurcation problems in algebraic biology, Math. Comput. Sci., 2, 3, 493-515 (2009) · Zbl 1205.37062
[34] Tan, W.; Packard, A., Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming, IEEE Trans. Automat. Control, 53, 2, 565-571 (2008) · Zbl 1367.34079
[35] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), Univ. of California Press · Zbl 0044.25102
[36] Wang, D.; Xia, B., Stability analysis of biological systems with real solution classification, (ISSAC (2005), ACM Press: ACM Press New York), 354-361 · Zbl 1360.92048
[37] Weber, A.; Sturm, T.; Seiler, W. M.; Abdel-Rahman, E. O., Parametric qualitative analysis of ordinary differential equations: Computer algebra methods for excluding oscillations, (CASC 2010. CASC 2010, Lecture Notes in Comput. Sci., vol. 6244 (2010)), 267-279 · Zbl 1290.68140
[38] Xia, B., DISCOVERER: A tool for solving semi-algebraic systems, ACM SIGSAM Bull., 41, 3, 102-103 (2007), Software Demo in ISSAC 2007, Waterloo. Also:
[39] Xia, B.; Zhang, T., Real solution isolation using interval arithmetic, Comput. Math. Appl., 52, 853-860 (2006) · Zbl 1131.65041
[40] Yang, L.; Hou, X.; Xia, B., A complete algorithm for automated discovering of a class of inequality-type theorems, Sci. China Ser. F, 44, 33-49 (2001) · Zbl 1125.68406
[41] Yang, L.; Xia, B., Real solution classifications of parametric semi-algebraic systems, (Dolzmann, A.; Seidl, A.; Sturm, T., Algorithmic Algebra and Logic — Proceedings of the A3L 2005 (2005), Herstellung und Verlag: Herstellung und Verlag Norderstedt), 281-289
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.