Invariants sets for a class of discrete-time lur'e Systems

INVARIANT SETS FOR A CLASS OF DISCRETE-TIME LUR’E SYSTEMS A. Cepeda †∗T. Alamo ∗E.F. Camacho ∗ ∗Departamento de Ingeniería de Sistemas y Automática, Universidad de Sevilla. Escuela Superior de Ingenieros Camino de los Descubrimientos s/n. 41092 Sevilla, SPAIN. Telephone: +34 954487347, Fax: +34 954487340 {cepeda,alamo,eduardo}@cartuja.us.es Abstract: We present a method to estimate the domain of attraction of a class of discretetime Lur’e systems. A new notion of LNL-invariance, stronger than the traditional invariance concept, is introduced. An algorithm to determinate the largest LNL-invariant set for this class of systems is proposed. Moreover, it is proven that the LNL-invariant sets provided by this algorithm are polyhedral convex sets and constitute an estimation of the domain of attraction of the non-linear system. Copyright c °2005 IFAC Keywords: Set invariance, Domain of attraction, Lur’e systems 1. INTRODUCTION The estimation of stability regions of non-linear systems is important for many fields in engineering. Regions of asymptotic stability are zones of safe operation that can avoid unnecessary operational restrictions if they are non-conservative (Chiang and Thorp, 1989; Gilbert and Tan, 1991; Blanchini, 1999). The importance of Lur’e systems in the context of control theory stems from the fact that different control schemes appearing in practical applications can be formulated using the Lur’e systems structure (Slotine and Li, 1991). In this paper, we consider Lur’e systems in which the non-linearity appearing in the feedback path has a piecewise affine nature. The stability analysis of a Lur’e system can be done, for example, by means of Popov and circle criterions (see (Vidyasagar, 1993)). A novel approach to this problem can be found in (Hu et al., 2004) where a ?†Corresponding author procedure to compute invariant ellipsoids for Lur’e systems with piecewise affine nonlinearity is given. In this paper, a new notion of invariance (LNL- invariance) is presented. Based on its geometrical properties, a simple algorithm to obtain the largest LNL-invariant set is proposed. LNL-invariance is a more conservative concept than traditional invariance, but its geometrical properties allows us to obtain a polyhedric estimation of the domain of attraction of the non-linear system. The paper is organized as follows. In section 2 the class of piecewise-affine discrete-time Lur’e systems considered is presented. In section 3 some geometrical properties are given. The new notion of LNL- invariance is introduced in section 4. This concept is extended to the one of LNL-domain of attraction in section 5. An illustrative example is given in section 6. The paper draws to a close with a section of conclusions. Copyright (c) 2005 IFAC. All rights reserved 16th Triennial World Congress, Prague, Czech Republic 91 2. PROBLEM STATEMENT Consider the following discrete-time Lur’e system: ½xk+1=Axk−Bφ(yk) yk=Fxk (1) where xk∈IRnrepresents the state vector and yk= Fxk∈IR the output of the system. The nonlinear function φ(·)is assumed to satisfy the following conditions: (i) φ(y)is piecewise-affine. (ii) φ(y)is a continuous odd function. (iii) φ(y)is concave in IR+. The following property characterizes all the functions φ(.)that satisfy previous assumptions. Property 1. (Hu et al., 2004) The piecewise-affine function φ(y)is concave in IR+if and only if it can be expressed as φ(y) =          k0yif y∈[0,b1) k1y+c1if y∈[b1,b2) . . . kNy+cNif y∈[bN,∞) ,∀y≥0 (2) where the scalars ki,i=0,...,N,bi,i=1,...,Nand ci,i=1,...,Nsatisfy: 0<b1<b2< . . . < bN k0>k1>k2> . . . > kN ci=½(k0−k1)b1if i=1 ci−1+(ki−1−ki)biif 2 ≤i≤N See figure 1 for an example of piecewise-affine concave function in IR+(N=3). c1 c2 c3 b1b2b3y φ(y) k0yk1y+c1 k2y+c2 k3y+c3 Fig. 1. An example of a piecewise-affine function φ(·) that is concave in IR+. Note that the results presented in this paper can also be applied to systems of the form: xk+1=ˆ Axk−ˆ Bˆ φ(yk) where ˆ φ(·)is an odd piecewise-affine function convex in IR+(it suffices to define φ(·) = −ˆ φ(·),A=ˆ Aand B=−ˆ B). 3. ANALYSIS OF THE NON-LINEAR FUNCTION In this section some properties of function φ(·)are presented. For that purpose the following definition is introduced. Definition 1. Given the piecewise-affine odd function: φ(y) =          k0yif y∈[0,b1) k1y+c1if y∈[b1,b2) . . . kNy+cNif y∈[bN,∞) ,∀y≥0, the odd functions φi(y),i=1,...,Nare defined as: φi(y) = ½k0yif y∈[0,di) kiy+ciif y∈[di,∞),∀y≥0,(3) where di=ci k0−ki ,i=1, . . . , N. Figure 2 depicts functions φi(·),i=1,...,3 for the function φ(·)corresponding to figure 1. c1 d1y φ(y) φ1(y) c2 d2y φ(y) φ2(y) c3 d3 y φ(y) φ3(y) Fig. 2. Three φi(·)functions related to the previous φ(·)function. The following lemma shows how function φ(·)can be expressed in terms of functions φi(·),i=1,...,N. Lemma 1. (Hu et al., 2004) Suppose that φ(·)is an odd piecewise-affine function concave in IR+. Then: φ(y) = min 1≤i≤Nφi(y),∀y>0 The previous lemma can be justified from a graphical point of view (see figure 2). It can be observed in that figure that φ(y)can be obtained from the minimum of φ1(y),φ2(y)and φ3(y). 92 4. THE LNL-INVARIANCE NOTION In this section, the concept of LNL-invariance is presented. This new notion of invariance is stronger than the classical one. However, the LNL-invariance enjoys from a number of geometrical properties that makes it possible the computation of the greatest LNL- invariance set by means of a simple algorithm. Definition 2. Consider system xk+1=Ax −Bφ(Fx) and let function φ(·)be defined as in equation (2), f(x) and fL(x)are defined as: f(x) = Ax −Bφ(Fx) fL(x) = Ax −Bk0Fx (4) The notion of LNL-invariance is introduced in the following definition: Definition 3. A set Ωis said to be LNL-invariant for system xk+1=Ax −Bφ(Fx)if x∈Ωimplies: f(x) = Ax −Bφ(Fx)∈Ω fL(x) = Ax −Bk0Fx ∈Ω This concept is stronger than simple invariance, that is, if Ωis LNL-invariant it is also invariant, but the opposite is not true. Remark 1. LNL stands for Linear and Non −Linear. Note that the new constraint fL(x)∈Ωadded to the concept of LNL-invariance is not a very strong constraint as there is a neighborhood of the origin where f(x)equals fL(x). Definition 4. We say that S0,S1,...,Skis an admissible sequence if Si∈ {1,−1},i=0,...,k. Definition 5. Given xand S∈ {1,−1}, function G(x,S) is defined as follows: G(x,S) = ½f(x)if S=1 fL(x)if S=−1 Definition 6. We say that xbelong to the LNL-domain of attraction of system xk+1=Ax −Bφ(Kx)if the recursion: xk+1=G(xk,Sk),x0=x converges to the origin for every admissible infinite sequence {S0,S1,S2,...}. 4.1 The one step function Definition 7. Given a set Ωand the system xk+1= Axk−Bφ(Fxk), where φ(·)is defined as in definition 2, the operators QNL(·),QL(·)and QLNL(·)are defined as follows: QNL(Ω) = {x:Ax −Bφ(Fx)∈Ω}. QL(Ω) = {x:Ax −Bk0Fx ∈Ω}. QLNL(Ω) = QL(Ω)\QNL(Ω). Given a convex set Ω, the one step set QNL(Ω)is not necessarily convex due to the non-linear nature of function φ(·). The non-convex nature of QNL(Ω) makes it difficult the use of operator QNL(·)in the computation of invariant sets the class of Lur’e systems under consideration. The most remarkable property of QLNL(·)is that given a convex polyhedral set Ω,QLNL(Ω)is a convex polyhedron. This fact is one of the main contributions of this paper and will be proved in this section. For that purpose, the following auxiliary operators QLNL,i(·)are defined. Definition 8. Given functions φi(·),i=1,...,N, defined as in equation (3), the operators Qi(·)i=1,...,N are defined as: QLNL,i(Ω) = QL(Ω)\{x:Ax −Bφi(Fx)∈Ω}. The following theorem states that QLNL,i(·)is a convex operator. Theorem 1. Let Ωbe a polyhedric set given by Ω= {x:Hx ¹g},QLNL,i(Ω)is a convex polyhedron that can be obtained from the equality: QLNL,i(Ω) = Pi(Ω),i=1,...,N where: Pi(Ω) = QL(Ω)\{x:H(A−BkiF)x¹g+|ciHB| }. Proof: Let us suppose that there is x∈Pi(Ω) such that x6∈ QLNL,i(Ω). In this case it results that x6∈ T{x:Ax −Bφi(Fx)∈Ω}. That is, there exists j such that denoting Hjand gjthe j-th row of H and j-th component of gjrespectively: Hj(Ax −Bφi(Fx)) >gj Using the inequality: aφi(y)≤max(ak0y,akiy− |aci|) (see lemma (2) in appendix A): Hj(Ax −Bφi(Fx)) ≤ ≤HjAx +max(−HjBk0Fx,−HjBkiFx −|HjBci|). Two different cases must be taken into account: (1) −HjBk0Fx >−HjBkiFx −|HjBci|: In this case: gj<Hj(Ax −Bφi(Fx)) ≤ ≤HjAx −HjBk0Fx =Hj(A−Bk0F)x. This contradicts the fact that H(A−Bk0F)x¹g (see the definition of Pi(Ω)). (2) −HjBk0Fx <−HjBkiFx −|HjBci| 93 In this case: gj<Hj(Ax −Bφi(Fx)) ≤ ≤HjAx −HjBk1Fx −|HjBci|. This contradicts the fact that H(A−Bk1F)x¹ g+|ciHB|(see the definition of Pi(Ω)). There is no x6∈ Qi(Ω)such that x∈Pi(Ω). This proves the first part of the claim. To conclude the proof it will be shown that QLNL,i(Ω)⊆ Pi(Ω). In effect, due to the fact that −|ciHB|¹ −HBφ(Fx): HAx −|ciHB|¹H(Ax −Bφ(Fx)) ¹g. In the following theorem it is shown that the operator QLNL(·)can be obtained from the intersection of operators QLNL,i(·),i=1,...,N. Theorem 2. Let Ωbe a convex polyhedron given by Ω={x:Hx ¹g}, then QLNL(Ω) = N \ i=1 QLNL,i(Ω) Proof: First it will be shown that QLNL(Ω)⊆ TN i=1QLNL,i(Ω). Let us suppose that x∈QLNL(Ω)and Fx ≥0. Then Ax −Bφ(Fx)∈Ω Ax −Bk0Fx ∈Ω. Note that lemma 1 guarantees that φ(Fx)≤φi(Fx)≤ k0Fx,i=1,...,N. From this, and the fact that Ωis a convex set, it can be shown that Ax −Bφi(Fx)∈Ω,i=1,...,N That is, x∈QLNL,i(Ω). To prove that TN i=1QLNL,i(Ω)⊆ QLNL(Ω)let us suppose that x∈ ∩QLNL,i(Ω)and Fx ≥ 0. Let jbe such that φj(Fx) = min(φi(Fx):i∈1,...,N). then as x∈QLNL,j(Ω), it is obtained that Ax −Bφj(Fx) = Ax −Bφ(Fx)∈Ω. Therefore, this and the fact that Ax−Bk0Fx ∈Ωleads to x∈QLNL(Ω), prove the claim. Similar analysis can be made if Fx <0. Theorem 3. Let Ωbe a convex polyhedron given by Ω={x:Hx ¹g}. Then QLNL(Ω)is a convex polyhedron that can be obtained from the following equality: QLNL(Ω) = N \ i=1 Pi(Ω). Proof: The proof stems from a direct application of theorems (1) and (2). 5. LNL-DOMAIN OF ATTRACTION In this section, it is proposed a recursion and shown it properties that allows to create an algorithm to obtain an LNL-invariant set that it is also LNL-domain of attraction. This invariant set is characterized by a convex polyhedron. Theorem 4. Denote L(F)the region of linear behaviour of system (1), that is, L(F) = {x∈IRn:|Fx|≤ b1}. Suppose that Φ∈L(F)is a convex polyhedric invariant set, with non zero volume, corresponding to the asymptotically stable system x+= (A−Bk0F)x. Denote now C0=Φand consider the following recursion: Ck+1=QLNL(Ck). Then: (1) Ckis a convex polyhedron, ∀k≥0. (2) Ckis an LNL-invariant set, ∀k≥0. (3) Ckbelongs to the LNL-domain of attraction of the system, ∀k≥0. (4) The sequence {C0,C1,...} converges to the LNL- domain of attraction of system (1). (5) The LNL-domain of attraction of system (1) is a convex set. Proof: (1) Theorem (3) states that if Ωis a convex polyhedron then QLNL(Ω)is also a convex polyhedron. This, and the fact that C0is a convex polyhedron, prove that the recursion Ck+1=QLNL(Ω)always yields convex polyhedrons. (2) As C0belongs to L(F)it results that x+=Ax − Bk0Fx =Ax −Bφ(Fx),∀x∈C0. Therefore, C0 is not only an invariant set for the linear system x+=Ax−Bk0Fx, but also for the nonlinear one: x+=Ax −Bφ(Fx). This is equivalent to say that C0is an LNL-invariant set. Let us now suppose that Ck−1is LNL-invariant, then Ck−1⊆QLNL(Ck−1) = Ck. Therefore, if x∈Ckthen Ax −Bk0Fx ∈Ck−1⊆Ckand Ax − Bφ(Fx)∈Ck−1⊆Ck. This proves the claim. (3) From the LNL-invariance of C0⊆L(F)and the asymptotically stability of the non saturated system it is inferred that C0belongs to the LNL- domain of attraction of the system. Note that if Ck−1belongs to the LNL-domain of attraction then Ck=QLNL(Ck−1)also belongs to the 94 LNL-domain of attraction. This is due to the fact that G(x,S)∈Ck−1, for all x∈Ckand for all S∈ {1,−1}. Therefore, the recursion Ck+1= QLNL(Ck)with C0=Φyields LNL-invariant sets that belong to the LNL-domain of attraction. (4) Suppose now that xbelongs to the LNL-domain of attraction of the system. As Φis an invariant set with nonzero volume, there exists psuch that the recursion xk+1=G(xk,Sk)with x0=x satisfies xp∈Φ=C0for all admissible sequence S0,S1,...,Sp. This is equivalent to say that xis included in Cp. That is, if xbelongs to the LNL- domain of attraction then there exists a finite integer psuch that xis included into the p-th LNL-invariant set provided by the algorithm. (5) This is directly inferred from the convexity of the obtained sets {C1,C2. . . , }and the fact that the sequence {C0,C1,...,} converges to the LNL- domain of attraction. The recursion presented in the previous theorem requires an invariant set of the linear system x+= (A− Bk0F)x, included in L(F). This admissible invariant set can be obtained by standard algorithms (see (Gilbert and Tan, 1991; Blanchini, 1999)). 6. NUMERICAL EXAMPLE InthissectionanLNL-invariantsetforanumerical example is obtained. We will compare this set with the one obtained using the results of (Hu and Lin, 2004). Let us consider the system x+=Ax −Bφ(Fx)with A=·1 1 0 1 ¸,B=·0.5 1¸, F= [0.6167 1.2703]. (5) and the odd function φ(·): φ(y) =    y,if y∈[0,0.5) 0.5y+0.25,if y∈[0.5,1.5) 1,if y∈[1.5,∞) y>0.(6) This function is represented in figure (3). Theorem 5 shows how to obtain a sequence of LNL- invariant sets that constitute an estimation of the domain of attraction of the nonlinear system. This sequence has been calculated for system (5) and it is shown in figure (4). In that figure, the most inner set is an invariant set of the linear system corresponding to the zone of linear behavior of the system. The LNL-domain of attraction of the system is also depicted. This is not the only method to determinate invariant sets for piecewise-affine feedback systems. In (Hu and Lin, 2004), the authors propose an algorithm to obtain 0.25 0.5y 1 1.5 φ(y) Fig. 3. φ(·)function of the example −15 −10 −5 0510 15 −8 −6 −4 −2 0 2 4 6 8 Maximal LNL−invariant set of the system x1 x2 Fig. 4. LNL-invariant set of the system ellipsoidal invariant sets for saturated feedback systems. This approach has been generalized in (Cao and Lin, 2003) to the class of Lur’e systems considered in this paper. Figure 5 shows the comparison between the ellipsoidal invariant set obtained by means of the results presented in (Hu and Lin, 2004), and the polyhedric LNL- invariant obtained by means of the algorithm proposed in this paper. 7. CONCLUSIONS In this paper we consider the problem of estimating the domain of attraction of a given class of Lur’e systems. A new notion of invariance is presented. This new notion of invariance has an interesting property: it leads to convex estimations of the domain of attraction of the nonlinear system. A simple algorithm for determining an estimation of the domain of attraction and an invariant set of the system is provided. An illustrative example is given. 95 −15 −10 −5 0510 15 −8 −6 −4 −2 0 2 4 6 8 Comparison between two invariant sets x1 x2 Fig. 5. LNL-invariant set and ellipsodial invariant set. Appendix A Lemma 2. Given an odd piecewise-affine function φ(·), convex in IR+, consider functions φi(·),i= 1,...,Ndefined as in definition (3). Then: aφi(y)≤max(ak0y,akiy−|aci|) Proof: There are two different possibilities. • |y| ≤ di: If |y| ≤ dithen φi(y) = k0yand the inequality holds. • |y|>di: In this case, φi(y) = kiy+sign(y)ci. Note that in virtue of property (1): ki<k0,ci>0 and di=ci ko−ki>0. There are now four different possibilities: ·a>0 and y>di. In this case: aφi(y) = akiy+aci<ak0y. ·a>0 and y<−di. In this case: aφi(y) = akiy−aci=akiy−|aci|. ·a<0 and y>di. In this case: aφi(y) = akiy+aci=akiy−|aci|. ·a<0 and y<−di. In this case: aφi(y) = akiy−aci<ak0y. REFERENCES Blanchini, F. (1999). Set invariance in control. Automatica 35, 1747–1767. Cao, Yong-Yan and Z. Lin (2003). Stability analysis of discrete-time systems with actuator saturation by a saturation-dependent lyapunov function. Automatica 39, 1235–1241. Chiang, H. and J.S. Thorp (1989). Stability regions of nonlinear dynamical systems: A constructive methodology. IEEE Transactions on Automatic Control 34, 1229–1241. Gilbert, E.G. and K.T. Tan (1991). Linear systems with state and control constraints: The theory and application of maximal output admissible sets. IEEE Transactions on Automatic Control 36, 1008–1020. Hu, T. and Z. Lin (2004). A general framework for absolute stability analysis of systems under a generalized sector condition. Technical report. Department of Electrical & Computer Engineering, University of Virginia. Hu, T., B. Huang and Z. Lin (2004). Absolute stability with a generalized sector condition. IEEE Transactions on Automatic Control 49, 535–548. Slotine, Jean-Jacques E. and Weiping Li (1991). Applied Nonlinear Control. Prentice-Hall International, Inc. Vidyasagar, M. (1993). Nonlinear Systems Theory. second ed.. Prentice-Hall International, Inc. 96