# American Institute of Mathematical Sciences

October  2015, 20(8): 2361-2381. doi: 10.3934/dcdsb.2015.20.2361

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

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

Received  June 2014 Revised  November 2014 Published  August 2015

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.
Citation: James Anderson, Antonis Papachristodoulou. Advances in computational Lyapunov analysis using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2361-2381. doi: 10.3934/dcdsb.2015.20.2361
##### 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), 7579. doi: 10.1109/CDC.2011.6161499. Google Scholar [2] J. Anderson, Dynamical System Decomposition and Analysis Using Convex Optimization,, PhD thesis, (2012). Google Scholar [3] G. Blekherman, P. A. Parrilo and R. R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry,, SIAM, (2013). Google Scholar [4] J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry,, Springer-Verlag, (1998). doi: 10.1007/BFb0084605. Google Scholar [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, (1994). doi: 10.1137/1.9781611970777. Google Scholar [6] S. Boyd, L. El Ghaoul, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory,, Vol. 15, (1987). Google Scholar [7] S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004). doi: 10.1017/CBO9780511804441. Google Scholar [8] G. Chesi, Estimating the domain of attraction for uncertain polynomial systems,, Automatica, 40 (2004), 1981. doi: 10.1016/j.automatica.2004.06.014. Google Scholar [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. Google Scholar [10] D. Cox, J. Little and D. O'Shea, Ideals, Varietis, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra,, Springer, (1997). Google Scholar [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. doi: 10.1016/j.jmaa.2013.08.014. Google Scholar [12] M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1.21., , (2011). Google Scholar [13] J. K. Hale and S. M. Verduyn Lunel, Introduction to Functional Differential Equations,, Applied Mathematical Sciences, (1993). doi: 10.1007/978-1-4612-4342-7. Google Scholar [14] E. J. Hancock and A. Papachristodoulou, Generalised absolute stability and sum of squares,, Automatica, 49 (2013), 960. doi: 10.1016/j.automatica.2013.01.006. Google Scholar [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. doi: 10.1145/779359.779363. Google Scholar [16] Y. Huang and A. Jadbabaie, Nonlinear H control: An enhanced quasi-LPV approach,, in Proceedings of the IFAC World Congress, (1999), 85. Google Scholar [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. doi: 10.1109/9.159566. Google Scholar [18] H. K. Khalil, Nonlinear Systems,, Prentice-Hall, (2000). Google Scholar [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. Google Scholar [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. doi: 10.1137/070685051. Google Scholar [21] J. Löfberg, Yalmip: A toolbox for modeling and optimization in MATLAB,, in Proceedings of the CACSD Conference, (2004). Google Scholar [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. doi: 10.1109/9.412643. Google Scholar [23] A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo, SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB,, , (2013). Google Scholar [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. doi: 10.1109/TAC.2009.2017168. Google Scholar [25] A. Papachristodoulou and S. Prajna, Analysis of non-polynomial systems using the sum of squares decomposition,, in Positive Polynomials in Control, 312 (2005), 23. Google Scholar [26] P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, PhD thesis, (2000). Google Scholar [27] P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems,, Mathematical Programming, 96 (2003), 293. doi: 10.1007/s10107-003-0387-5. Google Scholar [28] P. A. Parrilo and B. Sturmfels, Minimizing polynomials functions,, , (2001). Google Scholar [29] M. M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions,, Automatic Control, 54 (2009), 979. doi: 10.1109/TAC.2009.2017116. Google Scholar [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. doi: 10.1109/TAC.2012.2190163. Google Scholar [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. doi: 10.1137/070706999. Google Scholar [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, (2004), 157. Google Scholar [33] S. Prajna, P. A. Parrilo and A. Rantzer, Nonlinear control synthesis by convex optimization,, IEEE Transactions on Automatic Control, 49 (2004), 310. doi: 10.1109/TAC.2003.823000. Google Scholar [34] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,, Optimization Methods and Software, 11/12 (1999), 625. doi: 10.1080/10556789908805766. Google Scholar [35] W. Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming,, PhD thesis, (2006). Google Scholar [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. doi: 10.1109/ACC.2006.1655340. Google Scholar [37] M. J. Todd, Semidefinite optimization,, Acta Numerica 2001, 10 (2001), 515. doi: 10.1017/S0962492901000071. Google Scholar [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. doi: 10.1080/10556789908805762. Google Scholar [39] U. Topcu, A. Packard, P. Seiler and G. J. Balas, Robust region-of-attraction estimation,, IEEE Transactions on Automatic Control, 55 (2010), 137. doi: 10.1109/TAC.2009.2033751. Google Scholar [40] G. Valmorbida and J. Anderson, Region of attraction analysis via invariant sets,, in Proc. of the American Control Conference, (2014), 3591. doi: 10.1109/ACC.2014.6859263. Google Scholar [41] L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar [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. Google Scholar [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. doi: 10.1002/rnc.1682. Google Scholar

show all references

##### 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), 7579. doi: 10.1109/CDC.2011.6161499. Google Scholar [2] J. Anderson, Dynamical System Decomposition and Analysis Using Convex Optimization,, PhD thesis, (2012). Google Scholar [3] G. Blekherman, P. A. Parrilo and R. R. Thomas, Semidefinite Optimization and Convex Algebraic Geometry,, SIAM, (2013). Google Scholar [4] J. Bochnak, M. Coste and M.-F. Roy, Real Algebraic Geometry,, Springer-Verlag, (1998). doi: 10.1007/BFb0084605. Google Scholar [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, (1994). doi: 10.1137/1.9781611970777. Google Scholar [6] S. Boyd, L. El Ghaoul, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory,, Vol. 15, (1987). Google Scholar [7] S. Boyd and L. Vandenberghe, Convex Optimization,, Cambridge University Press, (2004). doi: 10.1017/CBO9780511804441. Google Scholar [8] G. Chesi, Estimating the domain of attraction for uncertain polynomial systems,, Automatica, 40 (2004), 1981. doi: 10.1016/j.automatica.2004.06.014. Google Scholar [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. Google Scholar [10] D. Cox, J. Little and D. O'Shea, Ideals, Varietis, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra,, Springer, (1997). Google Scholar [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. doi: 10.1016/j.jmaa.2013.08.014. Google Scholar [12] M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1.21., , (2011). Google Scholar [13] J. K. Hale and S. M. Verduyn Lunel, Introduction to Functional Differential Equations,, Applied Mathematical Sciences, (1993). doi: 10.1007/978-1-4612-4342-7. Google Scholar [14] E. J. Hancock and A. Papachristodoulou, Generalised absolute stability and sum of squares,, Automatica, 49 (2013), 960. doi: 10.1016/j.automatica.2013.01.006. Google Scholar [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. doi: 10.1145/779359.779363. Google Scholar [16] Y. Huang and A. Jadbabaie, Nonlinear H control: An enhanced quasi-LPV approach,, in Proceedings of the IFAC World Congress, (1999), 85. Google Scholar [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. doi: 10.1109/9.159566. Google Scholar [18] H. K. Khalil, Nonlinear Systems,, Prentice-Hall, (2000). Google Scholar [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. Google Scholar [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. doi: 10.1137/070685051. Google Scholar [21] J. Löfberg, Yalmip: A toolbox for modeling and optimization in MATLAB,, in Proceedings of the CACSD Conference, (2004). Google Scholar [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. doi: 10.1109/9.412643. Google Scholar [23] A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler and P. A. Parrilo, SOSTOOLS: Sum of Squares Optimization Toolbox for MATLAB,, , (2013). Google Scholar [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. doi: 10.1109/TAC.2009.2017168. Google Scholar [25] A. Papachristodoulou and S. Prajna, Analysis of non-polynomial systems using the sum of squares decomposition,, in Positive Polynomials in Control, 312 (2005), 23. Google Scholar [26] P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, PhD thesis, (2000). Google Scholar [27] P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems,, Mathematical Programming, 96 (2003), 293. doi: 10.1007/s10107-003-0387-5. Google Scholar [28] P. A. Parrilo and B. Sturmfels, Minimizing polynomials functions,, , (2001). Google Scholar [29] M. M. Peet, Exponentially stable nonlinear systems have polynomial Lyapunov functions on bounded regions,, Automatic Control, 54 (2009), 979. doi: 10.1109/TAC.2009.2017116. Google Scholar [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. doi: 10.1109/TAC.2012.2190163. Google Scholar [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. doi: 10.1137/070706999. Google Scholar [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, (2004), 157. Google Scholar [33] S. Prajna, P. A. Parrilo and A. Rantzer, Nonlinear control synthesis by convex optimization,, IEEE Transactions on Automatic Control, 49 (2004), 310. doi: 10.1109/TAC.2003.823000. Google Scholar [34] J. F. Sturm, Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,, Optimization Methods and Software, 11/12 (1999), 625. doi: 10.1080/10556789908805766. Google Scholar [35] W. Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming,, PhD thesis, (2006). Google Scholar [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. doi: 10.1109/ACC.2006.1655340. Google Scholar [37] M. J. Todd, Semidefinite optimization,, Acta Numerica 2001, 10 (2001), 515. doi: 10.1017/S0962492901000071. Google Scholar [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. doi: 10.1080/10556789908805762. Google Scholar [39] U. Topcu, A. Packard, P. Seiler and G. J. Balas, Robust region-of-attraction estimation,, IEEE Transactions on Automatic Control, 55 (2010), 137. doi: 10.1109/TAC.2009.2033751. Google Scholar [40] G. Valmorbida and J. Anderson, Region of attraction analysis via invariant sets,, in Proc. of the American Control Conference, (2014), 3591. doi: 10.1109/ACC.2014.6859263. Google Scholar [41] L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. doi: 10.1137/1038003. Google Scholar [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. Google Scholar [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. doi: 10.1002/rnc.1682. Google Scholar
 [1] Sigurdur Hafstein, Skuli Gudmundsson, Peter Giesl, Enrico Scalas. Lyapunov function computation for autonomous linear stochastic differential equations using sum-of-squares programming. Discrete & Continuous Dynamical Systems - B, 2018, 23 (2) : 939-956. doi: 10.3934/dcdsb.2018049 [2] Linna Li, Changjun Yu, Ning Zhang, Yanqin Bai, Zhiyuan Gao. A time-scaling technique for time-delay switched systems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020108 [3] B. Cantó, C. Coll, A. Herrero, E. Sánchez, N. Thome. Pole-assignment of discrete time-delay systems with symmetries. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 641-649. doi: 10.3934/dcdsb.2006.6.641 [4] Ming He, Xiaoyun Ma, Weijiang Zhang. Oscillation death in systems of oscillators with transferable coupling and time-delay. Discrete & Continuous Dynamical Systems - A, 2001, 7 (4) : 737-745. doi: 10.3934/dcds.2001.7.737 [5] Qinqin Chai, Ryan Loxton, Kok Lay Teo, Chunhua Yang. A unified parameter identification method for nonlinear time-delay systems. Journal of Industrial & Management Optimization, 2013, 9 (2) : 471-486. doi: 10.3934/jimo.2013.9.471 [6] Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019113 [7] Nguyen H. Sau, Vu N. Phat. LP approach to exponential stabilization of singular linear positive time-delay systems via memory state feedback. Journal of Industrial & Management Optimization, 2018, 14 (2) : 583-596. doi: 10.3934/jimo.2017061 [8] J. C. Robinson. A topological time-delay embedding theorem for infinite-dimensional cocycle dynamical systems. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 731-741. doi: 10.3934/dcdsb.2008.9.731 [9] Denis de Carvalho Braga, Luis Fernando Mello, Carmen Rocşoreanu, Mihaela Sterpu. Lyapunov coefficients for non-symmetrically coupled identical dynamical systems. Application to coupled advertising models. Discrete & Continuous Dynamical Systems - B, 2009, 11 (3) : 785-803. doi: 10.3934/dcdsb.2009.11.785 [10] Huijuan Li, Junxia Wang. Input-to-state stability of continuous-time systems via finite-time Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (11) : 0-0. doi: 10.3934/dcdsb.2019192 [11] Gunther Dirr, Hiroshi Ito, Anders Rantzer, Björn S. Rüffer. Separable Lyapunov functions for monotone systems: Constructions and limitations. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2497-2526. doi: 10.3934/dcdsb.2015.20.2497 [12] Jóhann Björnsson, Peter Giesl, Sigurdur F. Hafstein, Christopher M. Kellett. Computation of Lyapunov functions for systems with multiple local attractors. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4019-4039. doi: 10.3934/dcds.2015.35.4019 [13] Michael Schönlein. Asymptotic stability and smooth Lyapunov functions for a class of abstract dynamical systems. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 4053-4069. doi: 10.3934/dcds.2017172 [14] Sigurdur F. Hafstein, Christopher M. Kellett, Huijuan Li. Computing continuous and piecewise affine lyapunov functions for nonlinear systems. Journal of Computational Dynamics, 2015, 2 (2) : 227-246. doi: 10.3934/jcd.2015004 [15] P. Adda, J. L. Dimi, A. Iggidir, J. C. Kamgang, G. Sallet, J. J. Tewa. General models of host-parasite systems. Global analysis. Discrete & Continuous Dynamical Systems - B, 2007, 8 (1) : 1-17. doi: 10.3934/dcdsb.2007.8.1 [16] Victor Magron, Marcelo Forets, Didier Henrion. Semidefinite approximations of invariant measures for polynomial systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (12) : 6745-6770. doi: 10.3934/dcdsb.2019165 [17] Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881 [18] Sergey Zelik. On the Lyapunov dimension of cascade systems. Communications on Pure & Applied Analysis, 2008, 7 (4) : 971-985. doi: 10.3934/cpaa.2008.7.971 [19] Huijuan Li, Robert Baier, Lars Grüne, Sigurdur F. Hafstein, Fabian R. Wirth. Computation of local ISS Lyapunov functions with low gains via linear programming. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2477-2495. doi: 10.3934/dcdsb.2015.20.2477 [20] Thomas I. Seidman, Olaf Klein. Periodic solutions of isotone hybrid systems. Discrete & Continuous Dynamical Systems - B, 2013, 18 (2) : 483-493. doi: 10.3934/dcdsb.2013.18.483

2018 Impact Factor: 1.008