⚡ electrical engineering

Ordering and refining path-complete Lyapunov functions through composition lifts

This paper refutes a conjecture regarding the composition lift for path-complete Lyapunov functions while leveraging the resulting structural insights to iteratively refine path-complete graphs and propose a favorable adaptation of the lift.

Original authors: Wouter Jongeneel, Raphaël M. Jungers

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wouter Jongeneel, Raphaël M. Jungers

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to keep a complex machine running smoothly. This machine isn't just one engine; it's a switched system. Think of it like a car that can instantly switch between different gears, or a robot that changes its walking style every second. Sometimes, the individual parts (the gears or walking styles) are stable on their own, but if you switch them randomly, the whole machine might shake apart and crash.

The goal of this paper is to figure out how to prove that this machine will stay stable no matter how it switches.

The Problem: Too Many Rules, Not Enough Clarity

To prove stability, mathematicians use something called Lyapunov functions. You can think of these as "energy gauges" or "safety scores."

If the score goes down every time the machine switches, the machine is safe.
If the score goes up, the machine is in trouble.

The problem is that for complex machines, one single safety score isn't enough. You need a whole team of scores that talk to each other. The authors call this a Path-Complete Lyapunov Function (PCLF).

Imagine a map (a graph) where:

Nodes are different safety scores.
Arrows are the rules saying "If you use Score A now, and switch to Mode X, you must end up with Score B later."

The big question the paper asks is: "Which map is better?"
Is Map A better than Map B? Is Map C the ultimate map?
In the past, researchers tried to compare these maps using a technique called the "Sum Lift."

Analogy: Imagine you have two maps. The "Sum Lift" says, "Let's just add Map A and Map B together to make a super-map."
The Catch: This works great for some things, but the authors found it fails when dealing with specific types of machines (like those with reversible, linear movements). It's like trying to fix a watch by gluing two watches together; sometimes it just makes a bigger mess.

The New Idea: The "Composition Lift"

The authors decided to try a different trick called the Composition Lift.

Analogy: Instead of just adding maps, imagine you are a translator. If Map A says "Do X then Y," and your machine has a rule that "Y always turns into Z," the Composition Lift automatically rewrites the rule to "Do X then Z." It chains the rules together.

For a long time, researchers had a Conjecture (a strong guess) that this "Translation Trick" was perfect. They thought: "If Map A can be translated into Map B using this trick, then Map A is definitely better or equal to Map B."

The Twist: The Guess Was Wrong!

The authors proved that this guess was false.
They found a specific pair of maps where the "Translation Trick" failed to show that one was better than the other, even though, mathematically, one was actually better.

The Metaphor: It's like having two navigation apps. App A is actually faster than App B. But if you try to compare them by just "translating" their routes, the translation tool fails to see the difference. The tool is blind to a crucial advantage.

The Silver Lining: Refining the Maps

Even though the "Translation Trick" didn't work perfectly as a comparison tool, the authors found a hidden superpower in it.
They realized that while the trick doesn't always prove one map is better, it can actually improve a map.

Analogy: Imagine you have a rough sketch of a route. The "Composition Lift" is like a high-tech GPS that takes your sketch and adds new, smoother shortcuts you didn't see before.
The Result: By applying this trick repeatedly, they can take a "good" map and turn it into a "better" map that gives a more accurate safety guarantee. In their computer experiments, this method successfully found safer, more efficient routes for the machines about 12% of the time where the old method failed.

The Final Fix: The "Transitive Closure"

Since the "Translation Trick" (Composition Lift) alone wasn't enough to compare every map, the authors proposed a final upgrade: The Transitive Closure.

Analogy: If the Translation Trick connects A to B, and B to C, but misses the direct link from A to C, this new method forces the system to draw that missing line. It connects all the dots, ensuring that if you can get from A to C through a chain of translations, the system recognizes it.

Summary

The Goal: Prove complex switching machines are stable.
The Old Way: Tried to compare stability maps by adding them together (Sum Lift), but it had blind spots.
The New Way: Tried to compare maps by chaining their rules (Composition Lift).
The Discovery: The "Chaining" method doesn't always prove which map is better (the old guess was wrong).
The Win: However, "Chaining" is excellent at improving the maps, making them more accurate.
The Solution: To fix the comparison issue, they added a "connect-the-dots" step (Transitive Closure) to ensure no potential improvements are missed.

In short, the paper says: "We broke a popular theory, but in doing so, we found a better way to build and refine safety maps for complex machines."

1. Problem Statement

The paper addresses the challenge of analyzing the stability of discrete-time switched systems of the form $x(k+1) = f_{\sigma(k)}(x(k))$ , where the switching signal $\sigma$ is arbitrary. While the existence of a common Lyapunov function guarantees stability, many stable switched systems do not admit one. Consequently, researchers rely on Path-Complete Lyapunov Functions (PCLFs), which utilize multiple Lyapunov functions and a directed graph structure to certify stability.

The core problem identified is the lack of a systematic framework to compare the performance of different path-complete graphs (templates). Specifically:

How can one determine if one graph structure (and its associated set of inequalities) is strictly "better" (more expressive) than another?
Previous work introduced preorders based on simulation relations and lifts (transformations of graphs) to compare these structures.
A specific conjecture (Conjecture 8.20 in prior literature [10]) suggested that the composition lift (a transformation involving function composition with system dynamics) perfectly characterizes the preorder for systems with invertible linear maps and templates closed under composition. The authors aim to verify or refute this conjecture and explore the structural properties of these lifts.

2. Methodology

The authors employ a combination of graph theory, order theory, and Lyapunov stability analysis.

Path-Complete Graphs: They define a graph $G=(S, E)$ as path-complete if every finite sequence of switching modes corresponds to a valid path in the graph. Stability is certified if a set of Lyapunov functions $\{V_s\}$ satisfies inequalities $V_a(x) \geq \gamma V_b(f_i(x))$ for all edges $(a, b, i)$ .
Preorder Relations: They define a preorder $G_1 \preceq G_2$ meaning that if $G_1$ admits a Lyapunov certificate for a system, $G_2$ also admits one. This implies $G_2$ is "better" or more expressive.
Lifts: The authors analyze two types of graph transformations (lifts) designed to make these comparisons algorithmically tractable:
1. Sum Lift ( $G^{\oplus}$ ): Constructs a new graph where nodes are multisets of original nodes, and edges represent the sum of inequalities.
2. Composition Lift ( $G^{\circ}$ ): Constructs a new graph where nodes represent the composition of Lyapunov functions with system maps ( $V \circ f$ ). This includes forward ( $G^{\circ T}$ ) and backward lifts.
Counterexample Construction: The authors construct specific graph pairs ( $G_\phi, G_\psi$ ) and switched linear systems to test the validity of the conjecture that "Composition Lift Simulation $\iff$ Preorder."

3. Key Contributions

A. Refutation of a Key Conjecture

The paper's primary theoretical contribution is the disproof of Conjecture IV.2 (from [10]).

The Conjecture: For invertible linear maps and templates closed under composition, $G^{\circ}$ simulates $\tilde{G}$ if and only if $G \preceq_{V,F} \tilde{G}$ .
The Result: The authors provide a counterexample (Example IV.3) showing that while $G_\phi \preceq_{V,F} G_\psi$ (meaning $G_\psi$ is strictly better), the forward composition lift $G_\phi^{\circ}$ does not simulate $G_\psi$ .
Implication: This proves that the composition lift, unlike the sum lift, does not preserve the preorder relationship in a simple simulation manner. The ordering of graphs is more complex than previously thought.

B. Structural Properties of the Composition Lift

Despite refuting the conjecture, the authors identify beneficial structural features of the composition lift:

Refinement Capability: Unlike the sum lift (which preserves the Joint Spectral Radius approximation $\rho_{G,V}(A)$ ), the composition lift can strictly refine the stability bound. Specifically, $G \preceq G^{\circ T}$ holds, but $G^{\circ T} \preceq G$ does not necessarily hold. This means the lifted graph can provide a tighter (better) estimate of the Joint Spectral Radius (JSR).
Connectivity Preservation: The authors prove (Lemma III.3) that if a graph is connected and sink-free, its $T$ -forward composition lift remains connected. This contrasts with the sum lift, which can disconnect the graph.

C. Proposal of the Transitive Composition Lift

To resolve the gap identified in the counterexample (where $G_\phi \preceq G_\psi$ but $G_\phi^{\circ}$ does not simulate $G_\psi$ ), the authors propose a new construct: the Transitive Composition Lift ( $(G^{\circ})^+$ ).

This lift combines the composition lift with a transitive closure operation, effectively chaining inequalities (e.g., $V_a \geq V_b \circ f_i$ and $V_b \geq V_c \circ f_j$ implies $V_a \geq V_c \circ f_j \circ f_i$ ).
Theorem IV.5: They show that if the transitive composition lift $(G^{\circ})^+$ simulates $\tilde{G}$ , then the preorder $G \preceq_{V,F} \tilde{G}$ holds. This provides a corrected, sufficient condition for comparing graphs.

4. Results and Numerical Validation

Theoretical Counterexample: The paper rigorously demonstrates that for graphs $G_\phi$ and $G_\psi$ (Figure 4), the preorder holds, but the standard composition lift fails to simulate the target graph.
Numerical Experiments: The authors conducted experiments on random linear switched systems ( $n=3$ $n = 3$ , $N=1000$ $N = 1000$ samples).
- They compared the JSR approximation $\rho_{G,V}(A)$ of a base graph $G_\alpha$ against its 1-step and 2-step composition lifts ( $G_\alpha^{\circ 1}, G_\alpha^{\circ 2}$ ).
- Finding: In approximately 12% of cases, the composition lift provided a strictly tighter (lower) upper bound on the JSR than the original graph.
- Comparison: The sum lift ( $G^{\oplus}$ ) provided no improvement in these cases, confirming that the composition lift offers a unique refinement mechanism.

5. Significance

Correcting the State of the Art: The paper corrects a significant misconception in the literature regarding the equivalence of simulation relations and Lyapunov preorders under composition lifts. This prevents future research from relying on flawed assumptions.
New Tool for Stability Analysis: By introducing the Transitive Composition Lift, the authors provide a more powerful tool for certifying stability. It allows for the systematic refinement of path-complete graphs, leading to less conservative stability certificates.
Algorithmic Tractability: The work moves the field closer to algorithmic solutions for comparing Lyapunov templates. While the full characterization is complex, the proposed transitive lift offers a constructive path to finding "better" graphs for a given system.
Practical Impact: The numerical results suggest that for a non-trivial portion of switched systems, using composition lifts can yield significantly better stability bounds, which is crucial for control design and safety verification.

In summary, this paper refines the theoretical understanding of how to compare and improve path-complete Lyapunov functions. It replaces a flawed conjecture with a more nuanced understanding involving transitive closures, while demonstrating that composition lifts are a powerful, non-trivial method for tightening stability estimates in switched systems.