research-article

Algebraic analysis on asymptotic stability of continuous dynamical systems

Authors:

Zhiming ZhengAuthors Info & Claims

ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

Pages 313 - 320

https://doi.org/10.1145/1993886.1993933

Published: 08 June 2011 Publication History

Abstract

In this paper we propose a mechanisable technique for asymptotic stability analysis of continuous dynamical systems. We start from linearizing a continuous dynamical system, solving the Lyapunov matrix equation and then check whether the solution is positive definite. For the cases that the Jacobian matrix is not a Hurwitz matrix, we first derive an algebraizable sufficient condition for the existence of a Lyapunov function in quadratic form without linearization. Then, we apply a real root classification based method step by step to formulate this derived condition as a semi-algebraic set such that the semi-algebraic set only involves the coefficients of the pre-assumed quadratic form. Finally, we compute a sample point in the resulting semi-algebraic set for the coefficients resulting in a Lyapunov function. In this way, we avoid the use of generic quantifier elimination techniques for efficient computation. We prototypically implemented our algorithm based on DISCOVERER. The experimental results and comparisons demonstrate the feasibility and promise of our approach.

References

[1]

M. S. Branicky. Multiple Lyapunov functions and other analysis tools for switched andhybrid systems. IEEE Trans. on Auto. Contr., 43(4): 475--482, 1998.

[2]

G. E. Collins, H. Hong. Partial cylindrical algebraic decomposition for quantifier elimination. J. Symb. Comput., 12: 299--328, 1991.

Digital Library

[3]

C. W. Brown. QEPCAD B: a system for computing with semi-algebraic sets via cylindrical algebraic decomposition. SIGSAM Bull, 38(1): 23--24, 2004.

Digital Library

[4]

R. A. Decarlo, M. S. Branicky, S. Pettersson. Perspective and results on the stability annd stabilizability of hybrid systems. In Proc. of the IEEE, 88(7): 1069--1081, 2000.

[5]

A. Dolzmann, T. Sturm. REDLOG: computer algebra meets computer logic. SIGSAM Bull, 31(2): 2--9, 1997.

Digital Library

[6]

F. Forsman. Construction of Lyapunov functions using Gröbner bases. In Proc. of IEEE Conf. on Decision and Control, 798--799, 1991.

[7]

W. Hahn. Stability of Motion. Springer, 1967.

[8]

H. Hong, R. Liska, S. Steinberg. Testing stability by quantifier elimination. J. Symb. Comput., 24(2): 161--187, 1997.

Digital Library

[9]

M. Johansson, A. Rantzer. Computation of piecewise quadaratic Lyapunov functions for hybrid systems. IEEE Trans. on Auto. Contr., 43(4): 555--559, 1998.

[10]

M. El Kahoui, A. Weber. Deciding Hopf bifurcations by quantifier elimination in a software-component architecture. J. Symb. Comput., 30(2): 161--179, 2000.

Digital Library

[11]

H. K. Khalil. Nonlinear Systems. Prentice Hall, 2002.

[12]

M. Kocvara, M. Stingl. PENBMI User's Guide. Avaiable from http://www.penopt.com, 2005.

[13]

J. Löfberg. YALMIP: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference.Available from http://control.ee.ethz.ch/~joloef/yalmip.php, 2004.

[14]

J. Lunze and F. Lamnabhi-Lagarrigue, editors. Handbook of Hybrid Systems Control: Theory, Tools, Applications. Cambridge University Press, 2009.

[15]

M. A. Pai. Power System Stability by Lyapunov's Method. North Holland Publishing company, 1981.

[16]

A. Papachristodoulou, S. Prajna. On the construction of Lyapunov functions using the sum of squares decomposition. In: IEEE CDC 2002.

[17]

P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming (Series B), 96(2): 293--320, 2003.

[18]

S. Pettersson, B. Lennartson. An LMI approach for stability analysis of nonlinear systems. In Proc. of the 4th European Control Conference, 1997.

[19]

A. Podelski, S. Wagner. Model checking of hybrid systems: From reachability towards stability. In J. Hespanha and A. Tiwari, editors, Hybrid Systems: Computation and Control, LNCS 3927, Springer, 2006.

Digital Library

[20]

S. Prajna, A. Papachristodoulou, P. A. Parrilo. Introducing SOSTOOLS: A general purpose sum of squares programming solver. In Proc. of the IEEE Conf. on Decision and Control, 2002.

[21]

S. Ratschan, Z. She. Safety verification of hybrid systems by constraint propagation-based abstraction refinement. ACM Transactions on Embedded Computing Systems, 6(1), 2007.

Digital Library

[22]

S. Ratschan, Z. She. Providing a basin of attraction to a target region of polynomial systems by computation of Lyapunov-like functions. SIAM J. Control Optim., 48(7): 4377--4394, 2010.

Digital Library

[23]

Z. She, Y. Ran, B. Xue, Z. Zheng. On the Algebraization of Asymptotic Stability Analysis for Differential Systems. In Proc. of the 11th IASTED CA, pp. 68--74, ACTA Press, 2009.

[24]

Z. She, B. Xia, R. Xiao, Z. Zheng. A semi-algebraic approach for asymptotic stability analysis. Nonlinear Analysis: Hybrid system, 3(4): 588--596, 2009.

[25]

Z. She, B. Xia, Z. Zheng. Condition number based complexity estimate for solving polynomial systems. J. Comput. Appl. Math, 235(8): 2670--2678, 2011.

Digital Library

[26]

Z. She, Z. Zheng. Tightened reachability constraints for the verification of linearhybrid systems. Nonlinear Analysis: Hybrid Systems, 2(4): 1222--1231, 2008.

[27]

Z. She, Z. Zheng. Condition number based complexity estimate for solving local extrema. J. Comput. Appl. Math, 230(1): 233--242, 2009.

Digital Library

[28]

T. Sturm, A. Weber, E. O. Abdel-Rahman, M. El Kahoui. Investigating algebraic and logical algorithms to solve Hopf bifurcation problems in algebraic biology. Math. Comput. Sci., 2(3): 493--515, 2009.

[29]

W. Tan, A. Packard. Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming. IEEE Trans. on Automatic Control, 53(2): 565--571, 2008.

[30]

A. Tarski. A Decision Method for Elementary Algebra and Geometry. Univ. of California Press, 1951.

[31]

D. Wang, B. Xia. Stability analysis of biological systems with realsolution classification. In ISSAC, ACM Press, New York, pp. 354--361, 2005.

[32]

Andreas Weber, Thomas Sturm, Werner M. Seiler, Essam O. Abdel-Rahman. Parametric Qualitative Analysis of Ordinary Differential Equations: Computer Algebra Methods for Excluding Oscillations. In CASC2010, pp. 267--279, 2010.

Digital Library

[33]

L. Yang, B. Xia. Automated deduction in real geometry. In Geometric Computation, pp. 248--298, World Scientific, 2004.

Cited By

Banerjee ALamrani IGupta S(2020)Non-linear Analysis for Operational Safety Verification of Cyber Physical Systems2020 IEEE Conference on Industrial Cyberphysical Systems (ICPS)10.1109/ICPS48405.2020.9274758(529-534)Online publication date: 10-Jun-2020
https://doi.org/10.1109/ICPS48405.2020.9274758
Tong JBajcinca N(2018)Computation of Feasible Parametric Regions for Common Quadratic Lyapunov Functions2018 European Control Conference (ECC)10.23919/ECC.2018.8550205(807-812)Online publication date: Jun-2018
https://doi.org/10.23919/ECC.2018.8550205
Tong JBajcinca N(2017)Computation of feasible parametric regions for Lyapunov functions2017 11th Asian Control Conference (ASCC)10.1109/ASCC.2017.8287559(2453-2458)Online publication date: Dec-2017
https://doi.org/10.1109/ASCC.2017.8287559
Show More Cited By

Index Terms

Algebraic analysis on asymptotic stability of continuous dynamical systems
1. Applied computing
  1. Physical sciences and engineering
    1. Mathematics and statistics
2. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Computer algebra systems

Recommendations

An Algebraic Approach on Globally Exponential Stability of Polynomial Dynamical Systems
ISCID '13: Proceedings of the 2013 Sixth International Symposium on Computational Intelligence and Design - Volume 01

This paper presents a constructive method for analyzing globally exponential stability of polynomial dynamical systems by discovering quadratic Lyapunov functions. First, we derive an algebraic sufficient condition for analyzing globally exponential ...
Algebraic analysis on asymptotic stability of switched hybrid systems
HSCC '12: Proceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control

In this paper we propose a mechanisable approach for discovering multiple Lyapunov functions for switched hybrid systems. We start with the classical definition on asymptotic stability, which can be assured by the existence of multiple Lyapunov ...
Discovering polynomial Lyapunov functions for continuous dynamical systems

In this paper we analyze locally asymptotic stability of polynomial dynamical systems by discovering local Lyapunov functions beyond quadratic forms. We first derive an algebraizable sufficient condition for the existence of a polynomial Lyapunov ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '11: Proceedings of the 36th international symposium on Symbolic and algebraic computation

June 2011

372 pages

ISBN:9781450306751

DOI:10.1145/1993886

General Chair:
Éric Schost
The University of Western Ontario, Canada
,
Program Chair:
Ioannis Z. Emiris
University of Athens, Greece

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '11

Sponsor:

SIGSAM

ISSAC '11: International Symposium on Symbolic and Algebraic Computation

June 8 - 11, 2011

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
237
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Banerjee ALamrani IGupta S(2020)Non-linear Analysis for Operational Safety Verification of Cyber Physical Systems2020 IEEE Conference on Industrial Cyberphysical Systems (ICPS)10.1109/ICPS48405.2020.9274758(529-534)Online publication date: 10-Jun-2020
https://doi.org/10.1109/ICPS48405.2020.9274758
Tong JBajcinca N(2018)Computation of Feasible Parametric Regions for Common Quadratic Lyapunov Functions2018 European Control Conference (ECC)10.23919/ECC.2018.8550205(807-812)Online publication date: Jun-2018
https://doi.org/10.23919/ECC.2018.8550205
Tong JBajcinca N(2017)Computation of feasible parametric regions for Lyapunov functions2017 11th Asian Control Conference (ASCC)10.1109/ASCC.2017.8287559(2453-2458)Online publication date: Dec-2017
https://doi.org/10.1109/ASCC.2017.8287559
Lu JShe ZXue B(2015)Discovering multiple Lyapunov functions for switched hybrid systems with global exponential stability2015 54th IEEE Conference on Decision and Control (CDC)10.1109/CDC.2015.7402882(4252-4259)Online publication date: Dec-2015
https://doi.org/10.1109/CDC.2015.7402882
Liu YZhou WLi HYi C(2014)Time-invariant Lyapunov matrix equation solving by Neural Networks with Simulink models2014 12th International Conference on Signal Processing (ICSP)10.1109/ICOSP.2014.7015252(1512-1517)Online publication date: Oct-2014
https://doi.org/10.1109/ICOSP.2014.7015252
Chen XÁbrahám ESankaranarayanan S(2013)Flow*Proceedings of the 25th International Conference on Computer Aided Verification - Volume 804410.5555/2958031.2958094(258-263)Online publication date: 13-Jul-2013
https://dl.acm.org/doi/10.5555/2958031.2958094
She ZLiu HLi H(2013)An Algebraic Approach on Globally Exponential Stability of Polynomial Dynamical SystemsProceedings of the 2013 Sixth International Symposium on Computational Intelligence and Design - Volume 0110.1109/ISCID.2013.104(391-396)Online publication date: 28-Oct-2013
https://dl.acm.org/doi/10.1109/ISCID.2013.104
She ZLi H(2013)Dynamics of a density-dependent stage-structured predator–prey system with Beddington–DeAngelis functional responseJournal of Mathematical Analysis and Applications10.1016/j.jmaa.2013.04.053406:1(188-202)Online publication date: Oct-2013
https://doi.org/10.1016/j.jmaa.2013.04.053
Chen XÁbrahám ESankaranarayanan S(2013)Flow*: An Analyzer for Non-linear Hybrid SystemsComputer Aided Verification10.1007/978-3-642-39799-8_18(258-263)Online publication date: 2013
https://doi.org/10.1007/978-3-642-39799-8_18
She ZXue BDang TMitchell I(2012)Algebraic analysis on asymptotic stability of switched hybrid systemsProceedings of the 15th ACM international conference on Hybrid Systems: Computation and Control10.1145/2185632.2185661(187-196)Online publication date: 17-Apr-2012
https://dl.acm.org/doi/10.1145/2185632.2185661
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents