User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Path-Complete Graphs and Common Lyapunov Functions

Primary tabs

Angeli, David [University of Florence, Italy] Athanasopoulos, Nikolaos [UCL] Jungers, Raphaël M. [UCL] Philippe, Matthew [UCL]

A Path-Complete Lyapunov Function is an algebraic criterion composed of a finite number of functions, called its pieces, and a directed, labeled graph defining Lyapunov inequalities between these pieces. It provides a stability certificate for discrete-time switching systems under arbitrary switching. In this paper, we prove that the satisfiability of such a criterion implies the existence of a Common Lyapunov Function, expressed as the composition of minima and maxima of the pieces of the Path-Complete Lyapunov function. The converse, however, is not true even for discrete-time linear systems: we present such a system where a max-of-2 quadratics Lyapunov function exists while no corresponding PathComplete Lyapunov function with 2 quadratic pieces exists. In light of this, we investigate when it is possible to decide if a Path-Complete Lyapunov function is less conservative than another. By analyzing the combinatorial and algebraic structure of the graph and the pieces respectively, we provide simple tools to decide when the existence of such a Lyapunov function implies that of another.

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Access type Accès interdit
Publication date 2017
Language Anglais
Conference "the 20th International Conference", Pittsburgh, Pennsylvania, USA (du 18/4/2017 au 20/4/2017)
Peer reviewed yes
Host document "Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control - HSCC '17"
Publisher ACM Press
Publication status Publié
Affiliation UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Keywords Discrete-time switching systems ; Lyapunov Function ; PathComplete graph ; Observer Automaton
Links
  1. Shorten Robert, Wirth Fabian, Mason Oliver, Wulff Kai, King Christopher, Stability Criteria for Switched and Hybrid Systems, 10.1137/05063516x
  2. Philippe Matthew, Essick Ray, Dullerud Geir E., Jungers Raphaël M., Stability of discrete-time switching systems with constrained switching sequences, 10.1016/j.automatica.2016.05.015
  3. Parrilo Pablo A., Jadbabaie Ali, Approximation of the joint spectral radius using sum of squares, 10.1016/j.laa.2007.12.027
  4. Lin Hai, Antsaklis Panos J., Stability and Stabilizability of Switched Linear Systems: A Survey of Recent Results, 10.1109/tac.2008.2012009
  5. Liberzon D., Morse A.S., Basic problems in stability and design of switched systems, 10.1109/37.793443
  6. Lee Ji-Woong, Dullerud Geir E., Uniform stabilization of discrete-time switched and Markovian jump linear systems, 10.1016/j.automatica.2005.08.019
  7. Kozyakin Victor, The Berger–Wang formula for the Markovian joint spectral radius, 10.1016/j.laa.2014.01.022
  8. Raphael M Jungers, WPMH Heemels, and Atreyee Kundu. Observability and controllability analysis of linear systems subject to data losses. arXiv preprint arXiv:1609.05840, 2016.
  9. Raphael M Jungers, Amirali Ahmadi, Pablo Parrilo, and Mardavij Roozbehani. A characterization of lyapunov inequalities for stability of switched systems. arXiv preprint arXiv:1608.08311, 2016.
  10. Raphaël Jungers. The joint spectral radius. Lecture Notes in Control and Information Sciences, 385, 2009.
  11. Johansson M., Rantzer A., Computation of piecewise quadratic Lyapunov functions for hybrid systems, 10.1109/9.664157
  12. Rafal Goebel, Tingshu Hu, and Andrew 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. Springer, 2006.
  13. Essick Ray, Lee Ji-Woong, Dullerud Geir E., Control of Linear Switched Systems With Receding Horizon Modal Information, 10.1109/tac.2014.2321251
  14. Daafouz J., Riedinger P., Iung C., Stability analysis and control synthesis for switched systems: a switched Lyapunov function approach, 10.1109/tac.2002.804474
  15. Christos G Cassandras and Stephane Lafortune. Introduction to discrete event systems. Springer Science & Business Media, 2009.
  16. Branicky M.S., Multiple Lyapunov functions and other analysis tools for switched and hybrid systems, 10.1109/9.664150
  17. Blondel Vincent D., Tsitsiklis John N., The boundedness of all products of a pair of matrices is undecidable, 10.1016/s0167-6911(00)00049-9
  18. Pierre-Alexandre Bliman and Giancarlo Ferrari-Trecate. Stability analysis of discrete-time switched systems through lyapunov functions with nonminimal state. In Proceedings of IFAC Conference on the Analysis and Design of Hybrid Systems, pages 325--330, 2003.
  19. Athanasopoulos Nikolaos, Lazar Mircea, Alternative Stability Conditions for Switched Discrete Time Linear Systems, 10.3182/20140824-6-za-1003.01634
  20. Ahmadi Amir Ali, Jungers Raphaël M., Parrilo Pablo A., Roozbehani Mardavij, Joint Spectral Radius and Path-Complete Graph Lyapunov Functions, 10.1137/110855272
Bibliographic reference Angeli, David ; Athanasopoulos, Nikolaos ; Jungers, Raphaël M. ; Philippe, Matthew. Path-Complete Graphs and Common Lyapunov Functions.the 20th International Conference (Pittsburgh, Pennsylvania, USA, du 18/4/2017 au 20/4/2017). In: Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control - HSCC '17, ACM Press2017
Permanent URL http://hdl.handle.net/2078.1/194124