Matteo Della

Rossa Mirko Pasquini

David Angeli

M Pasquini

M Della Rossa

Path-Complete Lyapunov Functions for Continuous-Time Switching Systems

We use a graph-theory-based argument to propose a novel Lyapunov construction for continuous-time switching systems. Starting with a finite family of continuously differentiable functions, the inequalities involving these functions and the vector fields of the switching system are encoded in a direct and labeled graph. Relaying on the (path-)completeness of this graph, we introduce a signal-dependent Lyapunov function, providing sufficient conditions for stability under fixed-time or dwell-time switching hypothesis. For the case of linear systems, our conditions turn into linear matrix inequalities (LMI), and thus they are compared with previous results, via numerical examples.

Introduction

Switching dynamical systems form a large subclass of hybrid systems [START_REF] Liberzon | Switching in systems and control[END_REF], providing a modeling structure for many physical phenomena. In this setting, Lyapunov tools for stability/stabilization have been deeply studied in the past decades, (see for example the survey [START_REF] Lin | Stability and stabilizability of switched linear systems: A survey of recent results[END_REF] or [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF]).

Throughout this note we consider a finite family of vector fields f 1 , . . . , f K ∈ C 1 (R n , R n ). To model the evolution of trajectories resulting from timedependent switching among these individual subsystems, we introduce the switched system

ẋ(t) = f σ(t) (x(t)), (1)
where σ : R → {1, . . . , K} is a time-dependent signal.

Assessing the stability of (1) under specific classes of switching signals is a challenging task, see for example [1, Chapter 2], [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encountered in control theory[END_REF] and [START_REF] Dayawansa | A converse Lyapunov theorem for a class of dynamical systems which undergo switching[END_REF] for a thorough discussion.

Moreover, stability of the discrete-time counterpart of (1), (i.e. considering subsystems defined by x + = f j (x), j ∈ {1, . . . , K} and signals σ : N → {1, . . . K}) has also attracted attention in the past years, see [START_REF] Jungers | The Joint Spectral Radius: Theory and Applications[END_REF], [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF]. Recently, in the context of discrete-time linear switching systems, [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF] and [START_REF] Philippe | On path-complete Lyapunov functions: Geometry and comparison[END_REF] introduced and studied the notion of path-complete Lyapunov functions: starting from a finite family of quadratic functions V := {V s } s∈S ⊂ C 1 (R n , R), the inequalities involving these functions and the system-data are encoded in a direct and labeled graph G = (S, E). More precisely: given A := {A 1 , . . . A K } ⊂ R n×n , the edge (a, b, j) ∈ E if and only if V b (A j x) ≤ V a (x), for all x ∈ R n . This relation intuitively means that, after a discrete-time step, the sublevel sets of V a are mapped into the corresponding sublevel sets of V b by the discrete-time system x + = A j x. Graph theory tools are then used to study the stability of the difference inclusion x + ∈ co{A 1 x, . . . , A K x}, proposing conditions which rely on the topological properties (path-completeness) of the corresponding graph G = (S, E). This intuition can be applied in the continuoustime case, and this is the main contribution of this article. We recall that a frequent assumption on signals σ : R + → {1, . . . , K} is that there exists a minimum time-threshold, a so-called dwell-time, during which no switching occurs. Under this dwell-time assumptions, the behavior of a continuous-time switching systems (1) somehow approaches/mimics the evolution of a discrete-time switching system, and thus a graph-based Lyapunov approach seems promising also in this context.

It is appropriate to point out that stability of [START_REF] Liberzon | Switching in systems and control[END_REF] under dwell-time assumption is a well-studied problem. When considering linear sub dynamics, (i.e. f j (x) ≡ A j x, with A j ∈ R n×n for all j ∈ {1, . . . , K}), it is well known that, if all the matrices A 1 , . . . , A K are Hurwitz, there exists a (large enough) dwelltime for which the switched system (1) is asymptotically stable [9, Lemma 2]. In this context, various numerical approximations of the minimal dwelltime τ dw ∈ R + for which system (1) is stable have been proposed, most of them relying on Lyapunovfunctions approaches: in [START_REF] Geromel | Stability and stabilization of continuous-time switched linear systems[END_REF] a family of quadratics is used to give lower-bounds on τ dw , constructing Lyapunov functions decreasing between switching but possibly increasing at switching instants. In [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF], a different construction involving quadratic functions is proposed, with the peculiarity that the resulting Lyapunov functions are non-increasing (but possibly discontinuous) at every switching instant. In [START_REF] Briat | Convex conditions for robust stabilization of uncertain switched systems with guaranteed minimum and mode-dependent dwell-time[END_REF], a sum-of-square Lyapunov functions approach is investigated, while in [START_REF] Chesi | A nonconservative LMI condition for stability of switched systems with guaranteed dwell time[END_REF] the authors made use of homogeneous polynomial functions; in [START_REF] Blanchini | Vertex/plane characterization of the dwell-time property for switching linear systems[END_REF], polyhedral Lyapunov functions are considered. Regarding converse Lyapunov constructions in this setting, see the result presented in [START_REF] Wirth | A converse Lyapunov theorem for linear parameter-varying and linear switching systems[END_REF]Corollary 6.5].

In this paper, we exploit the path-complete graphs formalism in studying stability of continuous-time nonlinear switching systems under dwell-time assumptions. In Section 2 we recall the main definitions, while in Section 3 we introduce a continuoustime counterpart of the correspondence that links edges and inequalities, introduced in [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF] in the discrete-time setting. This will permit us to define, given any switching signal σ, time-dependent Lyapunov functions as a linear-interpolation between a finite number of continuously differentiable functions, similarly to [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF]. Under path-completeness of the resulting graph, this construction leads to sufficient conditions for stability of (1), under fixed-time or dwell-time assumptions. Our conditions depend on the chosen dwell-time (or fixed-time) τ > 0, and thus they could be compared, in the linear case, with the previously cited results contained in [START_REF] Geromel | Stability and stabilization of continuous-time switched linear systems[END_REF], [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF]. This comparison is carried out in Section 4 with the help of two numerical examples, showing that the same minimal dwell-times are obtained. Notation: The symbol R + denotes the set of nonnegative real numbers, i.e

R + := {x ∈ R | x ≥ 0}. A function α : R + → R is positive definite (α ∈ PD) if it is continuous, α(0) = 0, and α(s) > 0, for all s ∈ R + \ {0}. A function α : R + → R is of class K (α ∈ K) if it
is positive definite and strictly increas-ing; it is of class K ∞ if, in addition, it is unbounded. A continuous function β : R + × R + → R + is said to be of class KL if β(•, r) is class K for any fixed r ∈ R + and, for any fixed s > 0, β(s, •) is decreasing and lim r→∞ β(s, r) = 0.

Preliminaries

Setting and Definitions

Consider a finite family of vector fields

F := {f 1 , . . . , f K } ⊂ C 1 (R n , R n ). We study the switched system ẋ(t) = f σ(t) (x(t)). (2)
Defining I := {1, . . . K}, the switching signals σ are selected, in general, among the set S defined by

S := {σ : R + → I | σ piecewise constant} . ( 3
)
Without loss of generality we suppose that signals σ ∈ S are right-continuous. Given a σ ∈ S, we define the sequence of switching instants, that is the points at which σ is discontinuous, and we denote it by {t σ i }. The sequence {t σ i } may be infinite or finite, possibly reduced to the initial instant t 0 := 0; if it is infinite, then it is divergent; see Figure 1 for an example of σ ∈ S. Given a point x 0 ∈ R n , and a signal σ ∈ S, we denote with x(t, x 0 , σ) the solution of (2) starting at x 0 , evaluated at some instant t ≥ 0. Definition 1. Consider F := {f 1 , . . . , f K } ⊂ C 1 (R n , R n ) and a set of switching signals S ⊂ S. The switched system (2) is said to be globally stable on S if for all σ ∈ S, there exists an α ∈ K ∞ such that

|x(t, x 0 , σ)| ≤ α(|x 0 |),
for all x 0 ∈ R n and for all t ≥ 0. System (2) is said to be globally asymptotically stable on S, if for all σ ∈ S, there exists an

β ∈ KL such that |x(t, x 0 , σ)| ≤ β(|x 0 |, t),
for all x 0 ∈ R n and for all t ≥ 0.

It is well-known that (asymptotic) stability of (2) with respect to all the switching signals σ ∈ S is equivalent to (asymptotic) stability of the differential inclusion ẋ(t)

∈ co{f j (x) | j ∈ I}, (4)
where co(C) denote the convex hull of a set C ⊂ R n , see [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF]Section 2] for the technical details.

In this article we will consider two proper subclasses of S. Given a τ > 0, we define the class of fixed-time switching signals, as the set

S fix (τ ) := σ ∈ S | t σ i -t σ i-1 τ ∈ N, ∀t σ i > 0 , (5)
and the class of dwell-time switching signals, given by

S dw (τ ) := σ ∈ S | t σ i -t σ i-1 ≥ τ, ∀ t σ i > 0 . (6)

Graphs and Path-Completeness

Our main goal is the study of stability of (2), using a multiple-Lyapunov functions approach. For this reason we introduce a formalism that permits us to represent inequalities involving multiple Lyapunov functions by graphs.

Given a discrete alphabet I ⊂ N, a direct and labeled graph G = (S, E) is defined by a finite set S (the set of nodes) and E ⊂ S × S × I (the set of edges).

Definition 2 (Path-Completeness

). A graph G = (S, E) is path-complete for I if, for any K ≥ 1 and any "word" j 1 . . . j K , with j k ∈ I, there exists a path {(s k , s k+1 , j k )} 1≤k≤K such that (s k , s k+1 , j k ) ∈ E, for each 1 ≤ k ≤ K.
This formalism was introduced in [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF] and [START_REF] Philippe | On path-complete Lyapunov functions: Geometry and comparison[END_REF] in the context of discrete-time switched systems. For a thorough discussion and several examples of pathcomplete graphs we refer to [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF].

In what follows we analyze how these ideas can be adapted in the continuous-time setting.

3 Path-Complete Lyapunov Functions

Main Stability Results

Definition 3. Given a finite set S, a candidate vector-valued Lyapunov function is a map

V : R n → R |S| , such that V ∈ C 1 (R n , R
) is positive definite and radially unbounded for each ∈ S. More explicitly, for all ∈ S, there exists α , α ∈ K ∞ such that

α (|x|) ≤ V (x) ≤ α (|x|), ∀ x ∈ R n .
Given the system (2), let us fix a threshold τ > 0 and consider a candidate vector-valued Lyapunov function V : R n → R |S| . Given a, b ∈ S and j ∈ I, we say that there is an edge (a, b, j

) τ ∈ E if ∇V a (x), f j (x) ≤ 1 τ (V a (x) -V b (x)) ∀ x ∈ R n , ∇V b (x), f j (x) ≤ 1 τ (V a (x) -V b (x)) ∀ x ∈ R n . ( 7
)
Where there is no ambiguity, we will drop the subscript τ . With this definition, to each candidate vector-valued Lyapunov function V : R n → R |S| we can associate a direct and labeled graph G = (S, E) over the alphabet I. More precisely, given V : R n → R |S| , the associated graph G = (S, E) is defined by: (a, b, j) τ ∈ E if and only if inequalities [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF] are satisfied by V a , V b , and f j . We can thus give the following stability results

Theorem 1. Consider a τ > 0, a finite set S, and V : R n → R |S| a candidate vector-valued Lyapunov function. If the associated graph G = (S, E) is pathcomplete for I then system (2) is globally stable on S fix (τ ).

Proof. The main idea is the following: for any σ ∈ S fix (τ ), we construct a positive definite and continuous function W : R + × R n → R n non-increasing along solutions of (2), for any initial point x 0 ∈ R n . Consider σ ∈ S fix (τ ), we construct recursively the associated "word" as follows: for each t σ i > 0 consider the number n(i) =

t σ i -t σ i-1 τ
; by definition of S fix (τ ), n(i) ∈ N. If σ(t σ i-1 ) = j, then add a string of j's of length n(i). If the sequence {t σ i } is finite, add an infinite sequence of j M 's , where j M = σ(max{t σ i }), see Fig. 1 for a graphical interpretation. By path-completeness of G, we can consider a path in G = (V, E) corresponding to this sequence. Suppose that the first arch of the selected path is (a, b, j) τ ∈ E, for some a, b ∈ S and j ∈ I. Define the function

W on [0, τ ] × R n by W (t, x) := τ -t τ V a (x) + t τ V b (x) ∀t ∈ [0, τ ]. (8) Consider x 0 ∈ R n , we want to show that W (•, x(•, x 0 , σ)) : [0, τ ] → R is decreasing. Comput- ing the derivative of W along the solution x(t) := τ t σ 1 t σ 2 t σ 3 t σ 4 t σ 5 1 2 3 σ(t) 1 1 1 2 2 2 2 1 2 2 3 3 3 2 t I Figure 1:
An example of switching signal σ : R + → I := {1, 2, 3}, σ ∈ S fix (τ ) and the associated word, that is, the sequence

(1, 1, 1, 2, 2, 2, 2, 1, 2, 2, 3, 3, 3, 2, . . . ) ∈ I N . x(t, x 0 , σ) we have Ẇ (t, x(t)) = ∂W ∂x (t, x(t)), f j (x(t)) + ∂W ∂t (t, x(t)) = τ -t τ ∇V a (x(t)), f j (x(t)) + t τ ∇V b (x(t)), f j (x(t)) + V b (x(t)) -V a (x(t)) τ = τ -t τ ∇V a (x(t)), f j (x(t)) + V b (x(t)) -V a (x(t)) τ + t τ ∇V b (x(t)), f j (x(t)) + V b (x(t)) -V a (x(t)) τ .
Since (a, b, j) τ ∈ E, by definition ( 7), we thus have Ẇ (t, x(t)) ≤ 0, for all t ∈ (0, τ ). Since W ( • , x( • )) : [0, τ ] → R + is absolutely continuous, this implies that it is non-increasing. Noting that W (τ, x) = V b (x) for all x ∈ R n , we can iterate this argument for every subinterval of R + of length τ , following the path in G corresponding to the chosen switching signal σ. Since x 0 ∈ R n was arbitrary, the obtained function W : R + × R n → R is continuous and non-increasing along solutions of (2). Moreover W is positive definite and radially unbounded in x, uniformly in the t variable, since, recalling Definition 3 and by construction (8), we have

min ∈S α (|x|) ≤ W (t, x) ≤ max ∈S α (|x|),
for all (t, x) ∈ R + × R n . By arbitrariness of σ ∈ S fix (τ ) and by a standard comparison argument (see for example [START_REF] Khalil | Nonlinear Systems[END_REF]Theorem 4.8]) we conclude that (2) is stable on S fix (τ ).

Remark 1. In the context of dwell-time linear switched systems, the idea of constructing Lyapunov functions via linear interpolation as in [START_REF] Philippe | On path-complete Lyapunov functions: Geometry and comparison[END_REF], is used also in [11, Theorem 1], proposing inequalities similar to the ones presented in [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF]. On the other hand, the "global" construction proposed here is peculiar, since it relies on the structure of path-complete graphs and the set of required inequalities strongly depends on the chosen graph. This choice could be somehow suggested by the structure of the problem, or could be seen as a factor of flexibility, since many pathcomplete graphs (and thus many sets of inequalities) could be "explored" to have sufficient conditions for global (asymptotic) stability of (2). For a deeper comparison, see the following Section 4. This reasoning can be also applied for studying the stability on the class S dw (τ ); we need the following statement.

Lemma 1. Let us consider V a , V b ∈ C 1 (R n , R), f j ∈ C 1 (R n , R n ) and τ > 0. Then (a, b, j) τ ∈ E, (a, b, j) 2τ ∈ E, ⇒ (a, b, j) τ ∈ E, ∀ τ ∈ [τ, 2τ ]. (9)
Proof. Recalling [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF], the first inequalities encoded in the edges (a, b, j) τ ∈ E and (a, b, j) 2τ ∈ E are, respectively,

∇V a (x), f j (x) ≤ 1 τ (V a (x) -V b (x)) ∀ x ∈ R n , ∇V a (x), f j (x) ≤ 1 2τ (V a (x) -V b (x)) ∀ x ∈ R n .
Consider any λ ∈ [0, 1], we multiply these inequalities by λ and (1λ) respectively. Adding we obtain

∇V a (x), f j (x) ≤ λ τ (V a (x)-V b (x)) + 1-λ 2τ (V a (x)-V b (x)) = 1+λ 2τ (V a (x) -V b (x)).
Since the function φ :

[0, 1] → [1, 2] defined by φ(λ) = 2 1+λ
is bijective, we conclude that

∇V a (x), f j (x) ≤ 1 τ (V a (x) -V b (x)), ∀ τ ∈ [τ, 2τ ].
Using the same reasoning for the second inequalities encoded in (a, b, j) τ , (a, b, j) 2τ ∈ E, implication (9) holds.

Corollary 1 (Dwell-Time). Consider a finite set S, and V : R n → R |S| a candidate vector-valued function. Consider a τ > 0. Suppose the associated graph G = (S, E) is path-complete for I, and for all (a, b, j) τ ∈ E also (a, b, j) 2τ ∈ E. Then system (2) is stable on S dw (τ ).

Proof. Consider any σ ∈ S dw (τ ), for any t σ i > 0 define n(i) =

t σ i -t σ i-1 τ
, where, given a r ∈ R, r denotes the greatest integer less than or equal to r. By definition of S dw (τ ) in [START_REF] Jungers | The Joint Spectral Radius: Theory and Applications[END_REF], n(i) ≥ 1, for all t σ i > 0. Similarly to proof of Theorem 1, we construct the "word" associated to σ as follows: for each t σ i > 0, if σ(t σ i-1 ) = j, then add a string of j's of length n(i). If the sequence {t σ i } is finite, add an infinite sequence of j M 's, where j M = σ(max{t σ i }). It suffices now to consider the path in G = (S, E) corresponding to this word. We define the function W : R + × R n → R n as in proof of Theorem 1, with the peculiarity that here we split each interval [t σ i-1 , t σ i ] in n(i)-1 sub-intervals of length τ , namely

t σ i-1 , t σ i-1 + τ , t σ i-1 + τ, t σ i-1 + 2τ , . . .
and one last sub-interval, t σ i-1 + (n(i) -1) τ, t σ i . By definition of S dw (τ ) and n(i), this last sub-interval has length equal to t σ i -

t σ i-1 -(n(i) -1) τ ∈ [τ, 2τ
). Recalling Lemma 1, it is easy to adapt the construction presented in [START_REF] Philippe | On path-complete Lyapunov functions: Geometry and comparison[END_REF] for each of these sub-intervals, finally obtaining a continuous function W : R + ×R n → R n , positive definite and non-increasing along solutions of (2).

Remark 2 (Global Asymptotic Stability). In Theorem 1 and Corollary 1 we give sufficient conditions to ensure global stability of (2) on the classes S fix (τ ) and S dw (τ ). We follow here the same reasoning, proposing sufficient conditions for global asymptotic stability of system [START_REF] Lin | Stability and stabilizability of switched linear systems: A survey of recent results[END_REF]. For this goal, we only need to strengthen the conditions encoded in the generic edge (a, b, j) τ , as defined in [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF]. In particular, given V a , V b : R n → R and f j ∈ C 1 (R n , R n ), we say that the "strong" edge (a, b, j) τ is in E s (the set of strong edges) if there exists ρ ∈ PD such that

∇V a (x), f j (x) -Va(x)-V b (x) τ ≤ -ρ(|x|), ∀ x ∈ R n , ∇V b (x), f j (x) -Va(x)-V b (x) τ ≤ -ρ(|x|), ∀ x ∈ R n .
(10) It is now easy to prove that, given τ > 0, if G s = (S, E s ) is path-complete, then system (2) is globally asymptotically stable on S fix (τ ). Moreover if G s = (S, E s ) is path-complete and for all (a, b, j) τ ∈ E s also (a, b, j) 2τ ∈ E s , then system ( 2) is globally asymptotically stable on S dw (τ ).

Complete and co-Complete Case

In this section we underline how, in some particular cases, path-complete Lyapunov functions could ensure stability of system (2) under arbitrary switching, that is for all σ ∈ S, or, equivalently, for the differential inclusion (4).

Definition 4. A graph G = (S, E) on I is complete if ∀ a ∈ S, ∀ j ∈ I, there exists a b ∈ S such that (a, b, j) ∈ E. A graph G = (S, E) on I is co-complete if ∀ b ∈ S, ∀ j ∈ I, there exists an a ∈ S such that (a, b, j) ∈ E.
It is easy to see that a (co-)complete graph G = (S, E) is in particular path-complete.

W m (x) := min s∈S {V s (x)} , ∀ x ∈ R n , ( 11
)
is a Lyapunov function for system [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encountered in control theory[END_REF].

If G = (S, E) is co-complete then W M (x) := max s∈S {V s (x)} , ∀ x ∈ R n , ( 12
)
is a Lyapunov function for system (4).

Proof. Let us suppose G = (S, E) is complete, consider any a ∈ S, and define the region

X a := {x ∈ R n | V a (x) ≤ V s (x) ∀ s ∈ S }; we have R n = a∈S X a .
Consider any j ∈ I, by completeness there exists a b ∈ S such that (a, b, j) ∈ E. Consider any x ∈ X a where ∇W m exists, we have

∇W m (x), f j (x) = ∇V a (x), f j (x) ≤ 1 τ (V a (x) -V b (x)) ≤ 0.
By arbitrariness of a ∈ S and j ∈ I, we can conclude that ∇W m (x), f j (x) ≤ 0, for all x ∈ R n such that ∇W m (x) exists and for all j ∈ I. This implies that the locally Lipschitz function W m : R n → R is non-increasing along the solutions of (4), as showed for example in [START_REF] Teel | On assigning the derivative of a disturbance attenuation control Lyapunov function[END_REF] . The proof in the co-complete case (implying W M common Lyapunov function) can be obtained with the same reasoning, defining the partition R n = b∈S X b , with

X b := {x ∈ R n | V b (x) ≥ V s (x), ∀ s ∈ S }.
Remark 3. The use of pointwise minimum/maximum of continuously differentiable functions for stability of differential inclusions ( 4) is well-studied in literature. In [START_REF] Goebel | Conjugate convex Lyapunov functions for dual linear differential inclusions[END_REF], the authors presented conditions relying on pointwise maximum of quadratics and its convex conjugates in the context of linear differential inclusions (LDI), that is system (4) with f j (x) = A j x, for some A 1 , . . . , A K ∈ R n×n . In [START_REF] Hu | Stabilization of switched systems via composite quadratic functions[END_REF], candidate Lyapunov functions for LDI in the form of (convexhull of) pointwise minimum of quadratic functions are also proposed. For a thorough discussion of the use of various piecewise C 1 Lyapunov functions, we refer to [START_REF] Goebel | Conjugate convex Lyapunov functions for dual linear differential inclusions[END_REF] and reference therein. In this context, Lemma 2 is thus a trivial corollary of these well-known results. Instead, in the constrained-time switched systems setting, Lemma 2 is an useful tool: in studying the fixed-time (or dwell-time) stability of a switching system (2), if we know a priori that the system is not stable under arbitrary switching, we also know that there is no hope that the inequalities encoded in a (co-)complete graph are feasible, for any choice of candidate vector-valued Lyapunov function V : R n → R |S| . In this situation we have two possibilities: use a path-complete graph which is neither complete nor co-complete, or relax the conditions encoded in the edges, as we explain in the following subsection.

Splitting edges

In many situations ensuring that functions V a ,V b : R n → R and f j : R n → R n satisfy the inequalities encoded in the edge (a, b, j) τ for a fixed τ could be computationally hard, or even structurally infeasible (see Lemma 2 and Remark 3). One idea is to "relax" the conditions encoded in one or more edges: considering (a, b, j) τ we could split it in two new edges (a, c, j) τ /2 and (c, a, j) τ /2 . More precisely, recalling [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF], we require the existence of three positive definite functions V a , V b , V c : R n → R, such that

∇V a (x), f j (x) ≤ 2 τ (V a (x) -V c (x)), ∀ x ∈ R n , ∇V c (x), f j (x) ≤ 2 τ (V a (x) -V c (x)), ∀ x ∈ R n , ∇V c (x), f j (x) ≤ 2 τ (V c (x) -V b (x)), ∀ x ∈ R n , ∇V b (x), f j (x) ≤ 2 τ (V c (x) -V b (x)), ∀ x ∈ R n .
Following an idea proposed firstly in [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF], this reducing procedure could be generalized considering an N ∈ N and δ 1 , . . . , δ N > 0 such that Intuitively the resulting conditions imply again V b (x(τ, x 0 , f j )) ≤ V a (x 0 ), but without the stronger assumption encoded in (a, b, j) τ defined in [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF]. More precisely, the idea is to redefine W : [0, τ ) × R n → R used in the proof of Theorem 1 not simply as the linear interpolation on [0, τ ) between two function in C 1 (R n , R) (V a and V b ) as in ( 8), but as the linear interpolation between N + 1 functions, on a partition of [0, τ ) in N sub-intervals. See Fig. 2, 4 and 5 for a graphical illustration of this splitting procedure. We note here that this strategy is ineffective on edges which represent self-loops, that is, edges of the form (a, a, j) τ ∈ E, for some a ∈ S and j ∈ I. Indeed, a self-loop (a, a, j) τ ∈ E simply encodes the fact that the function V a : R n → R is a Lyapunov function for the system f j : R n → R n (independently of τ ∈ R + ) and thus it can not be relaxed splitting time intervals.

N k=1 δ k = τ , a b (1,τ ) (2,τ ) (1,τ ) (2,τ )

Linear Case and Numerical Examples 4.1 Linear Switched Systems

Let us consider A = {A 1 , . . . , A K } ⊂ R n×n , we define the linear switched system, as

ẋ(t) = A σ(t) x(t), (13)
where the switching signals σ are again selected in (a subclass of) S, see [START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF]. In this case we consider positive definite quadratics as base functions of our multiple-Lyapunov functions construction. More precisely, given a finite set S, we consider candidate vector-valued Lyapunov functions V : R n → R |S| component-wise quadratic, that is

V (x) = x P x, ∀x ∈ R n ,
where P ∈ R n×n are postive definite, for any ∈ S. In this setting, fixing a τ > 0, the inequalities encoded in (a, b, j) τ ∈ E given in [START_REF] Ahmadi | Joint spectral radius and pathcomplete graph Lyapunov functions[END_REF] are reduced to

P a A j + A j P a -1 τ (P a -P b ) ≤ 0, P b A j + A j P b -1 τ (P a -P b ) ≤ 0, (14)
that is a system of LMIs (linear matrix inequalities).

If one is interested in the strong counterpart (as defined in [START_REF] Geromel | Stability and stabilization of continuous-time switched linear systems[END_REF]), (a, b, j) τ ∈ E s , simply become

P a A j + A j P a -1 τ (P a -P b ) < 0, P b A j + A j P b -1 τ (P a -P b ) < 0. ( 15
)
While the choice of quadratics as base functions for ( 13) seems reasonable, it is important to point out that this introduces some degree of conservatism: the converse Lyapunov theorem in [START_REF] Wirth | A converse Lyapunov theorem for linear parameter-varying and linear switching systems[END_REF] relies on generic norms, see also the results in [START_REF] Chesi | A nonconservative LMI condition for stability of switched systems with guaranteed dwell time[END_REF] and [START_REF] Blanchini | Vertex/plane characterization of the dwell-time property for switching linear systems[END_REF] for the study of more general classes of Lyapunov functions for (13).

Numerical Examples

In what follows we introduce two linear switched systems [START_REF] Chesi | A nonconservative LMI condition for stability of switched systems with guaranteed dwell time[END_REF], and we want to estimate (as precisely as possible) τ dw ∈ R + , that is the minimal dwell-time for which (13) is GAS on the classes S dw (τ ), for all τ ≥ τ dw , using the ideas presented in the previous sections. If all the matrices in A are Hurwitz, it is known that such minimal dwell-time τ dw ≥ 0 exists, as proved in [9, Lemma 2].

Example 1. Consider system [START_REF] Chesi | A nonconservative LMI condition for stability of switched systems with guaranteed dwell time[END_REF] where

A = {A 1 , A 2 } ⊂ R 2×2 , with: A 1 = -18 17 -9 8 , A 2 = 13 -79 4 -20 The convex combination 1 2 A 1 + 1 2 A 2 = -2.5 -31 -2.5 -6
is non-Hurwitz, implying that the system is not stable under arbitrary switching. Moreover we can see explicitly in simulation (see Fig. 3) that using the switching signal σ = {1, 2, 1, 2, . . . }, with a fixed switching time τ = 0.3125, the system diverges, implying that τ dw > 0.3125.

a b c 1 c 2 c 3 d 1 d 2 d 3 (1, τ 4 ) (1, τ 4 ) (1, τ 4 ) (1, τ 4 ) (1,τ ) (2, τ 4 ) (2, τ 4 ) (2, τ 4 ) (2, τ 4 )
(2,τ )

Figure 4: Graph obtained by splitting the edges (a, b, 1) τ , (b, a, 2) τ using 3 auxiliary nodes for every edge.

If we consider the path-complete graph in Fig. 2, there is no Lyapunov function satisfying the associated constraints described in the previous Section: this graph is in particular co-complete and by Lemma 2, this would imply the existence of a common Lyapunov function for A 1 and A 2 jointly, which does not exist since there is a non-Hurvitz convex combination of A 1 and A 2 . Consider instead the graph in Fig. 4, constructed using the idea presented in Section 3.3, and thus splitting the edges (a, b, 1) τ , (b, a, 2) τ ∈ E in 4 sub-edges of length τ /4. We can find a PC-LF for the class S fix (τ ) for τ = 0.8. Using the idea of Corollary 1 (and thus "doubling" the inequalities) we are able to find a PC-LF for the class S dw (τ ) for τ = 1.1. It seems intuitive that: the more we split the edges (a, b, 1) τ , (b, a, 2) τ in the graph of Fig. 2, the more degrees of freedom we are adding to the problem and consequently we should be able to get a smaller τ . In fact, consider the graph where any of these two edges is split using N subnodes (Fig. 5). With N = 50 we can find a PC-LF for the class S dw (τ ) with τ = 0.35, while we need to increase to N = 90 to find a PC-LF for the class S dw (τ ) with τ = 0.345. We cannot find a feasible solution for τ = 0.34 even considering N = 400.

Example 2. Consider the following example, introduced in [11, Example 1], of system (13) with A = {A 1 , A 2 } ⊂ R 3×3 defined by

A 1 =   -1 0 1 -1 -1 0 0 1 -1   , A 2 =   -1 0 6 -1 -1 -5 0 1 -1  
In [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF] the authors are able to establish that the system is stable under the class of switching S dw (τ ) with τ = 0.4. The authors used a splitting technique similar to the one described in Section 3.3, using K = 95 sub-intervals of τ . With our method, using again the graph in Fig. 5, we can recover the same result, finding a PC-LF for the class S dw (τ ) with τ = 0.4, and N = 55. (2,τ )

Figure 5: Graph obtained by splitting the edges (a, b, 1) τ , (b, a, 2) τ using N auxiliary nodes for each edge.

Remark 4 (Uncertain Case). In [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF] the same minimal value τ dw = 0.4 for Example 2 is obtained using the result presented in [10, Theorem 1] with less computation effort. This result requires to compute the matrix exponentials e Aj τ for any j ∈ I. Since in general the function A → e Aτ is non-convex, the ideas of [START_REF] Geromel | Stability and stabilization of continuous-time switched linear systems[END_REF] can not be easily generalized to the case of uncertain matrices. On the contrary, the conditions in ( 14) and ( 15) (as the conditions proposed in [START_REF] Allerhand | Robust stability and stabilization of linear switched systems with dwell time[END_REF]) are linear in A j , j ∈ I, and thus the extension to the case with uncertainty is possible (but leading to a certain degree of conservatism), and open for further investigation.

Remark 5. The variable τ can, in principle, be added as a decision variable to the feasibility problem above but this would make the problem non-linear and potentially hard to solve. For this reason, a binary search on τ is performed to find numerically the lowest value for which the LMIs hold.

Conclusions

Considering continuous-time nonlinear switching systems, we explored stability conditions based on the concept of path-complete graphs. In the linear case, the obtained inequalities permitted us to estimate the minimal dwell-time using a finite number of LMIs. Possible open questions for further research are the case of uncertain systems and whether or not pathcomplete Lyapunov functions are universal (i.e. existence is also necessary) for the dwell-time stability.

Lemma 2 .

 2 Consider a finite set S, and V : R n → R |S| a candidate vector-valued function. Consider any τ > 0. If the associated graph G = (S, E) is complete then

Figure 2 :Figure 3 :

 23 Figure 2: Path-complete (co-complete) graph