A simple tree-based algorithm for deciding the stability of discrete-time switched linear systems

We re-evaluate the direct approach to study the stability of discrete-time switched systems with finitely many linear modes. We explore the tree of possible matrix products by pruning the paths leading to contractions and looking for unstable repeatable products. Generically, this simple strategy either terminates with all contracting leafs-showing the asymptotic stability of the system-or finds the shortest unstable matrix product. Although it behaves in the worst-case as the exhaustive search, we show that its performance is greatly enhanced by measuring contractiveness w.r.t. sum-of-squares polynomial norms, optimized to minimize the largest expansion among the system's modes. We test our approach on several benchmark examples proposed to test switched Lyapunov function methods. Although these methods are mathematically elegant and efficient, they are more involved to apply and cannot decide the system's instability. Moreover, our algorithm is flexible. Adding/removing system's modes, setting mode-independent dwell-times, and constraining switching to finite automata can all be easily implemented and exploited in control design.