×

A semi-algebraic approach for asymptotic stability analysis. (English) Zbl 1217.93153

Summary: This paper deals with the problem of computing Lyapunov functions for asymptotic stability analysis of autonomous polynomial systems of differential equations. We propose a new semi-algebraic approach by making advantage of the local property of the Lyapunov function as well as its derivative. This is done by first constructing a semi-algebraic system and then solving this semi-algebraic system in an adaptive way. Experimental results show that our semi-algebraic approach is more efficient in practice, especially for low-order systems.

MSC:

93D20 Asymptotic stability in control theory
93B25 Algebraic methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Nguyen, T. V.; Mori, T.; Mori, Y., Existence conditions of a common quadratic Lyapunov function for a set of second-order systems, Transactions of the Society of Instrument and Control Engineers, 42, 3, 241-246 (2006)
[2] Nguyen, T. V.; Mori, T.; Mori, Y., Relations between common Lyapunov functions of quadratic and infinity-norm forms for a set of discrete-time LTI systems, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E89-A, 6, 1794-1798 (2006)
[3] Tarski, A., A Decision Method for Elementary Algebra and Geometry (1951), Univ. of California Press: Univ. of California Press Berkeley · Zbl 0044.25102
[4] Collins, G. E., Quantifier elimination for the elementary theory of real closed fields by cylindrical algebraic decomposition, (Lect. Notes Comput. Sci., vol. 33 (1975)), 134-183
[5] Yang, L.; Xia, B., Automated deduction in real geometry, (Geometric Computation (2004), World Scientific), 248-298 · Zbl 1082.65054
[6] She, Z.; Xia, B.; Xiao, R., A semi-algebraic approach for the computation of Lyapunov functions, (Proceedings of the 2nd IASTED International Conference on Computational Intelligence (2006), ACTA Press), 7-12
[7] Hahn, W., Stability of Motion (1967), Springer · Zbl 0189.38503
[8] Henzinger, T. A.; Kopke, P. W.; Puri, A.; Varaiya, P., What’s decidable about hybrid automata, Journal of Computer and System Sciences, 57, 94-124 (1998) · Zbl 0920.68091
[9] S. Pettersson, B. Lennartson, An LMI approach for stability analysis of nonlinear systems, in: Proc. of the 4th European Control Conference, 1997; S. Pettersson, B. Lennartson, An LMI approach for stability analysis of nonlinear systems, in: Proc. of the 4th European Control Conference, 1997
[10] Branicky, M. S., Multiple Lyapunov functions and other analysis tools for switched and hybrid systems, IEEE Transactions on Automatic Control, 43, 4, 475-482 (1998) · Zbl 0904.93036
[11] Decarlo, R. A.; Branicky, M. S.; Pettersson, S.; Lennartson, B., Perspectives and results on the stability and stabilizability of hybrid systems, Proceedings of the IEEE, 88, 7 (2000)
[12] Burchardt, H.; Oehlerking, J.; Theel, O., The role of state-space partitioning in automated verification of affine hybrid system stability, (Proc. of the 3rd Intl. Conf. on Computing, Communications and Control Technologies, vol. 1 (2005), International Institute of Informatics and Systemics), 187-192
[13] Collins, G. E.; Hong, H., Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, 12, 299-328 (1991) · Zbl 0754.68063
[14] Rudin, W., Principles of Mathematical Analysis (1976), McGraw-Hill · Zbl 0148.02903
[15] Wang, D.; Xia, B., Computer Algebra (2004), Tsinghua Univ. Press: Tsinghua Univ. Press Beijing
[16] Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming Series. B, 96, 2, 293-320 (2003) · Zbl 1043.14018
[17] Gallo, G.; Mishra, B., Efficient algorithms and bounds for Wu-Ritt characteristic sets, (Mora, T.; Traverso, C., Effective Methods in Algebraic Geometry. Effective Methods in Algebraic Geometry, Progress in Mathematics (1994), Birkhäuser: Birkhäuser Bosten), 119-142 · Zbl 0747.13019
[18] A. Papachristodoulou, S. Prajna, On the construction of Lyapunov functions using the sum of squares decomposition, in: Proc. of the IEEE Conf. on Decision and Control, 2002; A. Papachristodoulou, S. Prajna, On the construction of Lyapunov functions using the sum of squares decomposition, in: Proc. of the IEEE Conf. on Decision and Control, 2002 · Zbl 1138.93391
[19] G. Ghesi, A. Tesi, A. Vicino, On the optimal quadratic Lyapunov functions for polynomial systems, in: 15 th Int. Symp. on Mathematical Theory of Networks and Systems, 2002; G. Ghesi, A. Tesi, A. Vicino, On the optimal quadratic Lyapunov functions for polynomial systems, in: 15 th Int. Symp. on Mathematical Theory of Networks and Systems, 2002
[20] K. Forsman, Optimization, stability and cylindrical decomposition, Technical report, Automatic Control Group in Linköping, 1993; K. Forsman, Optimization, stability and cylindrical decomposition, Technical report, Automatic Control Group in Linköping, 1993
[21] S. Prajna, A. Papachristodoulou, P.A. Parrilo, Introducing SOSTOOLS: A general purpose sum of squares programming solver, in: Proc. of the IEEE Conf. on Decision and Control, CDC, 2002; S. Prajna, A. Papachristodoulou, P.A. Parrilo, Introducing SOSTOOLS: A general purpose sum of squares programming solver, in: Proc. of the IEEE Conf. on Decision and Control, CDC, 2002
[22] K. Forsman, Construction of Lyapunov functions using Gröbner bases, in: Proc. of the 30th Conf. on Decision and Control, 1991, pp. 798-799; K. Forsman, Construction of Lyapunov functions using Gröbner bases, in: Proc. of the 30th Conf. on Decision and Control, 1991, pp. 798-799
[23] 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
[24] Shields, D. N.; Storey, C., The behaviour of optimal Lyapunov functions, International Journal of Control, 21, 4, 561-573 (1975) · Zbl 0318.93024
[25] Genesio, R.; Tartaglia, M.; Vicino, A., On the estimation of asympototic stability regions: State of the art and new proposals, IEEE Transactions on Automatic Control, 30, 8, 747-755 (1985) · Zbl 0568.93054
[26] T.-C. Wang, S. Lall, M. West, Polynomial level-set methods for nonlinear dynamical systems analysis, in: Proceedings of the Allerton Conference on Communication, Control and Computing, 2005; T.-C. Wang, S. Lall, M. West, Polynomial level-set methods for nonlinear dynamical systems analysis, in: Proceedings of the Allerton Conference on Communication, Control and Computing, 2005
[27] Lakshmikantham, V.; Leela, S.; Martynyuk, A., Practical Stability of Nonlinear Systems (1990), World Scientific · Zbl 0753.34037
[28] S. Ratschan, Z. She, Providing a basin of attraction to a target region by computation of Lyapunov-like functions, in: Proc. of the 4th IEEE Int. Conf. on Computational Cybernetics, 2006, pp. 245-249; S. Ratschan, Z. She, Providing a basin of attraction to a target region by computation of Lyapunov-like functions, in: Proc. of the 4th IEEE Int. Conf. on Computational Cybernetics, 2006, pp. 245-249 · Zbl 1215.65188
[29] Ratschan, S.; She, Z., Safety verification of hybrid systems by constraint propagation based abstraction refinement, ACM Transactions on Embedded Computing Systems, 6, 4, 1-23 (2007), Article No. 8
[30] 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, LNCS, vol. 3927 (2006), Springer) · Zbl 1178.93077
[31] She, Z.; Zheng, Z., Tightened reachability constraints for the verification of linear hybrid systems, Nonlinear Analysis: Hybrid Systems, 2, 4, 1222-1231 (2008) · Zbl 1163.93006
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.