Non-Zenoness of piecewise affine dynamical systems and affine complementarity systems with inputs

Le Quang THUAN

Department of Mathematics,Quy Nhon University,170 An Duong Vuong,Quy Nhon,Binh Dinh,Vietnam

Non-Zenoness of piecewise affine dynamical systems and affine complementarity systems with inputs

Le Quang THUAN?

Department of Mathematics,Quy Nhon University,170 An Duong Vuong,Quy Nhon,Binh Dinh,Vietnam

In the context of continuous piecewise affine dynamical systems and affine complementarity systems with inputs,we study the existence of Zeno behavior,i.e.,infinite number of mode transitions in a finite-length time interval,in this paper.The main result reveals that continuous piecewise affine dynamical systems with piecewise real-analytic inputs do not exhibit Zeno behavior.Applied the achieved result to affine complementarity systems with inputs,we also obtained a similar conclusion.A direct benefit of the main result is that one can apply smooth ordinary differential equations theory in a local manner for the analysis of continuous piecewise affine dynamical systems with inputs.

Piecewise affine systems;Zeno behavior;Hybrid systems;Affine complementarity systems

1 Introduction

Analysis,simulation and design of hybrid dynamical systems become considerably complicated when there are infinitely many mode transitions in a finite time interval.Such behavior is called Zeno behavior in the literature[1,2].To the best of our knowledge,the earliest work goes back to the eighties when references[3,4]studied Zeno behavior in the setting of piecewise analytic systems.With the increasing attention to hybrid systems,the study of Zeno behavior received considerable interest in the past few years[5–11].

In this paper,we focus on piecewise affine dynamical systems with inputs.Piecewise affine dynamical systems are a special kind of finite-dimensional,nonlinear input/state/output systems,with the distinguishing feature that the functions representing the systems differential equations and output equations are piecewise affine functions.Any piecewise affine system can be considered as a collection of finite-dimensional linear input/state/output systems,together with a partition of the product of the state space and input space intopolyhedral regions.Each of these regions is associated with one particular affine system from the collection.Depending on the region in which the state and input vector are contained at a certain time,the dynamics is governed by the affine system associated with that region.Thus,the dynamics switches if the state-input vector changes from one polyhedral region to another.Any piecewise affine systems is therefore also a hybrid system.

This note aims at providing conditions guaranteeing the absence of Zeno behavior for a class of piecewise affine dynamical systems.More specifically,we show the absence of Zeno behavior for continuous piecewise affine systems with the presence of a large class of external inputs.This result is an extension of the recent results in[12].Similar conditions were already given for various subclasses of piecewise affine systems.References[13–15]have provided such conditions for linear passive complementarity systems,[16,17]for linear complementarity systems with singleton property,[18]for conewise linear systems,[19]for well-posed bimodal piecewise linear systems,[20]for piecewise analytic systems.Conditions for presence of Zeno behavior have been addressed in[21,22]for linear relay systems.Closely related to piecewise affine dynamical systems,differential variational systems were another subclass of hybrid systems for which Zeno behavior has been studied[23,24].

The organization of the paper is as follows.In Section2,we introduce continuous piecewise affine dynamical systems with inputs and its alternative representations.This will be followed by stating and proving the main result of non-Zenoness of piecewise affine dynamical systems with inputs in Section 3.Section 4 presents some applications of what we have developed in Section 3 to affine complemenatarity systems.Finally,conclusions are addressed in Section 5.

2 Continuous piecewise affine dynamical systems

In this section we will introduce the class of continuous piecewise affine dynamical systems that will be considered in the paper.To give a precise definition,we begin by recalling the so-called piecewise affine functions and its properties.A function ψ :Rν→ R?is said to be affine if there exist a matrixF∈ R?×νand a vectorg∈ R?such that ψ(x)=Fx+gfor allx∈ Rν.It is called piecewise affine if there exists a finite family of affine functions ψi:Rν→ R?withi=1,2,...,rsuch that ψ(x) ∈ {ψ1(x),ψ2(x),...,ψr(x)}for allx∈ Rν.The affine function ψifori=1,2,...,ris called a selection function corresponding to ψ.

In this paper,we consider the dynamical systems of the form

wherex∈Rnis the state,u∈Rmis the input,andf:Rn×Rm→Rnis a continuous piecewise affine function.We call such a system continuous piecewise affine dynamical system(CPAS)with inputs.

Definition 1A solution to system(1)for the initial statex0and locally integrable inputuis understood in the sense that an absolutely continuous functionx:R→Rnsuch thatx(0)=x0and the pair(x,u)satisfies(1)for almost everywheret∈R.

Note that the representation(1)describes the system at hand in an implicit way via the component functions.Alternatively,a more explicit representation of(1)can be obtained by invoking the well-known properties of continuous piecewise affine functions.To do this,we use the notion of polyhedral subdivision which is defined as follows.A finite collection P of polyhedra in R?is a polyhedral subdivision of R?if the union of all polyhedra in P is equal to R?,each polyhedron in P is of full dimension,i.e.,?,and the intersection of any two polyhedra in P is either empty or a common proper face of both polyhedra.

Sincefis a continuous piecewise affine function on Rn×Rm,one can find a polyhedral subdivision Ξ ={Ξi|1≤i≤r}of Rn×Rmand a finite family of affine functions{fi|1≤i≤r}such thatfcoincidesfion Ξi;see for instance[25,Proposition 4.2.1].Suppose thatfi(x,u)=Aix+Biu+ei,and Ξihas the form

whereAi∈ Rn×n,Bi∈ Rn×m,ei∈ Rn,Ci∈ Rri×n,Di∈ Rri×m,anddi∈ Rri.For these notations,system(1)can be rewritten in the explicit form as follows:

In this form,the continuity of the functionfis equivalent to the validity of the following implication:

for alli,j∈{1,2,...,r}.Since a continuous piecewise affine function must be globally Lipschitz continuous(see,[25,Proposition 4.2.2]),it follows from the theory of the first-order ordinary differential equations that system(1),or equivalently system(2),must admit a unique solution for each initial statex0and locally integral inputu,which is denoted byxu(t;x0).

3 Non-Zenoness of CPASs with piecewise real-analytic inputs

It has been known that every continuous piecewise affine system is a hybrid system.In the hybrid systems literature,the occurrence of an infinite number of mode transitions within a finite time interval is called Zeno behavior.In hybrid systems literature,Zeno behavior refers to the possibility of infinitely many mode transitions in a finite time interval.The presence of Zeno behavior causes difficulties in computer simulation as well as in theoretical analysis of basic issues such as well-posedness, controllability,stabilizability,etc.It is therefore important to investigate under what conditions Zeno behavior occur.In recent years,with the increasing attention to hybrid systems,the study of Zeno behavior has received considerable interest.However,the existing theoretical results are quite limited.The lack of theoretical results has often led researchers to impose non-Zeno assumptions on hybrid systems for further analysis.Because of its importance,the non-Zenoness issue will be studied in the context of continuous piecewise affine systems with inputs.For this purpose,we first define several notions of non-Zeno behavior for continuous piecewise affine dynamical systems with inputs.

Definition 2The continuous piecewise affine system(1)is called to have

·the forward non-Zeno property with an inputuif for anyx0∈Rnandt?∈R,there exist an∈＞ 0 and an indexi∈{1,2,...,r}such that(xu(t;x0),u(t))∈Ξifor allt∈ [t?,t?+ ∈).

·the backward non-Zeno property with an inputuif for anyx0∈ Rnandt?∈ R,there exist∈＞ 0 and an indexi∈{1,2,...,r}such that(xu(t;x0),u(t))∈Ξifor allt∈ (t?? ∈,t?].

·the non-Zeno property with an inputuif it has both the forward and the backward non-Zeno property with this input.

In this paper,we restrict our consideration to the class of inputs which are piecewise real-analytic on any compact time interval.A vector-valued functionu:[a,b]→Rmis said to be real-analytic if it is a restriction of a real-analytic function defined on an open neighborhood of the interval[a,b].It is called piecewise real-analytic if there exists a finite partition of the interval[a,b]by the pointsa=t0＜t1＜...＜tk=bsuch that the restriction ofuon[ti,ti+1]is real-analytic for all 0≤i≤k?1.From now on,we will use‘piecewise real-analytic’standing for‘piecewisereal-analyticonany compact time interval’.

Note that the class of piecewise real-analytic functions is quite large.It covers the class of step functions,the class of Bohl function and piecewise Bohl functions,the class of piecewise polynomial functions,or more specially the class of real-analytic functions,etc.These classes are often used in analysis and control of dynamical systems with inputs;see for instance[26,27].

The following theorem is the main result of this paper regarding to the non-Zenoness of the continuous piecewise affine dynamical systems with inputs.It shows the absence of Zeno behavior in such a system with piecewise real-analytic inputs.

Theorem1The continuous piecewise affine dynamical system(2)has the non-Zeno property with piecewise real-analytic inputs.

ProofAssociated with system(2),we consider the reverse-time system defined as

wherexrt(t):=x(?t)andurt(t):=u(?t)for allt∈ R.It is clear that the reverse-time system(4)is also a continuous piecewise affine system.Moreover,ifuis piecewise real-analytic then so isurt.The following proposition relates the backward non-Zeno property of system(2)to the forward non-Zeno property of the associated reverse-time system(4).Its proof is straightforward and hence it is omitted.

Proposition 1The continuous piecewise affine dynamical system(2)has the backward non-Zeno property with piecewise real-analytic inputs if and only if its the associated reverse-time system(4)has the forward non-Zeno property with piecewise real-analytic inputs.

In the light of this proposition,in order to prove Theorem 1,it suffices to show that every continuous piecewise affine system of form(2)has the forward non-Zeno property with piecewise real-analytic inputs.In what follows,we will prove the latter statement.Letube a given piecewise real-analytic input,x0∈ Rnandt?∈ R.We need to prove that there exist an∈＞0 and an indexi∈{1,2,...,r}such that(xu(t;x0),u(t))∈Ξifor allt∈ [t?,t?+ ∈).To do so,first note that we only need to show for the caset?=0.The result of the general cases can be obtained by letting=xu(t?;x0),(t)=u(t+t?),and consideringand?uin the role ofx0andu,respectively.

Clearly,att?=0 one has eitheruis real-analytic oruis not real-analytic.Next,we will deal with each case of them.

Case 1This case addresses the case in whichuis real-analytic at the timet?=0.To do so,we need to introduce some nomenclature and some auxiliary results.

For an ordered tuplea=(a1,a2,...,ak),we writea≥0 ifa=0 or the first non-zero component is positive.Ifa≥0 anda≠0 then we writea＞0.Sometimes,we also use the symbols ‘≤’and ‘＜’with the obvious meanings.For a finite collection ofn-dimensional vectorsz=(z1,z2,...,zk),we writez≥ (＞)0 if for eachj∈{1,...,n}it holds thatwhere the subscriptjdenotes thejth component of the corresponding vector.The same notations are also used for infinite sequences.

For a vector-valued functionwwhich is infinitely differentiable att=0,we denotewkthekth derivative ofwatt=0,i.e.,wk=w(k)(0)and denotewk=col(w0,w1,...,wk).Also for eachi∈{1,2,...,r}we define the set

Finally,for agiven matrixMthe notation rowl(M)stands for thelth-row ofM.

For each inputwreal-analytic att=0,we will use the sets Yi,wto characterize the forward non-Zeno property of system(2)at timet=0 with this input.For this purpose,we first state the following lemma that relates the sets Ξi,Yi,w,and the behavior of solutions.

Lemma 1For each inputwreal-analytic att=0,the following statements are equivalent:

1)The statex0belongs to Yi,w.

2)There exists an∈＞0 such that(xw(t;x0),w(t))∈Ξifor allt∈ [0,∈].

Proof1)?2):Let?xw(t;x0)denote the solution to equation˙x(t)=Aix(t)+Biw(t)+eifor the initial statex0and the inputw,and let denote?yw(t;x0):=Ci?xw(t;x0)+Diw(t)+di.It can be seen that?yw(t;x0)is real-analytic att=0,and moreover at this point one has

for allk≥ 1 wherey(?),w(0;x0)denotes the ?th-derivative ofw(t;x0)att=0.Sincex0∈Yi,w,i.e.,

for allk≥1,we obtain that for eachl∈{1,2,...,ri}only one of the following two cases is possible:

i)The first case is that rowl0.Then,the analyticity of?yw(t;x0))att=0 guarantees the existence of an∈l＞0 such that rowl(?yw(t;x0))=0 for allt∈ [0,∈l].

ii)The second case is that

In this case,we first consider the case where the first element is positive,i.e.,rowlThen,due to continuity there exists∈l＞ 0 such that rowlfor allt∈[0,∈l].Now,suppose that rowlThen,it follows from(5)that there existskl≥1 such that rowlall 1≤j≤kl?1 and rowlSincethere exists∈l＞0 such that0 for allt∈[0,∈l]due to conti-This means that the functionstrictly increases on[0,∈l].Hence,

for allt∈ [0,∈l].By repeating this argument,we finally obtain

Finally,we can conclude that there exists∈l＞ 0 such thatfor allt∈[0,∈l]for both cases.Define∈:=Then,we havefor allt∈[0,∈]and hencefor allt∈[0,ε].This implies thatis a solution on the interval[0,∈]of system(1)for the initial statex0and inputw.Due to the uniqueness of solution,we havefor allt∈ [0,∈],and hence,

for allt∈ [0,∈].Letbe the solution to system(7)for the initial statex0and the inputw.Then,we havefor allt∈ [0,∈]andis real-analytic att=0 due to the real-analyticity ofwat this point.Thus,this solution can be expressed in convergent Taylor series aroundt=0 as

for allt≥0 sufficiently small.In views of(6)and(8)together with noticing thatobtain

for allt≥0 sufficiently small.It is easy to see that this inequality implies

for allk≥1,and hencex0∈Yi,w.

The following lemma characterizes for the forward non-Zeno property of a system of form(2)with piecewise real-analytic inputs at every analytic point of inputs in terms of the sets Yi,·,1 ≤i≤r.

Lemma 2Letwbe real-analytic at timet=0.Then,the following statements are equivalent:

1)The system(2)has the forward non-Zeno property with the inputwat timet=0,i.e.,for anyx0∈Rnthere exist∈＞ 0 and an indexisuch that

2)The following equality holds

ProofIf the first statement holds,then for anyx0∈Rnthere exist∈＞0 and an indexi∈{1,2,...,r}such that(xu(t;x0),w(t))∈ Ξifor allt∈ [0,∈].Due to Lemma 1,we obtainx0∈Yi,wand henceSince the reverse inclusion is evident,the second statement holds.

Note that the converse implication is obvious.

In general,a given vector in Rn×Rmmay be contained in more than one of the sets Ξi.We define for each(x0,y0)of Rn×Rmthe setI(x0,y0)as

The following lemma is the last auxiliary result that will be used in the proof of Theorem 1.Its proof was presented in[12].

Lemma 3[12] Let(x0,y0)∈Rn×Rmbe given.For any polynomialpintwith its coeficients are in Rn×Rmandp(0)=(x0,y0),there existi∈I(x0,y0)and∈＞0 such thatp(t)∈ Ξifor allt∈ [0,∈].

With all these preparations,we are now in a position to prove that system(2)has the forward non-Zeno property at timet?=0 with the inputu.In views of Proposition 1 and Lemma 2,it is enough to show that the equalityholds.The inclusionis obvious.To prove the inverse inclusion,we take anyx0∈Rn,and denoteI0=I(x0,u0)for brevity.It follows from(3)thatAix0+Biu0+ei=Ajx0+Bju0+ejfor alli,j∈I0.Leti∈I0and definex1:=Aix0+Biu0+ei.Lemma 3 ensures that the set

isnon-empty.SinceI1?I0andAi(x0+tx1)+Bi(u0+tu1)+ei=Aj(x0+tx1)+Bj(u0+tu1)+ejforalli,j∈I1and for all sufficiently smallt＞0,one hasAix1+Biu1=Ajx1+Bju1for alli,j∈I1.Let us definex2:=Aix1+Biu1for somei∈I1.The set

is non-empty due to Lemma 3.Now,we claim thatI2?I1.Indeed,for anyi∈I2we haveCix0+Diu0+di≥0 becauseI2?I0.Moreover,if rowl(Cix0+Diu0+di)=0 for some index 1≤l≤ri,then we must have rowl(Cix1+Diu1)≥ 0.Hence,it must hold thatCi(x0+tx1)+Di(u0+tu1)+di≥0 for all sufficiently smallt＞0.Thus,it follows thati∈I1and thenAix2+Biu2=Ajx2+Bju2for alli,j∈I2.Next,we definex3:=Aix2+Biu2for somei∈I2and

Due to Lemma 3,the setI3is non-empty.By similar arguments,we can show thatI3?I2andAix3+Biu3=Ajx3+Bju3for alli,j∈I3.Continuing this process,we can construct a infinite sequence of non-empty index

SinceI0is a finite set,this sequence has to be stationary.i.e.,there is ak0such that

for all ?≥ 0.Then,for anyi∈Ik0we claim thatx0∈ Yi,u.This claim can be proved by contradiction as follows.Assume thatx0? Yi,u,there existsk?≥k0such that Going back to the construction,we can find a sequence of elementsx1,x2,...,xk?such thatfor allt∈ [0,∈)for some∈＞0,or more specifically the element for allt∈ [0,∈).This implies thatis a contradiction,and hencex0∈Yi,u.

Case 2In this case we deal with the case in whichuis not real-analytic at the timet?=0.Sinceuis piecewise real-analytic,there exists δ＞0 such thatuis analytic on[0,δ].By the definition of the real-analytic functions on a compact time interval,there exists a real-analytic functionon(α,β)containing[0,δ]such that=uon[0,δ].Applying what we have just obtained in Case 1 to the functionwe can find an∈ ∈(0,δ)and an indexisuch that((t;x0),?(t))∈ Ξifor allt∈[0,∈].Noticing that(t;x0)=xu(t;x0)andu?(t))=u(t)for allt∈[0,∈),we conclude that the system has the forward non-Zeno property att?=0 with the inputu.

To summary,in both of cases we always obtain that the system has the forward non-Zeno property with the inputuat timet?.Since the piecewise real-analytic functionuis arbitrarily taken,we conclude that the system has the forward non-Zeno property with piecewise realanalytic inputs.The proof of Theorem 1 is completed.

4 Affine complementarity systems with external inputs

In recent years,differential complementarity problems are the main investigated object of several papers for many fundamental issues;see for instance[14,16,17,27,28]and the references therein.In such issues,the issue whether or not existence of Zeno behavior has been attracted the attention of many researchers because of its importance in analysis of such systems.

In the remainder of this paper,a special class of differential complementarity problems called affine complementarity systems will be considered for Zeno property.Our main contribution on this issue is that we show that some large classes of affine complementarity systems with piecewise real-analytic inputs do not exhibit Zeno behavior.This result is established based on applying the results what we have just developed in the previous section,and based on the piecewise affine reformulation of the affine complementarity systems with singleton property.In what follows,we will present in detail this result.The proceed begins with recalling the formulation of the linear complementarity problem and then we formally introduce the so-called affine complementarity systems.

4.1 Affine complementarity systems

In mathematical programming literature, the so-called linear complementarity problem has received much attention;see for instance[29]for a survey.This problem takes as data a vectorq∈Rmand a matrixM∈Rm×m,and asks whether it is possible to find a vectorz∈Rmsuch that

As usual,the notation LCP(q,M)will be used to refer this problem,the notation SOL(q,M)is standing for the set of all its solution,and the notation

indicates the relations in(9).One of the main results on the linear complementarity problems that will be used later is as follows[29,Theorem 3.3.7]:the problem LCP(q,M)admits a unique solution for eachqif and only ifMis aP-matrix,i.e.,all its principal minors is positive;see for instance[25,29]for further detail.

An affine complementarity system,roughly speaking,is a special case of differential complementarity problems[30]which is described by standard state space equations of input/state/output affine systems together with complementarity conditions as in the linear complementarity problem(9).Every affine complementarity system is arisen in such a way that one first takes a standard input/state/output affine system and then selects a number of pairs of input and output to impose for each these pairs complementarity relation at each timet.This process results in a differential-algebraic system with inequality constraints of the form

wherex∈Rnis the state,u∈Rmis the external input(unconstrained),the inputz∈Rpand the outputw∈Rpplay the role as the complementarity variables,and all the matrices are of appropriate sizes.In particular,wheng=0 ande=0,system(10)is known as a linear complementarity system with inputs.Such a system was well-studied in[27]for well-posedness,i.e.,existence and uniqueness of solutions,with considered inputs to be bounded piecewise Bohl functions,and was recently investigated in[28]for controllability.

The results we obtain in this section can be seen as the generalizations of the results of Shen and Pang[16]from linear to affine as well as from without inputs to the appearance of external inputs.Before presenting them in detail,we motivate that there are several problems in electrical engineering,mechanical systems,economics,etc.can be modeled as systems of form(10);see for instance[27,31,32].Let us give an example of systems that may be recast into the affine complementarity systems with external inputs.

Example 1As an illustrated example,we consider the state saturation system in Fig.1(a)with the PL relation is as in Fig.1(b).

Fig.1 Cascaded systems with a PL connection.(a)Cascaded systems,and(b)the graph of PL connection.

This is an affine complementarity system given by

4.2 Non-Zenoness of affine complementarity systems with external inputs

Suppose that the class of affine complementarity systems is considered in this section having the following properties:

S1)The solution set SOL(q,F)to the problem LCP(q,F)is non-empty for allq∈Rm.

S2)EandFhave theF-singleton property in the sense that the setsESOL(q,F)andFSOL(q,F)are singleton for eachq∈Rm.

Then,due to assumption S1)and theF-singleton prop-erty of E,ESOL(Cx+Du+e,F)is known to be a continuous piecewise linear function in Cx+Du+e and hence to be continuous piecewise affine in(x,u)∈Rn×Rm.In views of this,for each initial state x0and an integrable input u,there exist a unique absolutely continuous state trajectory xu(t;x0),integrable trajectories zu(t;x0)and wu(t;x0)such that xu(0;x0)=x0and the triple

satisfies relations(10)for almost all t∈R.We call such a triple(11)solution to the affine complementarity system(10)for the initial state x0and the input u.Note that xu(t;x0)and wu(t;x0)are uniquely determined,but zu(t;x0)may not be unique for each x0and input u.

Next,we will exactly give definitions of non-Zeno behavior for system(10).In the linear complementarity systems literature,there has existed two types of non-Zenoness notions[16,17]named strong non-Zenoness and weak non-Zenoness.These notions can extend to the context of affine complementarity systems with inputs.

To formally define the so-called strong non-Zenoness concept,we introduce the fundamental triple of index sets for a given initial state x0,input u and a solution(xu(t;x0),zu(t;x0),wu(t;x0))as follows:

Definition 3The affine complementarity system(10)with an input u is called to have

·the strong forward non-Zeno property if for any initial state x0∈ Rnand t?∈R there exists∈＞ 0 and a triple of index sets(α+,β+,γ+)such that

for all t∈ (t?,t?+ ∈].

·the strong backward non-Zeno property if for any initial state x0∈Rnand t?∈R there exists∈＞ 0 and a triple of index sets(α?,β?,γ?)such that

for all t∈ [t?? ∈,t?).

·the strong non-Zeno property if it has both the strong forward and backward non-Zeno property with this input.

In contrast,to define the modes in weak non-Zenoness we consider an affine differential algebraic system characterized by a pair of disjoint index sets(θ,θc)whose union is{1,2,...,p}:

Definition 4The affine complementarity system(10)with an input u is called to have

·the weak forward non-Zeno property if for any initial state x0∈ Rn,t?∈ R and solution

there exists ∈＞ 0 and a partition(θ,θc)of the set{1,2,...,p}such that(xu(t;x0),zu(t;x0),wu(t;x0))satisfies the differential algebraic system(12)for all t∈(t?,t?+ ∈].

·the weak backward non-Zeno property if for any initial state x0∈ Rn,t?∈ R and solution

there exists ∈＞ 0 and a partition(θ,θc)of the set{1,2,...,p}such that(xu(t;x0),zu(t;x0),wu(t;x0))satisfies the differential algebraic system(12)for all t∈[t?? ∈,t?).

·the weak non-Zeno property if it has both the weak forward and backward non-Zeno property with this input.

It is clear that strong non-Zeno property implies weak non-Zeno property.In the case that the matrix F is a P-matrix,the following theorem shows the absence of strong Zeno behavior,and hence of weak Zeno behavior,in the affine complementarity system(10).

Theorem 2If F is a P-matrix then the affine complementarity system(10)has the strong non-Zeno property with piecewise real-analytic inputs.

A proof of this theorem will be presented in the next subsection.As you will see later in that proof,the same conclusion still holds if we replace the assumption of P-matrix property of F by a more general assumption that the linear complement problem LCP(Cx+Du+e,F)has a unique solution for all x∈Rnand u∈Rm.

When the problem LCP(Cx+Du+e,F)does not have unique solution for some x∈Rnand u∈Rm,assumptions S1)and S2)do not guarantee for the absence of strong Zeno behaviors.The following is an illustrated example in which assumptions S1)and S2)hold,but strong non-Zenoness fails,which is taken from[16]:

Example 2Consider the linear complementarity system as

whereA∈Rn×n,b,c∈Rnwithn≥ 2,andfis a nonzerom-vector.This system is of form(10)withu(t)=0 for allt.

However,assumptions S1)and S2)do guarantee for the absence of weak Zeno behavior.This will be shown in the theorem below.

Theorem 3Under assumptions S1)and S2),the affine complementarity system(10)has the weak non-Zeno property with piecewise real-analytic inputs.

In the next two subsections below,we will present the proofs of Theorems 2 and 3.

4.3 Proof of Theorem 2

The proof of this theorem is accomplished in three steps.In the first one we reformulate the affine complementarity system(10)in terms of in put/state/output continuous piecewise affine system with the pair of complementarity variablesz,wplaying the role of non-negative outputs.In the second step we derive an auxiliary result related to sign partitions of components of the outputs in an input/state/output affine system.Finally,we apply this auxiliary result together with Theorem 1 to the system obtained in the first step to finalize the proof.

Before proceeding the plan,we need to introduce some more notations.For a matrixQ∈ Rn×m,QTstands for its transpose,Q?1stands for its inverse if this exists,imQrefers to its image,i.e.,the set{Qx|x∈Rm}.We writeQijfor the(i,j)th element ofQ.For α ? {1,2,...,n}and β ? {1,2,...,m},Qαβdenotes the submatrix(Qjk)i∈α,j∈β.If α ={1,2,...,n},we writeQ·βstanding forQαβ.The notationQα·is also defined in a similar way.

We are now ready to present the proof.SinceFis aP-matrix,the problem LCP(Cx+Du+e,F)has a unique solution for eachx∈Rnandu∈Rm.Thus,due to(10b)and(10c),for eachtthere exists an index set θt? {1,2,...,p}such that

where θctdenotes the complementary of θtin{1,2,...,p}.Note that θtis an arbitrary subset of the set{1,2,...,p},so that there are 2pdifferent sets θt,says θ1,θ2,...,θ2p.

For a subset θ of{1,2,...,p},we denote Πθthe permutation matrix of orderp×pwith Πθ(y)=col(yθ,yθc),and define

Corresponding to each index set θi,we construct a polyhedron Ξθiof Rn× Rmin such a way that

for alli=1,2,...,2pand for alltsuch that θi= θt.Due to this equality and the fact thatFis aP-matrix,we can verify that Σ ={Ξθ1,...,Ξθ2p}forms a polyhedral subdivision of Rn×Rm.Moreover,subsystem(10a)can be rewritten as a continuous piecewise affine system of the form

It also can be seen from(13)thatzandware nonnegative and piecewise affine as

whenever(x(t),u(t))∈ Ξθi.Therefore,system(10)is reformulated as the system concluding(14),(15)and(16).To obtain a further analysis of the sign of the components ofzandw,we derive the following auxiliary lemma.

Lemma4Consider the input/state/output affine system

Letxandube real-analytic on[0,∈]such that on this time interval they satisfy(17a)and(17b)andy(t)≥0.Then,there exist an δ＞0 and an index set of components of the outputysuch thatyθ(t)＞ 0 andyθc(t)=0 for allt∈ (0,δ].

ProofAs assumed,xis the solution to system(17a)for the initial statex0and the inputuon[0,∈].Due to the uniqueness of solutions to system(17a),we can see that the outputydoes not change the values on[0,∈]if we replaceuby its a real-analytic extension?uon an open neighborhood of[0,∈],and considerx?u(t;x0)on[0,∈]in stead ofx.Thus,if we can prove that the desired conclusion holds whenxanduare real-analytic at the timet=0,then we are done.Note that the later assumption implies that the outputyis real-analytic att=0.Therefore,in principle,by checking the sign of the derivatives of the rows ofy(t)at timet=0 we can form the index set θ and find a δ ＞ 0 as we claimed.

With this lemma,we can finalize the proof of Theorem 2.Let us first prove for the strong forward non-Zeno property.Letube a piecewise real-analytic input,x0∈ Rnandt?∈ R.Without loss of generality,we can assume thatt?=0.Note that the solutionsxu(t;x0),zu(t;x0)andwu(t;x0)of system(10)is unique,and they satisfy(14),(15)and(16).By Theorem 1,system(14)has the forward non-Zeno property with piecewise real-analytic inputs.Thus,there exist an∈＞0 and an indexisuch thatxu(t;x0)andu(t)are real-analytic and satisfy

on the closed time interval[0,∈].Automatically,zu(t;x0)≥0 andwu(t;x0)≥ 0 and they satisfy(15)and(16)on[0,∈]with θi,respectively.Now,using Lemma 4,we can find δ ＞ 0 and a triple of index sets(α+,β+,γ+)such that

for allt∈ (0,δ],i.e.,system(10)has the strong forward non-Zeno property.

By a similar argument,we also can prove that system(10)has the strong backward non-Zeno property,and hence system(10)has the strong non-Zeno property with piecewise real-analytic inputs.

4.4 Proof of Theorem 3

We begin with a technical lemma which will be employed later on.This can be seen as a generalization of Lemma 3.

Lemma 5Let Σ ={Σ1,Σ2,...,Σν}be a polyhedral subdivision of Rn×Rm.

2)For any two functionsx:R→Rnandu:R→Rmwhich are real-analytic on[0,δ],there exist an ∈∈ (0,δ)and an ?∈I(x(0),u(0))such thatp(t):=(x(t),u(t))∈ Σ?for allt∈ [0,∈].

ProofNote that one can identity the product space Rn×Rmwith Rn+m.Thus,the first statement follows from[12,Lemma 4.4].

For the second statement,we observe that the conclusion does not change if we replacexanduby analytically extension on an open neighborhood of[0,δ].Thus,without loss of generality we can assume thatxanduare real-analytic att=0.Ifx(t)=0 andu(t)=0 for allt∈ [0,∈],then the conclusion is trivial.Therefore,we consider for the case this does not hold.We prove this statement by contradiction.We assume that the claim does not hold.Then,for eachi∈I(x(0),u(0)),one of the following statements holds:

a)There exists∈＞ 0such thatp(t)? Σifor allt∈ (0,∈).

b)There exists an infinite sequence of positive scalarstkall distinct and converging to 0 ask→∞such thatx(t2k?1)∈ Σiandp(t2k)? Σifor allk≥ 1.

Note that the latter statement must hold for at least one indexi∈I(x(0),u(0)).Otherwise,there would exist a positive numberˉ∈such that

for allt∈(0,ˉ∈).However,the set on the right hand side contains a neigh bourhoodUof(x(0),u(0))due to the first statement of Lemma 3.This leads to a contradiction sincep(t)belongs toUfor all sufficiently smallt＞0 due to continuity.

Since b)holds for somei∈I(x(0),u(0)),for everyk≥ 1 there exists an index ?k∈ {1,...,mi}such that

Denote Λ ={?k|k≥ 1}.Then,note that Λ is a finite set,there exists an index ??∈ Λ such that

for infinitely manyk’s.Without loss of generality,we may assume that

for allk≥1.Then,for everyk≥1,due to(18)and the fact that row??(Cix(t2k?1)+Diu(t2k?1)+di)≥ 0,there exists μk∈ [t2k?1,t2k)such that

Since the μk’s are all distinct and row??(Cix(t)+Diu(t)+di)is a non-zero real-analytic function intwith real coefficients with finitely many roots on a finite time interval,we obtain row??(Cix(t)+Diu(t)+di)=0 for allt.This is contradiction with(18)and hence the second statement holds.

Proof of Theorem 3To prove this theorem,we first also reformulate the affine complementarity system(10)in terms of continuous piecewise affine systems.Due to S1)and S2),it is known thatESOL(Cx+Du+e,F)is continuous piecewise linear inCx+Du+e,and hence it is continuous piecewise affine in(x,u)onRn×Rm.Thus,one can find a polyhedral subdivision Σ ={Σ1,...,Σr}of Rn×Rmand the matricesPi,Qi,hi,1≤i≤r,such that

whenever(x,u)∈ Σi.Because of this,subsystem(10a)can be reformulated as a continuous piecewise affine system with the polyhedral subdivision Σ,

whenever(x,u)∈Δi.In views of this,win(10b)can be rewritten as

Now,letube a piecewise real-analytic input,x0∈Rnandt?∈ R.Then,the state solutionxu(t;x0)is also the solution to system(19)for the initialx0and the inputu.By Theorem 1,there exist∈1＞ 0 and an indexisuch that the pairxu(t;x0),u(t)satisfies(19)for allt∈ [t?,t?+ ∈1].By Lemma 5,we can find δ ＞ 0 such thatfor allt∈ [0,δ].Thus,we have

for allt∈ (0,∈].This means system(10)has the forward weak non-Zeno property with piecewise real-analytic inputs.

By a similar argument,we can prove that the system has the weak backward non-Zeno property,hence the weak non-Zeno property at timet?.The proof is completed.

5 Conclusions

In this paper,we proved that continuous piecewise affine dynamical systems with piecewise real-analytic inputs do not exhibit Zeno behavior.This is a generalization of recent results of the paper[12].Using the result which had just obtained,we also proved that some classes of affine complementarity systems with piecewise real-analytic inputs do not have Zeno behavior.The absence of Zeno behavior considerably simplifies the analysis of piecewise affine dynamical systems.This opens new possibilities in studying fundamental system theoretic problems like controllability and observability for these systems.Also the ideas employed in this note are akin to be extended for possibly discontinuous but well-posed(in the sense of existence and uniqueness of solutions)piecewise affine dynamical systems with inputs.

[1]J.Zhang,K.H.Johansson,J.Lygeros,et al.Zeno hybrid systems.International Journal of Robust and Nonlinear Control,2001,11(5):435–451.

[2]K.H.Johansson,M.Egersted,J.Lygeros,et al.On the regularization of Zeno hybrid automata.Systems&Control Letters,1999,38(3):141–150.

[3]P.Brunovsky.Regular synthesis for the linear quadratic optimal control problem with linear control constraints.Journal of Differential Equations,1980,38(3):344–360.

[4]H.J.Sussman.Bounds on the number of switchings for trajectories of piecewise analytic vector fields.Journal of Differential Equations,1982,43(3):399–418.

[5]A.Lamperski,A.D.Ames.Lyapunov-like conditions for the existence of Zeno behavior in hybrid and Lagrangian hybrid systems.Proceedings of the 46th IEEE Conference on Decision and Control.New Orleans:IEEE,2007:115–120.

[6]A.D.Ames,A.Abate,S.S.Sastry.Sufficient conditions for the existence of Zeno behavior in a class of nonlinear hybrid systems via constant approximations.Proceedings of the 46th IEEE Conference on Decision and Control.New Orleans:IEEE,2007:4033–4038.

[7]A.D.Ames,H.Zhang,R.D.Gregg,et al.Is there life after Zeno?Taking executions past the breaking(Zeno)point.Proceedings of the American Control Conference.Minneapolis:IEEE,2006:2652–2657.

[8]A.D.Ames,P.Tabuada,S.S.Sastry.On the Stability of Zeno Equilibria.Lecture Notes in Computer Science.Berlin:Springer-Verlag,2006:34–48.

[9]A.D.Ames,S.S.Sastry.Characterization of Zeno behavior in hybrid systems using homological methods.Proceedings of American Control Conference.Portland:IEEE,2005:1160–1165.

[10]R.Goebel,A.R.Teel.Lyapunov characterization of Zeno behavior in hybrid systems.Proceedings of the 47th IEEE Conference on Decision and Control.Cancun,Mexico:IEEE,2008:2752–2757.

[11]S.N.Simic,K.H.Johansson,J.Lygeros,et al.Towards a geometric theory of hybrid systems.Dynamics of Discrete,Continuous and Impulsive Systems,2005,12(5/6):649–687.

[12]L.Q.Thuan,M.K.Camlibel.Continuous piecewise affine dynamicalsystems do notexhibit Zeno behavior.IEEE Transactions on Automatic Control,2011,56(8):1932–1936.

[13]M.K.Camlibel,J.M.Schumacher.On the Zeno behavior of linear complementarity systems.Proceedings of the 40th IEEE Conference on Decision and Control.Orlando:IEEE,2001:346–351.

[14]M.K.Camlibel,W.P.M.H.Heemels,J.M.Schumacher.On linear passive complementarity systems.European Journal of Control,2002,8(3):220–237.

[15]W.P.M.H.Heemels,M.K.Camlibel,J.M.Schumacher.On the dynamic analysis of piecewise linear networks.IEEE Transactions on Circuits and Systems–I,2002,49(3):315–327.

[16]J.Shen,J.Pang.Linear complementarity systems with singleton properties:non-Zenoness.Proceedings of the American Control Conference.New York:IEEE,2007:2769–2774.

[17]J.Shen,J.Pang.Linear complementarity systems:Zeno states.SIAM Journal on Control and Optimization,2005,44(3):1040–1066.

[18]M.K.Camlibel,J.S.Pang,J.Shen.Conewise linear systems:non-Zenoness and observability.SIAM Journal on Control and Optimization,2006,45(5):1769–1800.

[19]M.K.Camlibel.Well-posed bimodal piecewise linear systems do not exhibit Zeno behavior.Proceedings of 17th IFAC World Congress on Automatic Control.Seoul:IFAC,2008:7973–7978.

[20]J.Shen.Robust non-Zenoness of piecewise analytic systems with applications to complementarity systems.Proceedings of the American Control Conference.Baltimore:IEEE,2010:148–153.

[21]A.Y.Pogromsky,W.P.M.H.Heemels,H.Nijmeijer.On solution concepts and well-posedness of linear relay systems.Automatica,2003,39(12):2139–2147.

[22]J.M.Schumacher.Time-scaling symmetry and Zeno solutions.Automatica,2009,45(5):1237–1242.

[23]J.Pang,J.Shen.Strongly regular differential variational systems.IEEE Transactions on Automatic Control,2007,52(15):1367–1386.

[24]L.Han,J.Pang.Non-Zenoness of a class of differential quasi-variational inequalities.Mathematical Programming,2010,121(1):171–199.

[25]F.Facchinei,J.Pang.Finite Dimensional Variational Inequalities and Complementarity Problems.New York:Springer-Verlag,2002.

[26]K.A.Grasse,H.J.Sussmann.Global controllability by nice controls.Nonlinear Controllability and Optimal Control.New York:Marcel-Dekker,1990:33–79.

[27]M.K.Camlibel.Complementarity Methods in the Analysis of Piecewise Linear Dynamical Systems.Ph.D.thesis.The Netherlands:Tilburg University,2001.

[28]M.K.Camlibel.Popov-belevitch-hautus type controllability tests for linear complementarity systems.Systems&Control Letters,2007,56(5):381–387.

[29]R.W.Cottle,J.Pang,R.E.Stone.The Linear Complementarity Problem.Boston:The Academic Press,1992.

[30]J.Pang,D.E.Stewart.Differential variational inequalities.Mathematical Progamming,2008,113(2):345–424.

[31]L.Han,A.Tiwari,M.K.Camlibel,et al.Convergence of time stepping schemes for passive and extended linear complementarity systems.SIAM Journal on Numerical Analysis,2009,47(5):3768–3796.

[32]R.Frasca,M.K.Camlibel,I.C.Goknar,et al.Linear passive networks with ideal switches:consistent initial conditions and state discontinuities.IEEE Transactions on Circuits and Systems,2010,57(12):3138–3151.

17 May 2013;revised 20 November 2013;accepted 21 November 2013

DOI10.1007/s11768-014-0074-5

?Corresponding author.

E-mail:lethuan2004@yahoo.com.

Le Quang THUANwas born in Binh Dinh,Vietnam,in 1980.He received his B.S.and M.S.degrees in Mathematics from Quy Nhon University,Vietnam,in 2002 and 2005,respectively.Since 2002,he has served as a lecturer at the Mathematics Department of the Quy Nhon University.In 2008,he joined the Systems,Control and Applied Analysis Group,the Department of Mathematics,the University of Groningen,The Netherlands,where he received his Ph.D.degree in 2013.E-mail:lethuan2004@yahoo.com.