Ordering and refining path-complete Lyapunov functions through composition lifts
Wouter Jongeneel, Raphaël M. Jungers · 2025
Read Ordering and refining path-complete Lyapunov functions through composition lifts by Wouter Jongeneel, Raphaël M. Jungers (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-18189.txt.
Introduction
Wouter Jongeneel and Raphaël Jungers work on proving that systems which switch between modes stay stable. A powerful method equips each mode with its own Lyapunov function, an energy-like score that must fall along allowed switches, arranged on a graph called a path-complete certificate. Comparing two such certificates was long thought possible through a trick called the composition lift.
The authors show a standing conjecture about that lift is false, with a counterexample. The failure is useful: it exposes a structural feature of the lift that lets them iteratively sharpen the underlying graphs. They also propose a repaired version of the lift that behaves better. The note clarifies how these certificates can be ordered and improved.
Catalog record
| CREATOR | Wouter Jongeneel, Raphaël M. Jungers |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-18189
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ordering and refining path-complete Lyapunov functions through composition lifts Wouter Jongeneel, Raphaël M. Jungers Abstract A fruitful approach to study stability of switched systems is to look for multiple Lyapunov functions. However, in general, we do not yet understand the interplay between the desired stability certificate, the template of the Lyapunov functions and their mutual relationships to accommodate switching. In this work we elaborate on path-complete Lyapunov functions: a graphical framework that aims to elucidate this interplay. In particular, previously, several preorders were introduced to compare multiple Lyapunov functions. These preorders are initially algorithmically intractable due to the algebraic nature of Lyapunov inequalities, yet, lifting techniques were proposed to turn some preorders purely combinatorial and thereby eventually tractable. In this note we show that a conjecture in this area regarding the so-called composition lift, that was believed to be true, is false. This refutal, however, points us to a beneficial structural feature of the composition lift that we exploit to iteratively refine path-complete graphs, plus, it points us to a favourable adaptation of the composition lift. I Introduction Switched systems can be motivated based on physical grounds ( e.g. , think of switching gears, a walking robot or packet loss), or topological grounds ( e.g. , think of local or global obstructions to the existence of continuous feedback). For references we point the reader to [ 1 , 2 , 3 , 4 , 5 ] . Concretely, we are interested in studying the stability of the origin 0\in\mathbb{R}^{n} under a discrete-time switched system of the form x(k+1)=f_{\sigma(k)}(x(k)),\quad k\in\mathbb{N}_{\geq 0}, (1) where \sigma:\mathbb{N}_{\geq 0}\to\Sigma is the switching signal, for \Sigma a finite alphabet that parametrizes a set of maps F=\{f_{i}\in C^{0}(\mathbb{R}^{n};\mathbb{R}^{n})\,|\,f_{i}(0)=0,\,i\in\Sigma\} , sometimes shortened to \{f_{i}\,|\,i\in\Sigma\} . We will assume that \sigma is random and we study in that sense worst-case behaviour of the switched system ( 1 ). To be precise, we are interested in understanding if 0 is uniformly globally asymptotically stable (UGAS) under ( 1 ). Stability of switched systems is theoretically interesting and non-trivial due to the fact that switching between stable maps f_{1},\dots,f_{|\Sigma|} can result in an unstable system and even more counter-intuitive, the combination of some unstable maps might be stable, although not under random switching. Although switched systems do admit a converse Lyapunov theory, e.g. , see [ 6 , Thm. 2.2] , looking for multiple Lyapunov functions and an appropriate switching scheme between them is ought to be more fruitful than looking for a common Lyapunov function [ 7 ] . Nevertheless, the search for multiple Lyapunov functions is somewhat of an art and with this work we aim to contribute to to making this a principled study. In particular, we look at path-complete Lyapunov functions (PCLFs) [ 8 ] , a framework that aims to streamline the study of multiple Lyapunov functions by looking at the problem through the lens of graph- and order theory. Specifically, given a set of (multiple) Lyapunov functions \{V_{s}\,|\,s\in S\} , then each Lyapunov inequality corresponding to the switched system ( 1 ) will be of the form V_{a}(x)\geq\gamma V_{b}(f_{i}(x)) , for some \gamma>0 , which can be understood as a labeled edge (a,b,i)\in E , being part of a directed graph (digraph) \mathcal{G}=(S,E) . We elaborate on this below. Throughout, we will assume that our graphs are always of the so-called “ expanded form ” ( e.g. , all edges have labels of length one) [ 8 , Def. 2.1] . Definition I.1 (Path-completeness) . Consider a labeled digraph \mathcal{G}=(S,E) on a finite alphabet \Sigma . Then, \mathcal{G} is said to be path-complete, denoted \mathcal{G}\in\mathrm{pc}(\Sigma) , when for any finite word i_{1}i_{2}\cdots i_{k}\in\Sigma^{k} , there exists a sequence of nodes s_{1},\dots,s_{k+1}\in S such that (s_{j},s_{j+1},i_{j})\in E \forall j\in[k] . For now, Lyapunov functions used to assert stability of 0\in\mathbb{R}^{n} under ( 1 ), live in C^{0}(\mathbb{R}^{n};\mathbb{R}_{\geq 0}) , are positive definite ( i.e. , V(0)=0 and V(x)>0 \forall\,x\in\mathbb{R}^{n}\setminus\{0\} ) and such that \alpha_{1}(\|x\|_{2})\leq V(x)\leq\alpha_{2}(\|x\|_{2}) \forall\,x\in\mathbb{R}^{n} for \mathcal{K}_{\infty} functions \alpha_{1} and \alpha_{2} . We denote this set of candidate Lyapunov functions , with respect to 0\in\mathbb{R}^{n} , by \mathrm{Lyap}_{0}(\mathbb{R}^{n}) . Definition I.2 (Path-complete Lyapunov functions) . Consider a switched system ( 1 ) comprised by F=\{f_{i}\,|\,i\in\Sigma\} and let \mathcal{V} be a template of functions. Then, a path-complete Lyapunov function (PCLF) for F is the triple (\mathcal{G},V_{S},\gamma) where \mathcal{G}\in\mathrm{pc}(\Sigma) , V_{S}=\{V_{s}\in\mathrm{Lyap}_{0}(\mathbb{R}^{n})\,|\,s\in S\}\subseteq\mathcal{V} and \gamma>0 such that for all edges (a,b,i) of \mathcal{G} we have that V_{a}(x)\geq\gamma V_{b}(f_{i}(x))\quad\forall x\in\mathbb{R}^{n}. (2) If this holds true, we say that the pair (V_{S},\gamma) is admissible for \mathcal{G} , \mathcal{V} and F , denoted by (V_{S},\gamma)\in\mathrm{pclf}(\mathcal{G},\mathcal{V},F) . We emphasize that the effective template under consideration is of the form \mathcal{V}\cap\cup_{n\in\mathbb{N}_{>0}}\mathrm{Lyap}_{0}(\mathbb{R}^{n}) , this, to clearly differentiate between structure due to the template and due to stability. Also, \gamma is introduced to allow for a general stability analysis ( i.e. , readily generalizable beyond linear systems). Note that a graph \mathcal{G} can be utilized as a PCLF for systems of different dimension ( e.g. , a common Lyapunov function is always a graph with a single node). As such, we will consider function spaces of the form \mathcal{F}=\cup_{n\in\mathbb{N}_{>0}}\{\mathcal{F}_{n}\subseteq C^{0}(\mathbb{R}^{n};\mathbb{R}^{n})\} and similarly \mathcal{V}=\cup_{n\in\mathbb{N}_{>0}}\mathcal{V}_{n} . We do add that F\subseteq\mathcal{F} is understood as a set contained in some \mathcal{F}_{n} . Now, path-completeness naturally connects to stability as follows ( e.g. , this is a natural extension of [ 8 , Thm. 2.4] ). Theorem I.3 (Uniform global asymptotic stability) . Let (V_{S},\gamma)\in\mathrm{pclf}(\mathcal{G},\mathcal{V},F) for a \mathcal{G}\in\mathrm{pc}(\Sigma) , template \mathcal{V} and set F parametrizing ( 1 ), then 0 is UGAS under ( 1 ) if \gamma>1 . Below we comment on a more informative version of Theorem I.3 for linear systems, but first we highlight where we aim to contribute in the study of multiple Lyapunov functions. We are inspired by the open problem posed in [ 8 , Sec. 7] : “ How can we compare the performance of different path-complete graphs in a systematic way? ” More concretely, consider the following example. Example I.1 (Ambiguity in selecting inequalities) . Suppose we have a switched system with \Sigma=\{1,2\} . Besides trying to find a common Lyapunov function, one could consider \begin{aligned} V_{\alpha}(x)\geq V_{\alpha}(f_{1}(x))\\ V_{\alpha}(x)\geq V_{\beta}(f_{2}(x))\\ V_{\beta}(x)\geq V_{\beta}(f_{2}(x))\\ V_{\beta}(x)\geq V_{\alpha}(f_{1}(x))\end{aligned}\quad\text{or}\quad\begin{aligned} V_{\alpha}(x)\geq V_{\alpha}(f_{1}(x))\\ V_{\alpha}(x)\geq V_{\beta}(f_{1}(x))\\ V_{\beta}(x)\geq V_{\beta}(f_{2}(x))\\ V_{\beta}(x)\geq V_{\alpha}(f_{2}(x))\end{aligned}, (3) corresponding to the path-complete graphs \mathcal{G}_{1} and \mathcal{G}_{2} , in Figure 1 . Similarly, one could consider the inequalities corresponding to Figure 4 . However, towards a principled study of multiple Lyapunov functions, we lack appropriate machinery to determine which set of inequalities to prefer ( e.g. , what should one enter into a solver), if any? \circ To study the ambiguity as illustrated by Example I.1 , we use the following preorder, which is a slight modification of previous work to get a better grip on stability, e.g. , see [ 9 , 10 ] , as such we use “ \preceq ” instead of “ \leq ”. Definition I.4 (Preorder relation) . Consider \mathcal{G}_{1},\mathcal{G}_{2}\in\mathrm{pc}(\Sigma) , \Gamma\subseteq\mathbb{R}_{>0} , a template of Lyapunov functions \mathcal{V} and a set of maps \mathcal{F} . If \forall F\in\mathcal{F}^{|\Sigma|} \exists(V_{S_{1}},\gamma\in\Gamma)\in\mathrm{pclf}(\mathcal{G}_{1},\mathcal{V},F)\implies\exists(V_{S_{2}},\gamma\in\Gamma)\in\mathrm{pclf}(\mathcal{G}_{2},\mathcal{V},F) then \mathcal{G}_{1}\preceq_{(\Gamma,\mathcal{V},\mathcal{F})}\mathcal{G}_{2}. (4) One can interpret ( 4 ) as \mathcal{G}_{2} being “ more expressive ” than \mathcal{G}_{1} and in that sense