LMITOOL: a Package for LMI Optimization in Scilab User's Guide
Contents
1. It is easy to see how a small amount of editing can do the rest 3 2 Interactive mode lmitool can be invoked with zero or one input argument as follows 3 2 1 Syntax txt lmitool txt lmitool file where e file isa string giving the name of an existing sci file generated by 1mitool In this mode 1mitool is fully interactive Using a succession of dialogue boxes user can completely define his problem This mode is very easy to use and its operation completely self explanatory Invoking 1mitool with one argument allows the user to start off with an existing file This mode is useful for modifying existing files or when the new problem is not too much different from a problem already treated by 1mitool 3 2 2 Example Consider the following estimation problem 10 where is unknown to be estimated y is known w is a unit variance zero mean Gaussian vector Co H 1 H N V Co V 1 V N where Co denotes the convex hull and H i and V i 1 N are given matrices The objective is to find L such that the estimate amp Ly is unbiased and the worst case estimation error variance E x 2 is minimized It can be shown that this problem can be formulated as a X problem as follows minimize subject to and 1 LQ V 2 LG V i X PO 1 gt 0 i 1 N use 1mitool for this proble2. with a solver function such as function X sylvester A B C flag na ma size A nb mb size B nc mc size C if ma na mb nb nc na mc nb then error invalid dimensions XLISTF lmisolver zeros nc mc sylvester_eval X XLISTF Then to solve the problem all we need to do is to assuming A and C are defined X sylvester A B C c for the continuous problem gt X sylvester A B C d for the discrete problem 3 Function LMITOOL The purpose of LMITOOL is to automate most of the steps required before invoking 1misolver In particular it generates a sci file including the solver function and the evaluation function or at least their skeleton The solver function is used to define the initial guess and to modify optimization parameters if needed lmitool can be invoked with zero or three arguments 3 Non interactive mode lmitool can be invoked with three input arguments as follows 3 1 Syntax txt lmitool probname varlist datalist where e probname a string containing the name of the problem e xlist astring containing the names of the unknown matrices separated by commas if there are more than one e dlist astring containing the names of data matrices separated by commas if there are more than one e txt string providing information on what the user should do next In this mode 1mitool generates a file in the current
3. EE 777 ZENRLURTION FUNCTION A ttt i tiii PII EA EL EE function CLME LMI OBJI MM_estim_eval XLIST gt L X gamma XLIST C PMPCIPPPP P P gl 7 7 DEFINE LME LMI and OBJ BELOW n m size H 1 gt LME1 listO LME2 1ist O LHI1 listO LMI2zlist for i 1 size H LME1Ci zeue L Hti LME2 i XCid KCi LHIiCi Leuet n n VCI WL s LV Ci Xi LHI2Ci gamma trace XCi en LNE list lt LME1 LME2 gt LHI zlist LHI1 LMI2 OBJ gamma Figure 4 After editing we obtain Scilab Dialog Panel BRS T Name of file in which you want the solver function and the evaluation function be saved overwrites if a file with the same name exists already Zusr home DrSci 1ab HH estim sci Figure 5 A file is proposed in which the solver and evaluation functions are to be saved You can modify it if you want 16
4. K LXT where X and L are obtained from the problem of minimizing Trace Y subject to 0 Y Y 0 and mg 4 x abc si C X Di L Du BT Du DF Y Co X D L gt 0 C5 X Dz L T X To solve this problem with 1misolver we define the evaluation function function LME LMI OBJj h2hinf eval XLIST X Y L EXLIST ME list X X Y Y MI list A X B2 L A X B2 L B1 B1 X C1l L D12 B1 D11 X C1 c L D12 B1 D11 gamma 2 eye D11 D11 Y C2 X TD22 1 C2 X D22 1 X OBJ trace Y and use it as follows X init zeros A Y init zeros C2 C2 L init zeros 2 XLISTO list X init Y init L init X ISTF 1misolver XLISTO h2hinf eval X Y L XLISTFE 2 2 5 Descriptor Riccati equations In Kalman filtering for descriptor system Ex k 1 y k 1 where u and r are zero mean white Gaussian noise sequences with covariance Q and R respectively one needs to obtain the positive solution to the descriptor Riccati equation see 4 Aa k u k Ca k 1 r k APAT Q 0 P 0 0 I 0 R 0 cT 0 1 It can be shown that this problem can be formulated as a X problem as follows maximize Trace P under constraints 0 Q 0 0 R gt 0 PTET p The evaluation function is function LME LMI OBJ ric dscr eval XLIST ME P P LMI A P A Q zeros
5. corresponding to the optimal value of the minimization problem 2 2 Examples 2 21 State feedback with control saturation constraint Consider the linear system t Bu where is an n x n and an n x nu matrix There exists a stabilizing state feedback K such that for every initial condition z 0 with z 0 lt 1 the resulting control satisfies w t for all gt 0 if and only if there exist an n x n matrix Q and ann x n matrix Y satisfying the equality constraint Q Q7 0 and the inequality constraints Q 2 BY gt 0 LAS in which case one such K can be constructed as K Y Q To solve this problem using 1misolver we first need to construct the evaluation function function LME LMI OBJ sf_sat_eval XLIST Q Y XLIST 0 0 LMI list A Q Q A B Y Y B umax 2 eye Y Y Y Y Q Q eye 0 OBJ Note that OBJ indicates that the problem considered is a feasibility problem i e we are only interested in finding a set of X s that satisfy LME and LMI functions Assuming A and umax already exist in the environment we can call 1misolver and reconstruct the solution in Scilab as follows Q_init zeros A Y_init zeros B gt XLISTO list Q_init Y_init XLIST l1misolver XLISTO sf sat eval Q Y EXLIST These Scilab commands can of course be encapsulated in a Scilab function say sf_sat Then To
6. solve this problem all we need to do is type 0 Y sf_sat A B umax We call sf_sat the solver function for this problem 2 2 2 Control of jump linear systems We are given a linear system t A r t a B r t u where A is n x n and B is x ny The scalar parameter r t is a continuous time Markov process taking values in a finite set 1 N The transition probabilities of the process r are defined by a transition matrix where are the transition probability rates from the th mode to the j th Such systems referred to as jump linear systems can be used to model linear systems subject to failures We seek a state feedback control law such that the resulting closed loop system is mean square stable That is for every initial condition 0 the resulting trajectory of the closed loop system satisfies lim 4 E z t 0 The control law we look for is a mode dependent linear state feedback i e it has the form u t K r t a t K i s are ny x n matrices the unknowns of our control problem It can be shown that this problem has a solution if and only if there exist n x n matrices Q 1 Q N andn x n matrices Y 1 Y N such that 00 007 0 TrQ 1 TrQ N 0 and YAT E N ia 0 BOY i Y i BG V TQ gt 0 i 1 N j l If such matrices exist a stabilizing state feedback is given by K i Y i Q i i 1 N I
7. A C E P zeros C A R C P P E P C P OBJ trace P which can be used as follows asuming A Q and are defined and have compatible sizes note that E and A need not be square P init zeros A A gt P lmisolver XLISTO ric_dscr_eval 2 2 6 Linear programming with equality constraints Consider the following classical optimization problem T minimize er subjectto Ar b gt 0 Cxr d 0 where A and are matrices and e b and d are vectors with appropriate dimensions Here the sign gt is to be understood elementwise This problem can be formulated in LMITOOL as follows function LME LMI OBJ linprog eval XLIST x XLIST m n size A ME C x d LMI list tmp A xt b for i 1 m LMI i tmp i end OBJ e x and solved in Scilab by assuming A C e b and d and an initial guess x0 exist in the environment x lmisolver x0 linprog eval 2 2 7 Sylvester Equation The problem of finding matrix X satisfying AX XB C or AXB C where A and B are square matrices of possibly different sizes is a well known problem We refer to the first equation as the continuous Sylvester equation and the second the discrete Sylvester equation These two problems can easily be formulated as X problems as follows function LME LMI OBJ sylvester_eval XLIST X XLIST if flag c then ME A X X B C else ME A X B C end LMI OBJ
8. D SG BEDE EES 10 A423 Example Lo ee RR KE Re ded RES CARER demde ES 10 A How 1misolver works 13 B Other versions 13 Ramine Nikoukhah inria fr tPrancois Delebecque inria fr tENSTA 32 Bvd Victor 75739 Paris France Internet elghaoui ensta fr Research supported in part by DRET under contract 92017 14 1 Purpose Many problems in systems and control can be formulated as follows see 2 minimize f Xi Xy Gj Xi1 0 1 1 2 subject to ic 1 M 4 esp Hj Xi eae gt 0 1 2 99 where e X Xm are unknown real matrices referred to as the unknown matrices e f isareal linear scalar function of the entries of the unknown matrices X1 X y itis referred to as the objective function e G s are real matrices with entries which are affine functions of the entries of the unknown matrices X1 they are referred to as Linear Matrix Equality LME functions e are real symmetric matrices with entries which are affine functions of the entries of the unknown matrices X1 they are referred to as Linear Matrix Inequality LMI functions In this report the V gt 0 stands for V positive semi definite unless stated otherwise The purpose of LMITOOL is to solve problem Y in a user friendly manner in Scilab using the code SP 1 This code is intended for small and medium sized problems say up to a few hundred variables 2
9. Function 1misolver LMITOOL is built around the Scilab function 1misolver This function computes the solution Xm of prob lem given functions f and H To solve user must provide an evaluation function which evaluates f and H as a function the unknown matrices as well as an initial guess on the values of the unknown matrices User can either invoke 1misolver directly by providing the necessary information in a special format or he can use the interactive function 1mitool described in Section 3 2 1 Syntax XLISTF OPT lmisolver XLISTO EVALFUNC options where e XLISTO a list structure including matrices and or list of matrices It contains initial guess on the values of the unknown matrices In general the ith element of XLISTO is the initial guess on the value of the unknown matrix X In some cases however it is more convenient to define one or more elements of XLISTO to be lists of unknown matrices themselves This is a useful feature when the number of unknown matrices is not fixed a priori see Example of Section 2 2 2 The values of the matrices in XLISTO if compatible with the LME functions are used as intial condition for the optimization algorithm they are ignored otherwise The size and structure of XLISTO are used to set up the problem and determine the size and structure of the output XLISTF e EVALFUNC a Scilab function called evaluation function supplied by the user which eval
10. LMITOOL a Package for LMI Optimization in Scilab User s Guide R Nikoukhah Delebecque L El Ghaoui Abstract This report describes a user friendly Scilab package and in particular its two main functions 1misolver and 1mitool for solving Linear Matrix Inequalities problems This package uses Scilab function semi de an interface to the program Semidefinite Programming SP Copyright 1994 by Lieven Vandenberghe and Stephen Boyd distributed with Scilab Contents 1 Purpose 2 2 Function lmisolver 2 ANE o P Cr TIT 2 22 IXAmpeS 654465 xd dete que mdp de VR RR Be Ee dui oD dr dh dein 3 2 2 1 State feedback with control saturation constraint 3 2 2 2 Controlofjump hnearsystems cca cecer eE e o o o E y 4 2 2 3 Descriptor Lyapunovineguall i s 2 gc doo 042552 e454 oes ER Y dw us 2 224 Mixed Hs HA Control due euge reperum Guru ode dm Se emen 5 22 5 Descriptor Riccar equauons zac RR ES Ros Ge RE 6 2 2 6 Linear programming with equality constraints 2e 7 224 EMAG uses supr meruere qu Eu d eed 7 3 Function LMITOOL 9 Sl NondnieracUVe ooo ook REOR ORO Rx dee Re RUE LR RC XR RR Ge Lob ig 9 SYMAK MMC TUTTI 9 mc cons e Be ety Ss eren ree BS ee SO ie e aos Dev Ee es SERS 9 3o Inerce Xo ee ES ee a eS apy ESE OE 4 So eS 10 S241 RYO de Xd Se SSG ASE ERED te ee EES ES Oe EE ERE
11. STO list Q init Y init XLISTF lmisolver XLISTO jump sf eval Q Y XLISTF The above commands can be encapsulated in a solver function say jump s in which case we simply need to type gt Q Y jump sf A B PI to obtain the solution 2 2 3 Descriptor Lyapunov inequalities In the study of descriptor systems it is sometimes necessary to find or find out that it does not exist an n x n matrix X satisfying ETX XTE 1 AXX A f lt where E and are n x n matrices such that E is a regular pencil In this problem which clearly is a X problem the LME functions play important role The evaluation function can be written as follows Function LME LMI OBJ dscr_lyap_eval XLIST X XLIST MESE X X E LMI list A X X A eye E X OBJ and the problem can be solved by assuming E and are already defined XLISTO list zeros A XLISTF lmisolver XLISTO dscr_lyap_eval gt X XLISIF 2 2 4 Mixed Control Consider the linear system t Bou a Diou z2 Cort Dou The mixed control problem consists in finding a stabilizing feedback which yields 7 12 lt y and minimizes 15 where Ta 12 and T24 denote respectively the closed loop transfer functions from w to 21 and 25 In 3 it is shown that the solution to this problem can be expressed as
12. directory The name of this file is obtained by adding sci to the end of probname This file is the skeleton of a solver function and the corresponding evaluation function 3 1 2 Example Suppose we want to use 1mitool to solve the problem presented in Section 2 2 1 Invoking txt lmitool sf sat Q Y A B umax yields the output gt txt To solve your problem you need to 11 edit file usr home DrScilab sf_sat sci 12 load and compile your functions getf usr home DrScilab sf sat sci c 3 Define A B umax and call sf sat function Q Y 2sf sat A B umax To check the result use LME LMI OBJ sf sat eval list OQ Y and results in the creation of the file usr home curdir sf_sat sci with the following content function 0Q Y sf_sat A B umax Generated by lmitool on Tue Feb 07 10 30 35 MET 1995 bound 1e3 abstol 1e 10 nu 10 maxiters 100 reltol 1e 10 options Mbound abstol nu maxiters reltol DEFINE INITIAL GUESS BELOW Q_init Y init XLISTO list Q_init Y_init XLIST lmisolver XLISTO sf_sat_eval options Q Y XLIST FUNCTION 1 function LME LMI OBJ sf_sat_eval XLIST Q Y XLIST DEFINE LME LMI and OBJ BELOW ME LMI OBJ
13. icular the size of the unknown vector Elimination of equality constraints Making repeated calls to the evaluation function 1misolver generates canonical representation of the form minimize subject to Boyd ap Per rodean Be 20 Az b 0 where z contains the coefficients of all matrix variables This step uses extensively sparse matrices to speed up the computation and reduce memory requirement Elimination of variables Then 1misolver eliminates the redundant variables The equality constraints are eliminated by computing the null space N of A and a solution zo if any of Ax b 0 At this stage all solutions of the equality constraints are parametrized by z Nz 20 where is a vector containing independent variables The computation of N 20 is done using sparse LU functions of Scilab Once the equality constraints are eliminated the problem is reformulated as minimize cla subjectto Fo a Fi ob xu 2 0 where c is a vector and Fo Fm are symmetric matrices and x contains the independent elements in the matrix variables X4 Xy If the F s are dependent a column compression is performed Optimization Finally 1 1 makes a call to the function semi def an interface to SP 1 This phase is itself divided into a feasibility phase and a minimization phase only if the linear objective function is not empty The feasibility phase is avoided if the initial guess is f
14. iters 100 reltol 1 10 options Mbound abstol nu maxiters reltoll f dd d d d DEFINE INITIAL GUESS BELOW L_init X_init gamma_init PPP Pg XLISTOzlist L init X init gamma init XLIST lmisolver XLISTO MM_estim_eval options IL X gammal XLIST PPPPPgP Pg 7777 II I ZZEMRLURTION FUNCTIONS 7772 ti i PP PP PP PPP Pg 7777 function OBJI MM_estim_eval XLIST gt IL X gammal XLIST U PPlgF lg 7 77 1 LME LMI and OBJ BELOW LMI OBJ Figure 3 This is the skeleton of the solver function and the evaluation function generated by LMI TOOL using the names defined previously 15 VIS SSS SII A AAAS Function definitions Here is a skeleton of the functions which you shoud edit You can do the editing in this window or click on save the skeleton and edit later using your favorite editor function L X gamma MM estim H V Generated by lmitool on Wed Feb 08 09 45 01 MET 1995 Mbound 1 3 abstol 1 10 10 maxiters 100 reltol 1 10 options Mbound abstol nu maxiters reltol f d DEFINE INITIAL GUESS BELOW L_init zeros H 1 gt X init listO for i 1 size H X init i zeros HCG amp HCD end gamma_init 0 NP XLISTO list L init X init gamma init XLISTz1misolver XLISTO HM estim eval options IL X gamma XLIST PPP PP EEE
15. m we invoke it as follows gt lmitool This results is an interactive session which is partly illustrated in following figures Scilab Mdialog Panels Problem definition LMITOOL will generate for you a skeleton of the functions needed see User s Guide for details For that you need to specify 1 Mame of you problem which will be given to the solver function 2 Names of unknown matrices or list of unknown matrices 3 Names of data matrices or list of data matrices LMI problem name foo Names of unknown matrices 1 2 Names of data matrices Figure 1 This window must be edited to define problem and the of variables used 11 Alaku Da a Scilab Mdialog BRS Problem definition LMITOOL will generate for you a skeleton of the functions needed see User s Guide for details For that you need to specify 1 Mame of you problem which will be given to the solver function 2 Mames of unknown matrices or list of unknown matrices Names of data matrices or list of data matrices Names of unknown matrices Names of data matrices HN Figure 2 For the example at hand the result of the editing should look something like this 12 A How lmisolver works The function 1misolver works essentially in four steps B 1 Initial set up The sizes and structure of the initial guess are used to set up the problem and in part
16. n the above problem the data matrices are A 1 A N B 1 B N and the transition matrix IT The unknown matrices Q 7 s which are symmetric n x n matrices and Y 7 s which are n x n matrices In this case both the number of the data matrices and that of the unknown matrices are a priori unknown The above problem is obviously a X problem In this case we can let XLIST bea list of two lists one representing the Q s and the other the Y s The evaluation function required for invoking 1misolver can be constructed as follows function LME LMI OBJ jump sf eval XLIST Q Y XLIST N size A n nu size B 1 LME list LMI1 list LMI2 list tr 0 for i 1 N tr tr trace Q i i Q i Q i MI1 i Q i Y i Y i eye nu nu SUM zeros n n for j 1 N SUM SUM PI j i Q j end LMI2 i 1 1 1 1 1 1 1 1 5 end MI list LMI1 LMI2 ME N 1 tr 1 OBJ Note that LMT is also a list of lists containing the values of the LMI matrices This is just a matter of convenience Now we can solve the problem in Scilab as follows assuming lists A and B and matrix PI have already been defined First we should initialize and Y gt N size A n nu size B 1 Q init list Y init list for i 1 N init i zeros n n Y init i zeros nu n end Then we can use 1misolver as follows gt XLI
17. ound to be feasible The function semidef is called with the optimization parameters abstol nu maxiters reltol The parameter M is set above the value Mbnd max sum abs FO Fm For details about the optimization phase and the meaning of the above optimization parameters see manual page for semidef Other versions LMITOOL is also available on Matlab The Matlab version can be obtained by anonymous ftp from tp ensta fr under pub elghaoui lmitool 13 References 1 Vandenberghe L and S Boyd Semidefinite Programming Internal Report Stanford University 1994 submitted to SIAM Review 2 Boyd S L El Ghaoui E Feron and V Balakrishnan Linear Matrix Inequalities in Systems and Control Theory SIAM books 1994 3 Khargonekar P and M A Rotea Mixed H H Control a Convex Optimization Approach IEEE Trans Aut Contr 39 1991 pp 824 837 4 Nikoukhah R Willsky A S and B C Levy Kalman Filtering and Riccati Equations for Descriptor Systems IEEE Trans Aut Contr 37 1992 pp 1325 1342 14 gt Scilab Dialog Panel RS Function definitions Here is a skeleton of the functions which you shoud edit You can do the editing in this window or click on ok save the skeleton and edit later using your favorite editor function L X gammal MM estim H V Generated by lmitool on Tue Feb 07 13 34 28 MET 1995 Mbound 1 3 abstol 1 10 10 max
18. uates the LME LMI and objective functions given the values of the unknown matrices The syntax is LME LMI OBJ EVALFUNC XLIST where XLIST alist identical in size and structure to XLISTO LME a list of matrices containing values of the LME functions G s for X values in XLIST LME be a matrix in case there is only one LME function to be evaluated instead of a list containing this matrix as unique element It can also be a list of a mixture of matrices and lists which in turn contain values of LME s and so on LMI a list of matrices containing the values of the LMI functions H s for X values in XLIST LMI can also be a matrix in case there is only one LMI function to be evaluated It can also be a list of a mixture of matrices and lists which in turn contain values of of LMI s and so on OBJ a scalar equal to the value of the objective function f for X values in XLIST If the problem has no equality constraints then LME should be Similarly for LMI and OBJ e options 5 1 vector containing optimization parameters Mbound abstol nu maxiters andreltol see manual page for semi def for details Mbound is a multiplicative coefficient for M This argument is optional if omitted default parameters are used e XLISTF list identical in size and structure to XLISTO containing the solution of the problem optimal values of the unknown matrices e a scalar
Download Pdf Manuals
Related Search