Exact asymptotic stability analysis and region-of-attraction estimation for nonlinear systems. (English) Zbl 1271.93128

Summary: We address the problem of asymptotic stability and region-of-attraction analysis of nonlinear dynamical systems. A hybrid symbolic-numeric method is presented to compute exact Lyapunov functions and exact estimates of regions of attraction of nonlinear systems efficiently. A numerical Lyapunov function and an estimate of region of attraction can be obtained by solving an (bilinear) SOS programming via BMI solver, then the modified Newton refinement and rational vector recovery techniques are applied to obtain exact Lyapunov functions and verified estimates of regions of attraction with rational coefficients. Experiments on some benchmarks are given to illustrate the efficiency of our algorithm.


93D20 Asymptotic stability in control theory
93D30 Lyapunov and storage functions
93B40 Computational methods in systems theory (MSC2010)
37N35 Dynamical systems in control
Full Text: DOI


[1] Polański, A., Lyapunov function construction by linear programming, Transactions on Automatic Control, 42, 7, 1013-1016 (1997) · Zbl 0885.93050 · doi:10.1109/9.599986
[2] Johansen, T. A., Computation of Lyapunov functions for smooth nonlinear systems using convex optimization, Automatica, 36, 11, 1617-1626 (2000) · Zbl 0971.93069 · doi:10.1016/S0005-1098(00)00088-1
[3] Grüne, L.; Wirth, F., Computing control Lyapunov functions via a Zubov type algorithm, Proceedings of the 39th IEEE Confernce on Decision and Control, IEEE
[4] Oliveira, R. C. L. F.; Peres, P. L. D., LMI conditions for robust stability analysis based on polynomially parameter-dependent Lyapunov functions, Systems & Control Letters, 55, 1, 52-61 (2006) · Zbl 1129.93485 · doi:10.1016/j.sysconle.2005.05.003
[5] Chesi, G.; Garulli, A.; Tesi, A.; Vicino, A., LMI-based computation of optimal quadratic Lyapunov functions for odd polynomial systems, International Journal of Robust and Nonlinear Control, 15, 1, 35-49 (2005) · Zbl 1056.93059 · doi:10.1002/rnc.967
[6] Liu, J.; Zhan, N.; Zhao, H., Automatically discovering relaxed Lyapunov functions for polynomial dynamical systems, Mathematics in Computer Science, 6, 4, 395-408 (2012) · Zbl 1261.93063
[7] Nguyen, T.; Mori, Y.; Mori, T.; Kuroe, Y., QE approach to common Lyapunov function problem, Journal of Japan Society for Symbolic and Algebraic Computation, 10, 1, 52-62 (2003)
[8] Papachristodoulou, A.; Prajna, S., On the construction of Lyapunov functions using the sum of squares decomposition, Proceedings of the 41st IEEE Conference on Decision and Control, IEEE
[9] She, Z.; Xia, B.; Xiao, R.; Zheng, Z., A semi-algebraic approach for asymptotic stability analysis, Nonlinear Analysis: Hybrid Systems, 3, 4, 588-596 (2009) · Zbl 1217.93153 · doi:10.1016/j.nahs.2009.04.010
[10] Grosman, B.; Lewin, D. R., Lyapunov-based stability analysis automated by genetic programming, Automatica, 45, 1, 252-256 (2009) · Zbl 1154.93405 · doi:10.1016/j.automatica.2008.07.014
[11] Forsman, K., Construction of Lyapunov functions using Grobner bases, Proceedings of the 30th IEEE Conference on Decision and Control, IEEE
[12] 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, ACM · Zbl 1323.68627
[13] Prajna, S.; Parrilo, P. A.; Rantzer, A., Nonlinear control synthesis by convex optimization, Transactions on Automatic Control, 49, 2, 310-314 (2004) · Zbl 1365.93164 · doi:10.1109/TAC.2003.823000
[14] Xia, B., DISCOVERER: a tool for solving semi-algebraic systems, ACM Communications in Computer Algebra, 41, 3, 102-103 (2007)
[15] Giesl, P., Construction of a local and global Lyapunov function using radial basis functions, IMA Journal of Applied Mathematics, 73, 5, 782-802 (2008) · Zbl 1155.34030 · doi:10.1093/imamat/hxn018
[16] Chiang, H.-D.; Thorp, J. S., Stability regions of nonlinear dynamical systems: a constructive methodology, Transactions on Automatic Control, 34, 12, 1229-1241 (1989) · Zbl 0689.93046 · doi:10.1109/9.40768
[17] Davison, E. J.; Kurak, E. M., A computational method for determining quadratic Lyapunov functions for non-linear systems, 7, 5, 627-636 (1971) · Zbl 0225.34027
[18] Cruck, E.; Moitie, R.; Seube, N., Estimation of basins of attraction for uncertain systems with affine and Lipschitz dynamics, Dynamics and Control, 11, 3, 211-227 (2001) · Zbl 1047.93043 · doi:10.1023/A:1015244102061
[19] Genesio, R.; Tartaglia, M.; Vicino, A., On the estimation of asymptotic stability regions: state of the art and new proposals, Transactions on Automatic Control, 30, 8, 747-755 (1985) · Zbl 0568.93054 · doi:10.1109/TAC.1985.1104057
[20] Jarvis-Wloszek, Z., Lyapunov based analysis and controller synthesis for polynomial systems using sum-of-squares optimization [Ph.D. thesis] (2003), Berkeley, Calif, USA: University of California, Berkeley, Calif, USA
[21] Prakash, S.; Vanualailai, J.; Soma, T., Obtaining approximate region of asymptotic stability by computer algebra: a case study, The South Pacific Journal of Natural and Applied Sciences, 20, 1, 56-61 (2002)
[22] Weehong, T.; Packard, A., Stability region analysis using sum of squares programming, Proceedings of the American Control Conference (ACC ’06), IEEE
[23] Parrilo, P. A., Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming B, 96, 2, 293-320 (2003) · Zbl 1043.14018 · doi:10.1007/s10107-003-0387-5
[24] Prajna, S.; Papachristodoulou, A.; Parrilo, P.
[25] Löfberg, J., YALMIP: a toolbox for modeling and optimization in MATLAB, Proceedings of the 2004 IEEE International Symposium on Computer Aided Control System Design
[26] Sturm, J. F., Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11, 1-4, 625-653 (1999) · Zbl 0973.90526 · doi:10.1080/10556789908805766
[27] Kocvara, M.; Stingl, M.
[28] Kaltofen, E.; Li, B.; Yang, Z.; Zhi, L., Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars, Proceedings of the 21th International Symposium on Symbolic and Algebraic Computation (ISSAC ’08), ACM
[29] Kaltofen, E. L.; Li, B.; Yang, Z.; Zhi, L., Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients, Journal of Symbolic Computation, 47, 1, 1-15 (2012) · Zbl 1229.90115 · doi:10.1016/j.jsc.2011.08.002
[30] Platzer, A.; Clarke, E. M., The image computation problem in hybrid systems model checking, Proceedings of the 10th International Conference on Hybrid Systems: Computation and Control (HSCC ’07), Springer · Zbl 1221.93118
[31] Khalil, H., Nonlinear Systems (2002), Upper Saddle River, NJ, USA: Prentice hall, Upper Saddle River, NJ, USA · Zbl 1003.34002
[32] Bochnak, J.; Coste, M.; Roy, M., Real Algebraic Geometry (1998), Berlin, Germany: Springer, Berlin, Germany · Zbl 0633.14016
[33] Chesi, G., LMI techniques for optimization over polynomials in control: a survey, Transactions on Automatic Control, 55, 11, 2500-2510 (2010) · Zbl 1368.93496 · doi:10.1109/TAC.2010.2046926
[34] Leibfritz, F.; Mostafa, E. M. E., An interior point constrained trust region method for a special class of nonlinear semidefinite programming problems, SIAM Journal on Optimization, 12, 4, 1048-1074 (2002) · Zbl 1035.90102 · doi:10.1137/S1052623400375865
[35] Kočvara, M.; Stingl, M., Pennon: a code for convex nonlinear and semidefinite programming, Optimization Methods & Software, 18, 3, 317-333 (2003) · Zbl 1037.90003 · doi:10.1080/1055678031000098773
[36] Wu, M.; Yang, Z., Generating invariants of hybrid systems via sums-of-squares of polynomials with rational coefficients, Proceedings of the International Workshop on Symbolic-Numeric Computation, ACM Press · Zbl 1345.65046
[37] Lin, W.; Wu, M.; Yang, Z.; Zeng, Z., Exact safety verification of hybrid systems using sums-of-squares representation, Science China Information Sciences (2012)
[38] Yang, Z.; Wu, M.; Lin, W., Exact verification of hybrid systems based on bilinear SOS representation
[39] Papachristodoulou, A.; Prajna, S., A tutorial on sum of squares techniques for systems analysis, Proceedings of the American Control Conference (ACC ’05), IEEE
[40] Löfberg, J., Modeling and solving uncertain optimization problems in YALMIP, Proceedings of the 17th World Congress, International Federation of Automatic Control (IFAC ’08) · doi:10.3182/20080706-5-KR-1001.1729
[41] Topcu, U.; Packard, A.; Seiler, P., Local stability analysis using simulations and sum-of-squares programming, Automatica, 44, 10, 2669-2675 (2008) · Zbl 1155.93417 · doi:10.1016/j.automatica.2008.03.010
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.