research-article

Analysis of the joint spectral radius via lyapunov functions on path-complete graphs

Authors:

Amir Ali Ahmadi,

Raphaël Jungers,

Pablo A. Parrilo,

Mardavij RoozbehaniAuthors Info & Claims

HSCC '11: Proceedings of the 14th international conference on Hybrid systems: computation and control

Pages 13 - 22

https://doi.org/10.1145/1967701.1967706

Published: 12 April 2011 Publication History

Abstract

We study the problem of approximating the joint spectral radius (JSR) of a finite set of matrices. Our approach is based on the analysis of the underlying switched linear system via inequalities imposed between multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of graphs called path-complete graphs, and show that any such graph gives rise to a method for proving stability of the switched system. This enables us to derive several asymptotically tight hierarchies of semidefinite programming relaxations that unify and generalize many existing techniques such as common quadratic, common sum of squares, maximum/minimum-of-quadratics Lyapunov functions. We characterize all path-complete graphs consisting of two nodes on an alphabet of two matrices and compare their performance. For the general case of any set of n x n matrices we propose semidefinite programs of modest size that approximate the JSR within a multiplicative factor of 1/⁴√n of the true value. We establish a notion of duality among path-complete graphs and a constructive converse Lyapunov theorem for maximum/minimum-of-quadratics Lyapunov functions.

References

[1]

A. A. Ahmadi. Non-monotonic Lyapunov functions for stability of nonlinear and switched systems: theory and computation. Master's Thesis, Massachusetts Institute of Technology, June 2008. Available from http://dspace.mit.edu/handle/1721.1/44206.

[2]

A. A. Ahmadi and P. A. Parrilo. Non-monotonic Lyapunov functions for stability of discrete time nonlinear and switched systems. In Proceedings of the 47th IEEE Conference on Decision and Control, 2008.

[3]

T. Ando and M.-H. Shih. Simultaneous contractibility. SIAM Journal on Matrix Analysis and Applications, 19:487--498, 1998.

Digital Library

[4]

V. D. Blondel and Y. Nesterov. Computationally efficient approximations of the joint spectral radius. SIAM J. Matrix Anal. Appl., 27(1):256--272, 2005.

Digital Library

[5]

V. D. Blondel, Y. Nesterov, and J. Theys. On the accuracy of the ellipsoidal norm approximation of the joint spectral radius. Linear Algebra and its Applications, 394:91--107, 2005.

[6]

V. D. Blondel and J. N. Tsitsiklis. The boundedness of all products of a pair of matrices is undecidable. Systems and Control Letters, 41:135--140, 2000.

[7]

M. S. Branicky. Multiple Lyapunov functions and other analysis tools for switched and hybrid systems. IEEE Transactions on Automatic Control, 43(4):475--482, 1998.

[8]

J. Daafouz and J. Bernussou. Parameter dependent Lyapunov functions for discrete time systems with time varying parametric uncertainties. Systems and Control Letters, 43(5):355--359, 2001.

[9]

R. Goebel, T. Hu, and A. R. Teel. Dual matrix inequalities in stability and performance analysis of linear differential/difference inclusions. In Current Trends in Nonlinear Systems and Control, pages 103--122. 2006.

[10]

R. Goebel, A. R. Teel, T. Hu, and Z. Lin. Conjugate convex Lyapunov functions for dual linear differential inclusions. IEEE Transactions on Automatic Control, 51(4):661--666, 2006.

[11]

J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to automata theory, languages, and computation. Addison Wesley, 2001.

Digital Library

[12]

T. Hu and Z. Lin. Absolute stability analysis of discrete-time systems with composite quadratic Lyapunov functions. IEEE Transactions on Automatic Control, 50(6):781--797, 2005.

[13]

T. Hu, L. Ma, and Z. Li. On several composite quadratic Lyapunov functions for switched systems. In Proceedings of the 45th IEEE Conference on Decision and Control, 2006.

[14]

T. Hu, L. Ma, and Z. Lin. Stabilization of switched systems via composite quadratic functions. IEEE Transactions on Automatic Control, 53(11):2571--2585, 2008.

[15]

M. Johansson and A. Rantzer. Computation of piecewise quadratic Lyapunov functions for hybrid systems. IEEE Transactions on Automatic Control, 43(4):555--559, 1998.

[16]

R. Jungers. The joint spectral radius: theory and applications, volume 385 of Lecture Notes in Control and Information Sciences. Springer, 2009.

[17]

J. W. Lee and G. E. Dullerud. Uniform stabilization of discrete-time switched and Markovian jump linear systems. Automatica, 42(2):205--218, 2006.

Digital Library

[18]

H. Lin and P. J. Antsaklis. Stability and stabilizability of switched linear systems: a short survey of recent results. In Proceedings of IEEE International Symposium on Intelligent Control, 2005.

[19]

D. Lind and B. Marcus. An introduction to symbolic dynamics and coding. Cambridge University Press, 1995.

Digital Library

[20]

A. Molchanov and Y. Pyatnitskiy. Criteria of asymptotic stability of differential and difference inclusions encountered in control theory. Systems and Control Letters, 13:59--64, 1989.

Digital Library

[21]

P. A. Parrilo and A. Jadbabaie. Approximation of the joint spectral radius using sum of squares. Linear Algebra and its Applications, 428(10):2385--2402, 2008.

[22]

V. Y. Protasov, R. M. Jungers, and V. D. Blondel. Joint spectral characteristics of matrices: a conic programming approach. SIAM Journal on Matrix Analysis and Applications, 31(4):2146--2162, 2010.

Digital Library

[23]

M. Roozbehani. Optimization of Lyapunov invariants in analysis and implementation of safety-critical software systems. PhD thesis, Massachusetts Institute of Technology.

[24]

M. Roozbehani, A. Megretski, E. Frazzoli, and E. Feron. Distributed Lyapunov functions in analysis of graph models of software. Springer Lecture Notes in Computer Science, 4981:443--456, 2008.

Digital Library

[25]

L. Rosier. Homogeneous Lyapunov function for homogeneous continuous vector fields. Systems Control Letters, 19(6):467--473, 1992.

Digital Library

[26]

G. C. Rota and W. G. Strang. A note on the joint spectral radius. Indag. Math., 22:379--381, 1960.

[27]

J. N. Tsitsiklis and V. Blondel. The Lyapunov exponent and joint spectral radius of pairs of matrices are hard- when not impossible- to compute and to approximate. Mathematics of Control, Signals, and Systems, 10:31--40, 1997.

Cited By

Gomes CLegat BJungers RVangheluwe H(2019)Stable Adaptive Co-simulation: A Switched Systems ApproachIUTAM Symposium on Solver-Coupling and Co-Simulation10.1007/978-3-030-14883-6_5(81-97)Online publication date: 15-May-2019
https://doi.org/10.1007/978-3-030-14883-6_5
Gomes CJungers RLegat BVangheluwe H(2018)Minimally, Constrained Stable Switched Systems and Application to Co-Simulation2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619223(5676-5681)Online publication date: Dec-2018
https://doi.org/10.1109/CDC.2018.8619223
Jungers RAhmadi AParrilo PRoozbehani M(2017)A Characterization of Lyapunov Inequalities for Stability of Switched SystemsIEEE Transactions on Automatic Control10.1109/TAC.2017.267134562:6(3062-3067)Online publication date: Jun-2017
https://doi.org/10.1109/TAC.2017.2671345
Show More Cited By

Index Terms

Analysis of the joint spectral radius via lyapunov functions on path-complete graphs
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Path-Complete Graphs and Common Lyapunov Functions
HSCC '17: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control

A Path-Complete Lyapunov Function is an algebraic criterion composed of a finite number of functions, called pieces, and a directed, labeled graph defining Lyapunov inequalities between these pieces. It provides a stability certificate for discrete-time ...
Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated ...
Dynamic Lyapunov functions

Lyapunov functions are a fundamental tool to investigate stability properties of equilibrium points of linear and nonlinear systems. The existence of Lyapunov functions for asymptotically stable equilibrium points is guaranteed by converse Lyapunov ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

HSCC '11: Proceedings of the 14th international conference on Hybrid systems: computation and control

April 2011

330 pages

ISBN:9781450306294

DOI:10.1145/1967701

General Chair:
Marco Caccamo
University of Illinois at Urbana-Champaign, USA
,
Program Chairs:
Emilio Frazzoli
Massachusetts Institute of Technology, USA
,
Radu Grosu
State University of New York at Stony Brook, USA

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

SIGBED: ACM Special Interest Group on Embedded Systems

In-Cooperation

IEEE

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 April 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

HSCC '11

Sponsor:

SIGBED

HSCC '11: Hybrid Systems: Computation and Control

April 12 - 14, 2011

IL, Chicago, USA

Acceptance Rates

Overall Acceptance Rate 153 of 373 submissions, 41%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
217
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gomes CLegat BJungers RVangheluwe H(2019)Stable Adaptive Co-simulation: A Switched Systems ApproachIUTAM Symposium on Solver-Coupling and Co-Simulation10.1007/978-3-030-14883-6_5(81-97)Online publication date: 15-May-2019
https://doi.org/10.1007/978-3-030-14883-6_5
Gomes CJungers RLegat BVangheluwe H(2018)Minimally, Constrained Stable Switched Systems and Application to Co-Simulation2018 IEEE Conference on Decision and Control (CDC)10.1109/CDC.2018.8619223(5676-5681)Online publication date: Dec-2018
https://doi.org/10.1109/CDC.2018.8619223
Jungers RAhmadi AParrilo PRoozbehani M(2017)A Characterization of Lyapunov Inequalities for Stability of Switched SystemsIEEE Transactions on Automatic Control10.1109/TAC.2017.267134562:6(3062-3067)Online publication date: Jun-2017
https://doi.org/10.1109/TAC.2017.2671345
Wang YRoohi NDullerud GViswanathan M(2017)Stability Analysis of Switched Linear Systems Defined by Regular LanguagesIEEE Transactions on Automatic Control10.1109/TAC.2016.259993062:5(2568-2575)Online publication date: May-2017
https://doi.org/10.1109/TAC.2016.2599930
Ahmadi AParrilo P(2017)Some Recent Directions in Algebraic Methods for Optimization and Lyapunov AnalysisGeometric and Numerical Foundations of Movements10.1007/978-3-319-51547-2_5(89-112)Online publication date: 3-May-2017
https://doi.org/10.1007/978-3-319-51547-2_5
Essick RPhilippe MDullerud GJungers R(2015)The minimum achievable stability radius of switched linear systems with feedback2015 54th IEEE Conference on Decision and Control (CDC)10.1109/CDC.2015.7402880(4240-4245)Online publication date: Dec-2015
https://doi.org/10.1109/CDC.2015.7402880
Essick RDullerud G(2015)Minimum achievable decay rates of the discrete linear inclusion2015 American Control Conference (ACC)10.1109/ACC.2015.7170878(1089-1094)Online publication date: Jul-2015
https://doi.org/10.1109/ACC.2015.7170878
Vankeerberghen GHendrickx JJungers RFráänzle MLygeros J(2014)JSRProceedings of the 17th international conference on Hybrid systems: computation and control10.1145/2562059.2562124(151-156)Online publication date: 15-Apr-2014
https://dl.acm.org/doi/10.1145/2562059.2562124
Jungers RD'Innocenzo ADi Benedetto M(2014)How to control Linear Systems with switching delays2014 European Control Conference (ECC)10.1109/ECC.2014.6862300(2231-2236)Online publication date: Jun-2014
https://doi.org/10.1109/ECC.2014.6862300
Athanasopoulos NLazar M(2014)Stability analysis of switched linear systems defined by graphs53rd IEEE Conference on Decision and Control10.1109/CDC.2014.7040241(5451-5456)Online publication date: Dec-2014
https://doi.org/10.1109/CDC.2014.7040241
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