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]

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, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113

[2]

Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331

[3]

Qingfeng Zhu, Yufeng Shi. Nonzero-sum differential game of backward doubly stochastic systems with delay and applications. Mathematical Control & Related Fields, 2021, 11 (1) : 73-94. doi: 10.3934/mcrf.2020028

[4]

Maoli Chen, Xiao Wang, Yicheng Liu. Collision-free flocking for a time-delay system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1223-1241. doi: 10.3934/dcdsb.2020251

[5]

Hui Lv, Xing'an Wang. Dissipative control for uncertain singular markovian jump systems via hybrid impulsive control. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 127-142. doi: 10.3934/naco.2020020

[6]

Lars Grüne. Computing Lyapunov functions using deep neural networks. Journal of Computational Dynamics, 2020  doi: 10.3934/jcd.2021006

[7]

Peter Giesl, Sigurdur Hafstein. System specific triangulations for the construction of CPA Lyapunov functions. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020378

[8]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[9]

Stefan Siegmund, Petr Stehlík. Time scale-induced asynchronous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1011-1029. doi: 10.3934/dcdsb.2020151

[10]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103

[11]

Biao Zeng. Existence results for fractional impulsive delay feedback control systems with Caputo fractional derivatives. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021001

[12]

Zhongbao Zhou, Yanfei Bai, Helu Xiao, Xu Chen. A non-zero-sum reinsurance-investment game with delay and asymmetric information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 909-936. doi: 10.3934/jimo.2020004

[13]

Simone Göttlich, Elisa Iacomini, Thomas Jung. Properties of the LWR model with time delay. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020032

[14]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334

[15]

Lingju Kong, Roger Nichols. On principal eigenvalues of biharmonic systems. Communications on Pure & Applied Analysis, 2021, 20 (1) : 1-15. doi: 10.3934/cpaa.2020254

[16]

Mauricio Achigar. Extensions of expansive dynamical systems. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020399

[17]

Ting Liu, Guo-Bao Zhang. Global stability of traveling waves for a spatially discrete diffusion system with time delay. Electronic Research Archive, , () : -. doi: 10.3934/era.2021003

[18]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[19]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[20]

Ilyasse Lamrani, Imad El Harraki, Ali Boutoulout, Fatima-Zahrae El Alaoui. Feedback stabilization of bilinear coupled hyperbolic systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020434

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (96)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]