Counter-Constrained Stability of Switched Linear Systems via Drift Tilting

Many control loops switch between a few linear behaviors, and the choice of behavior is gated by a resource: a deadline-miss budget that refills on successful runs, a token bucket, a battery that charging steps fill and actuation steps drain. A natural model for such gating is a vector addition system with states (VASS): a finite automaton carrying nonnegative integer counters, where each transition adds a fixed integer vector to the counters and may never drive a counter below zero. The stability question asks whether every product of the plant matrices along a counter-legal run shrinks the state. Existing stability tools handle arbitrary switching, or switching restricted by a finite automaton. Counters make the set of legal switching sequences infinite-state and non-regular, and reachability for VASS is notoriously hard, so nothing off the shelf applies.

The core claim is that, for the asymptotic growth rate, the counters can be removed exactly at the level of a sound upper bound. Multiply each transition's matrix by $e^{\lambda\cdot v}$, where $v$ is that transition's counter update and $\lambda\ge 0$ is a vector of "prices." Then compute an ordinary automaton-constrained growth rate with existing solvers, and minimize over $\lambda$, which is a convex problem. Cheap cycle-based lower bounds sandwich the true rate. The open scientific question is when the gap between the two bounds is zero. The note proposes to answer it with tools from the finiteness and norm-versus-spectral-radius literature.

Core Claim

Let the control automaton have states $Q$ and transitions $e=(q,A_e,v_e,q')$, with $A_e\in\mathbb{R}^{n\times n}$ the plant matrix and $v_e\in\mathbb{Z}^d$ the counter update. Define the counter-constrained joint spectral radius $\rho_V$ as the largest exponential growth rate of $\|A_w\|^{1/t}$ over runs $w$ of length $t$ that keep counters nonnegative from some initial counter vector $x_0$. The joint spectral radius (JSR) is the growth rate of the worst switching sequence; $\rho_V<1$ means stability under every legal schedule. Along any legal run, the total counter displacement is at least $-x_0$. Because $\prod_e e^{\lambda\cdot v_e}A_e = e^{\lambda\cdot\sum v}A_w$, the following holds:

$$\rho_V \;\le\; \inf_{\lambda\ge 0}\ \rho_G\big(\{e^{\lambda\cdot v_e}A_e\}\big), \qquad \rho_V \;\ge\; \max_{c:\ \Delta_c\ge 0}\ \rho(A_c)^{1/|c|}.$$

Here $\rho_G$ is the automaton-constrained JSR over the control graph alone, and the lower bound ranges over cycles $c$ whose net counter drift $\Delta_c$ is nonnegative in every coordinate. Such cycles can be repeated forever from a large enough $x_0$.

The log of the tilted rate is a supremum of functions affine in $\lambda$, so it is convex in $\lambda$. Any sound upper bound on $\rho_G$ at any $\lambda$, such as a sum-of-squares certificate, is therefore a sound bound on $\rho_V$. The certificate lives on an automaton with $|Q|$ states. There is no counter truncation and no blow-up of the form $(B+1)^d$.

The intuition is a Lagrangian: transitions that consume resources get shrunk, so they cannot dominate growth unless producers pay for them. A second consequence is conceptual. Exact VASS reachability is Ackermann-complete in general. It becomes NP-complete already for 3-counter simple linear path schemes, as shown in The Tractability Border of Reachability in Simple Vector Addition Systems with States. The asymptotic rate, however, depends only on long-run drift. That makes the stability question closer to the continuous relaxations studied in Reachability in Continuous Pushdown VASS than to discrete reachability. These hardness results constrain the proposal: we do not claim to decide exact finite-horizon legality cheaply, only the rate.

Relation to Prior Work

Three lines of work handle constrained switching, and all three assume finite memory. They supply the solver we call at each $\lambda$, and they motivate the gap.

Joint Spectral Radius and Path-Complete Graph Lyapunov Functions gives matrix-inequality certificates for switching restricted by a graph. Stability of discrete-time switching systems with constrained switching sequences treats regular-language constraints. Stability of Linear Systems Under Extended Weakly-Hard Constraints encodes window-based deadline-miss rules as an automaton, lifts it with Kronecker products, and bounds the result with sparse sum-of-squares. Window rules are regular. A refillable miss budget is a counter, and it is exactly what these works cannot express.

For the per-$\lambda$ computation we reuse two methods:

For the gap, the norm-spectral literature supplies tools. The finiteness conjecture for the generalized spectral radius of a set of matrices shows that under polytope norms the worst-case growth is attained by a product whose length is bounded by the polytope's face count. If the tilted system at the optimal price $\lambda^\*$ has such a finite extremal cycle, and that cycle has nonnegative drift, the two bounds meet and the certificate is exact. If instead the optimum requires mixing a resource-producing cycle with a growth-heavy consuming cycle, the gap can be genuinely nonzero. Concatenating two non-commuting cycle products can destroy growth; for example, one cycle can map the other's dominant direction toward its own contracting directions.

Continuity of the spectrum of norm-normal matrices bounds operator norm by twice the spectral radius for norm-normal matrices. This suggests a sufficient condition: if cycle products are norm-normal in a common norm, losses occur only at block boundaries and vanish in the long-run rate. We will try to prove this condition. We will also test whether it is close to necessary.

Research Program

On the theory side there are four goals. First, prove the sandwich and its convexity in full generality, including the case where every initial counter vector is allowed. Second, give a gap-zero theorem under a finiteness-plus-drift condition built on Lagarias–Wang. Third, give a gap bound for norm-normal or commuting cycle families using Zając's inequality. Fourth, construct an explicit two-cycle counterexample with a strictly positive gap, so that the limits of the bound are documented rather than hidden.

We will also ask whether deciding $\rho_V<1$ inherits the dimension cliff of VASS reachability. The concrete question is whether 1- and 2-counter instances admit exact dual characterizations while 3 counters already break them. This mirrors the 2-versus-3 border of Chistikov et al.

On the algorithmic side, we will build a solver with an outer loop and an inner solver. The outer loop is convex minimization over $\lambda\in\mathbb{R}^d_{\ge 0}$; it uses subgradients obtained from the near-extremal cycle found by the inner solver, whose drift is a subgradient of the log-rate. The inner solver is a path-complete or SparseJSR certificate on the $|Q|$-state lifted system. The lower bound comes from enumerating cycles of the control graph with nonnegative drift and pairwise drift-balanced mixtures of the form $C_1^aC_2^b$. Cycle lengths are capped by the Lagarias–Wang face bound when a polytope norm is available from a learned piecewise-linear certificate.

Baselines

The naive reference is the unconstrained JSR of all transition matrices, computed with SparseJSR. Because it bounds every schedule, it is sound but blind to the counters. On the 2D benchmark of Debauche et al., its tightness is anchored by reported upper bounds of about 8.69 for the neural method, 8.72 for degree-4 sum-of-squares, and 9.58 for ellipsoids. Any instance where our method certifies $\rho_V<1$ while this baseline reports $\ge 1$ counts as a win in kind, not in degree.

The second reference is the automaton-constrained JSR of the control graph with counters ignored, which is our method frozen at $\lambda=0$. This is the ablation that isolates the tilting. Every point of improvement over it is attributable to pricing resources.

The strongest competitor is counter truncation. Counters are capped at $B$ with saturation, which keeps the abstraction a sound over-approximation, giving an automaton of $|Q|(B+1)^d$ states. That automaton is lifted Kronecker-style as in Vreman et al. and bounded with SparseJSR. As $B$ grows, its bound should approach the true rate from above.

The fairness protocol has four parts. Both methods use the same SparseJSR relaxation order and the same solver and machine. Both get an equal wall-clock budget. Truncation is given its best $B$ within that budget, and our method is given its best $\lambda$ search within the same budget.

For context on scale, SparseJSR reports dense sum-of-squares taking over 3600 seconds at matrix size 100 versus 12 seconds for SparseJSR at size 120. It also reports upper bounds often within 0.05 of computed lower bounds. There is no reported result on Lacuna for any counter-constrained switched system, so truncation numbers will be produced here.

Beating truncation means one of two outcomes. The first is a tighter bound at equal time. The second is matching its large-$B$ limit at a fraction of the time, as $d$ and $n$ grow.

A brute-force lower reference enumerates all legal runs up to a fixed length from small initial counters. It validates both bounds on small instances.

Why not just…?

Why not just truncate the counters and use existing automaton tools? This is the real threat. For one counter with small updates, a modest $B$ may already be tight and cheap. The lifted dimension is $n\,|Q|(B+1)^d$, so with $d=3$ and $B=10$ it exceeds a thousand times $n$, beyond what dense solvers handle. Even sparse solvers depend on structure that Kronecker lifting tends to densify. Saturating counters is sound but inflates the bound in a way that only $B\to\infty$ removes. The truncation-versus-dimension sweep in the experiments settles where the crossover lies. If truncation wins for $d\le 2$, we will say so and position the method for $d\ge 2$.

Why not just use a regular separator of the VASS language as a finite abstraction? Regular separators, as in Regular Separators for VASS Coverability Languages and An Approach to Regular Separability in Vector Addition Systems, separate two disjoint languages. Stability needs a regular superset of legal runs that excludes growth-heavy patterns. The set of "growing" words is not a VASS language, so there is no second language to separate against. The trivial superset is the control automaton, which is exactly our $\lambda=0$ ablation.

Why not just train a neural Lyapunov function on sampled legal runs? Debauche et al. report that unregularized training gives estimates below the true JSR. Stability Verification for Switched Systems using Neural Multiple Lyapunov Functions notes that its counterexample-guided loop with SMT solvers is computationally heavy. Sampling legal runs also biases toward short counter excursions. Neural norms remain useful here as the inner solver at fixed $\lambda$. We will run that variant, so the comparison is about the outer reduction, not the certificate family.

Proposed Experiments

Constructed benchmarks. There is no counter-constrained benchmark, so we construct three families on top of the file's systems.

  1. The process-plant-plus-PI-controller of Vreman et al., with the window rule replaced by a refillable miss budget: misses decrement a counter, hits increment it with a cap-free refill. This also includes a two-task variant with $d=2$.
  2. The 2D and 8D switched benchmarks of Debauche et al., with random VASS control graphs of 3–20 states and $d\in\{1,2,3\}$, chosen so that the unconstrained JSR exceeds 1.
  3. Random sparse matrices of size up to 120, following the SparseJSR setup, for scaling.

Metrics. We record upper bound, lower bound, the relative gap between them, wall-clock time, and the fraction of instances certified stable.

Decisive checks.

  • On families 1 and 2, our bound must be strictly below the $\lambda=0$ ablation on a substantial share of instances. If it never is, tilting adds nothing.
  • On small instances, our upper bound must never fall below brute-force legal-run growth. This is a soundness check, and any violation is a bug.
  • On hand-built two-cycle instances designed with and without the norm-normal structure, the measured gap should be near zero exactly where the theory predicts, and positive on the constructed counterexample.
  • As $d$ goes from 1 to 3, truncation's time to match our bound should grow roughly like $(B+1)^d$, while ours grows only with $|Q|$ and the number of $\lambda$ iterations. If that separation does not appear, the main practical claim fails.