The reviewed record of science sign in
Pith

arxiv: 2607.00637 · v1 · pith:DTFKQNYG · submitted 2026-07-01 · math.OC

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

L\'ea Ninite , Rapha\"el M. Jungers This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-07-02 08:06 UTCgrok-4.3pith:DTFKQNYGrecord.jsonopen to challenge →

classification math.OC
keywords path-complete graphsjoint spectral radiusswitched linear systemsstability certificatesgraph liftingiterative algorithmoptimization
0
0 comments X

The pith

An iterative algorithm refines path-complete graphs by local node splitting to attain the exact joint spectral radius when a sufficient condition holds.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an iterative procedure for constructing path-complete stability certificates for switched linear systems. It uses a graph-theoretic examination of optimality conditions in the underlying optimization problem to determine when a given labeled directed graph yields the exact joint spectral radius. When the condition fails, the method isolates bottleneck nodes from the active-constraint subgraph and refines the graph by splitting those nodes. The process repeats until either the exact value is reached or further improvement is obtained. This matters because the joint spectral radius governs worst-case trajectory growth under arbitrary switching, and manual design of tight certificates has been difficult.

Core claim

The central claim is that analysis of the graph induced by active constraints in the path-complete optimization problem identifies nodes whose local lifting produces a strictly better certificate, and that a derived sufficient condition on this refined graph guarantees it attains the exact joint spectral radius.

What carries the argument

Path-complete graphs (labeled directed graphs encoding algebraic stability certificates via an associated optimization problem), refined by local lifting (node splitting) guided by the active-constraint subgraph.

If this is right

  • Whenever the sufficient condition is satisfied after lifting, the resulting certificate equals the exact joint spectral radius.
  • The procedure terminates with an exact certificate on instances where the condition becomes true.
  • The refinement adds nodes only locally, keeping the graphs parsimonious.
  • Numerical tests show the method outperforms prior state-of-the-art approaches on all challenging instances examined.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same active-constraint analysis could guide refinement in related graph-based certificate problems outside switched linear systems.
  • Systems with periodic or constrained switching signals might admit analogous lifting rules derived from their own optimality conditions.
  • The method's reported scalability suggests it could serve as a subroutine inside branch-and-bound or mixed-integer solvers for joint spectral radius.

Load-bearing premise

The active constraints correctly identify bottleneck nodes whose splitting produces a strictly better or exact certificate.

What would settle it

A switched linear system on which the sufficient condition is reported to hold yet the computed value differs from the true joint spectral radius obtained by any independent method.

Figures

Figures reproduced from arXiv: 2607.00637 by L\'ea Ninite, Rapha\"el M. Jungers.

Figure 1
Figure 1. Figure 1: (a) Path-complete graph with two nodes, for a system [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Forward lift of the graph in Figure 1a with respect to node a1. In the theorem below, we prove that the forward lift preserves path-completeness. Theorem 2: Let G = (S, E) be a path-complete graph. Then, for any node v ∈ S, the forward lift of G with respect to v is path-complete. Proof: Let K ∈ N>0 and let σ = (i1, . . . , iK) ∈ ⟨M⟩ K be any sequence of labels. Since G is path-complete, there exists a pat… view at source ↗
Figure 3
Figure 3. Figure 3: Comparison between the De Bruijn hierarchy and [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes an iterative algorithm for automatically refining path-complete graphs to approximate or attain the exact joint spectral radius (JSR) of switched linear systems. It performs a graph-theoretic analysis of the optimality conditions of the associated linear program to derive a sufficient condition under which a given path-complete graph yields the exact JSR. When the condition fails, the algorithm constructs the subgraph induced by active constraints to identify bottleneck nodes, applies local lifting via node splitting to refine the graph while preserving path-completeness, and iterates. Numerical experiments indicate that the method outperforms existing approaches on all tested challenging instances.

Significance. If the central claims hold, the work offers a systematic, optimization-driven procedure for improving path-complete stability certificates, with the potential to achieve exact JSR more reliably than prior heuristic or manual designs. The grounding in optimality conditions of the JSR LP and the empirical outperformance on hard instances are notable strengths that could advance computational methods for stability analysis of switched systems.

major comments (2)
  1. [Section on sufficient condition and active constraints] The section deriving the sufficient condition for exact JSR (based on active-constraint analysis): the argument that the induced subgraph correctly identifies all bottleneck nodes whose splitting yields exactness must explicitly rule out omitted cross-path dependencies in the path-complete graph; without this, the sufficiency claim risks being incomplete.
  2. [Section on graph lifting and refinement] The section on the local lifting operation: it is not shown that node splitting always produces a strictly tighter bound (or preserves feasibility) when the sufficient condition fails; if the lifting can leave the JSR upper bound unchanged due to unaccounted interactions, the iteration may terminate suboptimally even when refinement is possible.
minor comments (2)
  1. [Numerical experiments] The numerical experiments section would benefit from reporting the fraction of instances where the sufficient condition is met and from including an ablation on the effect of different splitting heuristics.
  2. [Preliminaries] Notation for the path-complete graph, the LP variables, and the active-set subgraph should be introduced with a single consistent table or diagram to aid readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We address each major comment below, indicating the revisions we will make to clarify and strengthen the arguments in the manuscript.

read point-by-point responses

  1. Referee: [Section on sufficient condition and active constraints] The section deriving the sufficient condition for exact JSR (based on active-constraint analysis): the argument that the induced subgraph correctly identifies all bottleneck nodes whose splitting yields exactness must explicitly rule out omitted cross-path dependencies in the path-complete graph; without this, the sufficiency claim risks being incomplete.

    Authors: We appreciate the referee pointing out the need for an explicit treatment of cross-path dependencies. Path-completeness ensures that every finite switching sequence corresponds to at least one path in the graph, so any interaction between paths that could affect the optimality conditions of the JSR linear program must appear as an active constraint. Consequently the induced subgraph on active constraints already incorporates all such interactions. To make this reasoning fully transparent we will insert a short clarifying paragraph immediately after the statement of the sufficient condition, explicitly invoking the path-completeness definition to rule out omitted cross-path dependencies. revision: yes

  2. Referee: [Section on graph lifting and refinement] The section on the local lifting operation: it is not shown that node splitting always produces a strictly tighter bound (or preserves feasibility) when the sufficient condition fails; if the lifting can leave the JSR upper bound unchanged due to unaccounted interactions, the iteration may terminate suboptimally even when refinement is possible.

    Authors: The referee correctly notes that a formal guarantee on the effect of the local lifting step is not stated. While the construction is motivated by the active-constraint subgraph and the numerical results show improvement, we do not provide a general proof that node splitting always yields a strictly smaller optimal value of the linear program (hence a strictly tighter JSR upper bound) while preserving feasibility and path-completeness. We will add a short proposition establishing these properties by exhibiting an explicit feasible solution on the lifted graph whose objective value is strictly better whenever the sufficient condition fails. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation rests on external optimization analysis and graph theory

full rationale

The paper presents an iterative refinement procedure whose core steps consist of analyzing the optimality conditions of a pre-existing linear program for path-complete JSR bounds, extracting an induced subgraph from active constraints, and performing local node-splitting lifts. No quoted equation or algorithmic step equates a derived quantity to a fitted parameter or to a self-referential definition; the sufficient condition for exactness is obtained by direct inspection of the dual or KKT system rather than by construction. Self-citations to prior path-complete literature are present but not load-bearing for the new lifting rule, which is justified inside the manuscript by the active-set construction itself. The numerical experiments are reported separately and do not feed back into the claimed derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review supplies no explicit free parameters, axioms, or invented entities; the central claim rests on the unstated details of the optimization problem and the correctness of the bottleneck identification step.

pith-pipeline@v0.9.1-grok · 5718 in / 1021 out tokens · 24217 ms · 2026-07-02T08:06:29.094986+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Liberzon,Switching in systems and control

    D. Liberzon,Switching in systems and control. Springer, 2003, vol. 190

    work page 2003

  2. [2]

    Jungers,The joint spectral radius: theory and applications

    R. Jungers,The joint spectral radius: theory and applications. Springer Science & Business Media, 2009, vol. 385

    work page 2009

  3. [3]

    Stability analysis of networked control systems using a switched linear systems approach,

    M. Donkers, W. M. H. Heemels, N. Van de Wouw, and L. Hetel, “Stability analysis of networked control systems using a switched linear systems approach,”IEEE Transactions on Automatic control, vol. 56, no. 9, pp. 2101–2115, 2011

    work page 2011

  4. [4]

    Constant and switching gains in semi-active damping of vibrating structures,

    F. Blanchini, D. Casagrande, P. Gardonio, and S. Miani, “Constant and switching gains in semi-active damping of vibrating structures,” International Journal of Control, vol. 85, no. 12, pp. 1886–1897, 2012

    work page 2012

  5. [5]

    Optimal and mpc switching strategies for mitigating viral mutation and escape,

    E. A. Hernandez-Vargas, R. H. Middleton, and P. Colaneri, “Optimal and mpc switching strategies for mitigating viral mutation and escape,” IFAC Proceedings Volumes, vol. 44, no. 1, pp. 14 857–14 862, 2011

    work page 2011

  6. [6]

    A note on the joint spectral radius,

    G.-C. Rota and G. Strang, “A note on the joint spectral radius,” Indagationes Mathematicae, vol. 22, pp. 379–381, 1960

    work page 1960

  7. [7]

    The boundedness of all products of a pair of matrices is undecidable,

    V . Blondel and J. Tsitsiklis, “The boundedness of all products of a pair of matrices is undecidable,”Systems & Control Letters, vol. 41, pp. 135–140, 10 2000

    work page 2000

  8. [8]

    The lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate,

    J. N. Tsitsiklis and V . D. Blondel, “The lyapunov exponent and joint spectral radius of pairs of matrices are hard—when not impossible—to compute and to approximate,”Mathematics of Control, Signals, and Systems, vol. 10, pp. 31–40, 1997

    work page 1997

  9. [9]

    S. Boyd, L. El Ghaoui, E. Feron, and V . Balakrishnan,Linear Matrix Inequalities in System and Control Theory. Society for Industrial and Applied Mathematics, 1994

    work page 1994

  10. [10]

    Approximation of the joint spectral radius using sum of squares,

    P. A. Parrilo and A. Jadbabaie, “Approximation of the joint spectral radius using sum of squares,”Linear Algebra and its Applications, vol. 428, no. 10, pp. 2385–2402, 2008

    work page 2008

  11. [11]

    Multiple lyapunov functions and other analysis tools for switched and hybrid systems,

    M. Branicky, “Multiple lyapunov functions and other analysis tools for switched and hybrid systems,”IEEE Transactions on Automatic Control, vol. 43, no. 4, pp. 475–482, 1998

    work page 1998

  12. [12]

    Uniform stabilization of discrete-time switched and markovian jump linear systems,

    J.-W. Lee and G. E. Dullerud, “Uniform stabilization of discrete-time switched and markovian jump linear systems,”Automatica, vol. 42, no. 2, pp. 205–218, 2006

    work page 2006

  13. [13]

    Joint spectral radius and path-complete graph lyapunov functions,

    A. A. Ahmadi, R. M. Jungers, P. A. Parrilo, and M. Roozbehani, “Joint spectral radius and path-complete graph lyapunov functions,”SIAM Journal on Control and Optimization, vol. 52, no. 1, pp. 687–717, 2014

    work page 2014

  14. [14]

    Stability analysis of discrete- time switched systems through lyapunov functions with nonminimal state,

    P.-A. Bliman and G. Ferrari-Trecate, “Stability analysis of discrete- time switched systems through lyapunov functions with nonminimal state,”IFAC Proceedings Volumes, vol. 36, no. 6, pp. 325–329, 2003

    work page 2003

  15. [15]

    On a combinatorial problem,

    N. G. De Bruijn and P. Erd ¨os, “On a combinatorial problem,” Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, vol. 51, no. 10, pp. 1277– 1279, 1948

    work page 1948

  16. [16]

    A charac- terization of lyapunov inequalities for stability of switched systems,

    R. Jungers, A. Ahmadi, P. Parrilo, and M. Roozbehani, “A charac- terization of lyapunov inequalities for stability of switched systems,” IEEE Transactions on Automatic Control, vol. 62, no. 6, pp. 3062– 3067, 2017

    work page 2017

  17. [17]

    Polyhedral path-complete lyapunov functions,

    N. Athanasopoulos and R. M. Jungers, “Polyhedral path-complete lyapunov functions,” in2019 IEEE 58th Conference on Decision and Control (CDC), 2019, pp. 3399–3404

    work page 2019

  18. [18]

    Succinct synthesis of multiple lyapunov certificates for switched systems,

    A. Abate, V . Debauche, M. Giacobbe, and D. Roy, “Succinct synthesis of multiple lyapunov certificates for switched systems,” inProceedings of the ACM International Conference on Hybrid Systems: Computation and Control (HSCC), 2026, to appear. APPENDIX A. Proof of Proposition 1 Let(γ ⋆,{P ⋆ a })and(˜γ,{ ˜Pa})be optimal solutions to Problem 1 onGand ˜G, re...

    work page 2026