Iterative graph lifting for automatic design of path-complete stability certificates
Abstract
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.
Related
- Closed-Relational Reconstruction Systems: Viability, Observable-History Lifting, and Finite Obstruction Certificates
- EquiPartition: Learning Player-Adaptive Deviation Certificates for Complete Enclosure of Approximate Nash Equilibria in Strategic Financial Markets
- Stability Transfer for Autonomous Systems via Higher-Order Taylor-Truncated Lyapunov Certificates
- Data-to-Certificates (D2C): Koopman Supereigenfunctions for Stability, Safety, and Control
- Functional Regression with Reconstructed Curves: Local Rank Stability and Optimized Confidence Certificates
BibTeX
@misc{ninite2026iterative,
title = {{Iterative graph lifting for automatic design of path-complete stability certificates}},
author = {Léa Ninite and Raphaël M. Jungers},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.00637},
eprint = {2607.00637},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.00637},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Iterative graph lifting for automatic design of path-complete stability certificates
AU - Léa Ninite
AU - Raphaël M. Jungers
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2607.00637
UR - https://arxiv.org/abs/2607.00637
AB - 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.
ER -