Home

User's Guide for SEDUMI INTERFACE 1.04

Contents

1. jas N O O GO u GOGO O F OG OG GO 4 FJ G OOOO 900 849 900 990 990 990 900 990 00 00 00 00 00 0000 NROORN Ndd KO D I 1 1 1 1 1 1 1 1 SC a a A e a e a e a E a E a O G O G G OOO 90 0 01010 0 OS O O OG OG Or Oe GOGO O GOG OCG OOS DD ED HO AAA ES CO As Rn E O MA O O E OOO 0 Or OVE S 19 00 OQ GO O OGO O 0 WwWNNNNDNRAPRARRRARRP RP WNNDNNDNNR RAPREARRRRAPRRPR ERP E gt Table 2 Solving an LMC problem with SeDuMi 1 05 gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name 1 N 2 gamma 2 3 Q no equality constraint inequality constraints index meig na 1 eps Q gt 0 2 eps Hinfty state feedback maximise objective gamma 2 27 3 feasible Table 3 Solved LMC problem 13 2 7 Extracting the computed solution In all cases SEDUMI returns the last iterate The sdmpb get function in SEDUMI INTERFACE allows the user to get this solution directly in a matrix format The user specifies varvalue as a second input argument and provides a third input argument containing the index of the desired matrix gt gt g2_opt get quiz varvalue gindex g2_opt 27 2878 A faster way to obtain the values of the variables is the sub reference with brackets gt gt Y_opt quiz Yindex Y_opt 41 2455 53 0257 0 8462 25 0895 This syntax allows to get dir
2. to call other solvers when the translation is admissible 34 Acknowledgements Thanks a lot to Jos Sturm of the Faculty of Economics Department of Econometrics Tilburg University The Netherlands for his work on SEDUMI and his encouragements Thanks also to Michal Kvasnica of the Slovak University of Technology in Bratislava Slovakia for his useful comments References 1 2 3 4 5 6 7 8 9 10 11 12 13 14 F ALIZADEH J P HAEBERLY M V NAYAKKANKUPPAM M L OVERTON and S SCHMIE TA SDPpack Version 0 9 Beta for Matlab 5 0 Semidefinite Quadratic Linearly Con strained Programs New York University 1997 URL www cs nyu edu faculty overton sdppack sdppack html S J BENSON and Y YE DSDP3 Dual Scaling Algorithm for General Positive Semidefinite Programs Tech report n ANL MCS P851 1000 November 2000 Argonne National Laboratory S J BENSON Y YE and X ZHANG Solving large scale sparse semidefinite programs for com binatorial optimization SIAM Journal of Optimization vol 10 2000 pages 443 461 B BORCHERS CSDP 2 3 User s Guide Optimization Methods and Software vol 11 n 1 1999 pages 597 611 B BORCHERS CSDP A C Library for Semidefinite Programming Optimization Methods and Software vol 11 n 1 1999 pages 613 623 S BOYD L EL GHAOUI E FERON and V BALAKRISHNAN Linear Matrix Inequalities in Syste
3. H 0 0 conj D11 1 i The first input argument is the sdmpb object to append The second and third input arguments are vectors containing respectively row block dimension and column block dimension in the equality constraint The last input argument is an optional label used for nice display The appended sdmpb object is returned along with an index 1meindex that makes reference to the declared constraint At this step the LMC problem is described in table 5 gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name Y gamma 2 Q diagonal D 6 wo MAIDA SP S S NP D G H J K equality constraints index name 1 K 0 0 Q11 H 0 0 conj D11 1 1 inequality constraints index name Q gt 0 Hinfty state feedback maximise objective gamma unsolved Table 5 Completely declared LMC problem To get data on these equalities constraints such as the number of constraints their block dimensions and their names use the following syntaxes 24 gt gt get quiz eqnb ans 1 get quiz eqdimrow lmeindex ans 2 1 get quiz eqdimcol lmeindex ans 3 1 gt gt get quiz eqname lmelindex ans K 0 0 011 H 0 0 conj D11 1 1 3 3 2 Add a term to an equality constraint sdmeq All terms in an LME constraint are declared with sdmeg as follows quiz sdmeq quiz LMEindex blrow blcol Xindex L R This command adds to
4. Table 12 Same LMC problem solved with a feasibility radius Note that the solution found this time has all its eigenvalues strictly positive It is a by product of the feasibility radius The SEDUMI solver has quite often less numerical problems if a feasibility radius 32 is appropriately chosen To guide the user in choosing this radius we recommend to solve the LMC problem once without any radius If the solution is not convenient get the value of the norm on the decision variable vector using the sdmpb get operator gt gt get quiz ynorm ans 2 7383e 06 At last solve again the same problem with a feasibility radius greater than the previously obtained norm This empirical procedure often gives successful results 4 Warnings for MATLAB LMI Toolbox users This section is specially written for users that are familiar with the LMI Control Toolbox of MATLAB Other readers can skip this section and therefore avoid potentially confusing remarks 4 1 Left and right sides of an inequality The notions of left and right sides of a matrix inequality are quite different in SEDUMI INTERFACE and in the LMI Control Toolbox In both interfaces the left and right sides correspond to the formulation L x lt Rix But while in the LMI Control Toolbox it is possible on a feasible point x to evaluate separately both sides in SEDUMI INTERFACE the notion of sides is only used to define the constraints Th
5. 0 lI sdmineq quiz LMIindex 0 I Assume that the constraint before this command was schematically described as L x lt R x The two commands append respectively the constraint such that L x LR R L lt R x L x lt R x LR R L The two resulting constraints are identical 3 2 3 Transpose of some matrix variable LX R By default a new declared term depends linearly on the matrix variable such as in LXR The conjugate transpose term R X L being automatically added there is no point in declaring terms that depend on the conjugate transpose of the matrix variable In the case when X is real there is therefore no need have a functionality to add a term that depends on the transpose of X XT X Nevertheless when X is complex valued it may be useful to declare terms that depend on the transpose not conjugate of some variable SEDUMI INTERFACE allows the user to do so In order to declare a term depending on the transpose of a matrix variable such as LX R the syntax is to multiply by 1 the third input argument of sdmineq The rule for matrix variable transpose is the following e not transposed If the third input argument of sdmineg is positive Xindex the term depends on the variable X such as in LXR and R X L is added to the symmetric block e transposed If the third input argument of sdmineq is negative Xindex the term depends on the transpose of the variable XT such as in L
6. gt get quiz objname ans gamma 2 2 6 Solve an LMC problem sdmsol Having defined an LMC problem SEDUMI INTERFACE makes the interface with the SEDUMI solver through the function sdmsol The use is shown in table 2 The variable containing the LMC problem is then appended and contains the last iterate of the SEDUMI algorithm SEDUMI runs with the default parameters To modify these parameters see the advanced description of sdmsol in section 3 6 1 When a problem is solved with SEDUMI the display informs the user on the feasibility of the LMC problem For the example chosen in this tutorial the solved LMC problem is displayed in table 3 An LMC problem solved with SEDUMI may have three status e feasible This means that the maximisation problem was solved and converged towards the optimal point Here the optimal criteria is 27 3 When no objective is specified feasibility means that the LMCs admit at least one solution found by SEDUMI e infeasible This means that the LMCs have no solution at all e marginal feasibility This occurs when SEDUMI has some numerical problems and cannot determine exactly a feasible solution To avoid such complications see comments in section 3 6 This information on the feasibility of the LMC problem is also available via the sdmpb get operator gt gt get quiz feas ans 1 The sdmpb get output is 1 if the problem is feasible 1 if the problem is infeasible 0 if t
7. gt gt R 052i gt gt quiz sdmineq quiz lmi2index 1 1 0 L R Note that the factor 0 5 gt is necessary For blocks on the diagonal blrow blcol the term R L is added to LR in the same block Beware not to declare it twice This is why one of the multiplying data matrices is divided by two in this example Following these rules the inequality constraints on the example are completely defined by adding the five remaining terms ineg quiz lmilindex Qindex 1mi2index Qindex 1mi2index Yindex 1mi2index Yindex 1mi2index gindex ineq quiz ineq quiz ineq quiz ineq quiz The usage of sdmineg described in this section is the most generic and allows to define all possible terms In SEDUMI INTERFACE other usages of sdmineg are also defined A complete description of these advanced functionalities can be found in section 3 2 2 5 Adda linear term to the objective sdmob3 By default the objective is empty The LMC problem is then a feasibility problem In order to define a maximisation or minimisation problem a unique function is used sdmobj Since SEDUMI is an algorithm that maximises the objective under LMCs the objective defined by sdmobj will be maximised To minimise some objective one has then to maximise its opposite Remark that if the objective is complex SEDUMI will maximise its real part As for inequality constraints the objective is recursively declared by adding line
8. trace T g 3 86 feasible Table 9 Optimally solved LMC problem having accuracy complications The display claims that the problem is feasible but the meig value of the fourth inequality is negative As exposed in the previous section this status is not surprising It indicates that SEDUMI stopped while the computed point was as close to the optimum as the accuracy level 3 6 1 SeDuMi parameters To improve the accuracy the user has to specify new parameters to SEDUMI This is done with the syntax gt gt quiz sdmsol quiz pars The optional second input argument of sdmsol must have the structure adopted by SEDUMI 25 One of the fields of the structure pars allows to choose a precision level default is 107 Let us modify in this way the accuracy of SEDUMI and hopefully the obtained iterate will have all eigenvalues strictly positive Table 10 shows the computation result gt gt pars eps le 12 gt gt quiz sdmsol quiz pars LMC problem H2 Hinfty state feedback synthesis matrix variables index name 1 X 2 T 3 S no equality constraint inequality constraints index meig 0 005 1 2 3e 09 3 3e 08 4 7e 10 maximise objective trace T g 3 86 marginal feasible Table 10 Same LMC problem solved with a smaller precision parameter 30 As can be seen SEDUMI failed to find a feasible solution satisfying the new precision In fact the last iterate 1s identical to the previous one SEDUMI stopped
9. IN The first input argument is the sdmpb object to append The second input argument is a vector containing the index of the inequality constraint and the block index in row and column b1 row blcol to which the term is added The third input argument is the index of the variable The last two input arguments correspond to the left and right multiplying data matrices OUT The appended sdmpb object is the unique retrieved output argument Note that since matrix inequalities are Hermitian symmetric in the case of real valued matrices the conjugate transpose term is automatically added This is an important feature of SEDUMI INTERFACE By default sdmineq always adds the conjugate transposed term R X L to the symmetric block given by b1col blrow along with the declared term LXR The last command line adds the term C Q in the 2 1 block the symmetric term QC is automatically added to the same 1 2 block To declare a constant term such as LR for example the usage of the function is the same at the difference that the variable index third input argument is set to zero Pay attention to the fact that the user is 10 assumed to define both left fourth input argument and right fifth input argument matrices Moreover the conjugate transpose term is automatically added R L is added in the b1col blrow block In our example the constant term is such as B Bi in the 1 1 block It can be declared as follows gt gt L Bw
10. Inequalities Problems with Rank Constraints pages 251 267 SIAM Philadelphia 2000 Edited by L El Ghaoui and S I Niculescu 35 15 T IWASAKI LPV System Analysis with Quadratic Separator for Uncertain Implicit Systems LMI Methods in optimisation identification and control Seminar Compi gne France May 1999 16 S E KARISCH CUTSDP A Toolbox for a Cutting Plane Approach Based on Semidefinite Pro gramming Department of Mathematical Modelling Technical University of Denmark June 1998 Technical Report IMM REP 1998 10 URL www imm dtu dk sk cutsdp 17 Y LABIT D PEAUCELLE and D HENRION SeDuMi interface 1 02 a tool for solving LMI problems with SeDuMi proceedings of CACSD Glasgow Scotland September 2002 para tre 18 F LEIBFRITZ An LMI based algorithm for designing suboptimal static H2 H output feedback controllers SIAM Journal on Control and Optimization vol 39 n 6 2001 pages 1711 1735 19 J LOFBERG YALMIP Yet Another LMI Parser August 2001 URL www control isy liu se johanl yalmip html 20 H D MITTELMANN An Independent Benchmarking of SDP and SOCP Solvers Tech report July 2001 Arizona State University URL www optimization online org DB_HTML 2001 07 358 html 21 D PEAUCELLE and D ARZELIER An Efficient Numerical Solution for Ah Static Output Feed back Synthesis proceedings of European Control Conference Porto Portugal
11. SEDUMI INTERFACE Getting started 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 LMC problem an sdmpb object 2 2 o a Defining matrix variables sdmvar 2 ee Defining an inequality constraint sdmlmi 2 2 ee ee Add a term to an inequality constraint sdmineq o o Add a linear term to the Objective sdmobj o o o e Solve an LMC problem sdmsol o oo Extracting the computed solution o ee Analysis of the computed solution 2 2 0 00 00 0002 eee eee 3 Advanced use of SEDUMI INTERFACE 3 1 3 2 3 3 3 4 3 5 3 6 Structured variables sdmvar 1 ee Advanced declaration of some inequality terms sdmineqg 04 3 2 1 Block partitioning e 3 2 2 Left and right sides of an inequality o 3 2 3 Transpose of some matrix variable EXI and eo eh 3 2 4 Matrix terms depending on a scalar variable o 3 2 5 Scalar L and R multipliers o a 3 2 6 Hermitian terms LXEFaddLE o o o o o 3 2 7 Terms with no multiplying data e e e 3 2 8 Terms with Kronecker products L KG9X RadLXSOK R Equality constraints seer ko pte Se a a RE oe de Sa y 3 3 1 Defining an equality constraint sdmlme ooa ee ee ee 3 3 2 Adda term to an equality constraint sdmeq 2 2 ee ee The trace as an objective max trace BX i sc Bes bee Ba ee eS Set a
12. September 2001 pages 3800 3805 22 D PEAUCELLE D HENRION and Y LABIT User s Guide for SEDUMI INTERFACE 1 01 Optimization Online November 2001 URL www optimization online org DB_HTML 2001 11 398 html 23 D PEAUCELLE D HENRION and Y LABIT User s Guide for SEDUMI INTERFACE 1 01 Solv ing LMI problems with SEDUMI Tech report n 01445 October 2001 LAAS CNRS Toulouse France URL www laas fr peaucell SeDuMilnt html 24 PETE SEILER LMllab Translator Tech report July 2001 University of Berkeley California URL vehicle me berkeley edu guiness lmitrans html 25 J F STURM Using SeDuMi 1 02 a MATLAB toolbox for optimization over symmetric cones Optimization Methods and Software vol 11 12 1999 pages 625 653 URL fewcal kub nl sturm software sedumi html 26 T C TOH M J TODD and R H TUTUNCU SDPT3 a MATLAB software package for semidefinite programming version 2 1 Optimization Methods and Software vol 11 1999 pages 545 581 URL www math nus edu sg mattohkc index html 27 J G VANANTWERP and R D BRAATZ A Tutorial on Linear and Bilinear Matrix Inequalities J Process Control vol 10 2000 pages 363 385 28 L VANDENBERGHE and S BOYD SP Softvare for semidefinite programming User s guide beta version Tech report 1994 K U Leuven and Stanford University URL www stanford edu boyd SP html 29 S P WU and S BOY
13. disappointed not to have strictly positive eigenvalues while the computed iterate is satisfying for SEDUMI To avoid such misunderstandings a way out is then to transform all semi definite inequalities into definite inequalities To do so the user has to introduce a constant positive definite term 1 in all inequalities such that L x lt R x al L x lt R x This operation transforms the constraint all eigenvalues must be strictly positive into all values must be superior or equal to amp gt 0 The modified constraint is conservative but one can expect that the modification is not disturbing as long as is small We now test this procedure on the H2 H state feedback synthesis problem First one has to add the constant term Q1 to all inequalities This may be tedious therefore a simplified syntax is adopted in SEDUMI INTERFACE e add a scalar to a LMC problem If a scalar a is added or subtracted to a sdmpb object the result of this operation is an identical sdmpb object where a constant matrix 1 of appropriate dimension has been added or subtracted to the right side of all inequality constraints The subtraction operator is applied to the example with a 10 The result is given in table 11 The result is satisfying all eigenvalues of the constraints in the LMC problem quiz2 are positive or 31 gt gt quiz2 quiz le 6 gt gt quiz2 sdmsol quiz2 LMC problem H2 Hinfty state feed
14. displayed as any other complex number gt gt 2 ans 2 gt gt 2 21 ans 2 0000 2 00001 Therefore the num2str MATLAB function will sometimes appear for nice display The result is a string that cannot be used for computation gt gt num2str 2 21 ans 2 21 1 2 LMC problems The academic results on LMIs use the following optimisation formalism 6 10 m p min c x st Fo xF gt 0 1 j 1 where the data are the m 1 symmetric matrices Fo Fn and the column vector c while the opti misation variables are gathered in the vector x with components xj The formalism underlines that an LMI problem is an optimisation problem with a linear objective and positive semi definite constraints involving symmetric matrices that are affine in the decision variables At this point note that there is another general formalism for writing LMIs 25 p min cx s t b Ax is positive semi definite Here the data are two vectors b c and a matrix A The expression is of course abusive A vector z b AX is said to be positive semi definite if the symmetric matrix Z build out of z with some stack operator is positive semi definite We do not get into more details The point is that the generic formalisms of LMIs on which are based SDP solvers are much too compact to be adapted easily to application problems In particular a major difficulty is that control problems are formulated with matrix varia
15. due to numerical problems The display explicitly warns that the feasibility is not satisfied with the required precision an eigenvalue is negative and less than 10712 but the algorithm does not prove that the LMC problem is infeasible To have details on the status of the obtained iterate the user can get the output information from SEDUMI with the help of the sdmpb get operator gt gt get quiz solver ans cpusec 2 5600 iter 17 feasratio 0 9403 pinf 0 dinf 0 numerr 1 For details on the fields of this output see 25 The last field numerr 1 is non zero in this example This explicitly shows that some numerical error has occurred 3 6 2 Definite and semi definite inequalities Up to this point we have discussed how to modify the algorithm parameters using the second argument of sdmsol and how to get the status of the SEDUMI solver issued after computation But we have not yet solved the H2 H state feedback synthesis problem There is still one non strictly satisfied inequality in the result the meig data of the fourth inequality is negative 7e 10 To explain the difficulty encountered here note that for SEDUMI the constraints are semi definite in equalities Therefore SEDUMI assumes that if a minimal eigenvalue meig of some constraint is equal to zero or close to zero at the precision level the constraint is satisfied In the H2 H synthesis problem that is used as an example here we are therefore
16. e Du Y sv 1 objective max y First let us initialise the sdmpb object within MATLAB and give it a name gt gt quiz sdmpb Optimal Hinfty State Feedback Synthesis LMC problem Optimal Hinfty State Feedback Synthesis no matrix variable no equality constraint no inequality constraint no linear objective unsolved The operator sdmpb creates an empty object An optional input argument allows to give a label to the LMC problem This label is used only for nice display At this step we have declared an empty sdmpb object The class of the variable quiz in MATLAB is sdmpb Each declared LMC problem is an sdmpb object gt gt whos quiz Name Size Bytes Class quiz 1x1 6406 sdmpb object In the following subsections we assume that the data A Bu Bw Cz Dzu n m q and p describing the LTI system are defined in the MATLAB environment For example we chose for this tutorial 1 p 2 0 110 1010 0 101 2 2 Defining matrix variables sdmvar All variables in SEDUMI INTERFACE are real or complex matrix variables Extensions to complex variables were introduced in 1 02 version of SEDUMI INTERFACE By default the variables are real full rectangular matrices declared as follows gt gt quiz Yindex sdmvar quiz m n Y IN The first input argument of the function is the sdmpb object for which the user wants to declare a new matrix variable The second and third input arguments are respectively the nu
17. input argument is an optional label used for nice display OUT The appended sdmpb object is returned along with an index 1milindex that makes reference to the declared constraint At this step the LMC problem of the example is composed of 3 variables and 2 constraints gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name 1 Y 2 gamma 2 3 Q no equality constraint inequality constraints index meig name 1 Inf Q gt 0 2 Inf Hinfty state feedback no linear objective unsolved To get data on these inequality constraints such as the number of constraints their names or the dimen sion of blocks use the following syntaxes gt gt get quiz ineqnb ans 2 gt gt get quiz ineqname 1lmi2index ans Hinfty state feedback gt gt get quiz ineqdim lmi2index ans 4 2 2 4 Add a term to an inequality constraint sdmineq By default the inequality constraints are empty When a term is declared 1t is added to the existing terms at the left side of the inequality sign lt Iteratively all the terms are therefore declared with the unique function sdmineg The constraints are linear in the matrix variables hence all terms can write as LXR where L and R are data matrices and where X is a matrix variable To add a term to an inequality the usage is gt gt L Ez gt gt R 1 gt gt quiz sdmineq quiz lmi2index 2 1 Qindex L R
18. matrix or a scalar B the term added to the maximisation objective is trace BX With the help of this syntax the objective can be declared in one line as follows gt gt quiz sdmobj quiz Xindex tr B trace BX gt gt get quiz objname ans trace BX Remark that if the dimensions fit the following relation holds trace AC trace CA Therefore to declare a term such as trace CXC one can declare trace BX with B C C 3 5 Set a value to some variable sdmset In some cases the user may want to solve an LMC problem with one or more variable frozen to a speci fied value This allows to test if some value belongs to the admissible set constrained by the inequalities The syntax is the following gt gt quiz sdmset quiz Xindex Xvalue The first input argument is the sdmpb object to append the second input argument is the index of the variable the third input argument is the value of the variable the user has chosen Having set a variable to some value the indexes of the other variables are not modified The equalities inequalities and the objective are rearranged to take into account that the variable becomes a constant The label of the removed variable is appended as well as the labels of removed inconsistent constraints To illustrate the use of sdmset let us consider the H state feedback problem of the previous section The LMC problem was defined in order to minimise the H c
19. matrix variables index name 1 iv 2 gamma 2 3 Q no equality constraint no inequality constraint no linear objective unsolved The function sdmpb get also allows to get information on the declared variables such as the number of variables gt gt get quiz varnb ans 3 the name of a variable referenced by its index gt gt get quiz varname gindex ans gamma 2 and also the structure of a variable gt gt get quiz vardec Qindex ans In the considered example n 4 the variable Q is a 4 by 4 symmetric matrix The array of integers generated here by the sdmpb get function describes its structure The integers relate the dependence of the matrix variable Q to the independent scalar decision variables of the matrix inequality canonical form For more information on this point see section 1 2 and the advanced usage of sdmvar in section 3 1 2 3 Defining an inequality constraint sdmlmi All matrix inequality constraints in SEDUMI INTERFACE are square Hermitian matrices characterised by their number of rows and an optional label To initialise an inequality constraint the usage is gt gt quiz lmilindex sdmlmi quiz In Q gt 0 gt gt quiz lmi2index sdmlmi quiz n p Hinfty state feedback IN The first input argument is the sdmpb object to append The second input argument is a vector containing the size of the diagonal blocks in the LMI constraint The last
20. the blrow blcol block of the equality constraint referenced by the index LMEindex a term LXR where X is the matrix variable referenced by the index Xindex If the index is equal to 0 a constant term LR is added Note that for the equalities there is no necessity for the constraints to be Hermitian Therefore nothing similar to the Hermitian terms added in LMIs is performed when adding a term to an LME On the other hand as for the inequality constraints the generic rule for defining LME terms has advanced usages These are now described shortly Block partitioning e specifying blocks When the second input argument of sdmeq is composed of three entries LMEindex blrow blcol then the term LXR is added to the blrow blcol block same comment for constant terms LR e not specifying block If the second input argument of sdmeq is a scalar LMEindex then the term LXR is added to the entire LME same comment for constant terms LR Note that in this case the number of rows of L must be equal to the number of rows of the whole LME sum of row dimensions of the blocks and the number of columns of R should be equal to the number of columns of the whole LME sum of column dimensions of the blocks Left ad right sides of the equality e left If the first entry of the second input argument of sdmeq is positive LMEindex the term is added in the LMEindex constraint to the left hand side of the inequality sign e right If
21. the first entry of the second input argument of sdmeg is negative LMEindex the term is added in the LMEindex constraint to the right hand side of the inequality sign 25 Transpose and conjugate of some matrix variable not transposed not conjugate If the third input argument of sdmineq is positive and real Xindex the term depends on the variable X such as in LXR transposed not conjugate If the third input argument of sdmineq is negative and real Xindex the term depends on the transpose of the variable XT such as in LXTR not transposed conjugate If the third input argument of sdmineq is positive and purely imaginary i Xindex the term depends on the conjugate of the variable X such as in LXR transposed conjugate If the third input argument of sdmineq is negative and purely imaginary i Xindex the term depends on the conjugate transpose of the variable X such as in LX R Hermitian terms LXL and LL e not Hermitian If both the fourth L and the fifth R input arguments are declared and are non empty then the added term is LXR or LR variable dependent term or constant term respectively e Hermitian If the fourth input argument L is specified and the fifth input argument R is omitted or empty R then the added term is LX or LL variable dependent term or constant term respec tively For LME constraints this advanced usage does not require the term to be added in a diagona
22. variable Contains m m 1 2 independent decision variables when m is the number of rows of the matrix The third input argument of sdmvar is set to the string value s An example of real symmetric variable is given in the previous section variable Q anti symmetric real or complex Square anti symmetric matrix variable Contains m m 1 2 independent decision variables when m is the number of rows of the matrix The third argument of sdmvar is set to the string value as An example of R anti symmetric variable is 16 gt gt quiz Gindex sdmvar quiz 3 as G gt gt quiz Gindex ans o 19 20 19 Qu 21 20 21 0 e Hermitian Square Hermitian matrix variable Only defined if the matrix is complex valued i e the second input argument is imaginary m i Contains m m 1 2 independent decision variables when m is the number of rows of the matrix The third input argument of sdmvar is set to the string value h An example of C Hermitian variable is gt gt quiz Hindex sdmvar quiz 2i h H gt gt num2str quiz Hindex ans 22 01 23 231 23 231 24 01 anti Hermitian Square anti Hermitian matrix variable Only defined if the matrix is complex valued i e the second input argument is imaginary m i Contains m m 1 2 independent decision variables when m is the number of rows of the matrix The third argument of sdmvar is set to the string value a
23. with a block partitioning of without In the sequel this block partitioning is sometimes avoided not to have complicated notations 3 2 2 Left and right sides of an inequality By default a new declared term is added to the left of the inequality sign lt For example assume that up to this point some terms have been declared and the inequality constraint writes in a schematic form as without describing the possible block partitioning L x lt 0 The command gt gt quiz sdmineq quiz LMIindex blrow blcol Xindex L R modifies the constraint into lt 0 or Diagonal blocks Other blocks But SEDUMI INTERFACE allows also to declare terms on the right hand side This can be done by multiplying by 1 the constraints index The command quiz sdmineq quiz LMIindex blrow blcol Xindex L R modifies the constraint into Diagonal blocks Other blocks The rule for left and right sides of inequality constraints are the following e left If the first entry of the second input argument of sdmineq is positive LMIindex the term is added in the LMIindex constraint to the left hand side of the inequality sign lt 20 e right If the first entry of the second input argument of sdmineg is negative LMIindex the term is added in the LMI index constraint to the right hand side of the inequality sign lt Following this rule the next two command lines are equivalent sdmineq quiz LMIindex
24. D Design and implementation of a Parser Solver for SDPs with Matrix Structure proceedings of IEEE Conference on Computer Aided Control System Design New York 1996 36
25. User s Guide for SEDUMI INTERFACE 1 04 Dimitri Peaucelle Didier Henrion Yann Labit Krysten Taitz LAAS CNRS 7 Avenue du Colonel Roche 31077 Toulouse cedex 4 France Tel 05 61 3364 17 fax 05 61 336969 email peaucelle laas fr henrionOlaas fr ylabitO laas fr 13th September 2002 Abstract This report describes a user friendly MATLAB package for defining Linear Matrix Constraints LMCs It acts as an interface for the Self Dual Minimisation package SEDUMI developed by Jos F Sturm The functionalities of SEDUMI INTERFACE are the following Declare an LMC problem Five MATLAB functions allow to define completely an LMC problem which can be charac terised by scalar and matrix variables linear matrix equality LME constraints linear matrix inequality LMI constraints and a linear objective Initialise the LMC problem sdmpb Declare the matrix variables sdmvar Declare the block partitioned equality constraints sdmlme and sdmequ Declare the block partitioned inequality constraints sdmlmi and sdminequ Declare the linear objective sdmob3 Solve an LMC problem A unique function sdmsol calls the SEDUMI solver Options allow to tune the solver param eters Modify an LMC problem At any moment it is possible to append an LMC problem by adding variables inequalities or linear terms to the objective Moreover the sdmset function allows to freeze matrix variables to specified values A
26. X R and R XL is added to the symmetric block Following the rule the two next command lines are equivalent if the variable is real and are not if it is complex valued sdmineg quiz LMIindex blrow blcol Xindex L R sdmineq quiz LMIindex blcol blrow Xindex R L 3 2 4 Matrix terms depending on a scalar variable A 1 by 1 matrix variable can be confounded with a scalar but from a mathematical point of view mul tiplying a 1 by 1 matrix with an other matrix assumes that the dimensions fit together Problems could therefore occur when dealing with scalar variables declared as 1 by 1 matrices But it is not the case with SEDUMI INTERFACE The user may proceed without worrying 21 3 2 5 Scalar L and R multipliers For the same reason as exposed in the last paragraph there could be some trouble when giving scalar values to the matrices L and R fourth and fifth input arguments of sdmineq But SEDUMI INTERFACE handles also these cases in the natural way 3 2 6 Hermitian terms LXL and LL Noticing that for Hermitian terms it is quite tedious to be aware of automatic duplication when working in a diagonal block another syntax is accepted by sdmineg This syntax is based on the fact that most Hermitian terms can be reformulated as LXL EE for variable dependent and constant terms respectively In order to declare such Hermitian terms the following rule is adopted e not Hermitian If both the fourt
27. aints name K 0 0 011 H 0 0 conj D11 1 1 inequality constraints name Q gt 0 Hinfty state feedback maximise objective gamma LMIs are feasible Table 6 Solved LMC problem The norm data correspond to the norm of each equality constraint evaluated on the point obtained by SEDUMI The constraints are satisfied if their minimal norm is zero The norm data can have different values e Inf occurs when the LMC problem has not been solved as in table 5 e 0 occurs when the constraint is strictly equal to zero eps occurs when the constraint is close to zero The SEDUMI algorithm has an accuracy set by default to 107 All constraints with a norm less than this accuracy level are assumed to be equal to zero The norm data is set to eps in SEDUMI INTERFACE e positive scalar occurs when the equality constraint is not satisfied 27 3 4 The trace as an objective max trace BX The operator sdmobj is designed to declare linear objectives by adding recursively scalar terms of the type e Xe where e and e are respectively a row and a column vector This usage was already defined in the previous section Here we demonstrate how it can be used to define a linear trace objective Assume the objective is max trace BX SEDUMI INTERFACE can declare directly the trace of a matrix variable The rule is trace objective If the third and fourth input arguments of sdmobj are respectively the string tr and a
28. ar objective terms All terms write in a generic manner as e Xe where e and e are respectively a row and a column vector so that the product e Xe defines a scalar linearly depending on the matrix variable X For the H state feedback example of this section the objective is declared as gt gt quiz sdmobj quiz gindex 1 1 gamma 2 IN The second input argument is the index of the variable on which depends the objective term The third and fourth input arguments are respectively the left and right multiplying vectors e and e The last input argument is an optional label describing the objective OUT The unique output argument contains the appended LMC problem quiz As for the sdmvar and sdmineq operators an advanced usage of sdmobj is available In particular it allows to declare the trace of some matrix variable as an objective term The advanced usage of sdmob 4 is described in section 3 4 At this stage the LMC problem is entirely declared in the MATLAB environment The sdmpb object contains all the information see table 1 11 gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name 1 Y 2 gamma 2 3 Q no equality constraint inequality constraints index name 1 Q gt 0 2 Hinfty state feedback maximise objective gamma 2 unsolved Table 1 Completely declared LMC problem The sdmpb get operator makes it possible to get the name of the linear objective gt
29. ator can give their dependency to the decision variables as shown in table 4 gt gt get quiz vardec Yindex ans 1 2 gt gt quiz gindex ans 5 gt gt quiz Qindex ans 6 7 8 9 Table 4 Get the structure of the variables Note that two different notations were used here to get the structure matrices The notations are equiv alent The second one composed of curly braces is a faster manner to get directly the structure of the variable referenced by its index When comparing the structure matrices one can see that they have the same structure as expected for the variable The three matrix variables are independent because they all depend on different decision variables Y is a 1 by 4 full block matrix that depends on the decision variables indexed from 1 to 4 y is a scalar variable that depends on the 5 th decision variable Q is a 4 by 4 full block symmetric matrix that depends on the decision variables indexed from 6 to 15 10 independent elements in a 4 by 4 symmetric matrix In the sequel assume that the new variables are independent of the previous ones 15 e real full rectangular The first input argument to sdmvar is the variable describing the LMC problem quiz the sec ond and third input arguments are respectively the number of rows m and columns n of the rectangular matrix variable at last as an option the user can give a label to the variable name gt gt quiz VARindex s
30. back synthesis matrix variables index name 1 X 2 T 3 5 no equality constraint inequality constraints index meig 1 0 005 2 eps 3 7e 09 4 eps maximise objective trace T g 3 86 feasible Table 11 Same LMC problem solved with amp translated constraints at least greater than the accuracy level 107 This means that the solution is acceptable for the LMC problem quiz with all eigenvalues superior or equal to 107 107 gt 0 3 6 3 Feasibility radius Another and last way to tune the solver convergence without modifying strongly the LMC problem is to impose a feasibility radius It constrains the norm of the vector of decision variables The convexity of the LMC problem is not modified but the additive constraint may add some extra conservatism The trick is to impose a sufficiently large feasibility radius and in the same time reduce at its maximum the domain in which the solver has to seek the optimal solution The syntax for constraining the feasibility radius is to give a third input argument to sdmsol Constrained with a radius of 10 the mixed H H state feedback synthesis problem converges to the solution of table 12 gt gt quiz sdmsol quiz 1e9 LMC problem H2 Hinfty state feedback synthesis matrix variables index name 1 X 2 T 3 S no equality constraint inequality constraints index meig 1 0 01 2 6e 06 3 2e 05 4 8e 07 maximise objective trace T g 3 86 feasible
31. bles while the generic formulations exposed above depend on vectors of decision variables Going from one formalism to another may be quite tedious Take for example the Lyapunov inequality it writes as an LMI constraint ATP PA lt 0 Assume A is a 2 by 2 matrix P is a symmetric matrix considered as the variable in the LMI problem Expressed in terms of the scalar data and the scalar variables bold face the LMI writes as ls le leaks le 2 lt o ar an2 p2 P3 p2 P3 a an and this corresponds in the formalism 1 to F 0 x p1 P2 P3 F 2a 412 P 2421 411 422 E 0 421 412 0 411 22 2412 421 2d2 The manipulations are trivial but tedious even for small size problems SEDUMI INTERFACE is designed to tackle these manipulations In particular the syntax adopted in SEDUMI INTERFACE is adapted to usual control LMI formulations A large spectrum of options allows to simplify some recurrent declara tions e First a large variety of matrix variables are admissible in SEDUMI INTERFACE It ranges from full block matrices to any structured matrix variable including the symmetric anti symmetric Hermitian and anti Hermitian variables e Second both linear matrix inequality LMI and equality LME constraints can be declared In the sequel an LMC problem is an optimisation problem with a linear objective and possibly both LMI and LME constraints e Third various types of linear matrix terms can be declared inclu
32. ding Kronecker products between data matrices and matrix variables e Fourth the linear objective is a sum of linear terms and can contain the trace operator e Fifth data matrices and variables can be real or complex valued LMIs are then interpreted as Hermitian positive definite constraints e Sixth the LMCs can be declared taking into account a block partitioning 1 3 Existing solvers Several research groups have produced software packages for SDP problems and many improvements are currently made Among the first solvers were the SP solver 28 and the LMI lab which evolved into the MATLAB LMI Control Toolbox 13 Since then a wide variety of solvers have been developed among which SEDUMI 25 SDPA 12 SDPHA 7 SDPpack 1 SDPT3 26 CSDP 5 4 CUTSDP 16 DSDP 3 2 This list is not exhaustive All solvers have particularities They have their own SDP formalism their options their potentialities their convergence speed their robustness For a recent comparison of these solvers see 20 Having ourselves tested some of the solvers and in view of the report 20 we came to the choice of SEDUMI The advantages of this solver that guided our choice are Asymptotic computational complexity Let n be the number of decision variables and m the num ber of rows of the LMIs The computational complexity of SEDUMI including main and inner iterations is in O n m gt m3 gt while the algorithm in 13 has a complexity O
33. dmvar quiz m n name The sdmvar operator outputs the appended sdmpb object and the index of the created variable Beware not to confuse this index with the decision variable structure The index is an integer that makes refer ence to a matrix variable of the LMC problem while the integer elements of the structure matrix make reference to scalar decision variables The variable index VARindex is used in the sequel for specifying a matrix variable in other operators of SEDUMI INTERFACE while the decision variable indexes are only used as arguments for sdmvar e complex full rectangular To declare a complex valued matrix variable the second input argument is slightly modified to be an imaginary integer It writes as m i where m is the number of rows and i is the imaginary number i 1 gt gt quiz VARindex sdmvar quiz m i n name This rule holds for all following structured matrix variables a diagonal real or complex Square matrix variable with independent entries on the diagonal and zero off diagonal entries The usage of sdmvar is the same as for full rectangular matrices except for the third input argument that is replaced with the string d An example of C diagonal variable is gt gt quiz Dindex sdmvar quiz 31 d D diagonal gt gt num2str quiz Dindex ans 16 16i 0 01 0 0i 0 0i 17 17i 0 0i 0 0i 0 0i 18 18i symmetric real or complex Square symmetric matrix
34. e right side in SEDUMI INTERFACE is used to declare terms that appear with the minus sign in a negative definite constraint For example if A is a real valued matrix gt gt quiz sdmineq quiz c Xindex A is a command that adds a term such as L x lt R x AXA or L x AXA lt R x In contrast with the LMI Control Toolbox it is NOT equivalent to gt gt quiz sdmineq quiz c Xindex A that declares a term such that L x A X A lt R x that is L x AXAT lt R x This remark also holds for constant terms that we chose to declare with the same structure as variable terms Therefore beware that the two following commands are totally different gt gt quiz sdmineq quiz c 0 B gt gt quiz sdmineq quiz c 0 B They respectively declare the following terms if B is real L x lt R x BB and L x B B lt R x which is NOT the same at all 4 2 Matrix and scalar multipliers for inequality terms A second warning concerns the use of scalar multipliers in sdmineg As described previously SEDUMI INTERFACE allows to declare terms such as quiz Xindex quiz Pindex sdmineg sdmineg sdmineg quiz Qindex q sdmineg quiz Rindex These commands add terms such that assume all matrices are real 21 X 31 31 7xT 21 7 6 X X 41 PA APT 41 7 4A PA ATP 51 Q 51 7 25Q 1 R 1 R Therefore the three following notat
35. ectly the value of the variable referenced by its index in a matrix format The function sdmpb get allows also to obtain the objective value at the optimum gt gt get quiz objopt ans 27 2878 For the specified H state feedback problem SEDUMI has found the minimal H norm achievable by state feedback AP 1 27 2878 5 2238 2 8 Analysis of the computed solution To analyse the obtained point the meig data allow to check that every inequality constraint is satisfied These data are displayed with the LMC problem table 3 and can also be obtained with the sdmpb get function as gt gt get quiz ineqmeig lmilindex ans eps The meig data correspond to the minimal eigenvalue of each inequality constraint evaluated on the point obtained by SEDUMI The constraints are satisfied if their minimal eigenvalue is positive The meig data can have different values e Inf occurs when the LMC problem has not been solved e 0 occurs when the minimal eigenvalue is strictly equal to zero this may happen because in SEDUMI the inequalities are in fact semi definite e eps or eps occurs when the minimal eigenvalue is positive or negative and close to zero The SEDUMI algorithm has an accuracy set by default to 107 All eigenvalues with absolute value less than this accuracy level are assumed to be equal to zero and set to eps or eps in SEDUMI INTERFACE Even if they are negative eps the r
36. elated LMI is considered to be satisfied e positive scalar occurs when the constraint is strictly satisfied positive definite e negative scalar the constraint is not satisfied 14 We believe that the discussion on semi definite and definite inequality constraints initiated in this section may confuse some readers Therefore for more details we recommend reading section 3 6 For less curious readers we may say that except for badly conditioned problems the indication on feasibility is relevant Playing with the solver parameters almost always confirms this information 3 Advanced use of SEDUMI INTERFACE 3 1 Structured variables sdmvar As exposed briefly in the previous section the operator sdmvar adds a new matrix variable to the LMC problem Moreover the operator allows to specify the structure of this variable Four classical structures are directly available and a fifth usage of sdmvar enables to declare any other structure Before describing the arguments of sdmvar for each case note that SEDUMI INTERFACE represents the structure of a variable as a matrix of the same size with integer elements This representation illustrates the dependency of the matrix variable elements with respect to some vector containing all independent decision variables see section 1 2 for the definition of this vector of decision variables For example take the variables declared in the LMC problem of the previous section The sdmpb get oper
37. er cannot access directly this class of variables but can operate on it in order to get some data or append the object It is defined within MATLAB as a new class of objects called sdmpb To guide the user of SEDUMI INTERFACE we propose a helpful display of sdmpb objects that allows to get at every step important information about the LMC problem In addition the function sdmpb get allows to retrieve any data of the problem The various possibilities of sdmpb get are described in the sequel as we expose step by step the usage of SEDUMI INTERFACE functions For this tutorial we choose a standard control problem of static state feedback synthesis for Linear Time Invariant LTI systems with an A objective 6 Let be an LTI system and K a state feedback gain such that X t Ax t B u t Byw t t Kx t Hi cal Dando poe where x R u R w R1 and z RP The system Y is stabilisable via a state feedback gain K Y Q7 and the closed loop transfer from w to z has an Ho norm less than y if and only if Q 0Q0 gt 0 AQ 047 B Y Y B7 BB QC Y D ai C Q D Y y1 The optimal synthesis problem is an LMC problem composed of three variables a linear objective and two inequality constraints The second matrix inequality is necessarily symmetric and composed of four blocks It can write as variables Q Q7eER YER PER n He 5Q lt 0 inequalities n t E l AQ B Y LB BT 0 a P f C Q
38. er tools and similar low speed complications are noticed We therefore chose not to develop such a GUI tool First we believe such tools are necessarily quite slow The second reason is that we do not have the required programming skills The chosen framework is an in line declaration of the LMC problems as in the LMI Control Toolbox 13 The result is less convivial than a GUI but allows more flexibility Nevertheless efforts were made on nice display and some complications we noticed in the LMI Control Toolbox do not occur in SEDUMI INTERFACE Note that more recently almost at the same time as SEDUMI INTERFACE 1 01 was achieved have appeared two other tools 24 19 They adopt a quite close approach but focus on offering the interface with multiple solvers LMIlab Translator 24 proposes a translator that allows to call various solvers among which SEDUMI using the interface of the LMI Control Toolbox YALMIP 19 is a completely new interface more alike LMITOOL 9 but without the GUI Having focused on translation these two tools are highly valuable to test the efficiency of solvers on different hard problems The by product is that they do not exploit all the potentialities of each solver 1 5 Functionalities The functionalities of SEDUMI INTERFACE are the following e Declare an LMC problem Five MATLAB functions allow to define completely an LMC problem characterised by matrix variables linear matrix equalities LMEs linear matr
39. h An example of C anti Hermitian variable is gt gt quiz Jindex sdmvar quiz gt gt num2str quiz Jindex ans 0 01 25 251 26 261 25 251 0 0i 27 271 26 261 274274 0 0i At this step note that the matrix describing the structure of the variables can be composed of zeros and integers that are possibly multiplied by 1 1 i 1 i 1 i and 1 i The rule is the following Let X be a matrix variable and Xdec quiz Xindex be the matrix that describes its structure Moreover let x be the vector of scalar real or complex decision variables see section 1 2 for its definition X x is the element of X in the j th row and k th column Xn is the n th decision variable Xdec 3 k 0 if Xj 0 constrained to be equal to zero Xdec j k n if X j 4 Xn the n th decision variable is real x R Xdec j k n if X j4 Xn opposite of Xp R Xdec j k tntn i if X j4 Xn the n th decision variable is complex Xn C Xdec j k n n i if X j 4 Xn opposite of Xp C Xdec j k tn n i if X j4 Xp conjugate of Xp C Xdec j k n n i if X 4 Xn opposite conjugate of Xp C Following this rule any structured variable can be declared 17 structured rectangular Rectangular structured matrix variable depending on other decision variables The second input argument of sdmvar must be a matrix of real or complex integers describing t
40. h L and the fifth R input arguments are declared and are non empty then the added term is LXR or LR variable dependent term or constant term respectively in the block blrow blcol and R X L or R L in the symmetric block b1col bl row e Hermitian If the fourth input argument L is specified and the fifth input argument R is omitted or empty R then the added term is LXL or LL variable dependent term or constant term respec tively This can only be done if the block is on the diagonal and the variable X is Hermitian To show that this syntax simplifies some notations take the constant term in the LMC problem of the previous section B B7 He 5B Bi This term can be equivalently declared with the two following syntaxes sdmineq quiz lmi2index 1 1 0 Bw 0 5 Bw sdmineq quiz lmi2index 1 1 0 Bw When declaring Hermitian terms such as LXL the matrix X is assumed to be Hermitian Otherwise there might be some complications In fact if X is square non Hermitian SEDUMI INTERFACE outputs a warning message and implements by default the term 0 5L X X L 3 2 7 Terms with no multiplying data Quite often some terms of the constraints depend directly on a matrix variable without any dependency on the data of the problem A famous example is the Lyapunov matrix In all control problems the Lyapunov matrix is constrained to be definite positive Q gt 0 In the example of the previous secti
41. he problem is marginally feasible and a string unsolved if SEDUMI was not executed on this LMC problem 12 gt gt quiz sdmsol quiz SeDuMi 1 05 by Jos F Sturm 1998 2001 Alg 2 xz corrector Step Differentiation theta 0 250 beta 0 500 eqs m 16 order n 13 dim 69 blocks 4 nnz A 74 0 nnz ADA 256 nnz L 136 PES b y gap delta rate t tP t tD feas cg cg 73E 0 000 50E 01 1 02E 0 00 81E 00 2 66E 0 00 91E 00 9 37E 0 00 32E 00 2 08E 0 00 47E 01 5 37E 0 00 99E 01 4 72E 0 82E 01 4 05E 0 78E 0 34E 0 75E 0 43E 0 74E 0 66E 0 74E 0 74E 0 73E 0 37E 0 73E 0 81E 0 73E 0 03E 0 73E 0 89E 10 73E 01 3 82E 11 0 00 201 900 73E 01 1 71E 12 0 00 044 990 iter seconds digits c x b y 17 1 1 Inf 2 7287769476e 01 2 7287769465e 01 Ax b 1 1e 09 Ay c _ 0 0E 00 x 4 1e 02 yl 3 0e 02 Max norms b 1 c 1 Cholesky add 0 skip 0 L L 193074 feasible 0588 2614 3520 2225 0257 0879 0859 3316 1067 1852 0003 177 071 030 062 000 900 900 900 900 990 900 900 900 000 900 855 2990 990 2990 900 900 900 912 917 990 917 900 0 14 0 0 1 3 0 4 0 9194 0 8 0 0 0 0 0 0 Pep 28 21 41 41 00 78 78 70 67 24 84 98 00 00 00 a y ol FP eR oo 00 OO OO oR Oo Oo o gt 00 00 00 0 Los 23 Ss 4 Ia Go Yt 8
42. he structure as exposed above The third input argument must be set to the string value st Some examples follow The first example consists in building a new matrix variable that depends only on existing decision variables Assume that the new variable F should be rectangular and composed of the conjugate of a diagonal block and an anti symmetric block as follows F D G where D and G are already defined matrix variables To declare F the commands are gt gt Ddec quiz Dindex gt gt Ddecbar conj Ddec gt gt Gdec quiz Gindex gt gt Fdec Ddecbar Gdec gt gt quiz Findex sdmvar quiz Fdec st D G gt gt num2str quiz Findex ans 16 16i 0 01 0 0i 0 0i 19 01 0 0i 17 17i 0 0i 19 0i 0 01 0 0i 0 0i 18 181 20 01 21 01 The second example consists in building a new matrix variable depending on new not yet declared decision variables Assume that the new variable K should depend on three new independent scalar variables with the following structure Tk 0 k oes ky z where k C k2 R and k3 C The procedure to declare this variable is first to get the number of existing decision variables then to build the structure matrix making reference to the new decision variables and finally to declare the variable using sdmvatr gt gt get quiz vardecnb ans 27 gt gt Kdec 28 28i 0 28 281 30 30i 29 30 301 gt gt quiz Kindex sdmvar qu
43. ions are equivalent R is assumed to be symmetric sdmineq quiz c Rindex sdmineg quiz c Rindex 1 sdmineg quiz c Rindex 1 0 5 but they are not equivalent as in the LMI Control Toolbox to the notation gt gt quiz sdmineq quiz c Rindex 1 1 5 Conclusions SEDUMI INTERFACE makes the interface between a standard LMI formalism and the solver SEDUMI For control applications it is well suited and we are already working on future evolutions We expect potential users to contact us with remarks and possibly pass on some examples to illustrate this report These remarks and contributions may influence the future developments and make the tool more com plete For example since SEDUMI INTERFACE 1 02 both complex LMIs and complex variables have been included to the tool since SEDUMI INTERFACE 1 03 linear matrix equalities can be added to the LMI constraints and since SEDUMI INTERFACE 1 04 block partitioning maximisation of Trace BX are available Among future evolutions are e Concatenation The concatenation of several LMC problems can be viewed as the optimisation problem con structed with all the linear matrix constraints of each LMC problem and where some of the matrix variables are common Such an operator can help for optimisation problems defined over the intersection of feasible domains e Translator Following the example of 19 24 9 the tool can include some translator functionalities in order
44. ix inequalities LMIs and a linear objective Initialise the LMC problem sdmpb Declare the matrix variables sdmvar Declare the block partitioned equality constraints sdmlme and sdmequ Declare the block partitioned inequality constraints sdmlmi and sdminequ Declare the linear objective sdmobj e Solve an LMC problem A unique function sdmsol calls the SEDUMI solver Options allow to tune the solver parameters e Modify an LMC problem At any moment it is possible to append an LMC problem by adding variables inequalities or linear terms to the objective Moreover the sdmset function allows to freeze matrix variables to specified values e Analyse the solution issued from the solver For all feasible or not problems the solver outputs the last computed iterate sdmget SEDUMI INTERFACE allows to analyse this result in a convivial display The solution is displayed directly in matrix format and indicators show which constraints are satisfied 1 6 Installing SEDUMI INTERFACE SEDUMI INTERFACE is composed of simple MATLAB files sdm m gathered in a directory SeDuMiInt104 and a subdirectory sdmpb The first directory contains e sdmguide ps this report e COPYING the GNU general public licence e Contents m the help file for SEDUMI INTERFACE e sdmdemo m the demonstration MATLAB file e sdmupq m sdmvec m sdmmat m sdmrank sdmclear five files called by some of the SE DUMI INTERFACE opera
45. iz Kdec st K gt gt num2str quiz Kindex ans 28 281 0 0i 28 281 30 301 29 01 30 301 18 3 2 Advanced declaration of some inequality terms sdmineq All terms in an LMI constraint can be declared with sdmineq as follows gt gt quiz sdmineq quiz LMIindex blrow blcol Xindex L R The modified LMI constraint is declared by its index LMI index and the matrix variable is referred to by the index Xindex The term LXR is added to the b1row b1co1 block and the Hermitian term R X L is added in the symmetric block blcol blrow If Xindex 0 then the constant terms LR and R L are respectively added in the symmetric blocks Some options to this function are now detailed 3 2 1 Block partitioning For some LMI constraints it may not be necessary to define a block partitioning For example take the first LMI of the previous section It writes as Q gt 0 s He 50 lt 0 It can be declared as previously as if composed of a single block gt gt quiz lmilindex sdmlmi quiz n 0 gt 0 gt gt quiz sdmlmi quiz lmilindex 1 1 Qindex An alternative is to remove all references to the blocks gt gt quiz lmilindex sdmlmi quiz n Q gt 0 gt gt quiz sdmlmi quiz lmilindex Qindex 0 5 Of course the two notations are equivalent But the usage of sdmineq without specifying blocks may also be used for block partitioned LMIs more than one block The rule is
46. l block e Elementary If both the fourth and the fifth input arguments Z and R are omitted then the added term is X Terms with Kronecker products L K X R and L X K R e first Kronecker product KX When the sdmeq operator is called with a sixth input argument K the added term is of the form L K X R e second Kronecker product X K When the sdmeq operator is called with a sixth input argument K and a seventh input argument set to 1 the added term is of the form L X amp K R All these rules can be applied together They are applied for the two examples of equalities assumed at the start of section 3 3 A first declaration writes as eindex Kindex eindex Hindex eindex 0 eindex Qindex eindex 0 eindex ixDindex 26 An equivalent version but more involved writes as elindex Kindex elindex Hindex elindex 0 e2index Qindex e2index 0 e2index i Dindex Analysis of the computed solution To analyse the obtained point the norm data allow to check that every equality constraint is satisfied These data are displayed with the LMC problem table 6 and can also be obtained with the get function as gt gt get quiz eqnorm lmelindex ans eps LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name Y gamma 2 Q diagonal D 6 00 300440 NR D G H J K equality constr
47. m and Control Theory SIAM Studies in Applied Mathematics Philadelphia 1994 N BRIXIUS R SHENG and F A POTRA SDPHA User Guide Department of Computer Sci ence University of Iowa July 1998 URL www cs uiowa edu brixius SDPHA M CHILALI M thodes LMI pour I Analyse et la Synth se Multi Crit re PhD thesis Paris IX Dauphine February 1996 L EL GHAOUI F DELEBECQUE and R NIKOUKHAH LMITOOL a User Friendly Inter face for LMI Optimisation 1995 User s Guide Beta version URL robotics eecs berkeley edu elghaoui 1mitoo1 1mitool html L EL GHAOUI and S I NICULESCU editors Advances in Linear Matrix Inequality Methods in Control Advances in Design and Control SIAM Philadelphia 2000 L EL GHAOUI F OUSTRY and M AITRAMI A Cone Complementarity Linearization Algorithm for Static Ouput Feedback and Related Problems IEEE Trans on Automat Control vol 42 n 8 1997 pages 1171 1176 K FUJISAWA M KOJIMA and K NAKATA SDPA SemiDefinite Programming Algo rithm User s Manual Version 5 00 Tokyo Institute of Technology August 1999 URL ftp ftp is titech ac jp pub OpRes software SDPA P GAHINET A NEMIROVSKI A J LAUB and M CHILALI LMI Control Toolbox User s Guide The Mathworks Partner Series 1995 K M GRIGORIADIS and E B BERAN Advances in Linear Matrix Inequality Methods in Con trol chapter 13 Alternating Projection Algorithms for Linear Matrix
48. mber of rows and the number of columns in the matrix variable The last input argument is optional Itis a label used mainly for nice explicit display OUT The output arguments are first the appended sdmpb object and second an index Yindex that makes reference to the declared variable The index is an integer used later on for various purposes It can be retrieved at any time by the user as follows gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name 1 Y no equality constraint no inequality constraint no linear objective unsolved In this example Y is the first variable with an index equal to 1 For scalar variables the usage of sdmvar is identical Scalar variables are 1 by 1 matrices gt gt quiz gindex sdmvar quiz 1 1 gamma 2 In LMC problems the matrix variables may have some structural properties In our example Q is sym metric The SEDUMI INTERFACE tool makes possible to declare a large variety of structured variables For this purpose see the sdmvar complete description in the following section of this guide Here we expose only how to declare symmetric variables gt gt quiz Qindex sdmvar quiz n s Q To declare symmetric therefore square variables the user sets the third argument of sdmvar to the string r At this stage the LMC problem of the example is characterised by gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis
49. n m The former algorithm is more efficient for problems with a large number of variables This is of major interest when solving large scale problems or when implementing LMI based iterative algorithms as in 11 15 21 14 18 Sparse format SEDUMI takes the SDP problem data in sparse format Therefore the disk space memory needed for defining problems is reduced in the case of structured data The results are satisfying for automatic control problems for which most of the data are sparse Large scale problems This remark is closely related to the two previous ones It appears that SEDUMT is quite competitive for medium size problems and can solve relatively large scale prob lems Complex valued problems Both the data and the variables may be given or constrained with real or complex values At the difference of 8 this is done without increasing the size of the problem Equality constraints SEDUMI allows to declare explicitely linear equality constraints without computing any kernel or artificially defining an equality as two opposite side inequalities e MATLAB Most of the researchers in the control community are used to work with MATLAB It is therefore attractive to have a tool that can be used within the MATLAB environment Free software SEDUMI is developed with an open source free software policy as well as SEDUMI INTERFACE We hope this will encourage the scientific community to support and follow up this initiative Poten
50. nalyse the solution issued from the solver For all feasible or not problems the solver outputs the last computed iterate sdmget SE DUMI INTERFACE allows to analyse this result in a convivial display The solution is displayed directly in matrix format and indicators show which constraints are satisfied This document is an update with respect to SEDUMI INTERFACE 1 01 23 22 SEDUMI INTER FACE 1 02 17 and SEDUMI INTERFACE 1 03 The last major modifications concern the blocks partitioning of LMCs the maximisation of Trace BX where B is a data matrix and the increase of LMC problem construction speed SEDUMI INTERFACE 1 04 Copyright 2002 Dimitri Peaucelle amp Krysten Taitz This program is free software you can redistribute it and or modify it under the terms of the GNU General Public License as published by the Free Software Foundation either version 2 of the License or at your option any later version This program is distributed in the hope that it will be useful but WITHOUT ANY WARRANTY without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE See the GNU General Public License for more details Contents 1 Purpose IEL Notations ic A ee E A A eS 12 EMC problems Wi e eS ei ee eb ee a 1 37 Existing Solvers x a a os e SO nach ee she et a 1 4 Existing Interfaces eeano it Beh Be ee ek Bea Bs eS Gh a ci 15 Functionaliteit as a Sobre ss de fh oh i iG e dr iG AS 1 6 2 Using
51. on this specification is translated into He 30 lt 0 To simplify the declaration of such simple terms the following rule is adopted e elementary terms If the fourth and the fifth input arguments of sdmineq are omitted then the added term is equal to the specified matrix variable 22 Following this rule and the left right rule the declaration of the inequality Q gt 0 has the two equivalent syntaxes sdmineg quiz lmilindex Qindex sdmineq quiz 1milindex Qindex 3 2 8 Terms with Kronecker products L K amp X R and L X K R Sometimes it may happen that the inequality constraint has one or more terms with a Kronecker product between a matrix variable and a data variable Such a product is linear in the variables but is quite tedious to implement It is frequently used to simplify the inequality notations but may complicate the programming Fortunately SEDUMI INTERFACE is designed to tackle the Kronecker products and does it quite fast Two configurations are considered L K X R or L X K R To deal with such terms the sdmineq operator is called with 6 or 7 input arguments one or two more input arguments than for the generic usage The rule is as follows e first Kronecker product K X When the sdmineg operator is called with a sixth input argument K the term L K X R is added to the blrow blcol block and the Hermitian term L K E X R is added to the symmetric blcol blrow block e second Kr
52. onecker product X K When the sdmineg operator is called with a sixth input argument K and a seventh input argument set to 1 the term L X K R is added to the blrow blcol block and the Hermitian term L X K R is added to the symmetric blcol blrow block To illustrate the use of this rule consider the Lyapunov inequalities assessing Hurwitz and Schur stability of a matrix A respectively ATP PA lt 0 and ATPA P lt 0 These two inequality constraints share the common expression 1 1 AT xor 3 J lt c with K i and K a i for Hurwitz and Schur stability respectively Applying both the Kronecker product rule and the symmetric matrix rule the inequality constraint is entirely defined for both stability conditions with the unique command gt gt quiz sdmineq quiz LMIindex Pindex eye n A K 23 3 3 Equality constraints Equality constraints can be defined quite in the same way as the inequality constraints The main differ ence is that equality constraints may not be square and may not be Hermitian For this user s guide the following constraint is used It is a purely fictitious constraints with no relation the the H problem in automatic control 3 1 gt gt i 2i i 24 le loo t le 00 0 17 0 Qan 0 Did 3 3 1 Defining an equality constraint sdmlme To initialise an equality constraint the usage is gt gt quiz lmeindex sdmlme quiz 2 1 3 1 K 0 0 Q
53. ost and is displayed by SEDUMI INTERFACE as shown in table 6 One can expect that since the optimal value is Y y27 2878 the LMC problem also has a solution if y is set to a higher value for example y v30 To check this set the value of y and solve the new LMC problem as shown in table 7 Note that the LMC problem has been transformed from a optimisation problem to a feasibility problem the objective is then equal to zero Moreover note that the variable y was removed from the inequalities but it is still possible to get its fixed value For recursively defined variables some complications may occur when using sdmset Take as an example the variable F defined as the concatenation of two previously defined variables F D G 28 gt gt quiz sdmset quiz gindex 30 gt gt quiz sdmsol quiz gt gt quiz LMC problem Optimal Hinfty State Feedback Synthesis matrix variables index name KA gamma 2 SET TO A CONSTANT Q diagonal D G 1 2 3 4 5 6 7 8 9 D G H J K equality constraints index name 1 K 0 0 Q11 H 0 0 conj D11 1 i inequality constraints index name il Q gt 0 2 Hinfty state feedback maximise objective gamma 2 0 feasible gt gt quiz gindex warning index refers to a variable that was set to a constant ans 30 Table 7 Same LMC problem with a frozen value of y The question is What happens to the variable Y if the value of G is set to a constant The an
54. scription of SEDUMI INTERFACE functions Before that we expose the choices that lead us to choose the SEDUMI solver and an interface much alike the LMI Control Toolbox for MATLAB 13 The user mostly interested in using the interface can skip the remaining part of this section and go directly to section 2 1 1 Notations is the imaginary unit equal to the square root of 1 R XA is the set of m by n real complex matrices 1 and 0 are respectively the identity and the zero matrices of appropriate dimensions All matrices are written using capital letters A while scalars and vectors are in lowercase a A is the conjugate of the complex matrix A A is its transpose and A is its conjugate transpose We remind that in the MATLAB environment the conjugate transpose writes as A while the transpose is obtained by A If A AT the matrix is symmetric and Hermitian if A A For real valued matrices both notions are equivalent He is the matrix operator such that He A A 4A For Hermitian matrices gt gt is the L wner partial order i e A gt gt B if and only if A Bis positive semi definite In matrix equalities and inequalities as well as in optimisation problems the decision variables and unknowns are in bold face x while the data is written using the usual mathematic fonts x Note that in the MATLAB environment real integers are nicely displayed as follows while complex integers are
55. swer is Nothing SEDUMI INTERFACE only modifies the inequalities and the objective that depend explicitly on the vari able whose value is set For recursively defined matrices there is no modification on the copies of the frozen variable This is illustrated in the above example by the fact that if G is frozen its structure matrix becomes empty while the variable F still depends on the same decision variables see table 8 gt gt quiz sdmset quiz Gindex 0 1 1 102 1 2 0 gt gt quiz Gindex Warning index refers to a variable that was set to a constant ans gt gt num2str quiz Findex ans 15 15i 0 0i 0 0i 0 0i 18 0i 0 0i 16 16i 0 0i 18 0i 0 0i 0 0i 0 0i 17 17i 19 0i 20 0i Table 8 Structure of G and F when G is set to a constant 3 6 Tuning the solver parameters To illustrate the influence of some parameters on the solution issued from the SeDuMi solver we chose an example for which some complications are noticed The example is a mixed H gt H state feedback 29 synthesis problem The exact data of this example are not given for conciseness reasons system of order n 10 When solved without any modification of the default solver parameters the result is shown in table 9 gt gt quiz sdmsol quiz LMC problem H2 Hinfty state feedback synthesis matrix variables index name 1 X 2 T 3 S inequality constraints index meig 1 0 005 2 3e 09 3 3e 08 4 eps maximise objective
56. the following e specifying blocks When the second input argument of sdmineq is composed of three entries LMIindex blrow blcol then the term LXR is added to the blrow blcol block and the Hermitian term R X E is added to the symmetric blcol blrow block same comment for constant terms LR e not specifying block If the second input argument of sdmineq is a scalar LMI index then the term LXR is added to the entire LMI so as the Hermitian term R X L same comment for constant terms LR Note that in this case the number of rows of L and the number of columns of R should be equal to the global LMI dimension sum of the blocks dimensions An example of this usage is now described First note that the second LMI of the previous example writes equivalently as He l AQ 5ByBi B e E IS 19 Without modifying any other declaration block decomposition of the LMI block declaration of other terms the Y dependent terms can be equivalently declared either by sdmineq quiz lmi2index 1 1 Yindex Bu sdmineg quiz lmi2index 2 1 Yindex Dzu or with the unique command line gt gt quiz sdmineq quiz lmi2index Yindex Bu Dzu eye n zeros n p The usage of sdmineg without the block partitioning may be useful for LMI constraints where only part of the terms are described with a block partitioning and the others do not explicitely respect this partitioning Any LMI constraint can be seen either
57. tialities In SEDUMI INTERFACE we mainly took advantage of SDP programming But SE DUMI has other potentialities It can deal simultaneously with linear programming and quadratic cones These potentialities will be integrated into SEDUMI INTERFACE in the future depending on possible feedback remarks 1 4 Existing Interfaces Quite few LMI interfaces for SDP solvers are available The most famous is the software in the LMI Control Toolbox 13 Then comes the sdpsol software 29 which is associated to the SP solver 28 and the LMITOOL package 9 which calls three different solvers SP 28 SDPHA 7 and SDPPack 1 All three interfaces work in MATLAB environment Except the plurality of the solvers the difference between these three interfaces is the way LMCs are declared They all adopt different formalisms LMITOOL is purely a graphical user interface GUD tool and is nice and convivial As a by product the transformation of data into the various solver formalisms is quite slow The LMC problems are often faster solved than converted to the convenient format For the sdpsol interface the speed results are less patent The LMIs are declared in a text file in a natural way They are then interpreted by the interface The speed of the interpretation is more efficient than for LMITOOL but still is not convenient for large scale problems At last a GUI is also available in the LMI Control Toolbox 13 but it is less convivial than the two form
58. tors The subdirectory sdmpb contains the 14 essential operators for LMC problem declaration The interface works with MATLAB version 5 3 or more and with SEDUMI version 1 05 We assume that one of these two versions of the software is installed on your computer If it is not the case refer to the instructions at http fewcal kub nl sturm software sedumi html To install the SEDUMI INTERFACE you only have to link it to your MATLAB path In the MATLAB environment this can be done with the following command gt gt path path TheDirectoryWherelputIt SeDuMiInt104 Then test if SEDUMI INTERFACE and SEDUMI are properly installed by typing gt gt sdmdemo Demonstration examples of SEDUMI INTERFACE are then run One follows the example in this user s guide The other describes the declaration of a H2 H state feedback problem from control theory The example is run for a random problem of large size It demonstrates the nice convergence speed of SEDUML1 2 Using SEDUMI INTERFACE Getting started 2 1 LMC problem an sdmpb object An LMC problem within SEDUMI INTERFACE is described by a single MATLAB variable It contains all the information on the matrix variables the inequality and equality constraints the linear objective and the optimal solution The various fields containing this information are assigned as the LMC problem is declared and then solved We do not enter here in the detail of the structure of this object The us
59. value to some variable sdmset o ee ee Tuning the solver parameters a 3 6 1 SeDUMIparameters m seri ee a Re Pt A ea le Soe BS 3 6 2 Definite and semi definite inequalities o ooa 3 6 3 Feasibility radius e mail ann Bae ae ede Foes ER 4 Warnings for MATLAB LMI Toolbox users 4 1 4 2 Left and right sides of an inequality o e e e Matrix and scalar multipliers for inequality terms o o 5 Conclusions References 15 15 19 19 20 21 21 22 22 22 23 24 24 25 28 28 29 30 31 32 33 33 34 34 35 1 Purpose The tool described in this report is designed to associate both efficient Semi Definite Programming SDP algorithms and the nice Linear Matrix Constraint LMIs and LMEs formalism used for control applica tions This work was inspired by the observation that on the one hand Linear Matrix Constraints LMCs have a major position in current academic research 6 10 27 and on the other hand there are new promising tools for solving relatively large scale SDP problems 20 But there are few tools that asso ciate both an efficient SDP solver and a pleasant interface for declaring LMC problems within the most commonly used software environment MATLAB SEDUMI INTERFACE is designed as an add on for MATLAB and allows to declare LMC problems to be solved with the SEDUMI solver proposed by Jos Sturm 25 The major part of this report is a de

Download Pdf Manuals

Related Search

Related Contents

Samsung NP910S5JI Käyttöopas (Windows 7)  Port of RedHat eCos to the CubeSat Computer  Use o 1/4" drill bit to drill mounting hole locations. For  SAHM User`s Manual - Sacramento Stormwater Quality Partnership  

Copyright © All rights reserved. Failed to retrieve file