{'fraction_non_alphanumeric': 0.052580645161290324, 'fraction_numerical': 0.01672043010752688, 'mean_word_length': 3.90921087358142, 'pattern_counts': {'":': 0, '<': 16, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Data-based computation of stabilizing minimum dwell times for discrete-time switched linear systems

We present an algorithm to compute stabilizing minimum dwell times for discrete-time switched linear systems without the explicit knowledge of state-space models of their subsystems. Given a set of finite traces of state trajectories of the subsystems that satisfies certain properties, our algorithm involves the following tasks: first, multiple Lyapunov functions are designed from the given data; second, a set of relevant scalars is computed from these functions; and third, a stabilizing minimum dwell time is determined as a function of these scalars. A numerical example is presented to demonstrate the proposed algorithm.


A. Motivation
Identification of classes of switching signals that preserve stability of switched systems (commonly called as stabilizing switching signals) constitutes a key topic in hybrid systems literature. A vast body of the existing works in this direction utilizes the concept of "slow switching" vis-a-vis minimum dwell time switching and its variants, see e.g., [9, Chapter 3], [13], [6], [7] for results and discussions. A switching signal satisfying a minimum dwell time τ > 0 dwells on any subsystem at least for τ units of time before it switches to a different subsystem. τ is called stabilizing if a switching signal obeying this minimum dwell time preserves stability of the switched system under consideration. Loosely speaking, the underlying idea of stability under minimum dwell time switching is that if all the subsystems are stable and the switching is sufficiently slow, then the "energy injected due to switching" gets sufficient time for dissipation due to the stability of the individual subsystems. It follows that a switched system whose individual subsystems are stable, may be unstable under arbitrary switching signals but always admits a stabilizing switching signal that satisfies a large enough minimum dwell time. Numerical computation of stabilizing minimum dwell times for switched systems typically requires the availability of mathematical models of the subsystems, see e.g., [6], [7] and the references therein. However, in many real-world scenarios, particularly for largescale complex systems, accurate mathematical models such as transfer functions, state-space models or kernel representations of the subsystems are often not present. This interesting fact motivates the current paper. We devise an algorithm to compute stabilizing minimum dwell times for discrete-time The author is with the Department of Electrical Engineering, Indian Institute of Science Bangalore, Bengaluru -560012, Karnataka, India, Email: atreyeek@iisc.ac.in Atreyee Kundu's research work is supported by INSPIRE Faculty Award IFA17-ENG225 by the Department of Science and Technology, Govt. of India.
switched linear systems when explicit knowledge of the statespace models of their subsystems are not available.

B. Literature survey
Stability analysis and control synthesis of switched systems without explicitly involving mathematical models of their subsystems, are dealt with recently in [5], [8], [1]. The work [5] addresses the problem of deciding stability of a discrete-time switched linear system from a set of finite traces of state trajectories. Probabilistic stability guarantees are provided as a function of the number of available state observations and a desired level of confidence. In [8] reinforcement learning techniques are employed for optimal control of switched linear systems. A Q-learning based algorithm is proposed to design a discrete switching signal and a continuous control signal such that a certain infinite-horizon cost function is minimized. The convergence guarantee of the proposed algorithm is, however, not available. A randomized polynomial-time algorithm for the design of switching signals under the availability of certain information about the multiple Lyapunov(-like) functions [9, §3.1] corresponding to the individual subsystems in an expected sense, is presented in [1]. The authors show that if it is allowed to switch from any subsystem to a certain number of stable subsystems, then a switching signal obtained from the proposed algorithm is stabilizing with overwhelming probability.

C. Our contributions
We consider the availability of finite traces of state trajectories of the subsystems that satisfy certain properties (henceforth to be called as subsystems data), possibly collected from a simulation model or during the operation of the switched system, and combine two ingredients: (a) data-based techniques for stability analysis of discrete-time linear systems and (b) multiple Lyapunov functions based techniques for the computation of stabilizing minimum dwell times for switched systems, towards developing an algorithm for the computation of stabilizing minimum dwell times in the absence of explicit knowledge of the state-space models of the subsystems. Our computation of stabilizing minimum dwell times involves the following steps: first, we design multiple Lyapunov functions, one for each subsystem, from the given data; second, we compute a set of scalars from these functions; and third, we determine a stabilizing minimum dwell time as a function of the above set of scalars.
Computation of stabilizing minimum dwell times for switched systems from multiple Lyapunov functions is standard, see e.g., [13], [7] and the references therein. However, these functions are commonly designed under complete knowledge of the state-space models of the subsystems. We assume certain properties of the subsystems data, and involve techniques of data-based stability analysis of linear systems proposed in [11] to design multiple Lyapunov functions. These functions are then employed to compute minimum dwell times. At this point, it is worth highlighting that we do not opt for the construction of mathematical models of the subsystems from the given data, and hence the proposed technique does not involve system identification of the subsystems.1 To the best of our knowledge, this is the first instance in the literature where stabilizing dwell times for switched systems are computed without the explicit knowledge of state-space models of the subsystems.

D. Paper organization
The remainder of this paper is organized as follows: In §II we formulate the problem under consideration. A set of preliminaries required for our result is presented in §III. Our result appears in §IV. We present a numerical example in §V, and conclude in §VI with a brief discussion of future research directions.

E. Notation
R is the set of real numbers and N is the set of natural numbers, N 0 = N ∪ {0}. I d denotes the d × d identity matrix, 0 n and 0 n denote the d ×1 zero matrix and d × d zero matrix, respectively. For a matrix B ∈ R d×d , B 0 (resp., B ≺ 0) denotes that B is positive definite (resp., negative definite), and λ max (B) denotes the maximal eigenvalue of B.

II. P
We consider a family of discrete-time linear systems where x(t) ∈ R d is the vector of states at time t, P = {1, 2, . . . , N } is an index set, and are full-rank constant Schur stable matrices.2 Let σ : N 0 → P be a switching signal. A discrete-time switched linear system generated by the family of systems (1) and a switching signal σ is described as where we have suppressed the dependence of x on σ for notational simplicity.
1In general, the problem of system identification of switched systems involves identification of the subsystems dynamics from noisy input-output data collected during the operation of the system, see e.g., the recent works The scalars a i, j , j = 0, 1, . . . , d − 1, i ∈ P, are unknown. We let χ = {(x i (0), x i (1), . . . , x i (L)), i ∈ P} be a given set of finite traces of state trajectories of the subsystems i ∈ P. Here, In the sequel we will refer to the set χ as subsystems data.
Let 0 =: κ 0 < κ 1 < κ 2 < · · · be the switching instants; these are the points in time where σ jumps. A switching signal σ is said to satisfy a minimum dwell time τ > 0 if the following condition holds: For a fixed τ, we let S τ denote the set of all switching signals σ that satisfy condition (4). We are interested in stability of the switched system (3) under every σ ∈ S τ for a certain τ.
Recall that Definition 1: The switched system (3) is globally asymptotically stable (GAS) for a given switching signal σ if (3) is Lyapunov stable and globally asymptotically convergent, i.e., for all x(0), lim t→+∞ x(t) = 0. We will solve the following problem: Problem 1: Given χ, compute τ such that the switched system (3) is GAS under every switching signal σ ∈ S τ .
Towards solving Problem 1, we will assume certain properties of χ, design multiple Lyapunov functions for the subsystems i ∈ P from χ, and compute a set of scalars corresponding to these functions. Then we will compute a dwell time τ as a function of the above set of scalars such that each element σ ∈ S τ is stabilizing. Prior to presenting our solution to Problem 1, we catalog a set of preliminaries.

III. P
The following fact is well-known: Fact 1: [6, Fact 1] For each i ∈ P, there exists a pair (P i , λ i ) ∈ R d×d × R, where P i is a symmetric and positive definite matrix and 0 < λ i < 1, such that, with we have and γ i (·) solves the i-th recursion in (1). The functions V i , i ∈ P are Lyapunov functions corresponding to the subsystems i ∈ P. The scalar λ i , i ∈ P gives a quantitative measure of stability of subsystem i. The Lyapunov functions corresponding to the individual subsystems are related as follows: Fact 2: [6, Fact 2] There exists R µ i j > 0 such that A tight estimate of µ i j , i, j ∈ P, is provided below.
Proposition 1: [6, Proposition 1] The scalars µ i j , i, j ∈ P can be computed as follows: Lemma 1: Consider the family of systems (1). Let λ i = λ s for all i ∈ P and µ i j = µ for all i, j ∈ P. Then the switched system (3) is GAS for every switching signal σ ∈ S τ with τ > ln µ |ln λ s | .
The estimate of a stabilizing minimum dwell time, τ, presented in Lemma 1 is standard in the literature, and has been proved in many contexts. For example, Lemma 1 follows directly from [7, Proposition 1] with no unstable subsystems.
The computation of the scalars λ i , i ∈ P and µ i j , i, j ∈ P (and hence the scalars λ s and µ) with known matrices, A i , i ∈ P, is addressed in [6]. However, we do not have the said information available. To cater to this scenario, we rely on data-based computation techniques of quadratic Lyapunov functions for stable linear systems presented in [11]. Let x ∈ R (d+1)×d , T ∈ {0, 1, . . . , L − 1} be such that its column vectors are linearly independent. We will operate under the following Assumption 1: The set χ is such that Ψ i is well-defined for all i ∈ P. Fix i ∈ P. Notice that whether Ψ i is well-defined or not, depends on the initial value, x i (0), and the length, L+1, of the available trace (x i (0), x i (1), . . . , x i (L)). Indeed, to design Ψ i , we need L d and x i (0) is such that the vectors q i (T), q i (T + 1), . . . , q i (T + d − 1) are defined and linearly independent for some T ∈ {0, 1, . . . , L − 1}. From [10, Lemma 3] it follows that for every A i in the companion form described in (2), there exists x i (0) ∈ R d such that Ψ i is well-defined with T = 0 and L = d. Clearly, a large number of traces of state trajectories of the subsystem i can be collected to arrive at such x i (0).
Lemma 2: For each subsystem i ∈ P, condition (6) is equivalent to the following: there exists a symmetric and positive definite matrix P i ∈ R d×d and a scalar 0 < λ i < 1 such that Proof: Follows under the set of arguments employed in [11,Theorem 2].
Lemma 2 provides a mechanism to design a set of Lyapunov functions V i , i ∈ P, defined in Fact 1, from the subsystems data, χ. We now combine Lemmas 1, 2 and Proposition 1 to provide a solution to Problem 1.

IV. R
Given subsystems data, χ, such that Assumption 1 holds, Algorithm 1 computes stabilizing minimum dwell times for discrete-time switched linear systems. It involves the following tasks: • First, the matrices Ψ i , i ∈ P, are constructed from the set χ. • Second, Lemma 2 is employed to compute symmetric and positive definite matrices, P i , i ∈ P and a scalar 0 < λ s < 1 that satisfy (11) with λ i = λ s for all i ∈ P. • Third, the estimates of P i , i ∈ P obtained above are used to compute the scalars µ i j , i, j ∈ P by employing Proposition 1. The scalar µ is chosen to be the maximum of µ i j , i, j ∈ P. • Fourth, τ is computed as a function of λ s and µ as described in Lemma 1.
Algorithm 1 Model-free computation of stabilizing minimum dwell time, τ Input: Subsystems data, χ, such that Assumption 1 holds. Output: A stabilizing minimum dwell time, τ. 1: Step I: Construct Ψ i , i ∈ P from χ. 2: Step II: Compute P i , i ∈ P and λ s as follows: 3: Fix h > 0 (small enough) and compute k ∈ N such that k is the largest integer satisfying k h < 1. 4: for λ s = h, 2h, . . . , k h do 5: for i = 1, 2, . . . , N do 6: Solve the following feasibility problem in P i : minimize 1 subject to condition (11) with λ i = λ s , P i = P i 0. if a solution P i to (12) is found for all i ∈ P then 9: Store λ s and P i , i ∈ P, and go to Step II.
Notice that solving (11) with both P i , i ∈ P and λ s unknown is a numerically difficult task. To address this issue, we employ a line search technique [2] as follows: a finite set of values of λ s on the interval ]0, 1[ is fixed, and corresponding to each element of this set, the feasibility problem (12) is solved for N symmetric and positive definite matrices, P i , i ∈ P. The value of λ s for which (12) admits a solution for all i ∈ P and its corresponding P i , i ∈ P are stored. We observe the following: Proposition 2: Consider µ ∈ R computed as µ = max i, j ∈ P µ i j , where µ i j , i, j ∈ P are as given in (8). Then µ > 1. Proof: Fix i, j ∈ P, i j. Let 0 < µ i j = λ max (P j P −1 i ) < 1. Clearly, λ min (P j P −1 i ) λ max (P j P −1 i ) < 1. In addition, P j P −1 i is similar to P −1/2 i (P j P −1 i )P 1/2 i and the matrix P −1/2 i P j P −1/2 i is symmetric and positive definite. Since the spectrum of a matrix is invariant under similarity transformations, we have λ min (P Since 0 < λ min (P j P −1 i ) < 1, it follows that µ ji > 1. Consequently, µ > 1. Proposition 2 asserts that ln µ |ln λ s | > 0. Proposition 3: Consider the switched system (3). Suppose that subsystems data, χ, such that Assumption 1 holds, are available. Then (3) is GAS under every switching signal σ ∈ S τ , where τ is obtained from Algorithm 1.
Proof: Follows from Lemmas 1 and 2. Remark 1: Notice that the choice of λ s for which the feasibility problem (12) admits a solution for all i ∈ P, is not unique. Algorithm 1 exits Step II with the minimum such λ s ∈ {h, 2h, . . . , k h}. To minimize τ over all λ s ∈ {h, 2h, . . . , k h} such that there is a solution to (12) for all i ∈ P, an algorithm requires to store all such λ s , compute the corresponding µ and τ, and output the minimum value of τ.
Remark 2: An important aspect of Algorithm 1 is the choice of the step size h > 0. Fact 1 and Lemma 1 guarantee the existence of λ s ∈]0, 1[ such that (12) admits solutions for all i ∈ P. However, λ s may be very small. For executing Algorithm 1, one may either pick h to be close to 0, or perform a trial and error procedure with h = 0.1, 0.01, 0.001, . . . until a solution to (12) is found for all i ∈ P.
Remark 3: It is worth noting that Algorithm 1 computes a stabilizing minimum dwell time and not the minimum dwell time on every subsystem required for GAS of (3). Indeed, Lemma 2 provides a sufficient condition for GAS of (3) and does not conclude that a switching signal σ satisfying a dwell time τ < τ, where τ obtained from Algorithm 1, is destabilizing.

V. A
Consider P = {1, 2, 3, 4, 5}. The matrices A i , i ∈ P and their eigenvalues are given in Table I. Our objective is to design a stabilizing minimum dwell time τ when A i , i ∈ P are not known, but subsystems data, χ that satisfy Assumption 1 are available.3 We employ Algorithm 1 for this purpose. The following steps are executed: 3For this experiment, we generate the elements of the matrices A i , i ∈ P with numbers from the interval [−1, 1] chosen uniformly at random. We build a simulation model, M, in Scilab 6.0.2 to generate the subsystems data χ.
Step I: For each subsystem i ∈ P, we construct Ψ i from the elements of the set χ. Numerical values of x i (0), x i (1), · · · , x i (L), i ∈ P and their corresponding Ψ i , i ∈ P are given in Table II. Step II: We fix h = 0.1, vary λ s over the interval ]0, 1[ with a step size h, and solve the feasibility problem (12) for symmetric and positive definite matrices, P i , i ∈ P. The following set of solutions is obtained:4 λ s = 0.7, Step III: We compute the scalars µ i j , i, j ∈ P by employing (8) and then fix µ = max i, j ∈ P µ i j . The numerical values are given below:  (12) is solved using the lmisolver tool in Scilab 6.0.2. µ 53 = 9.4062392, µ 54 = 3.60176, µ 55 = 1, and µ = 9.4062392.
Step IV: We fix ε = 0.01 and obtain a stabilizing minimum dwell time τ = ln µ |ln λ s | + ε = 7 units of time. We now demonstrate that τ is indeed a stabilizing minimum dwell time for the switched system under consideration. Towards this end, we perform the following experiment: we pick x(0) ∈ R 5 from the interval [−1, 1] 5 uniformly at random, design a switching signal σ randomly but ensuring a minimum dwell time τ on every subsystem, and plot the state trajectory ( x(t) ) t ∈N 0 of the switched system (3). This process is repeated 1000 times, and the corresponding plots of ( x(t) ) t ∈N 0 are given in Figure 1.

VI. C
To summarize, in this paper we presented an algorithm to compute stabilizing minimum dwell times for discrete-time switched linear systems when state-space models of their subsystems are not known explicitly. We consider that a set of finite traces of state trajectories of the subsystems that satisfies certain properties, is available. We design multiple Lyapunov functions corresponding to the subsystems from the subsystems data and determine a stabilizing minimum dwell time as a function of a set of scalars obtained from these Lyapunov functions.
A next natural question is regarding the extension of our techniques to the design of stabilizing switching signals when not all subsystems are stable and the admissible switches between the subsystems are restricted. This matter is currently under investigation, and will be reported elsewhere.