Advances in computational Lyapunov analysis using sum-of-squares programming

James  Anderson; Antonis  Papachristodoulou

doi:10.3934/dcdsb.2015.20.2361

Article Contents

2015, Volume 20, Issue 8: 2361-2381. Doi: 10.3934/dcdsb.2015.20.2361

This issue Previous Article Classical converse theorems in Lyapunov's second method Next Article Polynomial optimization with applications to stability analysis and control - Alternatives to sum of squares

Advances in computational Lyapunov analysis using sum-of-squares programming

James Anderson^1, and
Antonis Papachristodoulou^1,

1.
Department of Engineering Science, University of Oxford, Parks Road, Oxford, OX1 3PJ

Received: May 31, 2014

Revised: October 31, 2014

Published: September 2015

Abstract Related Papers Cited by

Abstract

The stability of an equilibrium point of a nonlinear dynamical system is typically determined using Lyapunov theory. This requires the construction of an energy-like function, termed a Lyapunov function, which satisfies certain positivity conditions. Unlike linear dynamical systems, there is no algorithmic method for constructing Lyapunov functions for general nonlinear systems. However, if the systems of interest evolve according to polynomial vector fields and the Lyapunov functions are constrained to be sum-of-squares polynomials then stability verification can be cast as a semidefinite (convex) optimization programme. In this paper we describe recent advances in sum-of-squares programming that facilitate advanced stability analysis and control design.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Related Papers

Cited by

References

[1]	A. A. Ahmadi, M. Krstic and P. A. Parrilo, A globally asymptotically stable polynomial vector field with no polynomial Lyapunov function, in Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on, IEEE, 2011, 7579-7580.doi: 10.1109/CDC.2011.6161499.
[2]	J. Anderson, Dynamical System Decomposition and Analysis Using Convex Optimization, PhD thesis, University of Oxford, Oxford, U.K., 2012.
[3]	G. Blekherman, P. A. Parrilo and R. R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry, SIAM, 2013.
[4]	J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry, Springer-Verlag, Berlin, 1998.doi: 10.1007/BFb0084605.
[5]	S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1994.doi: 10.1137/1.9781611970777.
[6]	S. Boyd, L. El Ghaoul, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, Vol. 15, Society for Industrial Mathematics, 1987.
[7]	S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.doi: 10.1017/CBO9780511804441.
[8]	G. Chesi, Estimating the domain of attraction for uncertain polynomial systems, Automatica, 40 (2004), 1981-1986.doi: 10.1016/j.automatica.2004.06.014.
[9]	G. Chesi, A. Garulli, A. Tesi and A. Vicino, Homogeneous Polynomial Forms for Robustness Analysis of Uncertain Systems, Springer, 2009.doi: 10.1007/978-1-84882-781-3.
[10]	D. Cox, J. Little and D. O'Shea, Ideals, Varietis, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer, 1997.
[11]	P. A. Giesl and S. F. Hafstein, Revised CPA method to compute Lyapunov functions for nonlinear systems, Journal of Mathematical Analysis and Applications, 410 (2014), 292-306.doi: 10.1016/j.jmaa.2013.08.014.
[12]	M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx, 2011.
[13]	J. K. Hale and S. M. Verduyn Lunel, Introduction to Functional Differential Equations, Applied Mathematical Sciences, 99, Springer-Verlag, 1993.doi: 10.1007/978-1-4612-4342-7.
[14]	E. J. Hancock and A. Papachristodoulou, Generalised absolute stability and sum of squares, Automatica, 49 (2013), 960-967.doi: 10.1016/j.automatica.2013.01.006.
[15]	D. Henrion and J. B. Lasserre, GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi, ACM Transactions on Mathematical Software (TOMS), 29 (2003), 165-194.doi: 10.1145/779359.779363.
[16]	Y. Huang and A. Jadbabaie, Nonlinear H control: An enhanced quasi-LPV approach, in Proceedings of the IFAC World Congress, 1999, 85-90.
[17]	A. Isidori and A. Astolfi, Disturbance attenuation and $H_{\infty}$-control via measurement feedback in nonlinear systems, IEEE Transactions on Automatic Control, 37 (1992), 1283-1293.doi: 10.1109/9.159566.
[18]	H. K. Khalil, Nonlinear Systems, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 2000.
[19]	V. Kolmanovskii and A. Myshkis, Introduction to the Theory and Applications of Functional Differential Equations, Kluwer Academic Publishers, 1999.doi: 10.1007/978-94-017-1965-0.
[20]	J. Lasserre, D. Henrion, C. Prieur and E. Trelat, Nonlinear optimal control via occupation measures and LMI-relaxations, SIAM Journal on Control and Optimization, 47 (2008), 1643-1666.doi: 10.1137/070685051.
[21]	J. Löfberg, Yalmip: A toolbox for modeling and optimization in MATLAB, in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004.
[22]	W. M. Lu and J. C. Doyle, $H_{\infty}$ control of nonlinear systems: A convex characterization, IEEE Transactions on Automatic Control, 40 (1995), 1668-1675.doi: 10.1109/9.412643.
[23]	A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo, SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB, arXiv:1310.4716, 2013. Available from http://www.eng.ox.ac.uk/control/sostools, http://www.cds.caltech.edu/sostools and http://www.mit.edu/~parrilo/sostools.
[24]	A. Papachristodoulou, M. M. Peet and S. Lall, Analysis of polynomial systems with time delays via the sum of squares decomposition, IEEE Transactions on Automatic Control, 54 (2009), 1058-1064.doi: 10.1109/TAC.2009.2017168.
[25]	A. Papachristodoulou and S. Prajna, Analysis of non-polynomial systems using the sum of squares decomposition, in Positive Polynomials in Control, Springer, 312 (2005), 23-43.
[26]	P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization, PhD thesis, Caltech, Pasadena, CA, 2000.
[27]	P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Mathematical Programming, 96 (2003), 293-320.doi: 10.1007/s10107-003-0387-5.
[28]	P. A. Parrilo and B. Sturmfels, Minimizing polynomials functions, arXiv:math/0103170v1, 2001.
[29]	M. M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions, Automatic Control, IEEE Transactions on, 54 (2009), 979-987.doi: 10.1109/TAC.2009.2017116.
[30]	M. M. Peet and A. Papachristodoulou, A converse sum of squares Lyapunov result with a degree bound, IEEE Transactions on Automatic Control, 57 (2012), 2281-2293.doi: 10.1109/TAC.2012.2190163.
[31]	M. M. Peet, A. Papachristodoulou and S. Lall, Positive forms and stability of linear time-delay systems, SIAM J. Control Optim., 47 (2008), 3237-3258.doi: 10.1137/070706999.
[32]	S. Prajna, A. Papachristodoulou and F. Wu, Nonlinear control synthesis by sum of squares optimization: A Lyapunov-based approach, in 5th Asian Control Conference, IEEE, 2004, 157-165.
[33]	S. Prajna, P. A. Parrilo and A. Rantzer, Nonlinear control synthesis by convex optimization, IEEE Transactions on Automatic Control, 49 (2004), 310-314.doi: 10.1109/TAC.2003.823000.
[34]	J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods and Software, 11/12 (1999), 625-653.doi: 10.1080/10556789908805766.
[35]	W. Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming, PhD thesis, Berkeley, Berkeley, CA, 2006.
[36]	B. Tibken and Y. Fan, Computing the domain of attraction for polynomial systems via BMI optimization method, in Proceedings of the American Control Conference, 2006, 117-122.doi: 10.1109/ACC.2006.1655340.
[37]	M. J. Todd, Semidefinite optimization, Acta Numerica 2001, 10 (2001), 515-560.doi: 10.1017/S0962492901000071.
[38]	K. C. Toh, M. J. Todd and R. H. Tütüncü, SDPT3 - a Matlab software package for semidefinite programming, version 1.3, Optimization Methods and Software, 11 (1999), 545-581.doi: 10.1080/10556789908805762.
[39]	U. Topcu, A. Packard, P. Seiler and G. J. Balas, Robust region-of-attraction estimation, IEEE Transactions on Automatic Control, 55 (2010), 137-142.doi: 10.1109/TAC.2009.2033751.
[40]	G. Valmorbida and J. Anderson, Region of attraction analysis via invariant sets, in Proc. of the American Control Conference, IEEE, 2014, 3591-3596.doi: 10.1109/ACC.2014.6859263.
[41]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, 38 (1996), 49-95.doi: 10.1137/1038003.
[42]	Q. Zheng and F. Wu, Nonlinear output feedback $H_{\infty}$ control for polynomial nonlinear systems, in Proceedings of the 2008 American Control Conference, 2008, 1196-1201.
[43]	Q. Zheng and F. Wu, Generalized nonlinear $H_{\infty}$ synthesis condition with its numerically efficient solution, International Journal of Robust and Nonlinear Control, 21 (2011), 2079-2100.doi: 10.1002/rnc.1682.