Introducing Linear Matrix Inequalities in a Control Course

INTRODUCING LINEAR MATRIX INEQUALITIES IN A CONTROL COURSE T. Alamo†∗Julio E. Normey-Rico ∗∗ M.R. Arahal ∗ D. Limon ∗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 {alamo,arahal,limon,eduardo}@cartuja.us.es ∗∗Federal University of Santa Catarina, Brazil, [email protected] Abstract: The important role that linear matrix inequalities have attained in the last years makes it compulsory to include them in the education of a control engineer. As the development of efficient semidefinite programming algorithms date from the early nineties, there is a lack of teaching experience in this field (at least when it is compared with other well established aspects of control theory). This paper proposes a simple way to introduce linear matrix inequalities in a control course. The main objective of the paper is to show that in the formulation of (robust) control problems as linear matrix inequalities a very reduced number of elementary technical results are required. It is illustrated how to introduce, in a progressive way, these technical results along with motivating examples. All of this is done in such a way that it facilitates the assimilation of this important subject. The presented methodology has been successfully applied for more than four years in a doctoral course on control theory. Copyright c 2006 IFAC Keywords: LMI, Control Theory, Robustness, Teaching innovation in Control 1. INTRODUCTION A great variety of control problems can be formulated in a natural way using Linear Matrix Inequalities (LMIs). From an historical point of view, the most remarkable example can be found in the seminal work of Lyapunov who, in 1890, showed that the stability of the linear system ˙x=Ax is equivalent to the existence ?†Corresponding author The authors acknowledge MCYT-Spain for funding this work (DPI 2005-04568). Partially supported by CAPES-BRAZIL. We thank also the suggestions to improve the paper of several anonymous reviewers. of a positive definite matrix Psatisfying the LMI: A>P+PA <0. Some stability criteria for systems with actuator nonlinearities that appeared in the 1940’s and 1950’s had a natural LMI interpretation. However, at that time, the benefits of formulating a problem in LMI form where very limited: there where no powerful computers nor efficient algorithms to solve the related semidefinite programming problem. This problem was partially circumvented by some researches by reducing the solution of the LMIs to simple graphical criteria like the Popov criterion and the Circle criterion. The use of LMIs in the control context was seriously compromised due to the lack of efficient algorithms during most of the twentieth century. This situation changed dramatically with the appearance of a new generation of interior points algorithms that allowed to solve problems formulated in LMI form in a very efficient way (Nesterov and Nemirovskii, 1994). As a result of this major breakthrough, the control community started to reinterpret previous analysis and synthesis results from the LMI point of view. Moreover, a great number of new results were obtained using the LMI framework. The publication in 1994 of the book "Linear Matrix Inequalities in System and Control Theory" (Boyd et al., 1994) and the appearance of the LMI Control Toolbox for use with Matlab (Gahinet et al., 1995) accelerated this process. Nowadays the use of LMIs is ubiquitous in many control fields and there exists many efficient polynomial-time solvers like SeDuMi, SDPT3, etc. Moreover, there exists some parsers, like the free-distribution YALMIP, that serve as interface between the LMI formulation and different solvers. The important role that linear matrix inequalities have attained makes mandatory to include them in the education of a control engineer. This paper proposes a simple way to introduce linear matrix inequalities in a control course. As there is no much teaching experience in this field we believe that this paper is of potential interest to the control education community. The main objective of the paper is to show that in the formulation of (robust) control problems as linear matrix inequalities a very reduced number of elementary technical results are required. It is illustrated how to introduce, in a progressive way, these technical results along with motivating examples. In this way a simple and clear introduction to this important subject is given to the students. The presented methodology has been successfully applied for more than four years in a doctoral course on control theory. The paper is organized as follows: in section 2, the basic technical results required to manipulate linear matrix inequalities are introduced. Some examples concerning the formulation of analysis problems as LMIs are introduced in section 3. A systematic strategy to address synthesis problems is presented in section 4. In section 5 it is shown the relevant role that plays the Schur complement. Some hints on formulating robust problems are presented in section 6. The paper draws to a close with a section of conclusions. 2. PRELIMINARY NOTIONS ON LINEAR MATRIX INEQUALITIES In this section the main technical results required to introduce the linear matrix inequalities in a control course are summarized. The following property, whose proof can be found in any text book on linear algebra, states important properties of a symmetric matrix. Property 1. (i) The inverse of a non singular symmetric matrix is symmetric. (ii) The eigenvalues of a symmetric real matrix are real. (iii) Given a symmetric real matrix H∈IRn×n, x>Hx >0, for every x6=0 if and only if all the eigenvalues of Hare strictly greater than zero. Definition 1. A symmetric real matrix His said to be positive definite if all its eigenvalues are strictly greater than zero. Analogously, a symmetric real matrix His said to be negative definite if all its eigenvalues are strictly smaller than zero. Notation 1. Given symmetric matrices Hand G, the notation H>Gmeans that H−Gis positive definite. Analogously, H<Gdenotes that H−Gis negative definite. From property 1 and the previous notation results the following property: Property 2. Given a symmetric matrix H,x>Hx >0, for every x6=0 if and only if H>0. Analogously, x>Hx <0, for every x6=0 if and only if H<0. As it will be shown in this paper, the following two properties (Boyd et al., 1994) are very useful when manipulating matrix inequalities in the context of control theory. Property 3. Given a non singular matrix T:H>0 if and only if T>HT >0. Analogously, H<0 if and only if T>HT <0 Property 4. [Schur complement] The following matrix inequalities : H>0 T−S>H−1S>0 are satisfied if and only if T S> S H >0 The notion of linear matrix inequality is precisely given in the following definition: Definition 2. Given the matrix variables X1,X2, ..., Xm, and the matrix function H(X1,X2,...,Xm)we say that the matrix inequality H(X1,X2,...,Xm)>0 (or analogously H(X1,X2,...,Xm)<0) is a linear matrix inequality (LMI) on the decision variables X1, X2, ..., Xmif H(X1,X2,...,Xm)is a symmetric matrix for every X1,X2, ..., Xmand the dependence of H(X1,X2,...,Xm)with respect to X1,X2, ..., Xmis affine. Note that decision variables X1,X2, ..., Xmare matrices that can be symmetric or not. For example, suppose that X1=Wis assumed to be symmetric and X2= Yand X3=Zare square matrices of appropriate dimension, then the following inequalities are linear matrix inequalities on the decision variables W=W>, Yand Z: W>0 I−W+BY +Y>B><0 W BY +CZ Y>B>+Z>C>W>0 On the other hand, the following examples are not linear matrix inequalities on the decision variables W=W>and Y: •BY >0 is not an LMI because BY is not symmetric for every Y. •W+Y>W+WY <0 is not an LMI because the dependence with respect to Wand Yis not affine. The most important feature of linear matrix inequalities is that they impose convex constraints on the decision variables. That is, suppose the following set of p linear matrix inequalities on the decision variables X1, X2,...,Xm: Hi(X1,X2,...,Xm)<0,i=1,...,p Then the set of matrices X1,X2,...,Xmthat simultaneously satisfy all the linear matrix inequalities is a convex set. This stems from the fact that the inequalities Hi(X1,X2,...,Xm)<0, i=1,...,pcan be rewritten as max(Hi(X1,X2,...,Xm)) <0, i=1,...,pwhere max(·)stands for greatest eigenvalue. As max(·)is a convex function in the space of symmetric matrices and Hi(X1,X2,...,Xm)is an affine function of X1,X2, ..., Xmit is inferred that each LMI impose a convex constraint on the decision variables. The recently appeared efficient interior points algorithms (Nesterov and Nemirovskii, 1994) take advantage of the aforementioned convexity to obtain (if possible) a feasible solution for a given sets of LMIs. That is, if there exists X1,X2,...,Xmsatisfying simultaneously all the LMIs, the interior points algorithm finds a solution with an affordable computational time. As it will be shown in the following sections, a considerable number of analysis and synthesis control problems can be rewritten as LMIs on a given set of matrix decision variables (normally parameters of the controller or matrices defining a given quadratic Lyapunov function). Once the control problem has been formulated in LMI form, a feasible solution to the problem can be obtained using specialized optimization packages (for example, the LMI Control Toolbox for Matlab (Gahinet et al., 1995)). 3. FORMULATING SIMPLE ANALYSIS CONTROL PROBLEMS AS LMIS In this section it is shown how to use the LMI framework to solve some analysis control problems. This is done by means of two illustrative examples that introduce in a progressive way the some technical results required to manipulate LMIs. 3.1 Example 1: Stability of a continuous-time linear system Consider the quadratic function V(x) = x>Px, where Pis a positive definite matrix. From the positive definiteness of Pit results that √x>Px =pV(x)is a weighted norm that serves as a measure of the distance to the origin x=0. Given a linear continuous system of the form ˙x=Ax, a natural way of proving that the system is stable consists in proving that the distance to the origin (measured as a given weighted norm) is always decreasing. That is, the stability of the system is guaranteed if there exists P>0 such that d dt V(x) = d dt (x>Px)<0, for all x6=0. This constraint can be easily rewritten in LMI form: d dt V(x) = d dt (x>Px) =˙x>Px +x>P˙x=x>A>Px +x>PAx =x>(A>P+PA)x<0,∀x6=0 If Psatisfies the previous constraints then V(x)constitutes a Lyapunov function for the system. Taking now into account property 2 it results that d dt V(x) = x>(A>P+PA)x<0, ∀x6=0 if and only if A>P+ PA <0. Therefore, the system is stable if there exists Psatisfying the following two LMIs: A>P+PA <0 P>0 It can be shown that the existence of a matrix P satisfying the previous LMIs is not only a sufficient condition for the stability of the system but also a necessary condition. That is, if ˙x=Ax is stable then there exists P=P>>0 such that the distance to the origin (measured as √x>Px) is always decreasing. 3.2 Example 2: Stability of a discrete-time linear system Consider the system x(k+1) = Ax(k), which, for notational convenience, will be rewritten as: x+=Ax, where x+denotes the successor state corresponding to x. The same aforementioned ideas can be applied: the system is stable if the distance to the origin (measured by means of a certain weighted norm √x>Px) is always decreasing. Therefore, the system is stable if there is P>0 such that (x+)>Px+<x>Px,∀x6=0. That is, x>A>PAx −x>Px <0,∀x6=0 x>(A>PA −P)x<0,∀x6=0 which, according to property 2 is equivalent to: A>PA −P<0. Therefore, the system is stable if there exists Psuch that: P>0 A>PA −P<0 4. FROM ANALYSIS TO SYNTHESIS In this section it is presented how to formulate control synthesis problems as LMIs. First, an example that illustrates some of the difficulties encountered when formulating a synthesis problem in LMI form is given. After this, a simple strategy that allows in numerous occasions to formulate control synthesis problems as LMIs is presented. 4.1 Example: Linear control law for a continuous-time system Consider the system ˙x=Ax+Bu, where udenotes the control action. As it will be shown in what follows, the problem of obtaining a linear control law of the form u=Kx such that the closed-loop system is stable can be recast as an LMI. Consider the closed loop system: ˙x=Ax +BKx = (A+BK)x. As it was proved in subsection 3.1, the system ˙x= (A+BK)xis stable if and only if there exists P=P>>0 such that: (A+BK)>P+P(A+BK)<0 P>0(1) In this way, if matrices Pand Kare found in such a way that the previous matrix inequalities are satisfied the control law u=Kx stabilizes the system and V(x) = x>Px constitutes a Lyapunov function for the closed loop system. However, it is important to remark that the matrix inequality (A+BK)>P+P(A+BK)< 0 is not a linear matrix inequality on the decision variables Pand K. In effect, there are two non linear terms in the matrix inequality: K>B>Pand PBK. The constraint P>0 guarantees that P, and its inverse P−1are non singular. Applying property 3, and pre-multiplying and post-multiplying the inequalities given in (1) by (P−1)>=P−1and P−1respectively, the following equivalent inequalities are obtained: P−1[(A+BK)>P+P(A+BK)]P−1<0 P−1PP−1>0 This is rewritten as: P−1A>+P−1K>B>+AP−1+BKP−1<0 P−1>0 Making now the following change of variable: W= P−1and Y=KP−1the following LMIs on the decision variables Wand Yare obtained: WA>+Y>B>+AW +BY <0 W>0(2) It is then concluded that if there exists Wand Y satisfying the previous LMIs then the control law given by: u=Kx =YW −1xstabilizes the system. 4.2 Successful strategy to tackle the synthesis problem The encountered situation found in the last example is typical in synthesis problems: when trying to formulate a synthesis problem in terms of a gain matrix K and a Lyapunov function V(x) = x>Px, the obtained matrix inequalities contain generally non linear terms that depend in a bilinear way on Pand K. Fortunately, this problem can be circumvented by a simple strategy: if the non linear matrix inequality is premultiplied and post-multiplied by an appropriate matrix, the obtained matrix inequality can be recast as an LMI by the change of variable: W=P−1,Y=KP−1. The following strategy permits (when there are bilinear terms on Pand K, or there are simultaneously terms on Pand P−1) to formulate the synthesis problem as an LMI on the decision variables W=P−1and Y=PK: (i) Pre-multiply and post-multiply the matrix inequality by a symmetric non singular matrix in such a way that in the obtained matrix inequality only terms on P−1and Kare present. This can be achieved pre-multiplying and post-multiplying by an appropriate matrix that depends in an affine way on P−1. (ii) Make the change of variable: W=P−1,Y= KP−1. Normally, the obtained matrix inequality will be an LMI on the decision variables Wand Y. (iii) Obtain Wand Ysuch that the corresponding linear matrix inequalities are satisfied. (iv) Obtain Pand Kfrom the equalities: P=W−1, K=YW−1. The proposed strategy can be applied to the synthesis of state feedback controllers. If output feedback controllers are to be considered then there exists a more involved "systematic" strategy to formulate the synthesis problem in LMI form (see (Scherer et al., 1997)). 4.3 Example: Pole-placement constraint Given the system ˙x=Ax +Bu, obtain a feedback control law of the form u=Kx in such a way that the closed loop system ˙x= (A+BK)xsatisfies the following pole-placement specification: the real part of all the eigenvalues of A+BK is strictly smaller than −, where >0. Taking into account that a system ˙x=Ax is stable if and only if the real parts of the eigenvalues of Aare strictly negative, the aforementioned pole-placement design problem is equivalent to the determination of a gain matrix Ksuch that the system ˙x= (A+BK +I)xis stable. As commented before, ˙x= (A+BK +I)xis stable if and only if there is a positive definite matrix Psuch that: (A+BK +I)>P+P(A+BK +I)<0. Note that the obtained matrix inequality is not linear on the decision variables Pand K. We therefore apply the strategy proposed in the last subsection: pre and postmultiplying the inequality by P−1: P−1[(A+BK +I)>P+P(A+BK +I)]P−1<0 P−1A>+P−1K>B>+AP−1+BKP−1+2P−1<0 Making the change of variable: W=P−1,Y=KP−1it results that the pole-placement constraint is equivalent to: WA>+AW +BY +Y>B>+2W<0. As commented before, the constraint P>0 is equivalent to W>0. Therefore, if matrices Wand Yare obtained in such a way that W>0 and WA>+AW +BY + Y>B>+2W<0, the control law u=Kx =YW −1x satisfies the pole-placement constraint. More sophisticated pole-placement constraints could have been considered. See (Chilali and Gahinet, 1999). 5. SCHUR COMPLEMENT AND MORE INVOLVED SYNTHESIS PROBLEMS As it will be shown in this section by means of two synthesis problems, the Schur complement constitutes an important tool when formulating control problems as LMIs. 5.1 State feedback for linear discrete-time systems Consider now the problem of obtaining a linear state feedback u=Kx for the discrete time system: x+= Ax +Bu. The closed loop system results in x+= (A+ BK)xand, as it was shown in subsection 3.2, the closed loop system x+= (A+BK)xis stable if there exists a matrix Psuch that: P>0 (A+BK)>P(A+BK)−P<0 This can be rewritten as: P>0 P−(A+BK)>P(A+BK)>0 Using the Schur complement (see property 4) it results that the previous matrix inequalities are equivalent to the following matrix inequality: P(A+BK)> (A+BK)P−1>0 Note that the obtained matrix inequality is not an LMI because there are terms on Pand P−1. In this case, the strategy proposed in subsection 4.2 can be applied. If the matrix inequality is pre-multiplied and post-multiplied by the symmetric, non-singular matrix P−10 0 I , the following is obtained: P−10 0 I  P(A+BK)> (A+BK)P−1P−10 0 I >0 P−1P−1A>+P−1K>B> AP−1+BKP−1P−1>0 Making now the change of variable: W=P−1,Y= KP−1: W WA>+Y>B> AW +BY W >0 (3) That is, if there exists matrices Wand Ysuch that the previous LMI is satisfied then the control law u=Kx =YW −1xstabilizes the system. Moreover, it can be shown that this is an if and only if result. 5.2 Constraints on the control action Suppose a single-input system, that is, the control input u(t)is assumed to be a scalar (the generalization to multi-input systems is straightforward). Consider also an initial condition x(0)and the synthesis problem of obtaining a control law u(t) = Kx(t)such that the initial condition x(0)is driven to the origin without violating the following constraint on the control action |u(t)|=|Kx(t)|≤umax,∀t≥0. Obviously, Kshould be obtained in such a way that the closed loop is stable. This can be accomplished determining matrix P>0 and Kin such a way that d dt (x>Px)<0, ∀x6=0 (in case of a continuous-time linear system) or (x+)>Px+<x>Px,∀x6=0 (in case of a discrete-time linear system). As seen before, these inequalities can be rewritten in LMI form in the decision variables W=P−1and Y=KP−1(see LMIs (2) and (3) respectively). Suppose that x(0)>Px(0)<1. As V(x) = x>Px is forced to be a Lyapunov function, the evolution of the system starting from this initial condition is confined in the ellipsoid: {x:x>Px ≤1}. Therefore, the control constraint is satisfied if the maximum of |Kx| in the ellipsoid {x:x>Px ≤1}is smaller than umax. Making now the change of variable: z=P1 2x, the previous constraint can be rewritten as: umax >max z|KP−1 2z| s.t.z>z≤1 The solution to the previous maximization problem is z∗=±P−1 2K> √KP−1K>. Thus, the control constraint will be satisfied if: umax >|KP−1 2z∗|=√KP−1K> or equivalently: u2 max −KP−1K>>0. As Pis assumed to be positive definite, the application of the Schur complement yields: u2 max K K>P>0 Recall that in order to force V(x) = x>Px to be a Lyapunov function, an LMI on the variables W=P−1 and Y=KP−1is imposed. Therefore it is necessary to rewrite the previous matrix inequality in terms of Wand Y. For that purpose, we follow the strategy proposed in subsection 4.2: we pre and post-multiply the matrix inequality by a symmetric matrix such that the obtained inequality has only terms in P−1. That is, we pre and post-multiply by I 0 0P−1: I 0 0P−1u2 max K K>PI 0 0P−1>0 u2 max KP−1 P−1K>P−1=u2 max Y Y>W>0 (4) Note also that the constraint x(0)>Px(0)<1 is rewritten, using the Schur complement, as: 1x(0)> x(0)P−1=1x(0)> x(0)W>0 (5) Summing up, given x(0), and the system ˙x=Ax +Bu, the constrained control synthesis problem is solved if there exists Wand Ysuch that the LMIs (4), (5) and (2)are satisfied. On the other hand, given x(0), and the discrete-time system x+=Ax +Bu, the synthesis problem is solved if there exists Wand Ysuch that the LMIs (4), (5) and (3)are satisfied. 6. EXTENSIONS TO DEAL WITH UNCERTAIN PLANTS One of the most remarkable features of LMIs is that, in most cases, it is straightforward to convert a nominal analysis (or synthesis) problem into a robust one. For example, suppose that given a plant we have a family of linear systems ˙x=Aix+Biu,i=1,...,q that describe the dynamics of the system at different operating points. In this context, the following robust synthesis problem may arise: obtain matrix Ksuch that the feedback control law u=Kx stabilizes each of the qconsidered plants. This is equivalent to impose that the closed loop systems ˙x= (Ai+BiK)x,i= 1,...,qare stable. As it has been shown in section 4.1, if there exists W>0 and Ysuch that AW +WA>+ BY +Y>B>Y<0 then u=Kx =YW −1xstabilizes the system ˙x=Ax +Bu. Therefore, u=Kx =YW −1x stabilizes the qplants if: W>0 AiW+WA> i+BiY+Y>B> i<0,i=1,...,q A great variety of robust problems can be addressed by means of the LMI framework. For a much more detailed exposition, see (Boyd et al., 1994). 7. CONCLUSIONS In this paper it has been shown how to introduce the linear matrix inequalities in a control course. The main contribution was not to provide an exhaustive collection of results relating control problems and LMIs but to show that in order to pose analysis and synthesis problems as LMIs a very reduced number of technical results are required. A simple systematic strategy to address synthesis problems is presented. The student learns how to manipulate matrix inequalities by means of a sequence of relevant examples of increasing complexity. REFERENCES Boyd, S., L. E. Ghaoui, E. Feron and V. Balakrishnan (1994). Linear Matrix Inequalities in systems and control theory. Vol. 15. Studies in Applied Mathematics, SIAM. Chilali, M. and P. Gahinet (1999). Robust pole placement in LMI regions. IEEE Transactions on Automatic Control 44(12), 2257–2270. Gahinet, P., A. Nemirovski, A.J. Laub and M. Chilali (1995). LMI Control Toolbox for use with MATLAB. The Math Works Inc. Nesterov, Yu. E. and A. Nemirovskii (1994). Interiorpoint polynomial methods in convex programming. Vol. 13. Studies in Applied Mathematics, SIAM. Scherer, S., P. Gahinet and M. Chilali (1997). Multiobjective output-feedback control via lmi optimization. IEEE Transactions on Automatic Control 42(7), 896–911.