Convergence in uncertain linear systems
Filippo Fabiani Giuseppe Belgioioso Franco Blanchini Patrizio Colaneri Sergio Grammatico






delft]Filippo Fabiani,
tue]Giuseppe Belgioioso,
udine]Franco Blanchini,
milano]Patrizio Colaneri,
delft]Sergio Grammatico

[delft]Delft Center for Systems and Control, TU Delft, The Netherlands
[tue]Control Systems group, TU Eindhoven, The Netherlands
[udine]Dipartimento di Scienze Matematiche, Informatiche e Fisiche, University of Udine, Italy
[milano]Dipartimento di Elettronica,  Informazione e Bioingegneria, Politecnico di Milano, and CNR-IEIIT, Italy
Email addresses: f.fabiani@tudelft.nl (F. Fabiani), g.belgioioso@tue.nl (G. Belgioioso), franco.blanchini@uniud.it (F. Blanchini), patrizio.colaneri@polimi.it (P. Colaneri), s.grammatico@tudelft.nl (S. Grammatico).
	This work was partially supported by NWO under research projects OMEGA (613.001.702) and P2P-TALES (647.003.003), and by the ERC under research project COSMOS (802348).



State convergence is essential in several scientific areas, e.g. multi-agent consensus/disagreement, distributed optimization, monotone game theory, multi-agent learning over time-varying networks. This paper is the first on state convergence in both continuous- and discrete-time linear systems affected by polytopic uncertainty. First, we characterize state convergence in linear time invariant systems via equivalent necessary and sufficient conditions.

In the presence of uncertainty, we complement the canonical definition of (weak) convergence with a stronger notion of convergence, which requires the existence of a common kernel among the generator matrices of the difference/differential inclusion (strong convergence). We investigate under which conditions the two definitions are equivalent. Then, we characterize weak and strong convergence by means of Lyapunov and LaSalle arguments, (linear) matrix inequalities and separability of the eigenvalues of the generator matrices. We also show that, unlike asymptotic stability, state convergence lacks of duality.








§ INTRODUCTION

Hand in hand with stability, state convergence of dynamical, possibly uncertain, systems represents a fundamental problem in system theory. However, while stability and asymptotic stability have been intensively studied in the system-and-control community, state convergence has received little attention, especially for uncertain systems. Unlike asymptotic convergence, where the state of a certain system is supposed to converge to a known (desired) state, with state convergence, we mean convergence of a system to some state, which in general is unknown a-priori. For this reason, we address the state convergence problem of continuous- and discrete-time linear systems, both time invariant and affected by polytopic uncertainty, by means of spectral and geometrical analysis, Lyapunov and LaSalle theories. To the best of our knowledge, we are the first to study convergence in uncertain linear systems.
The problem of convergence to a constant, a-priori unknown equilibrium state is ubiquitous and spans, for instance, from distributed consensus problems to multi-agent optimization and games over networks, positive system dynamics and tuning of plants with unknown input-output map. Two motivating problems are presented next. Further applications
are discussed in the example section (8). 



Motivating applications:
We consider polar opinion dynamics in social networks <cit.>. Given a group of N agents indexed by the set I{1, …, N} and connected in a directed social network, we refer to the model proposed in <cit.>, where the collective opinion vector [x_1; …; x_N]  x ∈ [-1,1]^N, evolves according to

    ẋ(t) = - A(x(t)) L x(t).

Here, A(x(t)) ∈([0, 1]^N), for all t ≥ 0, is the diagonal matrix that characterizes the susceptibility to persuasion of each agent, while L ∈^N × N is the Laplacian matrix of the graph. The fundamental question in these models is whether or not the state x(t) converges to some  a-priori unknown state x̅. In that case, we have consensus as A(x̅) L x̅ = 0, therefore x̅ is a zero of the mapping x ↦ A(x) L x.

Since A(x(t)) ∈([0, 1]^N), A(x) ∈{A_1, …, A_m} for all x ∈ [-1,1]^N and given matrices A_i ∈^N × N, i ∈M{1, …, m}, then there always exist time-varying functions α_i(t, x(t)) ≥ 0, for all i ∈M and t ≥ 0, ∑_i ∈Mα_i(t, x(t)) = 1, such that A(x(t)) = ∑_i ∈Mα_i(t, x(t)) A_i. In <cit.>, A(x) is chosen equal to (I - (x)^2), 12(I - (x)) or (x)^2. Therefore, by denoting with e_i the i-th vector of the canonical basis, in all the three cases, we have



    A(x) ∈{[e_1,  0,  …,  0],  …, [0,  …,   0,  e_N]}.

Thus, the system in (<ref>) can be equivalently rewritten as

    ẋ(t) = - ( ∑_i ∈Mα_i(t, x(t)) A_i L ) x(t).

Clearly, the state solution to (<ref>) belongs to the set of solutions to the linear differential inclusion ẋ∈({A_i L}_i ∈M) x, whose convergence implies convergence of the original nonlinear dynamics in (<ref>). 


A second motivating application of state convergence is multi-agent learning over time-varying networks  
<cit.>.
For example, in multi-agent games, the simplest dynamics to learn a Nash equilibrium are the projected pseudo-gradient dynamics, i.e., for each agent i ∈I,

    x_i(k+1) = _Ω_i( x_i(k) - ϵ∇_x_i J_i(x_i(k), x_-i(k)) ),

where Ω_i is a local constraint set, ϵ > 0 is a step size and J_i is the local cost function, which depends on the local decision variable x_i (first argument) and on the decision variables of the other agents x_-i (second argument).
For simplicity, let x_i be of dimension 1. Let J_i be quadratic in x_i and affine in x_-i, hence ∇_x_i J_i(x_i, x_-i) = Φ_i^⊤x + ϕ_i, for some Φ_i ∈^N and ϕ_i ∈, and Ω_i = [a_i, b_i] ⊃{0}, hence the projection is a switched affine operator, i.e., _Ω_i(v) ∈{ a_i, v, b_i  }.
Therefore, the dynamics in (<ref>) are contained in switched affine dynamics x_i^+ = _Ω_i( x_i - ϵ∇_x_i J_i(x_i, x_-i) ) ∈{  a_i,  x_i - ϵ Φ_i^⊤x - ϵ ϕ_i, b_i }, and in turn in the uncertain affine dynamics

    y_i(k)       =   x_i(k) - ϵ Φ_i^⊤x(k) - ϵ ϕ_i  
    
    x_i(k+1)     =
    {[              y_i(k)  a_i < y_i(k) < b_i; (b/y_i(k))   y_i(k)        y_i(k) ≥ b_i; (a/y_i(k))   y_i(k)        y_i(k) ≤ a_i;                     ]. 
       ∈ [0,1] ( x_i(k) - ϵ Φ_i^⊤x(k) - ϵ ϕ_i ) ,





since b/y_i(k),   a/y_i(k)∈ [0,1] in their respective intervals.
Thus, for the collective dynamics, we have the following affine difference inclusion:

    x(k+1)     = _Ω
    ( x(k)- ϵ  F (x(k)) 
       ∈ [0,1]^N ( (I - ϵ Φ^⊤)  x(k) - ϵ ϕ) ,

where Ω×_i=1^N Ω_i and F(x) ×_i=1^N ∇_x_i J_i(x_i, x_-i) is the so-called pseudo-gradient mapping.
Clearly, convergence of the affine difference inclusion in (<ref>) implies convergence of the original nonlinear dynamics in (<ref>). In this paper, we study uncertain linear systems, since the affine case can be cast into the linear one via additional auxiliary states, see 8.1.

Essentially, the Nash equilibrium problem is the problem to ensure that the state x(t) of the system in (<ref>) converges to some a-priory unknown state x^*, which happens to be a Nash equilibrium due to the structure of the dynamics.
Similarly, primal-dual projected pseudo-gradient dynamics can be designed for computing a generalized Nash equilibrium in games with coupling constraints <cit.>.
While multi-agent optimization and game equilibrium dynamics are typically nonlinear, the analysis of the linear case provides necessary conditions for convergence <cit.>, e.g. potential certificates of non-convergence, see <cit.> for an example of non-convergent linear time-varying primal-dual dynamics.

Contribution:





	
  * Preliminarily, we start with necessary and sufficient conditions for state convergence of linear time invariant systems. Specifically, we link state convergence with the existence of a (weak) Lyapunov function, the separability of the eigenvalues, the stability of an auxiliary system and (linear) matrix inequalities (3 - for ease of readability, the proofs of this section are reported in Appendix <ref>);
	
  * We introduce the notions of weak and strong convergence for uncertain linear systems. We show that a sufficient condition, i.e., the kernel sharing property among the generator matrices of the difference/differential inclusion, implies that the two definitions are equivalent (4);
	
  * We show that the existence of a quadratic or polyhedral Lyapunov function is not sufficient for strong convergence: the existence of a suitable common decomposition of the generating matrices is required (5);
	
  * We associate sufficient (linear) matrix inequalities to weak and strong convergence (5-6);
	
  * We investigate weak convergence via LaSalle arguments and define the concept of weak kernel (6);
	
  * We show the lack of duality of state convergence in uncertain linear systems. Nevertheless, we show that the existence of a quadratic Lyapunov function guarantees duality of strong convergence (7).


Notation: 
,
 and _≥ 0 denote the sets of natural, real and non-negative real numbers, respectively;
bdry(S) denotes the boundary of a set S. ker(A)
denotes the kernel of matrix A;
μ(A) denotes its Lozinski measure, i.e., μ(A)=lim_h→ 0I+hA-1/h;
P ≻ (≽)   0 denotes that P is a positive (semi-)definite symmetric matrix.
0 (1) denotes vectors with elements all equal to 0 (1).











§ MATHEMATICAL BACKGROUND



Let us consider a DT LTI system

    x(k+1) = A   x(k),


where x ∈^n and A ∈^n × n, k ∈. For LTI systems, we are interested in global convergence of the state x to some vector x̅, which may depend on the initial conditions x(0), accordingly with the following definition.


	

	The system in (<ref>) is convergent if, for all x(0) ∈^n, there exists x̅∈^n such that the solution x(k) to (<ref>) satisfies lim_k →∞ x(k) - x̅ = 0.
	□


The convergence of LTI systems is closely related with the location of the eigenvalues of the matrix A and their algebraic/geometric multiplicity. Thus, let us recall the notion of semi-simple eigenvalue <cit.> and of (weak) Lyapunov function.


	

	An eigenvalue is semi-simple if it has equal algebraic and geometric multiplicity. An eigenvalue is simple if it has algebraic and geometric multiplicities both equal to 1.
	□









	

	A positive definite function V: ^n →_≥ 0 is a wLF for the system in (<ref>) if V(A x) ≤ V(x), for all x ∈^n.
	□


In particular, to link convergence results and stability of dynamical systems, we will consider several classes of wLF, as wQLF, wPLF and, more generally, wCLF.

The same definitions of convergence and stability apply to the CT LTI system
 

  

    ẋ(t) = A   x(t),


 

by substituting k ∈ with t ≥ 0. The definition of wLF in Definition <ref>, instead, reads as V̇(x) ≤ 0 for all x ∈^n. 




§ CONVERGENCE IN LTI SYSTEMS




 §.§ Discrete-time systems

We start with some equivalence results that link the convergence of (<ref>) with the (at least marginal) stability of an auxiliary system, (linear) matrix inequality (LMI) conditions and existence of a wLF. The proofs are reported in the appendix.


	
	The system in (<ref>) is convergent if and only if there exists η∈ (0,1) such that the system 
	
    x(k+1) = (  1/η A - 1-η/ηI ) x(k)  A^_η x(k),

	 is (marginally) stable.
□



	 

	The following statements are equivalent:
	
		
  * The system in (<ref>) is convergent;
		
  * ∃ η∈ (0,1) such that  the system in (<ref>) is (marginally) stable;
		
  * there exists a wPLF for the system in (<ref>);
		
  * there exists an invertible matrix T ∈^n × n such that 
		
    T^-1 A T = 
    		[ [ A^     0; A^     I ]],

		for some Schur matrix A^;








 

  * ∃ η∈ (0,1) and P ≻ 0 such that:
		
    η (A^⊤ PA-P)+(1-η)(A^⊤ -I)P (A-I) ≼ 0  ;

	
  * ∃ Q ≻ 0 and P ≽ 0, with rank(P) = n -  dim( ker(A-I)),  such that:
		
    A^⊤ PA-P+(A^⊤ -I)Q (A-I) ≼ 0  ;


□
	


We note that if the matrix inequality (e) in Proposition <ref> holds for some (η, P), then it also holds for (η_1, P), where η < η_1 < 1. This is because the function η↦ -(1-η)/η is increasing for η>0. Thus, we can fix η arbitrarily close to 1 and solve the corresponding LMI for P ≻ 0.


The system in (<ref>) is convergent if and only if the mapping x ↦ A x is “averaged” <cit.>. 
□














We conclude the subsection by noticing that the existence of a wPLF does not imply convergence. For example, consider the system x(k+1) = [ [  0 -1;  1 -0 ]] x(k), where the state does not converge, yet x(k) _∞ is constant.




























 §.§ Continuous-time systems

To characterize the convergence of the CT LTI in (<ref>), let us also introduce the following DT auxiliary system.


	

	Given τ > 0, the DT system
	
    x(k+1) = ( I + τ A) x(k)  A_τ x(k)

	is the EAS of the CT system in (<ref>).
	□


We then have the following results.

 
	The system in (<ref>) is convergent if and only if there exists ϵ > 0 such that the system 
	
    ẋ(t) = A   (I + ϵ A)^-1  x(t)  A^_ϵ  x(t),

	is (marginally) stable.
□



	 

	The following statements are equivalent:
	
		
  * The system in (<ref>) is convergent;
		
  * ∃ ϵ > 0 such that the system in (<ref>) is (marginally) stable;
		
  * there exists a wPLF for the system in (<ref>);
		
  * there exists an invertible matrix T ∈^n × n such that 
		
    T^-1 A T =  [
    		[ A^     0; A^     0 ] ],

		for some Hurwitz matrix A^;
		
  * ∃ τ>0 such that the EAS in (<ref>) converges;
		
  * ∃ ϵ > 0 and P ≻ 0 such that:	
		
    A^⊤ P + PA + ϵ  A^⊤ P A ≼ 0  ;

		

  * ∃ Q ≻ 0 and P≽ 0, with rank(P)=n- dim( ker(A)),  such that:
		
    A^⊤ P + PA + A^⊤ Q A ≼ 0  .


		□
	



Similarly to Proposition <ref> (e), we can fix an arbitrarily small ϵ > 0 and solve the corresponding LMI (f) in Proposition <ref> for P ≻ 0.





§ UNCERTAIN LINEAR SYSTEMS



For difference or differential linear inclusions <cit.> the definition of convergence requires some care. Specifically, we shall distinguish between weak and strong convergence. 


 §.§ Weak and strong convergence

We consider uncertain DT linear systems of the form

    x(k+1) = A(w(k)) x(k),

where A(w(k)) satisfies the following assumption.

	

	
    A(w) ∑_i ∈M A_i w_i,

	with M{1, 2, …, M } and w ∈W, defined as
	
    W{ w ∈^M  |  ∑_i ∈M w_i = 1,   w_i ≥ 0  ∀ i ∈M}.
 
	□

In CT, we consider the differential inclusion of the form

    ẋ(t) = A(w(t)) x(t),

with the same polytopic uncertainty structure.

As for LTI systems, we investigate whether x(k) converges to some x̅, which in general depends on w(k). For instance, if A(w(k)) = [ [ a_1,1(k)                 0;        1                 1 ]], 
with a_1,1(k) ∈{1/2,   3/4} for all k ∈, then x_1(k) → 0 and x_2(k) →x_2 = x_2(0) + ∑_k≥ 0 x_1(k), which is finite but depends on (a_1,1(k))_k ∈.

In view of this example, we give two different definitions of convergence.

	

	The difference inclusion in (<ref>) (respectively, differential inclusion in (<ref>)) is weakly convergent if, for all sequences  w(k) ∈W (resp., for all w(t) ∈W) and initial conditions x(0) ∈^n, there exists a vector x̅∈^n such that k →∞lim x(k) -   x̅ = 0 (t →∞lim x(t) -   x̅ = 0).
	□


Next, we introduce a stronger notion of convergence, i.e., convergence to the common kernel of the matrices {A_i-I}_i ∈M in DT (<ref>), or {A_i}_i ∈M in CT (<ref>).


	

	The difference inclusion in (<ref>) (resp., differential inclusion in (<ref>)) is strongly convergent if, for all sequences w(k) ∈W (resp., for all w(t) ∈W) and initial conditions x(0) ∈^n, there exists a vector x̅∈𝒳̅⊆^n, where 
	
    𝒳̅⋂_i ∈M (A_i - I),    ( resp., 𝒳̅⋂_i ∈M (A_i) )
 
	such that lim_k →∞ x(k) - x̅ = 0 ( lim_ t →∞ x(t) -   x̅ = 0).
	□


Therefore, to have strong convergence, the limit vector must be a steady state.
In other words, if we initialize the state x(0) ∈𝒳̅ then x(k) = x(0) for all k > 0 and for all possible sequences w(k) ∈W. 

On the other hand, this is not ensured with a limit vector in the case of weak convergence. Moreover, as stressed in the following example, while strong convergence implies weak convergence, the converse does not necessarily hold. 


	The scalar difference inclusion x(k+1) ∈{1/2,   1}  x(k) is weakly convergent (because the sequence { x(k) }_k ∈ is non-increasing over k ≥ 0) but not strongly convergent.
	□




 §.§ Kernel sharing property: when weak convergence implies strong convergence

We now investigate under which conditions the weak convergence of an uncertain system of the form (<ref>) (or (<ref>)) implies strong convergence. 


	If the difference inclusion in (<ref>) (resp., differential inclusion in (<ref>))
	is strongly  convergent, then the matrices {A_i - I}_i ∈M (resp.,  {A_i}_i ∈M), have exactly the same kernel:
	
    (A_i - I) = ⋂_i ∈M(A_i - I),   ∀ i ∈M
       (resp., (A_i)  = ⋂_i ∈M(A_i),   ∀ i ∈M).

□


	We prove the DT case by contradiction (the proof in CT is analogous). Let us assume that there exists some j ∈M such that we have strict inclusion, i.e., X̅⊂(A_j - I). Then, for some x(0) ∈(A_j - I) ∖X̅, and for A(w(k)) = A_j for all k ∈, we have the constant solution x(k) = x(0) ∉X̅.	
	▪


Along this idea, we link weak and strong convergence via the KSP introduced next.



	The family of matrices {A_i}_i ∈M has the Kernel Sharing Property if (<ref>) holds true.
	□



Note that the KSP is equivalent to claiming that (A(w) ) = K (resp., (A(w)-I  ) = K ) is invariant with respect to w ∈W.

We now show that, under the KSP assumption, if the system is weakly convergent, then it is also strongly convergent. Some preliminary results are reported first.  


	Let x(k) be a solution to (<ref>). If x(k) →x̅, then (A(w(k)) - I)x̅→ 0.
□
 

	Let z(k)  x(k) -x̅ → 0. By (<ref>), we have 
	
    z(k+1) = A(w(k)) z(k) + (A(w(k)) - I) x̅.

	Then, z(k) → 0 implies that (A(w(k)) - I) x̅→ 0.
	▪


The CT counterpart is not immediate, due to some technical problems, as stressed by the following example.

	The scalar differential inclusion ẋ(t) ∈{0,   -1}  x(t) is weakly convergent (because x(t) is non-increasing over t ≥ 0). Now, let us consider the case that A switches to -1 with spikes of decreasing length Δ_h < 1, i.e., let A(w(t))=-1 when t ∈ [h, h+Δ_h], and A(w(t))=0 otherwise.
	By considering an interval size such that ∑_h ≥ 0Δ_h =ln(2), we observe that x(t) tends asymptotically to x(0)/2, which is not in the common kernel of the A_i matrices.
	□


Thus, the natural extension of Lemma <ref> to the CT case does not hold, i.e., x(t) →x̅ does not imply that A(w(t)) x̅→ 0. However, convergence does happen on average, as formalized next.


	Let x(t) be a solution to (<ref>). If x(t) →x̅, then 
	
    lim_T →∞ 1/T∫_0^T A(w(t)) x̅  dt = 0  .

□
 
	

 
	Let z(t)  x(t) -x̅→ 0. Then, by (<ref>),
	
    ż(t) = A(w(t)) z(t) + A(w(t)) x̅.


	By integrating and diving by T > 0, we obtain
	
    1/T∫_0^T A(w(t)) x̅  dt = 1/T∫_0^T (ż(t)-A(w(t))z(t) )    dt
       = 1/T[x(T) -x(0)] - 1/T∫_0^T A(w(t))z(t)    dt → 0.

	For T →∞, the first term converges to 0 because x(t) is bounded and, since A(w(t)) z(t) → 0,
        the average of a function converging to 0 converges to 0 as well. Thus, lim_T →∞1/T∫_0^T A(w(t)) x̅  dt = 0.
	▪



	Let x(k) be a solution to (<ref>) (resp., x(t) solution to (<ref>)). If x(k) →x̅ (resp., x(t) →x̅), then there exists some w̅∈W such that (A(w̅) - I) x̅=0 (resp., A(w̅) x̅ = 0).
	□

	


	In the DT case, by Lemma <ref> we have:
	
    u(k) ∑_i ∈M^(A_i w_i(k) - I) x̅ = ∑_i ∈M   w_i(k)  (A_i - I )x̅→ 0.

	For all k ∈, since w(k) ∈W, the vector u(k) belongs to the convex hull of the vectors {(A_i  - I)x̅}_i ∈M, which is closed and convex. Thus, in the limit for k →∞, u(k) shall belong to the convex hull as well, i.e.,
	0 = ∑_i ∈Mw̅_i    (A_i  - I) x̅,
	namely, ( A(w̅) - I ) x̅ =0.
	
	In the CT case, by Lemma <ref>, we have:
	
    1/T∫_0^T ∑_i ∈M   w_i(t)  A_i  x̅  dt = 
    	(∑_i ∈M1/T∫_0^T  w_i(t)   dt )  A_i  x̅
       = ∑_i ∈Mω_i(T)  A_i  x̅→ 0,

	where ω_i(T) 1/T∫_0^T  w_i(t)   dt denotes the nonnegative average values of {w_i(t)}_i ∈M for every T > 0.
	Then, to derive A(w̅) x̅=0 for some w̅, we use the same argument on the limit used in the DT case.
	▪


	

	
We are now ready to exploit the previous lemmas to link weak and strong convergence under the KSP.
 
	If the family of matrices {A_i}_i ∈M has the Kernel Sharing Property, then weak convergence implies strong convergence.
□

	


	In view of Lemma <ref>, the convergence (if it holds)
	shall be in the kernel of some (A(w̅)-I) (resp., A(w̅)), since the kernel is common.
	▪



	In view of the properties of the Laplacian matrix of a strongly connected graph,
	the family of matrices {A_i L}_i ∈M in (<ref>), the first motivating application, has the KSP, since ∈(A_i L), for all i ∈M.
	□


The KSP, which can be efficiently verified by means of linear algebra arguments, is crucial to investigate strong convergence. In fact, it follows from Propositions <ref> and <ref> that if the matrices do not have a common kernel, there can not be strong convergence.






§ STRONG CONVERGENCE





 §.§ Separability of the eigenvalues


We first characterize the strong convergence property of difference (differential) inclusions via separability of the eigenvalues of the generator matrices.
Essentially, if the KSP holds, then the convergence analysis reduces to investigate the asymptotic stability of a subsystem.


	



	The following statements are equivalent:
	
		
  * The difference inclusion in (<ref>) (resp., differential inclusion in (<ref>)) is strongly convergent;
		
		
		
  * there exists an invertible matrix T ∈^n × n such that, for all i ∈M,
		
    T^-1 A_i T = 
    		[ [ A_i^         0; A_i^       I_m ]] 
    		
    		 (resp., = 
    		[ [ A_i^         0; A_i^       0_m ]]
    		),

		where m (X̅) and the matrices {A_i^}_i ∈M generate an asymptotically stable difference inclusion (resp., differential inclusion).
□
	


	
	We give the proof for the DT case, since the one in CT is analogous. Let T_2 ∈^n × m be the matrix generated by a basis of X̅, i.e., (A_i - I) T_2 = 0 for all i ∈M, and let T_1 ∈^n × (n-m) be a complement of T_2 such that T  [T_1   T_2] ∈^n × n is invertible. Then, T determines a similarity transformation that separate the eigenvalues of the matrices {A_i}_i ∈M as follows: 
		
    T^-1 A_i T=[[ A_i1         0; A_i2       I_m ]],    for all  i ∈M.
 
	Since the difference inclusion (<ref>) converges to X̅, this implies that the matrices {A_i1}_i ∈M shall generate an asymptotically stable difference inclusion.
	▪
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	






















































































 §.§ Lyapunov-like results


Next, we characterize the strong convergence property for both difference and differential inclusions by means of a Lyapunov analysis. First, we show that strong convergence implies the existence of a polyhedral Lyapunov function.


	If the difference inclusion in (<ref>) (resp., differential inclusion in (<ref>)) is strongly convergent, then it admits a wPLF.
	□

	


	We give the proof for the CT case (the one in DT is analogous).
	The strong convergence of (<ref>) allows to partition each matrix A_i as in (<ref>)
	with {A_i^}_i ∈M that generate an asymptotically stable differential inclusion. 
	By <cit.>, it admits a PLF whose vertices are in X ∈^(n-m) × r such that, for all i ∈M,
	
    A_i^ X = X P_i,

	with P_i ∈^r × r strictly column diagonally dominant, i.e., μ(P_i)< 0, for all i ∈M. Then, let us consider the augmented system with β > 0:
	
    [[ A_i^         0; A_i^       0_m ]]  [[     X           0;     0       β I_m ]]^ X^ = 
    	[[     X           0;     0       β I_m ]]  [[        P_i                     0; 1/β A_i^ X                   0_m ]]^ P_i^.

	For β sufficiently large, each matrix P_i^ is such that μ(P_i^)≤ 0, so that  X^ represents the matrix of vertices of a wPLF.	
	▪

	


While strong convergence implies the existence of a wPLF, it does not imply the existence of a wQLF. This follows by seeing asymptotic stability as a special case of strong convergence to the kernel {0} (i.e., robust asymptotic stability). In fact, there are uncertain linear  systems that are asymptotically stable but do not admit a quadratic Lyapunov function <cit.>. Conversely, the existence of either a wPLF or a wQLF in general does not imply convergence, neither strong nor weak, as shown by the following examples.



For the DT system x(k+1) ∈{-1,  1} x(k), with x(0) = 1, V(x) = x^2 is a wQLF and √(V(x)) = |x| is a wPLF. Whenever A(w(k)) = 1 for k even and A(w(k)) = -1 for k odd, the system does not converge.
□




 
Consider a CT system with A(w(t)) ∈{[
	[ -α -β; -α -β ]]  ,  [
	[ -γ -δ; -γ -δ ]] } for some α, β, γ, δ > 0. 
	This system is column weakly diagonally dominant, hence x_1 is a wPLF <cit.>.
	If we take x(0) such that x_1(0) + x_2(0) =1, then x_1(t) + x_2(t) = 1 for all t.
However, on the plane  x_1 + x_2 = 1, x_2(t) is not constant under persistent switching.
□


 


For the CT system with A(w) =
	[
	[  0 -w;  w -0 ]], with w > 0, V(x) = x^2 is a wQLF. While V̇(x) = 0, the system exhibits persistent oscillations since the eigenvalues are on the imaginary axis.
□












































Moreover, while (marginal) stability is equivalent to the existence of a homogeneous Lyapunov function <cit.>,  
Theorem <ref> and the previous examples show that the existence of a wPLF is necessary but not sufficient for convergence. In the next statement, we show instead a necessary and sufficient condition, which is the existence of a wPLF with special conditions.


	
	The difference inclusion in (<ref>) (resp., differential inclusion in (<ref>)) is strongly convergent if and only if there exist a full row rank matrix X and matrices 
	
    P_i=[[ P_i^         0; P_i^       I_m ]]  (resp., 
    	P_i=[[ P_i^         0; P_i^       0_m ]] ),

	where {P_i^}_i ∈M are such that P_i^_1<1 (resp., μ(P_i^)<0) and, for all i ∈M,
	
    A_i	 X=X P_i.

	
□


	




	We give the proof for the CT case, since the one in DT is analogous. The necessity part (only if) has been proved in Theorem <ref>. 
For the sufficiency (if), we consider the augmented system ż=P(w)z, with z(0) such that x_0=Xz(0), so that x(t)=Xz(t), t≥ 0. Such a system is strongly convergent in view of Theorem <ref>:
z(t) →z̅, with z̅ in the common kernel of the P_i, i.e. P_i z̅ =0.
We conclude the proof by noticing that x converges as well: x(t) = X  z(t) → X z̅x̅, which belongs to ker({A_i}_i ∈M). The last claim is immediate, because A_i x̅ = A_i X z̅ =   X P_i z̅ =0.	▪









































As for LTI systems, let us give (sufficient) LMI conditions to characterize strong convergence of difference and differential inclusions.   


	The difference inclusion in (<ref>) (resp., differential inclusion in (<ref>)) is strongly convergent if there exist P ≽ 0, with rank(P)=n- dim(𝒳̅), and Q≻ 0 such that, for all i ∈M,
	
    A_i^⊤ P A_i - P + (A_i^⊤-I)  Q  (A_i-I) ≼ 0
       
       (resp., A_i^⊤ P+PA_i +A_i^⊤ Q A_i ≼ 0).

□

	



	 The proof in CT mimics the one for the implication (g) ⇒ (d) of Proposition <ref>, by replacing A with A_i and Â with Â_i1, for all i ∈M.  The positive definite matrix P_1 generates a common wQLF for the subsystem with matrices {Â_1i}_i ∈M and hence strong convergence. 	Analogously, the proof in the DT case mimics the one for the implication (d) ⇒ (f) of Proposition <ref>.  

	▪









































Finally, we characterize the relation between the strong convergence of the differential inclusion in (<ref>) and the associated Euler difference inclusion 

    x(k+1)=(I+ τ A(w(k)) )x(k).



	
	The differential inclusion in (<ref>) is strongly convergent if and only if there exists τ >0 such that the  difference inclusion in (<ref>) is strongly convergent. 
□

	


	For all i ∈M, let A_τ,i I+τ A_i. The proof follows from Theorem <ref> by first noticing that ker (A_i) =  ker (A_τ,i-I), for all i ∈M. Moreover, the fact that μ(P_i^)<0 implies I+τ P_i^_1<1 for all τ <min_k {-2/d_kk}, where d_kk are the diagonal entries of  P_i^. Finally, if τ >0 is such that P_i^_1<1, then μ_1((P_i^-I)/τ)<0.
	
	
	
	
	
	
	▪





 §.§ Convergence rate

We close the section with a convergence rate estimate for strong convergence. Let us consider the decomposition in Theorem <ref>. Since A^(w) defines an exponentially stable inclusion, the first variable x_1(t) converges to zero exponentially fast, i.e., x_1(t) ≤ c_0  x_1(0)  e^-β t, for some 0 < β := - max_i ∈ℳμ(P^_i), see Corollary <ref>. The second component satisfies ẋ_2 = A^(w) x_1, thus 
	
    x_2(t) = x_2(0) + ∫_0^t A^(w(τ)) x_1(τ) d τ.

Consider c_1 such that A^(w)≤ c_1 for all w. Then, we have the following convergence rate for x_2(t):

    x_2(t) - x_2(∞)  = ∫_t^∞  A^(w(τ)) x_1(τ)  d τ
    ≤     
    		c_1  ∫_t^∞x_1(τ)  d τ≤  
    		c_0 c_1 ∫_t^∞  e^-β t d τ 
    		= c_0 c_1/βe^-β t.




	
	






§ WEAK CONVERGENCE





 §.§ Lyapunov-like results

We now characterize weak convergence for uncertain systems via Lyapunov arguments. First, we have a converse Lyapunov theorem.


	If the difference inclusion in (<ref>) (resp. the diffrential inclusion (<ref>)) is weakly convergent, then it admits a wCLF.
	□

	


	Let us consider any polytopic, 0-symmetric, set X⊆^n including the origin
	in its interior, and denote R_k as the set of reachable states for the uncertain system (<ref>) in at most k steps from  x(0) ∈X_0.
	Let R_∞ be the union of all these sets, i.e., R_∞⋃_k ∈ R_k.
	By <cit.>, R_∞ is bounded, namely there exists some b ≥ 0 such that x(k)≤ b, for all x ∈R_∞.
	Indeed, for all k ∈, there exists some x(k) that belongs to a trajectory
	originating from x(0) ∈X_0 (actually on a vertex <cit.>)
	which is on the boundary. Therefore, the boundedness of R_∞ is necessary for weak convergence.
	Thus, by defining C{R_∞}, we note that its closure is a convex, compact, 0-symmetric set including the origin in its interior, and by <cit.> the norm induced by this set is a wCLF.
	 The proof is similar (although a bit more involved) in the CT case.
	▪


	


Then, we provide sufficient matrix inequality conditions for weak convergence via a common wQLF.
  

	If there exist P≻ 0 and  η∈ (0,  1) (resp., ϵ>0 ) such that, for all i ∈M, the LMI
	
    η(A_i^⊤ PA_i -P)+ (1-η) (A_i^⊤ - I) P (A_i -I) ≼ 0
       
       (resp., 
    		A_i^⊤ P+PA_i + ϵ A_i^⊤ P A_i ≼ 0)


	holds, then the difference inclusion in (<ref>) (resp., differential inclusion in (<ref>)) is weakly convergent.
	
□

	


	Let ϵ=(1-η)/η. By considering the wQLF V(x)=x^⊤ P x, the Schur complement applied to the first inequality in (<ref>) gives, for any w ∈W,
	
    [[     V(x(k+1))-V(x(k))                       (x(k+1)^⊤ - x(k)^⊤) P;       P (x(k+1)-x(k))                                        -1ϵP ]]≼ 0.

	Then, V(x(k+1))-V(x(k))≤ 0 and x(k+1)=x(k)  for some x(k)= x̅. By noticing that the first inequality in (<ref>) can be equivalently rewritten as 
	
    [[                P      A(w(k))^⊤ P (A(w(k))^⊤ - I)P;        P A(w(k))                P                0;    P(A(w(k))- I)                0              1ϵP ]]≽ 0,

	for all k ≥ 0, and by averaging in the interval [0, K-1], we finally conclude that x̅ belongs to (A(w̅)), where 
	w̅=lim_K→∞1/K∑_k = 0^K-1 w(k).
	Hence, the difference inclusion in (<ref>) converges and V(x) is a common wQLF.
	
	The CT version is analogous: we consider the wQLF V(x)=x^⊤ P x and we apply the Schur complement to the second inequality in (<ref>), hence obtaining, for any w ∈W,
	
    [[ V̇(x)       ẋ^⊤ P;   P ẋ        -1ϵP ]]≼ 0.

	Then, V̇(x)≤ 0 and V̇(x)=0 for ẋ(t)=0, i.e, for some x = x̅. By noticing that the second inequality in (<ref>) can be equivalently rewritten as 
	
    [[ A(w(t))^⊤ P+PA(w(t))                               A(w(t))^⊤ P;             PA(w(t))                                      -1ϵP ]]≼ 0,

	for all t ≥ 0, and by averaging in the interval [0, T], we finally conclude that x̅ is in the null space of A(w̅), where 
	w̅=lim_T→∞1/T∫_0^T w(t)   dt.
	Thus, the differential inclusion converges and V(x) is a common wQLF.
	▪	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	




The first inequality in (<ref>) (resp., the second inequality in (<ref>)) is equivalent to 

    (A_η, i^)^⊤ P A_η, i^≼ P   (resp.,(A_ϵ,i^)^⊤ P + PA_ϵ,i^≼ 0)

for all i ∈M, where A_η,i^ = η A_i - 1-ηη I (resp., A_ϵ, i^=A_i(I+ϵ)^-1), 
implying weak stability of the auxiliary difference inclusion (resp., differential inclusion) 

    x(k+1) = A_η^ (w(k)) x(k),  (resp., ẋ(t) = A_ϵ^(w(t)) x(t)).

□




	Differently from strong convergence, we cannot characterize the speed of convergence in the weak case, since it can be arbitrarily slow and strongly depends on the uncertain parameter. An example in CT is the scalar system ẋ = w(t)   x, with w(t) ∈ [0, 1], for each t ≥ 0.
□






 §.§ LaSalle-like criteria

A necessary condition for convergence requires that the difference (differential) inclusion is at least marginally stable. To have convergence to a non-zero vector x̅, at least one matrix inside the convex hull of the matrices {A_i-I}_i ∈M (resp., {A_i}_i ∈M) shall be singular. In this case, the convergence does not need a common kernel and it can be associated with a specific singular element. As an example in CT, let us consider

    A(w(t)) ∈{A_1, A_2} = {[ 
    [  0    -1;  1    -1 ]], 
    [ 
    [ -0    -1; -1    -1 ]]},

where A̅= 12(A_1+A_2) is singular. Then, if A(w) “converges" to  A̅, then the trajectory converges to a non-zero vector of the form [x̅_1; 0], otherwise x → 0. Next, we investigate LaSalle arguments of this type.



	Let V be a positively homogeneous wLF for the differential inclusion in (<ref>) with derivative
	
    D^+V(x,A(w)x) h→ 0^+lim   sup V(x+hA(w)x)-V(x)/h,

	and assume that
	
    D^+V(x,A(w)x) ≤ -ϕ(x, A(w)x),

	for some positive semi-definite, locally Lipschitz function ϕ. Then x(t), solution to (<ref>), converges to the set
	
    𝒩{ x ∈^n  |  min_w ∈W{ϕ(x, A(w)x) } = 0 }.

□


 Let x(t) be any trajectory of (<ref>). We have:
	
    V(x(0))    ≥∫_0^t - D^+ V   dσ
    ≥∫_0^t  ϕ(x(σ), A(w(σ)) x(σ))   dσ
       ≥∫_0^t min_w ∈W {ϕ(x(σ), A(w)x(σ)) }  dσ .

	The function ϕ is Lipschitz continuous inside
	the set {x ∈^n | V(x) ≤ V(x(0)}. Since 𝒲 is a compact and convex set, the min function is also nonnegative and Lipschitz <cit.>. Therefore, in view of the Barbalat's lemma, lim_t→∞ min_w ∈W {ϕ(x, A(w)x) } = 0.
	▪

	

	
The next two results follow as a direct consequence of Lemma <ref>.


	Let V be a smooth wLF for the differential inclusion in (<ref>). Then x(t), solution to (<ref>), converges to the set
	
    𝒩{ x ∈^n  |  min_i ∈M { - ∇ V(x) A_i x} = 0 }.

□

	

	

	The proof follows by applying Lemma <ref> with ϕ(x, A(w)x)  = -∇ V(x) A(w) x ≥ 0 and by noticing that the minimum in (<ref>) is achieved on the vertices, i.e.,
	w ∈Wmin {-∇ V(x) A(w) x}=  i ∈Mmin {-∇ V(x) A_i x}.
	▪



Barbalat's lemma requires Lipschitz continuity of D^+V(x,A(w)x). Consequently, if the differential inclusion in (<ref>) admits a non-smooth wLF, V, then we cannot guarantee the convergence to the set where min {-D^+ V(x, A(w) x)} = 0. In that case, we shall rely on some locally Lipschitz function ϕ, as in Lemma <ref>.
□


 
	Let V be a positively homogeneous wCLF for the Euler auxiliary difference inclusion in (<ref>) and define
	
    Δ_τ V(x,w) V(x+τ A(w)x)-V(x)/τ,

	which is non-positive. Then x(t), solution to (<ref>), converges to the set 
	
    𝒟{ x ∈^n  |  min_w ∈W {- Δ_τ V(x,w) } = 0 }.

□

	



Since V is convex, for all x and w, we have that D^+V(x,A(w)x) ≤Δ_τ V(x,w) <cit.>. The proof then follows by taking  -ϕ=Δ_τ V, which is Lipschitz continuous.

▪



Let us observe that if V is a positively homogeneous wPLF for (<ref>), we can choose ϕ(x,A(w)x) = Δ_τ V(x,w) in (<ref>), for some small enough τ > 0. This follows by the fact that a polyhedral function is a wPLF for the differential inclusion (<ref>) if and only if, for some τ >0, it is a wPLF for the associated Euler auxiliary difference inclusion.






















In the DT case, we have the following LaSalle-like statement.


	Let V be a positively homogeneous wCLF for the difference inclusion (<ref>).
	Then x(k), solution to (<ref>), converges to the set 
	
    𝒟{ x ∈^n  |  min_w ∈W{ V(A(w) x) - V(x) } = 0 }.

□



	We have
		V(x(0)) =  ∑_k=0^∞  [ V(x(k)) - V(A(w(k)) x(k))]
		≥∑_k=0^∞ min_w ∈W{-Δ V(x(k),w)}, where -Δ V(x(k),w(k)) = V(x(k)) - V(A(w(k)) x(k)).
	The terms of the series are positive, hence boundedness implies that
	w ∈Wmin {-Δ V(x(k),w)}→ 0.
	▪

	




 §.§ Weak kernel


To further characterize weak convergence for differential inclusions, let us introduce the notion of weak kernel.



The weak kernel of the differential inclusion in (<ref>) is denoted by the set

    K{ x ∈^n |∃ w ∈W  s.t.   A(w) x = 0 }.

□


By referring to the set N in (<ref>), in general K⊆𝒩. The next example shows a case in which K and N coincide, and the solution to (<ref>) converges to the weak kernel.


	For the differential inclusion with
	A(w(t)) ∈{A_1, A_2} = {diag(-1,0),  diag(0,-1) },
	V(x) = 12(x_1^2+ x_2^2) is a wQLF. The set N in (<ref>) is
	characterized by the equation
	
    min_i ∈M {x^⊤ A_i x} = min {x_1^2,x_2^2} =0,

	which represents the (nonconvex) union of the two axes. Note that, in general, if there exists a wQLF for the differential inclusion in (<ref>), since A_i P + PA_i = -Q_i, with Q_i ≽ 0 for all i ∈M, the set 𝒩 = { x ∈^n |min_i ∈M { x^⊤ Q_i x } = 0 } 
	can be computed as the union of the kernels.
	□



Our result is that, under the existence of a wPLF, asymptotic stability of the differential inclusion in (<ref>) is equivalent to the fact that the weak kernel is trivial.



	Let V be a wPLF for the differential inclusion in (<ref>). Then A(w) is robustly 
	non-singular, i.e., 𝒦 = {0}, if and only if the solution to (<ref>),
	x(t), tends to 0 for all x(0) and (w(t))_t≥0.
□

	


	If A(w) is singular for some w ∈W, then we can not have robust stability. Thus, we only need to prove the converse statement

	Let A(w) be robustly non-singular and let V be defined by s-planes, indexed in S{1, …, s}. Given some ρ > 0, we introduce the set
	L_(V/ρ){x ∈^n | V(x) ≤ρ} = {x ∈^n | f^⊤_i x ≤ρ,  ∀ i ∈S}.

	Moreover, let A(x) be the set indexing the active planes, i.e., A(x) {i ∈S| f^⊤_i x = V(x)} and let ℱ_𝒜 be any arbitrary ℓ-dimensional face 
	
    ℱ_𝒜{x ∈L_(V/ρ)| f^⊤_i x =ρ,  ∀ i ∈ℰ},

	where E indexes the “active” planes at bdry(L_(V/ρ)). The remainder of the proof exploits <cit.>. Thus, for some ℓ-dimensional face, and hence for some indices i ∈𝒜(x), we shall have, for all x ∈ℱ_𝒜 and w ∈W, D^+V(x,A(w)x) = f^⊤_i A(w) x < 0.
	Otherwise, the existence of some w̅∈W such that f^⊤_i A(w̅) x = 0 for all i ∈𝒜(x) implies the positive invariance of the LTI system ẋ = A(w̅) x, and hence the singularity of  A(w̅).
	Thus, let x(t) be the solution to (<ref>) with initial condition x(t_0). If x(t_0) ∈ℱ_𝒜, by continuity there exists a right neighborhood [t_0, τ_1] of t_0, with τ_1 > 0, such that the active set can not grow, i.e, 𝒜(x(t)) ⊂𝒜(x(t_0)) for all t ∈ [t_0, τ_1].
	By repeating the same argument, x(t) shall reach a face of dimension 1 where there is only a single active constraint, i.e., A(x(t)) = {i}. Here, in view of the considerations above, f^⊤_i A(w) x <0 for all x ∈F_A and w ∈W.
	Therefore, for any initial condition x(t_0) such that V(x(t_0)) = ρ, in an arbitrary small neighborhood [t_0, τ] of t_0, for some τ >0, we have V(x(τ)) < ρ.
	Then, V(x(t)) ≥ 0 is monotonically non-increasing along any x(t), and hence it has a limit V(x(t)) →ρ̅ from above. From now on, the proof replicates the one in <cit.>, and hence is here omitted.
	
	
	
	
	
	▪



Finally, we note that robust non-singularity, i.e., trivial weak kernel, along with the existence of a wLF (which is not polyhedral), does not imply convergence. For example, consider the system
	ẋ =  [ [  0 -1;  1  0 ] ] x and V = x.








































§ CONVERGENCE LACKS OF DUALITY


It is known that the stability (asymptotic or marginal) of x(k+1) = A(w(k)) x(k)  (resp., ẋ(t) = A(w(t)) x(t)) implies the stability of the dual system
x(k+1) = A^⊤(w(k)) x(k) (resp., ẋ(t) = A^⊤(w(t)) x(t)). Similarly, it can be shown that duality holds in the LTI case, i.e., if x(k+1) = A x(k)  (resp., ẋ(t) = A x(t)) converges, then x(k+1) = A^⊤ x(k)  (resp., ẋ(t) = A^⊤ x(t)) converges as well. Interestingly, the convergence of an uncertain linear system lacks of duality. 



The convergence of x(k+1) = A(w(k)) x(k)  (resp., ẋ(t) = A(w(t)) x(t)) does not imply the convergence of the dual system
x(k+1) = A^⊤(w(k)) x(k) (resp., ẋ(t) = A^⊤(w(t)) x(t)).

□

	


	The proof goes by means of two examples. We consider the DT case first. 
	With a ∈ (0,1), the system
	
    A(w(k)) ∈{A_1, A_2} = {[
    	[ a   1; 0   1 ]],
    	[
    	[ a   2; 0   1 ]]}

	is neither strong nor weak convergent. In fact, while x_2(k) = x_2(0), for all k > 0, by taking alternatively A(w(k)) = A_1 for k even and A(w(k)) = A_2 for k odd, x_1(k) exhibits persistent oscillations. However, the dual system is strongly convergent, since it is in the block-triangular form in Theorem <ref> (b).
	
	In CT, the differential inclusion characterized by
	
    A(w(t)) ∈{A_1, A_2} = {[
    	[ -α    -β; -α    -β ]]  ,  [
    	[ -γ    -δ; -γ    -δ ]] },

	for some α, β, γ, δ > 0, does not converge (see Example <ref>) while the dual system with A^⊤(w(t)) is strongly convergent to κ, κ∈. It follows by considering V(x) = |x_1 - x_2| as a common Lyapunov function.
	▪

	


However, an intriguing fact is that weak quadratic Lyapunov functions provide some kind of duality.


	Assume that the difference inclusion in (<ref>) (differential inclusion in (<ref>)) admits a wQLF. Then, it is strongly convergent if and only if the dual system is strongly convergent.
	□

	


	We prove the CT version first. By applying the state decomposition of Theorem <ref>, we consider a wQLF for (<ref>) such that, for all i ∈M,
	
    [[   P   R; R^⊤   Q ]] 
    	[[ A_i^         0; A_i^       0_m ]]
    	+  
    	[[ (A_i^)^⊤          (A_i^)^⊤;        0               0_m ]] [[   P   R; R^⊤   Q ]]  =
       [[ P A_i^ +(A_i^)^⊤ P + RA_i^ + (R A_i^)^⊤                                                                             (*);                     R^⊤ A_i^   +  QA_i^                                                                             0_m ]]   ≼ 0,

	where (*) = (A_i^)^⊤ R   +  (A_i^)^⊤ Q. The relation above implies  
		R^⊤ A_i^   +  Q A_i^ = 0,
		for all i ∈M. Then, we use the matrices R^⊤ and Q to introduce an additional state transformation as follows
		
    [[   I   0; R^⊤   Q ]]
    		[[ A_i^         0; A_i^       0_m ]][[   I   0; R^⊤   Q ]]^-1 =
    		[[ A_i^         0;    0       0_m ]].

		Since {A_i^}_i ∈M generate asymptotically stable differential inclusions, the same holds for {(A_i^)^⊤}_i ∈M. Hence the strong convergence of diag( A_i^, 0_m )






		implies the strong convergence of the linear differential inclusion defined by {A_i^⊤}_i ∈M, where
		A_i^⊤=[[ (A_i^)^⊤          (A_i^)^⊤;        0               0_m ]].

	The proof is similar for the difference inclusion in (<ref>). Indeed, by considering a wQLF, we have
	
    [[ (A_i^)^⊤ (A_i^)^⊤;        0      I_m ]][[   P   R; R^⊤   Q ]] [[ A_i^    0; A_i^  I_m ]] - [[   P   R; R^⊤   Q ]] ≼ 0,

	which implies, for all i ∈M,
	R^⊤ A_i^   +  QA_i^ - R^⊤ = 0.
	Moreover, by adopting the same additional state transformation introduced above, we have
	
    [[   I   0; R^⊤   Q ]]
    	[[ A_i^         0; A_i^         I ]][[   I   0; R^⊤   Q ]]^-1 =
    	[[ A_i^         0;    0       I_m ]],

	where {A_i^}_i ∈M generate an asymptotically stable difference inclusion. So is {(A_i^)^⊤}_i ∈M, and by following the same reasoning for the CT case, we obtain the strong convergence of the dual system.
	▪


	



Let us summarize the main implications for linear differential/difference inclusions next, in Table <ref>.





§ EXAMPLES



 §.§ Uncertain linear systems with persistent input

Let us consider the system

    ẋ(t) = A(w(t)) x(t) + Bu̅

where u̅∈ is a constant scalar, and assume that the unforced system is asymptotically stable for any signal w(t) ∈W.
We observe that the state of such system converges if and only if the following extended (marginally stable) system is strongly convergent:




    [[  ẋ; u̇ ]] =  [[  A(w)     B; 0_n^⊤     0 ]]
     [[ x; u ]].



In fact, strong convergence implies that the extended state converges to the common kernel K = { [x̅  ;  u̅] ∈^n+1| A(w) x̅ + B u̅ =0 }. 
This subspace has dimension 1, since A(w) is non-singular. 
Let ( x̅, u̅ ) ∈𝒦: with the transformation 
T=[ [   I_n          x̅; 0_n^⊤          u̅ ]],
we have that
T^-1[[  A(w)     B; 0_n^⊤     0 ]]T= diag(A(w),0 )	,
hence, by Theorem <ref>, the extended system in (<ref>) is strongly convergent. 

The DT case is analogous, since the uncertain affine system x(k+1) = A(w(k)) x(k) + B u̅, where u̅∈ is constant, reads as the following uncertain linear system, where u(0) = u̅:

    [
    
    x^+ 
    
    u^+
    ] = [ 
    
    A(w)     B 
    0_n^⊤    1
    ] [
    
    x 
    
    u
    ].





 §.§ Uncertain opinion dynamics in social networks


An example of uncertain system with persistent input is the following model of the probability distribution of a linear emulative network of stochastic agents. Let x^[r](t)∈^M denote the unit-sum opinion probability vector for the r-th agent, r ∈N{1,2,…,N}, in linear emulative model with an arbitrary network topology. It is shown in <cit.> that the probability distribution of the r-th agent can be written as, for j ∈M{1,2,…,M},

    ẋ_j^[r]=∑_i ∈M q_i,j^[r]x_i^[r]+λ( ∑_k∈𝒩_r x_j^[k]/|𝒩_r|-x_j^[r])

where
λ>0 represents the influence intensity, equal for different opinions, 𝒩_r the set of neighbors of agent r, and  q_i,j^[r]  the probability transition rate from opinion i to opinion j for agent r in absence of influence. From now on, we assume that all the transition rate matrices Q^[r], r ∈N, of the isolated agents are irreducible and M=2. Since 1_2^⊤ x^[r]=1, we can discard the second component of each probability vector, so that the reduced N-dimensional model reads as

    ż(t)=(-Δ + λ G)z(t)+ q

where G is the graph matrix, a Metzler matrix such that 1_N^⊤ G = 0_N^⊤, Δ = diag(δ_1, …, δ_N) is a positive diagonal matrix with elements δ_r = q_1,2^[r]+q_2,1^[r] and q is a column vector with q_r=q_2,1^[r]. Let us consider that the graph matrix is uncertain and given by

    G(w)=∑_i=1^g G^[i] w_i

with G^[i], i=1,2,…, g, suitable graph matrices of connected graphs. 
The augmented system is then

    [ [  ż; u̇ ]]=[ [ ∑_i=1^g (-Δ + λ G^[i])w_i                                                   q;                         0                                                   0 ]] [ [ z; u ]].

We note that no common kernel exists unless q=β̅Δ 1_N, and in this case, the common (1-dimensional) kernel is given by 
span( [ 1_N^⊤,    ( Δ 1_N)^⊤ ]^⊤ ),
since 
-(-Δ + λ G^[i])^-1 1_N= 1_N, ∀ i ∈𝒩.
This is the well known unbiased network case, i.e., the bias parameters β_r =
q_21^[r]/(q_21^[r]+q_12^[r]) are all equal to β̅<1. 
It follows from 8.1 that the augmented uncertain system in (<ref>) is strongly convergent, in particular, for all z(0) and u(0), lim_t →∞z(t) =  1_N β̅u(0).



 §.§ Kolmogorov–like equations


Let us consider the system 

    ẋ(t) = ( ∑_i ∈M  A_i w_i(t) ) x(t),

where each A_i is an irreducible, Metzler matrix with strictly positive off-diagonal elements. 

If A_i are column-stochastic matrices, i.e., if 1^⊤ A_i = 1^⊤ for all i ∈M, then V(x) = x_1 is a wPLF for the system in (<ref>), while if A_i are row-stochastic matrices, i.e., if A_i 1 = 1 for all i ∈M, then V(x) = x_∞ is a wPLF.

In general, as shown in Example <ref>, column-stochastic matrices do not share a common kernel. Conversely, in the row-stochastic case, for τ > 0 small enough, we note that the associated Euler difference inclusion
x(k+1) = F(w(k)) x(k)= (∑_i ∈M w_i (k) F_i ) x(k),
where  F_i   I+τ A_i, ∀ i ∈M, is a positive, row-stochastic matrix. Then, we have
F_i   x_∞≤x_∞
where, unless x_1=x_2=… =x_n, the relation holds as strict inequality since, for all i ∈M, ∑_j (F_i)_hj |x_j| < max_j |x_j|. Therefore, the state of the system converges to the set K ={x ∈^n | x_1=x_2=… =x_n}. Under the irreducibility assumption, K corresponds to the common kernel of the generator matrices {A_i}_i ∈M.



 §.§ Plant tuning with singularity

Given a static plant governed by an unknown mapping

    y(t) = f(u(t))

such that the Jacobian matrix of f belongs to a polytope  M in which all the elements are non-singular (robust non-singularity) and such that f(u̅) =0 for some unique u̅, then there exists a dynamic control law u̇(t) = ϕ(y(t))








that steers u(t) to u̅ <cit.>.  Conversely, let us consider the case in which there are isolated singular elements in M, hence we cannot guarantee convergence to 0, but we still need to ensure state convergence.

As an example, let us consider the flow system governed  by the equations















    {   y_1 = -ϕ(u_1 - u_2) +r_1
       y_2 = ϕ(u_1 - u_2) + ψ(u_2) -r_1 +r_2,
    .


where r_1 and r_2 are references, a_min≤ a ϕ^'(u) ≤ a_max, b_min≤ b ψ^'(u) ≤ b_max. 
Next, we consider an integral control law u̇  = - k    y, with k > 0 and derive the dynamics ẏ = Jf(u)  u̇, i.e.,

    [[ ẏ_1; ẏ_2 ]]=   - k [[  -a  -a;  -a a+b ]] [[ y_1; y_2 ]] ,




which is a linear differential inclusion since a ∈ [a_min, a_max] and b ∈ [b_min, b_max].
For this system, V(y) =  y is a wLF and, in view of Corollary <ref>, the state weakly converges to the set N = {y ∈^2 | y_1 - y_2 =0}.


















§ CONCLUSION

The state convergence problem is highly relevant within the system-and-control community, since it occurs in several areas, from multi-agent learning, consensus and opinion dynamics to plant tuning. For LTI systems, state convergence can be characterized via necessary and sufficient linear matrix inequalities and Lyapunov-like conditions. 
In the presence of uncertainty, two different definitions of state convergence, i.e., strong and weak convergence, shall be considered. These two are equivalent under the kernel sharing property.
In general, while strong convergence is structurally guaranteed by the separability of the eigenvalues of the generator matrices, weak convergence is not. 
Lyapunov-like sufficient conditions for weak convergence can be established via linear matrix inequalities. Necessary and sufficient conditions for weak convergence are currently unknown.








§ PROOFS OF STATEMENTS IN SECTION <REF>




 §.§ Proof of Lemma <ref>

Let _r { z ∈ℂ| | z - (1-r) | ≤ r }, the disk of radius r>0 centered in (1-r,0). 

The system in (<ref>) is (marginally) stable if and only if the eigenvalues of A^_η are contained in the unit disk _1 and those at 1 are semi-simple. By <cit.> the eigenvalues of A are in _η and those at bdry(_η), which always containts { 1}, are semi-simple. Therefore, the system in (<ref>) is (marginally) stable and it converges.




▪




 §.§ Proof of Proposition <ref>

	(a) ⇔ (b) follows from Lemma <ref>, while (b) ⇔ (c) follows by <cit.>.
	(a) ⇔ (d) follows from the fact that A has all the eigenvalues strictly inside the unit disk and the eigenvalues in 1 are semi-simple, thus there always exists a state transformation that allows to separate stable and critical eigenvalues. 
	(c) ⇔ (e) : By the Lyapunov theorem, the system in (<ref>) is (marginally) stable if and only if
(A^_η)^⊤ P A^_η≼ P,
	which leads to inequalities (e). 

	(d) ⇒ (f): Assume that 

    T^-1 A T = 
    		[ [ A^     0; A^     I ]],

		for some Schur matrix A^;

and take P_1≻ 0 such that 
	
    (A^)^⊤ P_1 A^ -P_1+W≺ 0,

	where 
	W  (A^-I)^⊤ (A^-I) + (A^)^⊤ A^≻ 0. Then the inequality in the statement is satisfied with P and Q such that T^⊤ PT= diag (P_1,   0) and T^⊤ QT=I. 
	

	(f) ⇒ (d) :
	Let Â=U^⊤ Q^1/2AQ^-1/2U, P̂=U^⊤ Q^-1/2PQ^-1/2U, where U is an orthogonal matrix such that         
	P̂= diag( P_1,0 ),
	with P_1≻ 0. Hence, the matrix inequality in the statement can be rewritten as  
	
    Â^⊤P̂Â-P̂+ (Â^⊤ -I)(Â-I) ≼ 0  ,
        
	Letting	Â=  [
	[ Â_1     Â_3; Â_2     Â_4 ] ],
the previous inequality implies that Â_3=0, Â_4=I, so that 
	Â=  [
	[ Â_1       0; Â_2       I ] ],. 
Moreover,  
	
    P_1 ≽Â_1^⊤ P_1 Â_1+  W,

where  
Ŵ (Â_1^⊤ -I)(Â_1-I) + Â_2^⊤Â_2.
Due to the assumption on the rank of P, Ŵ is positive definite, hence A_1 is Schur and the system is convergent.

▪








 §.§ Proof of Lemma <ref>


	The proof follows by noticing that there exists a relation among the eigenvalues λ∈Λ(A) and ν∈Λ(A^_ϵ) that does not alter both geometric and algebraic multiplicities, i.e.,
	ν = (λ)/(1 + ϵλ).
	The system in (<ref>) converges if and only if all its eigenvalues have strictly negative real part and those on the imaginary axis are semi-simple and all equal to 0. Hence, there always exists ϵ > 0 small enough that maps each λ∈Λ(A) with strictly negative real part to some ν∈Λ(A^_ϵ) belonging to the open left-half plane. Therefore, by noticing that the eigenvalues of A at 0 are mapped in 0, the system in (<ref>) is stable.
	▪



 §.§ Proof of Proposition <ref>


	(a) ⇔ (b) follows from Lemma <ref>.
	(a) ⇔ (c) ⇔ (d) follows from <cit.>.
	(a) ⇔ (e) : As in Lemma <ref>, there exists a relation among the eigenvalues λ∈Λ(A) and ν∈Λ(A_τ) that does not alter both geometric and algebraic multiplicities, i.e., ν = 1 + τλ. Moreover, the eigenvectors of A_τ are respectively the same of those of A. Therefore, the eigenvalues at 0 of A are semi-simple if and only if the eigenvalues at 1 of A_τ are semi-simple.






	
	(b) ⇔ (f) : By the Lyapunov theorem, the system in (<ref>) is (marginally) stable if and only if
	(A^_ϵ)^⊤ P + P A^_ϵ≼ 0.
	Hence, by pre and post-multiplying by (I + ϵ A)^⊤ and (I + ϵ A), respectively, we obtain the inequality in (f).

(d) ⇒ (g): Assume that 

    T^-1 A T = 
    		[ [ A^     0; A^     0 ]],

		for some Hurwitz matrix A^;

and take P_1≻ 0 such that 
	
    (A^)^⊤ P_1+ P_1 A^ +W≺ 0,

	where 
	W  (A^)^⊤ A^ +( A^)^⊤ A^≻ 0. Then the inequality in the statement is satisfied with P and Q such that T^⊤ PT= diag (P_1,   0) and T^⊤ QT=I. 
	

	(g) ⇒ (d) :
	Let Â=U^⊤ Q^1/2AQ^-1/2U, P̂=U^⊤ Q^-1/2PQ^-1/2U, where U is an orthogonal matrix such that         
	P̂= diag( P_1,0 ),
	with P_1≻ 0. Hence, the matrix inequality in the statement can be rewritten as  
	
    Â^⊤P̂ +P̂Â+Â^⊤Â≼ 0  ,
        
	Letting	Â=  [
	[ Â_1     Â_3; Â_2     Â_4 ] ],
the previous inequality implies that Â_3=0, Â_4=0, so that 
	Â=  [
	[ Â_1       0; Â_2       0 ] ]. 
Moreover,  
	
    P_1 ≽Â_1^⊤ P_1 Â_1+  W,

where  
ŴÂ_1^⊤Â_1 + Â_2^⊤Â_2.
Due to the assumption on the rank of P, Ŵ is positive definite, hence A_1 is Hurwitz and the system is convergent.
▪










plain



















	


	


	


	


	


	


	


	


	


	














	



	



	


	


	







	


	




	


	


	



	


