Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72962 https://orcid.org/0000-0003-1132-8477 |
| _version_ | 1826189498369703936 |
|---|---|
| author | Ahmadi, Amir Ali Jungers, Raphael M. Parrilo, Pablo A. Roozbehani, Mardavij |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Ahmadi, Amir Ali Jungers, Raphael M. Parrilo, Pablo A. Roozbehani, Mardavij |
| author_sort | Ahmadi, Amir Ali |
| collection | MIT |
| description | 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/[superscript 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. |
| first_indexed | 2024-09-23T08:16:11Z |
| format | Article |
| id | mit-1721.1/72962 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:16:11Z |
| publishDate | 2012 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/729622022-09-23T11:58:50Z Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs Ahmadi, Amir Ali Jungers, Raphael M. Parrilo, Pablo A. Roozbehani, Mardavij Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Parrilo, Pablo A. Ahmadi, Amir Ali Jungers, Raphael M. Parrilo, Pablo A. Roozbehani, Mardavij 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/[superscript 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. 2012-09-14T15:48:16Z 2012-09-14T15:48:16Z 2011-04 Article http://purl.org/eprint/type/ConferencePaper 978-1-4503-0629-4 http://hdl.handle.net/1721.1/72962 Amir Ali Ahmadi, Rapha\&\#235;l Jungers, Pablo A. Parrilo, and Mardavij Roozbehani. 2011. Analysis of the joint spectral radius via lyapunov functions on path-complete graphs. In Proceedings of the 14th international conference on Hybrid systems: computation and control (HSCC '11). ACM, New York, NY, USA, 13-22. https://orcid.org/0000-0003-1132-8477 en_US http://dx.doi.org/10.1145/1967701.1967706 Proceedings of the 14th international conference on Hybrid systems: computation and control (HSCC '11) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Ahmadi, Amir Ali Jungers, Raphael M. Parrilo, Pablo A. Roozbehani, Mardavij Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs |
| title | Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs |
| title_full | Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs |
| title_fullStr | Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs |
| title_full_unstemmed | Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs |
| title_short | Analysis of the Joint Spectral Radius Via Lyapunov Functions on Path-Complete Graphs |
| title_sort | analysis of the joint spectral radius via lyapunov functions on path complete graphs |
| url | http://hdl.handle.net/1721.1/72962 https://orcid.org/0000-0003-1132-8477 |
| work_keys_str_mv | AT ahmadiamirali analysisofthejointspectralradiusvialyapunovfunctionsonpathcompletegraphs AT jungersraphaelm analysisofthejointspectralradiusvialyapunovfunctionsonpathcompletegraphs AT parrilopabloa analysisofthejointspectralradiusvialyapunovfunctionsonpathcompletegraphs AT roozbehanimardavij analysisofthejointspectralradiusvialyapunovfunctionsonpathcompletegraphs |