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

Amir Ali Ahmadi, Raphaël M. Jungers, Pablo A. Parrilo, Mardavij Roozbehani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations

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 × n matrices we propose semidefinite programs of modest size that approximate the JSR within a multiplicative factor of 1/ 4 √ 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.

Original languageEnglish (US)
Title of host publicationHSCC'11 - Proceedings of the 2011 ACM/SIGBED Hybrid Systems
Subtitle of host publicationComputation and Control
Pages13-22
Number of pages10
DOIs
StatePublished - 2011
Externally publishedYes
Event14th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2011 - Chicago, IL, United States
Duration: Apr 12 2011Apr 14 2011

Publication series

NameHSCC'11 - Proceedings of the 2011 ACM/SIGBED Hybrid Systems: Computation and Control

Other

Other14th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2011
Country/TerritoryUnited States
CityChicago, IL
Period4/12/114/14/11

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Control and Systems Engineering

Keywords

  • Finite automata
  • Joint spectral radius
  • Lyapunov methods
  • Semidefinite programming
  • Stability of switched systems

Fingerprint

Dive into the research topics of 'Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs'. Together they form a unique fingerprint.

Cite this