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.

[2]

J. Anderson, Dynamical System Decomposition and Analysis Using Convex Optimization,, PhD thesis, (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, (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, (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, (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. 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. doi: 10.1016/j.jmaa.2013.08.014.

[12]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1.21., , (2011).

[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.

[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.

[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.

[16]

Y. Huang and A. Jadbabaie, Nonlinear H control: An enhanced quasi-LPV approach,, in Proceedings of the IFAC World Congress, (1999), 85.

[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.

[18]

H. K. Khalil, Nonlinear Systems,, Prentice-Hall, (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. doi: 10.1137/070685051.

[21]

J. Löfberg, Yalmip: A toolbox for modeling and optimization in MATLAB,, in Proceedings of the CACSD Conference, (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. 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,, , (2013).

[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.

[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.

[26]

P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, PhD thesis, (2000).

[27]

P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems,, Mathematical Programming, 96 (2003), 293. doi: 10.1007/s10107-003-0387-5.

[28]

P. A. Parrilo and B. Sturmfels, Minimizing polynomials functions,, , (2001).

[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.

[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.

[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.

[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.

[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.

[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.

[35]

W. Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming,, PhD thesis, (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. doi: 10.1109/ACC.2006.1655340.

[37]

M. J. Todd, Semidefinite optimization,, Acta Numerica 2001, 10 (2001), 515. 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. 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. 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, (2014), 3591. doi: 10.1109/ACC.2014.6859263.

[41]

L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. 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.

[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.

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.

[2]

J. Anderson, Dynamical System Decomposition and Analysis Using Convex Optimization,, PhD thesis, (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, (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, (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, (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. 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. doi: 10.1016/j.jmaa.2013.08.014.

[12]

M. Grant and S. Boyd, CVX: Matlab software for disciplined convex programming, version 1.21., , (2011).

[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.

[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.

[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.

[16]

Y. Huang and A. Jadbabaie, Nonlinear H control: An enhanced quasi-LPV approach,, in Proceedings of the IFAC World Congress, (1999), 85.

[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.

[18]

H. K. Khalil, Nonlinear Systems,, Prentice-Hall, (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. doi: 10.1137/070685051.

[21]

J. Löfberg, Yalmip: A toolbox for modeling and optimization in MATLAB,, in Proceedings of the CACSD Conference, (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. 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,, , (2013).

[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.

[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.

[26]

P. A. Parrilo, Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization,, PhD thesis, (2000).

[27]

P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems,, Mathematical Programming, 96 (2003), 293. doi: 10.1007/s10107-003-0387-5.

[28]

P. A. Parrilo and B. Sturmfels, Minimizing polynomials functions,, , (2001).

[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.

[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.

[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.

[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.

[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.

[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.

[35]

W. Tan, Nonlinear Control Analysis and Synthesis using Sum-of-Squares Programming,, PhD thesis, (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. doi: 10.1109/ACC.2006.1655340.

[37]

M. J. Todd, Semidefinite optimization,, Acta Numerica 2001, 10 (2001), 515. 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. 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. 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, (2014), 3591. doi: 10.1109/ACC.2014.6859263.

[41]

L. Vandenberghe and S. Boyd, Semidefinite programming,, SIAM Review, 38 (1996), 49. 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.

[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.

[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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

William Clark, Anthony Bloch, Leonardo Colombo. A Poincaré-Bendixson theorem for hybrid systems. Mathematical Control & Related Fields, 2019, 0 (0) : 0-0. doi: 10.3934/mcrf.2019028

[18]

Xiang Xie, Honglei Xu, Xinming Cheng, Yilun Yu. Improved results on exponential stability of discrete-time switched delay systems. Discrete & Continuous Dynamical Systems - B, 2017, 22 (1) : 199-208. doi: 10.3934/dcdsb.2017010

[19]

Michael Stich, Carsten Beta. Standing waves in a complex Ginzburg-Landau equation with time-delay feedback. Conference Publications, 2011, 2011 (Special) : 1329-1334. doi: 10.3934/proc.2011.2011.1329

[20]

Nabil T. Fadai, Michael J. Ward, Juncheng Wei. A time-delay in the activator kinetics enhances the stability of a spike solution to the gierer-meinhardt model. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1431-1458. doi: 10.3934/dcdsb.2018158

2017 Impact Factor: 0.972

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]