Iterative graph lifting for automatic design of path-complete stability certificates

Stability of switched linear systems under arbitrary switching is a fundamental problem in control theory, closely related to the joint spectral radius (JSR), which characterizes the worst-case growth rate of system trajectories.

In this paper, we contribute to the path-complete approach for approximating the JSR.

This framework constructs algebraic stability certificates using labeled directed graphs, known as path-complete graphs.

These certificates can be computed via an associated optimization problem.

We propose an iterative algorithm that refines path-complete graphs in an efficient and parsimonious manner.

The algorithm relies on a graph-theoretic analysis of the optimality conditions of the underlying optimization problem.

In particular, we derive a sufficient condition under which the exact JSR is attained by a given path-complete graph.

When this condition is not satisfied, we identify bottleneck nodes by analyzing the graph induced by the active constraints.

We then use this information to refine the path-complete graph via local graph lifting (node splitting), and repeat the procedure.

Numerical experiments demonstrate the effectiveness and scalability of the proposed approach, outperforming state-of-the-art methods on all challenging instances tested.