TY - GEN
T1 - Analysis of the joint spectral radius via Lyapunov functions on path-complete graphs
AU - Ahmadi, Amir Ali
AU - Jungers, Raphaël M.
AU - Parrilo, Pablo A.
AU - Roozbehani, Mardavij
N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
KW - Finite automata
KW - Joint spectral radius
KW - Lyapunov methods
KW - Semidefinite programming
KW - Stability of switched systems
UR - http://www.scopus.com/inward/record.url?scp=79956010261&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79956010261&partnerID=8YFLogxK
U2 - 10.1145/1967701.1967706
DO - 10.1145/1967701.1967706
M3 - Conference contribution
AN - SCOPUS:79956010261
SN - 9781450306294
T3 - HSCC'11 - Proceedings of the 2011 ACM/SIGBED Hybrid Systems: Computation and Control
SP - 13
EP - 22
BT - HSCC'11 - Proceedings of the 2011 ACM/SIGBED Hybrid Systems
T2 - 14th ACM International Conference on Hybrid Systems: Computation and Control, HSCC 2011
Y2 - 12 April 2011 through 14 April 2011
ER -