When Is a Set of LMIs a Sufficient Condition for Stability?

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

Abstract

This paper provides a definitive answer to a fundamental question in control theory: which sets of Linear Matrix Inequalities (LMIs) actually guarantee the stability of a discrete-time switching system? The authors prove that a set of LMIs is a valid stability criterion if and only if its underlying combinatorial structure forms a "path-complete" graph. Furthermore, they demonstrate that verifying this property is PSPACE-complete, revealing a fundamental computational limit in the automated discovery of stability proofs.

Introduction

The paper focuses on switching systems, dynamical systems that change behavior over time by switching between different linear modes represented by a set of matrices $\Sigma = \{A_1, \dots, A_m\}$. These systems are ubiquitous in fields ranging from viral disease treatment optimization to autonomous agent tracking.

The central challenge is stability: determining if the system's state always trends toward zero, regardless of the switching sequence. Proving this is notoriously difficult because it requires calculating the "joint spectral radius" (JSR) of the matrices, a task known to be computationally hard. Engineers typically use Linear Matrix Inequalities (LMIs) to find a common Lyapunov function—a mathematical "energy" function that decreases at every step—to prove stability. While many LMI-based tests exist, there was previously no general rule to determine if a newly proposed set of LMIs was a valid proof of stability.

Graphical Representation and Path-Completeness

The authors utilize a framework that maps sets of LMIs to directed labeled graphs. In this representation, each node in the graph corresponds to a Lyapunov function, and each directed edge represents an LMI—a requirement that the "energy" decreases when a specific matrix from $\Sigma$ is applied.

Figure 2: A directed labeled graph representing a set of LMIs for two matrices, $A_1$ and $A_2$. This specific graph is path-complete.

A graph is defined as "path-complete" if every possible sequence of matrix applications (every "word" in the alphabet of matrices) can be found as a subword of some path in the graph. This property ensures that the stability test "covers" all possible trajectories the system might take.

Key Theoretical Insights

The paper's primary contribution is the Combinatorial Link: the validity of an LMI-based stability test is fundamentally about the combinatorics of the switching sequences. If a test does not account for every possible "path," it cannot be a sufficient condition for stability.

The authors prove a "converse" theorem. While it was already known that path-complete graphs provide sufficient conditions, this paper proves they are the only ones for common classes like ellipsoidal and entrywise-comparison Lyapunov functions. To prove this, they developed a method to build specific "unstable" matrices. If a graph is not path-complete, there exists some sequence of switches it doesn't cover. The authors construct a set of matrices that are unstable precisely because of that missing sequence, yet still satisfy the LMIs defined by the non-path-complete graph.

Results and Complexity

The core results, Theorems 5 and 6, state that for both entrywise-comparison and ellipsoidal Lyapunov inequalities, the criterion is sufficient for stability if and only if the corresponding graph is path-complete.

Figure 3: An example of a non-path-complete graph. This cycle only represents a specific subset of switching sequences, failing to cover all possible words in the alphabet {1, 2}.

Beyond the characterization, the paper addresses the Complexity Barrier. By reducing the problem to the "full language problem" in automata theory, the authors show that deciding if a set of LMIs is a valid stability criterion is PSPACE-complete. This implies there is likely no efficient algorithm to verify new stability criteria as they increase in complexity.

Conclusion and Future Work

This work establishes a rigorous foundation for LMI-based stability analysis. However, several avenues for future research remain:

  • Scope of Lyapunov Functions: The proof covers ellipsoidal and entrywise-comparison functions. It remains an open question whether the path-complete requirement holds for other families, such as Complex Polytope Lyapunov functions.
  • Matrix Count: The PSPACE-completeness proof requires a variable number of matrices. The complexity for a fixed, small number of matrices (e.g., two) is still unknown.
  • Generalization: These techniques could potentially be generalized to other hybrid systems or different spectral characteristics, such as the Lyapunov exponent or the joint spectral subradius.

Summary updated

BibTeX
@inproceedings{ahmadi2012when,
  author = {Amir Ali Ahmadi and Raphaël M. Jungers and Pablo A. Parrilo and Mardavij Roozbehani},
  title = {{When Is a Set of LMIs a Sufficient Condition for Stability?}},
  booktitle = {ROCOND},
  year = {2012},
  doi = {10.3182/20120620-3-dk-2025.00098},
}
Figure