Home

SOSTOOLS - Control & Dynamical Systems

1. gt 0 i dz x gt 0 3 6 However several differences do exist In particular a third argument can be given to sosineq to handle the following cases e When there is only one independent variable in the SOSP i e if the polynomials are uni variate a third argument can be given to specify the range of independent variable for which We remind you that a gt 0 has to be interpreted as a being a sum of squares See the discussion in Section 1 1 22 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS the inequality constraint has to be satisfied For instance assume that p and Program2 are respectively univariate polynomial and univariate SOSP then gt gt Program2 sosineq Program2 diff p x x72 1 21 will add the constraint A La s for 1 lt x lt 2 3 7 Ox to the SOSP See Sections 3 7 and 3 8 for application examples where this option is used When the left side of the inequality is a high degree sparse polynomial i e containing a few nonzero terms it is computationally more efficient to impose the SOS condition using a reduced set of monomials see 19 in the Gram matrix form This will result in a smaller size semidefinite program which is easier to solve By default SOSTOOLS does not try to obtain this optimal reduced set of monomials since this itself takes an additional amount of computational effort however SOSTOOLS always does some reasonably efficient and computationally cheap he
2. Create the polynomial P Z monomials x 0 ndeg 1 prog P1 sospolyvar prog Z P Pi gam x ndeg The leading coeff of P is gam Imposing the inequalities prog sosineq prog 1 P prog sosineq prog 1 P o LJ 1 1 11 And setting objective prog sossetobj prog gam Then solve the program prog sossolve prog Finally get solution SOLV sosgetsol prog P GAM sosgetsol prog gam echo off Figure 4 8 Chebyshev polynomials sosdemo7 m 4 8 BOUNDS IN PROBABILITY AT distribution We refer the reader to the work of Bertsimas and Popescu 1 for a detailed discussion of the general case as well as references to earlier related work Consider an unknown arbitrary probability distribution q x with support in x 0 5 We know that its mean p is equal to 1 and its standard deviation o is equal to 1 2 The question is what is the worst case probability over all feasible distributions of a sample having x gt 4 Using the tools in 1 it can be shown that a bound on or in this case the optimal worst case value can be found by solving the optimization problem SOSDEMOS Minimize amo bm cm2 subject to br cx gt 0 Wzel 0 5 br cx gt 1 Vere 4 5 where mo 1 m u and ma u o The optimization problem above is clearly an SOSP and is implemented in sosdemo8 m shown in Figure 4 9 The optimal bound computed from
3. Set objective maximize gam prog sossetobj prog gam And call solver prog sossolve prog Finally get solution SOLgamma sosgetsol prog gam echo off Figure 4 3 Bound on global extremum sosdemo3 m 37 38 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING A lower bound for f x can be computed using Positivstellensatz based relaxations Assume that there exists a set of sums of squares o x s and a set of polynomials x s such that f z y co z e hj x Dolo gil oir ia gis E E 47 11 12 then it follows that y is a lower bound for the constrained optimization problem stated above This specific kind of representation corresponds to Schmiidgen s theorem 21 By maximizing y we can obtain a lower bound that becomes increasingly tighter as the degree of the expression 4 7 is increased As an Ha a consider the problem of minimizing x x2 subject to x gt 0 z2 gt 0 5 ry 23 1 2 x 0 5 0 A lower bound for this problem can be computed using SOSTOOLS as follows gt gt syms xi x2 gt gt degree 4 gt gt gam vars opt findbound x1 x2 x1 x2 0 5 x172 x272 1 x2 x172 0 5 degree In the above command degree is the desired degree for the expression 4 7 The function findbound will automatically form the products gi 1 g x 9i X Gin X gig x and so on and then construct the sum of squares and polynomial multiplier
4. clear echo on syms x1 x2 vartable x1 x2 This is the problem data p x172 x272 gamma 1 go 2 0 x1 x2 theta 1 Y gt Initialize the sum of squares program prog sosprogram vartable pe The multiplier Zmon monomials vartable 0 4 prog s sospolymatrixvar prog Zmon 1 1 Y ae Term to be added to g0 Zmon monomials vartable 2 3 prog g1 sospolymatrixvar prog Zmon 1 1 Yo ESESES The expression to satisfy the set containment Sc theta 2 s gamma p g0 g1 g0 g1 1 prog sosmatrixineq prog Sc eps eye 2 option solver sdpt3 option params vers 2 option params gaptol le 7 prog sossolve prog option s sosgetsol prog s gl sosgetsol prog g1 Program is feasible x g0 g1 theta theta g0 g1 gt 0 contains x p lt gamma echo off Figure 4 11 Set containment sosdemo10 m 52 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING Chapter 5 Inside SOSTOOLS In this chapter the data structures that underpin SOSTOOLS are described The information in this section can help advanced users to manipulate the sosprogram structure in order to create additional functionality It is assumed from this point on that the user has a strong working knowledge of the functions descr
5. prog Q i sossosvar prog Z end Figure 4 5 Upper bound of structured singular value sosdemo5 m part 1 of 2 4 6 MAX CUT 43 4 r s constant sum of squares Z monomials vartable 0 r cell 4 4 for i 1 4 for j i 1 4 prog r i j sossosvar prog Z wscoeff Next define SOSP constraints Constraint sum Qi x Ai x sum rij Ai x Aj x I x gt 0 expr 0 Adding term for i 1 4 expr expr Af it Q i end for i 1 4 for j i 1 4 expr expr Afi A j r i j end end Constant term I x x1 4 x874 I sum vartable 4 expr expr I prog sosineq prog expr And call solver prog sossolve prog Program is feasible thus 0 8724 is an upper bound for mu echo off Figure 4 6 Upper bound of structured singular value sosdemo5 m part 2 of 2 44 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING For sosdemo6 m see Figure 4 7 we consider the 5 cycle i e a graph with 5 nodes and 5 edges forming a closed chain The number of cut is given by f x 2 5 0 52122 0 52223 0 54324 0 52425 0 52521 4 17 Our SOSP is as follows SOSDEMO6 6 Choose a fixed value of y For f x given in 4 17 find il y sum of squares p 1 A Q A polynomials p 1 1 of degree 2 for i 1 n such that 4 16 is satisfied Using sosdemo6 m we can show that f x lt 4 Four is indeed
6. wscoeff Next define SOSP constraints Constraint 1 V x x172 x272 x3 2 gt 0 prog sosineqg prog V x172 x272 x3 2 Constraint 2 dV dx x372 1 f gt 0 expr diff V x1 f 1 diff V x2 f 2 diff V x3 f 3 x372 1 prog sosineq prog expr And call solver sprog sossolve_PREV prog prog sossolve prog Finally get solution SOLV sosgetsol prog V echo off Figure 4 2 Lyapunov function search sosdemo2 m 36 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING method can be formulated as follows Suppose that there exists a scalar y such that f z y gt 0 is an SOS then we know that f x gt y for every x R In this example we will use the Goldstein Price test function 8 which is given by f z 1 z1 2 1 7 19 142 3x7 1429 61 22 322 30 2x1 3x2 18 32x1 121 48x2 362119 2743 The SOSP for this problem is SOSDEMOS Minimize y such that Figure 4 3 depicts the MATLAB code for this problem The optimal value of y as given by SOSTOOLS is Yopt 3 This is in fact the global minimum of f x which is achieved at z 0 r2 1 The function findbound is provided by SOSTOOLS and can be used to find a global lower bound for a polynomial This function takes just one argument the polynomial to be minimized The function will return a lower bound which may possibly be
7. Calling findsos with the argument M will will return the Gram matrix Q the vector of monomials Z and the decomposition H such that M z H z H z I 8 Z 2 Q 1 8 Z 2 where J denotes the r dimensional identity matrix In order to illustrate this functionality con sider the following code for which we extract the SOS matrix decomposition from a solution to a SOS program with matrix constraints 3 5 SETTING AN OBJECTIVE FUNCTION 27 gt gt syms x1 x2 x3 gt gt x x1 x2 x3 gt gt prog sosprogram x gt gt prog M sospolymatrixvar prog monomials x 0 2 3 3 symmetric gt gt prog sosmatrixineq prog M x172 x2 2 x3 2 xeye 3 Mineq gt gt prog sossolve prog gt gt M sosgetsol prog M gt gt Q Z H findsos M 3 5 Setting an Objective Function The function sossetobj is used to set an objective function in an optimization problem The objective function has to be a linear function of the decision variables and will be minimized by the solver For instance if a and b are symbolic decision variables in an SOSP named Program4 then gt gt Program4 sossetobj Program4 a b will set minimize a b 3 9 as the objective of Program4 Sometimes you may want to minimize an objective function that contains one or more re served variables coeff_nnn which are created by sospolyvar or sossosvar These variables are not individually available in the
8. Nonlinear Systems Prentice Hall Inc second edition 1996 M Kojima Sums of squares relaxations of polynomial semidefinite programs research report b 397 Technical report Dept of Mathematical and Computing Science Tokyo Institute of Technology Tokyo Japan 2003 J B Lasserre Global optimization with polynomials and the problem of moments SIAM J Optim 11 3 796 817 2001 Y Nesterov Squared functional systems and optimization problems In J Frenk C Roos T Terlaky and S Zhang editors High Performance Optimization pages 405 440 Kluwer Academic Publishers 2000 A Packard and J C Doyle The complex structured singular value Automatica 29 1 71 109 1993 63 64 14 15 16 17 18 19 20 21 22 23 24 ea 25 29 BIBLIOGRAPHY P A Parrilo Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization PhD thesis California Institute of Technology Pasadena CA 2000 Available at http www control ethz ch parrilo pubs index html P A Parrilo Semidefinite programming relaxations for semialgebraic problems Mathematical Programming Ser B 96 2 293 320 2003 P A Parrilo and S Lall Semidefinite programming relaxations and algebraic op timization in Control Lecture notes for the CDC 2003 workshop Available at http control ee ethz ch parrilo cdc03_workshop Dec 2003 V Powers and T W rmann An al
9. coeff_3 coeff_4 gt gt Q Q coeff 5 coeff 6 coeff 6 coeff 7 To declare a symmetric matrix where the elements are homogenous quadratic polynomials the function sospolymatrixvar is called with the following arguments gt gt prog R sospolymatrixvar prog monomials x 2 2 2 gt gt R 1 1 coeff_8 x172 coeff_9 x1 x2 coeff_10 x272 gt gt R 1 2 ans coeff_11 x172 coeff_12x x1 x2 coeff_13 x272 3 4 ADDING CONSTRAINTS 21 gt gt R 2 1 ans coeff_11 x1 2 coeff_12 x1 x2 coeff 13 x272 gt gt R 2 2 ans coeff_14 x172 coeff_15 x1 x2 coeff_16 x272 In the next section it will be shown how these matrix variables can be incorporated as constraints in sum of squares optimization problems 3 4 Adding Constraints Sum of squares program constraints such as 2 3 2 4 are added to a sum of squares program using the functions soseq and sosineq 3 4 1 Equality Constraints For adding an equality constraint to a sum of squares program you must use the function soseq As an example assume that p is an SOSP variable then gt gt Program9 soseqg Program9 diff p x x 2 will add the equality constraint o gh ae 0 3 5 to Program9 3 4 2 Inequality Constraints Inequality constraints are declared using the function sosineq whose basic syntax is similar to soseq For example type gt gt Programi sosineg Programi diff p x x 2 to add the inequality constraint Op J
10. 2 GETTING STARTED WITH SOSTOOLS thing to keep in mind is that while being stricter the condition that f x is SOS is much more computationally tractable than nonnegativity 14 At the same time practical experience indicates that replacing nonnegativity with the SOS property in many cases leads to the exact solution The SOS condition 2 1 is equivalent to the existence of a positive semidefinite matrix Q such that p x Z 1 QZ 0 2 2 where Z x is some properly chosen vector of monomials Expressing an SOS polynomial using a quadratic form as in 2 2 has also been referred to as the Gram matrix method 5 17 As hinted above sums of squares techniques can be used to provide tractable relaxations for many hard optimization problems A very general and powerful relaxation methodology intro duced in 14 15 is based on the Positivstellensatz a central result in real algebraic geometry Most examples in this manual can be interpreted as special cases of the practical application of this general relaxation method In this type of relaxations we are interested in finding polynomials pila i 1 2 N and sums of squares p x for i 1 N such that a j x Dome ale 0 for j no ledd where the a j x s are some given constant coefficient polynomials Problems of this type will be termed sum of squares programs SOSP Solutions to SOSPs like the above provide certificates or Positivstellensatz refutation
11. Inequalities LMIs An LMI corresponds to a degree zero polynomial matrix The following example illustrates how 3For this reason Mvar should not be used as a variable name 26 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS SOSTOOLS can be used as an LMI solver Consider the LTI dynamical system Eat Ax t 3 8 where x t R It is well known that 3 8 is asymptotically stable if and only if there exists a positive definite matrix P R such that ATP PA lt 0 The code below illustrates how this can be implemented in SOSTOOLS gt gt syms x gt gt G rss 4 2 2 gt gt A G a gt gt eps le 6 I eye 4 gt gt prog sosprogram x gt gt prog P sospolymatrixvar prog monomials x 0 4 4 symmetric gt gt prog sosmatrixineq prog P eps I1 quadraticMineq gt gt deriv A P PxA gt gt prog sosmatrixineq prog deriv eps I1 quadraticMineq gt gt prog sossolve prog gt gt P double sosgetsol prog P gt gt A 1 2083 0 6003 0 0488 0 2103 0 6003 1 6257 0 1917 0 0031 0 0488 0 1917 2 1235 1 0333 0 2103 0 0031 1 0333 1 6770 0 5612 0 1350 0 0190 0 0542 0 1350 0 4675 0 0288 0 0003 0 0190 0 0288 0 4228 0 1768 0 0542 0 0003 0 1768 0 4984 NOTE The custom function findsos see example in Section 4 1 of SOSTOOLS v3 00 is overloaded to accept matrix arguments Let M be a given symmetric polynomial matrix of dimension r x r
12. We illustrate its usage below Running gt gt syms X y gt gt p 4xx 4x y 6 x 2 x y 2 y 2 gt gt Q Z findsos p rational we obtain a rational sum of squares representation for p x y given by y Tet 0 01 y 7 Hi 0 1 0 2 0 z ry 4 0 0 0 xy xy 0 2 0 2 0 xy xy 1 0 0 0 4 xy where the matrix is given by the symbolic variable Q and Z is the vector of monomials When polynomial object is used three output arguments should be given to findsos gt gt pvar x y gt gt p 4 x 4 y 6 x 2 x y 2 y 2 gt gt Q Z D findsos p rational In this case Q is a matrix of integers and D is a scalar integer The variables are related via p z 4 527 e 0 Q2 0 9 4 2 Lyapunov Function Search The Lyapunov stability theorem see e g 9 has been a cornerstone of nonlinear system analysis for several decades In principle the theorem states that a system x f x with equilibrium at the origin is stable if there exists a positive definite function V x such that the derivative of V along the system trajectories is non positive We will now show how to search for Lyapunov function using SOSTOOLS Consider the system E 3 2 21 2 a Ea 12 1 T2 l 4 2 A 31 2 23 T3 ari IT T3 4 2 LYAPUNOV FUNCTION SEARCH SOSDEMO1 Sum of Squares Test Section 3 1 of SOSTOOLS User s Manual h clear echo on syms x1 x2 vartable x1 x2 First initialize the s
13. affine dimension than the number of variables this case occurs for instance for homogeneous polynomials where the sum of the degrees is equal to a constant in which case a projection to a lower dimensional space is performed prior to the convex hull computation 24 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS 3 4 4 Multipartite Structure In this section we concentrate on a particular structure of polynomials that appears frequently in robust control theory when considering for instance Lyapunov function analysis for linear systems with parametric uncertainty For such a case the indeterminates that appear in the Lyapunov conditions are Kronecker products of parameters zeroth order and higher and state variables second order This special structure should be taken into account when constructing the vector Z a used in the sum of squares decomposition p x Z QZ x Let us first define what we mean by a multipartite polynomial A polynomial p x R x1 Xn in _ m indeterminates where x 1 Cim given by P t D cox xp o xin a is termed multipartite if for alli gt 2 Qik is constant i e the monomials in all but one partition are of homogeneous order In other words a multipartite polynomial is homogenous when fixing any n 1 blocks of variables always including the first block This special structure of p x can be taken into account through its Newton polytope It has been argued in an earlier
14. be used with multiple inequalities 57 There is one further field prog extravar which SOSTOOLS creates This field has the fol lowing entries gt gt prog extravar prog extravar num 2 Z 41 3x3 double 13x3 double ZZ 6x3 double 52x3 double T 9x6 double 169x52 double idx 4 13 182 At this point all the variables have been defined and both constraints and an objective function if desired have been set the SOSP is ready to be solved This is done using the function gt gt prog sossolve prog which calls the SDP solver and then converts the solution data back into SOSP form However the original SDP problem and solution data is stored by SOSTOOLS in the field prog solinfo which contains the subfields gt gt prog solinfo prog solinfo x 181x1 double y 58x1 double RRx 181x1 double RRy 181x1 double info 1x1 struct solverOptions 1x1 struct var 1x1 struct extravar 1x1 struct decvar 1x1 struct It is worth remembering that in general users do not need to know how to access use or even interpret this data as all the polynomial variables can be accessed via the sosgetsol function For example gt gt V sosgetsol prog V Y 6 6582 x 2 4 5965y 2 2 0747 z 2 However there may be occasions when the user would like the specific sum of squares decomposition or indeed the SDP form of the solution Before describing how this is done we explain w
15. have seen in the previous subsection that for declaring SOSP variables using sospolyvar we need to construct a vector whose entries are monomials While this can be done by creating the individual monomials and arranging them as a vector SOSTOOLS also provides a function named monomials that can be used to construct a column vector of monomials with some pre specified degrees This will be particularly useful when the vector contains a lot of monomials The function takes two arguments the first argument is a vector containing all independent variables in the monomials and the second argument is a vector whose entries are the degrees of monomials that you want to create As an example to construct a vector containing all monomials in x and y of degree 1 2 and 3 type the following command gt gt VEC monomials x y 1 2 31 18 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS VEC x y H2 xx y y72 8 x 2 y x y 2 y73 We clearly see that VEC contains all monomials in x and y of degree 1 2 and 3 For some problems such as Lyapunov stability analysis for linear systems with parametric uncertainty it is desirable to declare polynomials with a certain structure called the multipartite structure See Section 3 4 4 for a more thorough discussion on this kind of structure Multipar tite polynomials are declared using a monomial vector that also has multipartite structure To construct multipartite monomial ve
16. is feasible The matrix J is copositive echo off Figure 4 4 Matrix copositivity sosdemo4 m 4 6 MAX CUT 41 SOSDEMOS Choose a fixed value of y For I x and A x as described in 4 12 4 15 find sums of squares Quiz a Qi fori 1 2n Tij 0 zero order SOS for 1 lt i lt j lt 2n such that 4 10 is satisfied The optimal value of y can be found for example by bisection In sosdemo5 m Figures 4 5 4 6 we consider the following M from 13 a 0 0 a M UV U V E Cc Jc C JC d f jf d with a y 2 a b c 1 va d y b a f 1 3 41 08 a 3 v3 B V3 1 It is known that u M A 0 8723 Using sosdemo5 m we can prove that u M A lt 0 8724 4 6 MAX CUT We will next consider the MAX CUT problem MAX CUT is the problem of partitioning nodes in a graph into two disjoint sets Vi and V2 such that the weighted number of nodes that have an endpoint in V and the other in Va is maximized This can be formulated as a boolean optimization problem 1 1 2 0 sel 2 2 wl a 5 or equivalently as a constrained optimization Here wij is the weight of edge connecting nodes 7 and j For example we can take w 0 if nodes i and j are not connected and w 1 if they are connected If node i belongs to Vi then x 1 and conversely x 1 if node is in Va A sufficient condition for max 2_ f x lt y is as follows Assume that our graph contains
17. oo a vector with the variables of the polynomial and if an additional condition is satisfied the dual solution has rank one also a point where the bound is achieved Thus for example to compute a global minimum for the polynomial F af 1 bf D c 1 d 1 2a 3b 4c 5d you would type gt gt syms abc d gt gt F a 4 1 b 4 1 c 4 1 d 4 1 2xa 3xb 4xc 5xd gt gt bnd vars xopt findbound F For this problem a polynomial of total degree 16 in four variables SOSTOOLS returns a certified lower bound bnd 7 759027 and also the corresponding optimal point in less than thirty seconds In the current version findbound can also be used to compute bounds for constrained poly nomial optimization problems of the form minimize f x subject to g x gt 4 3 GLOBAL AND CONSTRAINED OPTIMIZATION 7 SOSDEMO3 Bound on Global Extremum Section 3 3 of SOSTOOLS User s Manual clear echo on syms x1 x2 gam vartable x1 x2 First initialize the sum of squares program prog sosprogram vartable Declare decision variable gam too prog sosdecvar prog gam Next define SOSP constraints Constraint r x f x gam gt 0 x is the Goldstein Price function f1 x1 x2 1 f2 19 14 x1 3 x172 14 x2 6 x1 x2 3 x27 2 3 2 x1 3 x2 f4 18 32 x1 12 x172 48x x2 36 x1 x2 27 x272 f 1 f172xf2 30 f372xf4 prog sosineq prog f gam
18. the maximum cut for 5 cycle 4 7 Chebyshev Polynomials This example illustrates the sosineq range specification option for univariate polynomials see Section 2 4 2 and is based on a well known extremal property of the Chebyshev polynomials Consider the optimization problem SOSDEMO7 Let pn x be a univariate polynomial of degree n with y being the coefficient of x Maximize y subject to lpn x lt 1 Va e 1 The absolute value constraint can be easily rewritten using two inequalities namely 1 pn x 2 0 Lp ee 02 Va 1 1 The optimal solution is y 2 with pi x arccos cos nx being the n th Chebyshev polyno mial of the first kind Using sosdemo7 m shown in Figure 4 8 the problem can be easily solved for small values of n say n lt 13 with SeDuMi aborting with numerical errors for larger values of n This is due to the ill conditioning of the problem at least when using the standard monomial basis 4 8 Bounds in Probability In this example we illustrate how the sums of squares programming machinery can be used to obtain bounds on the worst case probability of an event given some moment information on the 4 8 BOUNDS IN PROBABILITY SOSDEMO6 MAX CUT Section 3 6 of SOSTOOLS User s Manual clear echo on syms x1 x2 x3 x4 x5 vartable x1 x2 x3 x4 x5 Number of cuts f 2 5 0 5 x1 x2 0 5 x2 x3 0 5 x3 x4 0 5 x4 x5 0 5 x5 x1 Boolean const
19. the optimization problem is equal to 1 37 with the optimal polynomial being a ba ca Bey The worst case probability distribution is atomic 36 1 11 g z 37 0 12 a l 4 Al these values actually their floating point approximations can be obtained from the numerical solution obtained using SOSTOOLS 48 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING SOSDEMO8 Bounds in Probability Section 3 8 of SOSTOOLS User s Manual clear echo on syms xa bc The probability adds up to one m0 1 Mean mi 1 Variance sig 1 2 h E x72 m2 sig 2 m172 Support of the random variable R 0 5 Event whose probability we want to bound E 4 5 Y Constructing and solving the SOS program prog sosprogram x a b c P a b x C X72 Nonnegative on the support prog sosineq prog P R Greater than one on the event prog sosineq prog P 1 E The bound bnd a mO b mi c m2 Objective minimize the bound prog sossetobj prog bnd prog sossolve prog A eee Get solution BND sosgetsol prog bnd 16 PP sosgetsol prog P echo off Figure 4 9 Bounds in probability sosdemo8 m 4 9 SOS MATRIX DECOMPOSITION 49 4 9 SOS Matrix Decomposition This example illustrates how SOSTOOLS v3 00 can be used to determine if an r x r polynomial matrix P is an SOS mat
20. to keep in mind the possible gap between nonnegativity and SOS Besides pure feasibility the other natural class of problems in convex SOS programming involves optimization of an objective function that is linear in the coefficients of p x s The general form of such optimization problem is as follows OPTIMIZATION Minimize the linear objective function where c is a vector formed from the unknown coefficients of polynomials p 1 fori 1 2 N sums of squares p x for i N 1 N such that N ao j x X pi a ai x 0 for J 1 2 sn i 1 N ag j S gt pi a ai j x are sums of squares gt 0 1 1 forj J HD J 2 J In this formulation w is the vector of weighting coefficients for the linear objective function Both the feasibility and optimization problems as formulated above are quite general and in specific cases reduce to well known problems In particular notice that if all the unknown poly nomials p are restricted to be constants and the a b are quadratic forms then we exactly recover the standard linear matrix inequality LMI problem formulation The extra degrees of freedom in SOS programming are actually a bit illusory as every SOSP can be exactly converted to an equivalent semidefinite program 14 Nevertheless for several reasons the problem specifica tion outlined above has definite practical and methodological advantages and establishes a useful framework within w
21. used in the Gram matrix form For the same polynomial as above we may as well type gt gt Q Z findsos p to find Q and Z x such that p x Z x QZ x If p x is not a sum of squares the function will return empty Q and Z 31 32 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING For certain applications it is particularly important to ensure that the SOS decomposition found numerically by SDP methods actually corresponds to a true solution and is not the result of roundoff errors This is specially true in the case of ill conditioned problems since SDP solvers can sometimes produce in this case unreliable results There are several ways of doing this for instance using backwards error analysis or by computing rational solutions that we can fully verify symbolically Towards this end we have incorporated an experimental option to round to rational numbers a candidate floating point SDP solution in such a way to produce an exact SOS representation of the input polynomial which should have integer or rational coefficients The procedure will succeed if the computed solution is well centered far away from the boundary of the feasible set the details of the rounding procedure will be explained elsewhere Currently this facility is available only through the customized function findsos by giving an additional input argument rational On future releases we may extend this to more general SOS program formulations
22. 3 4 3 Exploiting Sparsity For a polynomial p x the complexity of computing the sum of squares decomposition p x Y p x or equivalently p x Z x T QZ x where Z x is a vector of monomials see 14 for details depends on two factors the number of variables and the degree of the polynomial However when p x has special structural properties the computation effort can be notably simplified through the reduction of the size of the semidefinite program removal of degeneracies and better 3 4 ADDING CONSTRAINTS 23 2 1 3 4 Figure 3 1 Newton polytope for the polynomial p x y 4x y 1 xy y left and possible monomials in its SOS decomposition right numerical conditioning Since the initial version of SOSTOOLS Newton polytopes techniques have been available via the optional argument sparse to the function sosineq The notion of sparseness for multivariate polynomials is stronger than the one commonly used for matrices While in the matrix case this word usually means that many coefficients are zero in the polynomial case the specific vanishing pattern is also taken into account This idea is formalized by using the Newton polytope 24 defined as the convex hull of the set of exponents considered as vectors in R It was shown by Reznick in 19 that Z x need only contain monomials whose squared degrees are contained in the convex hull of the degrees of monomials in p x Consequ
23. Constrained Optimization o AA Matrix Coposibiviby usa med aa e e de a PR hae ee Ge eS 4 5 Upper Bound of Structured Singular Value 2 46 MAX GUT ces seg lr od ee ag A ee RD POR RUE dee ee 3 4 7 Chebyshev Polynomials 00 0 eee ee 4 8 Bounds in Probability 2 044 5 45 064 AH eo awe ee E E RA 4 9 SOS Matrix Decomposition s easa 000000 ae ioa a aa ee al o 10 11 13 13 15 15 15 16 dea 18 19 21 21 21 22 24 25 27 27 29 CONTENTS 4 A IO Set Containment sino aa a BO a do uD A 50 5 Inside SOSTOOLS 53 61 6 List of Functions Chapter 1 About SOSTOOLS v3 00 It has been almost ten years since the original release of SOSTOOLS During this time much has changed the number of applications that sum of squares programming has found is enormous and so is the the size and complexity of the resulting optimization problems Moreover the software which SOSTOOLS relies on i e the SDP solvers and symbolic engines have also been evolving the latter of these being the primary primary cause for the latest release Previous versions of SOSTOOLS relied upon the MATLAB Symbolic Math Toolbox When SOSTOOLS was first released the Symbolic Math Toolbox that MATLAB used was the MAPLE engine which performed all symbolic manipulations Recently however MATLAB has switched from the MAPLE engine to a MuPAD engine which has a significantly different syntax In addition to this there
24. MATLAB workspace by default You must give the argument gt wscoeff to the corresponding sospolyvar or sossosvar call in order to have these variables available in the MATLAB workspace This has been described in Section 2 3 2 3 6 Calling Solver A sum of squares program that has been completely defined can be solved using sossolve m For example to solve Program5 the command is gt gt Program5 sossolve Program5 options This function converts the SOSP into an equivalent SDP calls the solver defined in field options solver with solver specific options as fields of the structure options params e g when setting SeDuMi in options solver it is possible to define the tolerance by setting field options params tol and con verts the result given by the semidefinite programming solver back into solutions to the original SOSP Default values for solver and parameters are used when calling sossolve m with only one argument as gt gt Program5 sossolve Program5 or when the input options does not contain fields options or params An example illustrating the a user defined solver and its options is given in Section 4 10 Typical output that you will get on your screen is shown in Figure 3 2 Several things deserve some explanation e Size indicates the size of the resulting SDP 28 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS e Residual norm is the norm of numerical error in the solution e pinf 1 or dinf 1 indicate primal
25. O6P CHAPTER 6 LIST OF FUNCTIONS Sum of squares test Lyapunov function search Bound on global extremum Matrix copositivity Upper bound for the structured singular value mu MAX CUT Chebyshev polynomials Bound in probability Sum of squares matrix decomposition Set containment Bibliography 1 D Bertsimas and I Popescu Optimal inequalities in probability A convex optimization approach INSEAD working paper available at http www insead edu facultyresearch tm popescu 1999 2001 B Borchers CSDP A C library for semidefinite programming Optimization Methods and Software 11 1 4 613 623 1999 S Boyd and L Vandenberghe Convex Optimization Cambridge University Press 2004 M D Choi T Y Lam and B Reznick Real zeros of positive semidefinite forms I Mathe matische Zeitschrift 171 1 1 26 1980 M D Choi T Y Lam and B Reznick Sum of squares of real polynomials Proceedings of Symposia in Pure Mathematics 58 2 103 126 1995 G E Dullerud and F Paganini A Course in Robust Control Theory A Convex Approach Springer Verlag NY 2000 K Fukuda CDD CDD reference manual 2003 Institute for Operations Research Swiss Federal Institute of Technology Lausanne and Z rich Switzerland Program available at http www ifor math ethz ch staff fukuda A A Goldstein and J F Price On descent from local minima Mathematics of Computation 25 569 574 1971 H K Khalil
26. SOSTOOLS Sum of Squares Optimization Toolbox for MATLAB User s guide Version 3 00 3rd October 2013 Antonis Papachristodoulou James Anderson Giorgio Valmorbida Stephen Prajna Peter Seiler Pablo A Parrilo Department of Engineering Science University of Oxford Oxford U K 2Control and Dynamical Systems California Institute of Technology Pasadena CA 91125 USA 3 Aerospace and Engineering Mechanics Department University of Minnesota Minneapolis MN 55455 0153 USA Laboratory for Information and Decision Systems Massachusetts Institute of Technology Massachusetts MA 02139 4307 USA Copyright C 2002 2004 2013 A Papachristodoulou J Anderson G Valmorbida S Prajna P Seiler P A Parrilo 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 You should have received a copy of the GNU General Public License along with this program if not write to the Free Software Foundation Inc 59 Temple Place Suite 330 Boston MA 02111 1307 USA Contents 1 About SOSTOOLS v3 00 2 Get
27. STOOLS some is generated by SeDuMi 3 7 GETTING SOLUTIONS 29 3 7 Getting Solutions After your sum of squares program has been solved you can get the solutions to the program using sosgetsol m The function takes two arguments where the first argument is the SOSP and the second is a symbolic expression which typically will be an SOSP variable All decision variables in this expression will be substituted by the numerical values obtained as the solution to the corresponding SDP Typing gt gt SOLp1 sosgetsol Program6 p1 where p1 is an polynomial variable for example will return in SOLp1 a polynomial with some numerical coefficients which is obtained by substituting all decision variables in p1 by the numerical solution to the SOSP Problem6 provided this SOSP has been solved beforehand By default all the numerical values returned by sosgetsol will have a five digit presentation If needed this can be changed by giving the desired number of digits as the third argument to sosgetsol such as gt gt SOLp1 sosgetsol Program7 p1 12 which will return the numerical solution with twelve digits Note however that this does not change the accuracy of the SDP solution but only its presentation 30 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS Chapter 4 Applications of Sum of Squares Programming In this chapter we present some problems that can be solved using SOSTOOLS The majority of the examples here are from 14
28. a solution For example one may wish to see the sum of squares decomposition the vector Zi x and positive semidefinite matrix Q of the constraint OV OV OV i n 8 1 41 das 28 D o Bog 3 Dis gt 0 This is achieved using the prog solinfo extravar primal field The prog solinfo extravar field has the following structure gt gt prog solinfo extravar ans primal 3x3 double 13x13 double double 3x3 double 13x13 double The derivative condition was the second constraint to be set so in order to obtain the corre sponding Q the following command is used gt gt Q2 prog solinfo extravar primal 2 In this example Q2 is a 13 x 13 matrix which we will omit due to space constraints The matrix Q corresponding to the first constraint is 59 gt gt Q1 prog solinfo extravar primal 1 Q1 5 6852 0 0000 0 0000 0 0000 3 5965 0 0000 0 0000 0 0000 1 0747 and the corresponding vector of monomials Zi x y z is obtained using gt gt Z1 mysympower x y z prog extravar Z 1 Zi X y Zz which proves that ZT x y z Q1Z z y 2 V x y z a7 y 2 gt 0 In this example as we mentioned earlier there is no objectve function to minimise However for SOSPs that do contain an objective function the field prog solinfo decvar returns both the primal solution c x corresponding to 5 1 and the dual solution b7y corresponding to 5 3 The numerical information r
29. an alternative custom built polynomial object along with some basic polynomial manipulation methods to represent and manipulate polynomials For this we have integrated the Multivariate Polynomial Toolbox a freely available toolbox for constructing and manipulating multivariate polynomials In the remainder of the section we give a brief introduction to the new polynomial objects in SOSTOOLS Polynomial variables are created with the pvar command For example the following command creates three variables gt gt pvar x1 x2 x3 New polynomial objects can now be created from these variables and manipulated using standard addition multiplication and integer exponentiation functions gt gt p x3 4 5 x2 x172 p x3 4 5 x2 x172 Matrices of polynomials can be created from polynomials using horizontal vertical concatenation and block diagonal augmentation e g gt gt M1 blkdiag p 2 x2 M1 x3 4 5xx2 x1 2 o O 2 x2 Naturally it is also possible to build new polynomial matrices from already constructed submatri ces Elements of a polynomial matrix can be referenced and assigned using the standard MATLAB referencing notation gt gt M1 1 2 x1x x2 Mi x374 5 x2 x172 x1 x2 O 2 x2 The internal data structure for an N x M polynomial matrix of V variables and T terms consists of a T x NM sparse coefficient matrix a T x V degree matrix and a V x 1 cell array of variable names This
30. andenberghe and S Boyd Semidefinite programming SIAM Review 38 1 49 95 1996 M Yamashita K Fujisawa K Nakata M Nakata M Fukuda K Kobayashi and K Goto A high performance software package for semidefinite programs Sdpa 7 research report b 460 Technical report Dept of Mathematical and Computing Science Tokyo Institute of Technology Tokyo Japan 2010 X Zhao D Sun and K Toh A Newton CG augmented Lagrangian method for semidefinite programming SIAM Journal on Optimization 20 4 1737 1765 2010
31. ands above is equivalent to gt gt syms x y ab gt gt Program3 sosprogram x y gt gt Program3 sosdecvar Program3 a b and also equivalent to gt gt syms x y a b gt gt Program4 sosprogram x y a gt gt Program4 sosdecvar Program4 b When using polynomial objects the commands are for example gt gt pvar x y ab gt gt Program2 sosprogram x y a b 3 3 2 Scalar Polynomial Variables Polynomial variables in a sum of squares program are simply polynomials with unknown coefficients e g pi x in the feasibility problem formulated in Chapter 1 Polynomial variables can obviously be created by declaring its unknown coefficients as decision variables and then constructing the polynomial itself via some algebraic manipulations For example to create a polynomial variable v x y ax bxy cy where a b and c are the unknowns you can use the following commands gt gt Programb sosdecvar Program5 la b c gt gt v a x 2 bxx y cxy 2 However such an approach would be inefficient for polynomials with many coefficients In such a case you should use the function sospolyvar to declare a polynomial variable gt gt Program6 v sospolyvar Program6 x 2 x y y 2 In this case v will be gt gt v coeff_1 x 2 coeff_2 x y coeff_3 y 2 We see that sospolyvar automatically creates decision variables corresponding to monomials in the vector which is given as the seco
32. blems 5 Call solver 6 Get solutions In the next sections we will describe each of these steps in detail But first we will look at how polynomials are represented and manipulated in SOSTOOLS 3 1 Polynomial Representation and Manipulations Polynomials in SOSTOOLS can have representation as symbolic objects using the MATLAB Sym bolic Toolbox Typically a polynomial is created by first declaring its independent variables and then constructing it using the usual algebraic manipulations For example to create a polynomial p x y 2x 3xy 4y you declare the independent variables x and y by typing gt gt syms X y and then construct p x y as follows gt gt p 2 x72 3 x y 4 y74 p 2 x72 3 x y 4 4y 4 Polynomials such as the one created above can then be manipulated using the usual operators Another operation which is particularly useful for control related problems such 13 14 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS as Lyapunov function search is differentiation which can be done using the function diff For instance to find the partial derivative op you should type gt gt dpdx diff p x dpdx 4 x 3 y For other types of symbolic manipulations we refer you to the manual and help comments of the Symbolic Math Toolbox In the current version of SOSTOOLS users without access to the Symbolic Toolbox such as those using the student edition of MATLAB have the option of using
33. ctors the command mpmonomials can be used For example gt gt VEC mpmonomials x1 x2 y1 y2 z1 1 2 1 3 VEC z173 x1 y1 z173 x2 y1 z173 x1 2 y1 z173 x1 x2 y1 z173 x2 2 y1 z173 x1 y2 Z1 3 x2 y2 z173 x1 2 y2 z173 x1 x2 y2 z173 x2 2 y2 LVL ll aS SS es will create a vector of multipartite monomials where the partitions of the independent variables are Sy 1 22 So y1 Y2 and S3 21 whose corresponding degrees are 1 2 1 and 3 3 3 4 Sum of Squares Variables Sum of squares variables are also polynomials with unknown coefficients similar to polynomial variables described in Section 3 3 2 The difference is as its name suggests that an SOS variable is constrained to be an SOS This is imposed by internally representing an SOS variable in the Gram matrix form cf Section 2 1 p x Z 2 QZ a 3 1 and requiring the coefficient matrix Q to be positive semidefinite 3 3 VARIABLE DECLARATION 19 To declare an SOS variable you must use the function sossosvar The monomial vector Z x in 3 1 has to be given as the second input argument to the function Like sospolyvar this function will automatically declare all decision variables corresponding to the matrix Q For example to declare an SOS variable p a y Ta HE 3 2 type gt gt Program8 p sossosvar Program8 x y where the second output argument is the name of the variable In this example the coefficient matr
34. d There are five functions used for this purpose corresponding to variables of these types e Scalar decision variables e Polynomial variables e Sum of squares variables e Matrix of polynomial variables e Matrix of sum of squares variables Each of them will be described in the following subsections 3 3 1 Scalar Decision Variables Scalar decision variables in an SOSP are meant to be unknown scalar constants The variable y in sosdemo3 m see Section 3 3 is an example of such a variable These variables can be declared either by specifying them when an SOSP is initialized with sosprogram or by declaring them later using the function sosdecvar To declare decision variables you must first create symbolic objects corresponding to your decision variables This is performed using the functions syms or sym from the Symbolic Math Toolbox in a way similar to the one you use to define independent variables in Section 3 1 As explained earlier you can declare the decision variables when you initialize an SOSP by giving them as a second argument to sosprogram Thus to declare variables named a and b use the following command 16 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS gt gt syms x y a b gt gt Program2 sosprogram x y a b Alternatively you may declare these variables after the SOSP is initialized or add some other decision variables to the program using the function sosdecvar For example the sequence of comm
35. egarding the solution as returned from the SDP solver is stored in the field prog solinfo info The exact information stored is dependent upon which of the solvers is used However the typical information returned is displayed in Figure 3 2 The fields prog solinfo RRx and prog solinfo RRy are populated with the complete solution of the SDP The elements of the fields prog solinfo decvar primal prog solinfo extravar primal andprog solinfo decvar dual prog solinfo extravar dual are actually computed by extracting and rearranging the entries of prog solinfo RRx and prog solinfo RRy The used solver and its parameters are stored in the fields prog solinfo solverOptions solver and prog solinfo solverOptions params The notation RRx and RRy is due to the fact that they receive the values of RRx RR c A y where x and y are the primal and the dual solutions computed by the solver The matrix RR is a permutation matrix used to rearrange the input data for the solver This is required because the solvers need to distinguish between decision variables which are on the cone of positive semi definite matrices and other decision variables With the permutation matrices RR this arrangement of decision variables previous to the call to the SDP solver is transparent to the user of SOSTOOLS 60 CHAPTER 5 INSIDE SOSTOOLS Chapter 6 List of Functions SOSTOOLS Sum of Squares Toolbox Version 3 00 3 October 2013 h Monomial vectors c
36. ently for sparse p x the size of the vector Z 1 and matrix Q appearing in the sum of squares decomposition can be reduced which results in a decrease of the size of the semidefinite program Consider for example the polynomial p x y 4x y 2 xy y taken from 16 Its Newton polytope is a triangle being the convex hull of the points 4 6 2 0 1 2 2 0 see Figure 3 1 By the result mentioned above we can always find a SOS decomposition that contains only the monomials 1 0 0 1 1 1 1 2 2 3 By exploiting sparsity non negativity of p x y can thus be verified by solving a semidefinite program of size 5 x 5 with 13 constraints On the other hand when sparsity is not exploited we need to solve a 11 x 11 semidefinite program with 32 constraints SOSTOOLS takes the sparse structure into account and computes an appropriate set of mono mials for the sum of squares decompositions The convex hulls are computed using either the native MATLAB command convhulln which is based on the software QHULL or the specialized ex ternal package CDD 7 developed by K Fukuda This choice is determined by the content of the file cddpath m If in this file the variable cdd is set to be an empty string then convhulln will be used On the other hand if CDD is to be used then the location of the CDD executable file should be assigned to the variable cdd Special care is taken with the case when the set of exponents has lower
37. es Two of them are e sostools docs containing this user s manual and license file It is not recommended that both SDPNAL and SDPT3 be on the MATLAB path simultaneously 5To use the CSDP solver please note that the CSDP binary file must be in the working directory and not simply be on the MATLAB path 12 CHAPTER 2 GETTING STARTED WITH SOSTOOLS e sostools demos containing several demo files The demo files in the second subdirectory above implement the SOSPs corresponding to examples in Chapter 4 Throughout this user s manual we use the typewriter typeface to denote MATLAB variables and functions MATLAB commands that you should type and results given by MATLAB MAT LAB commands that you should type will also be denoted by the symbol gt gt before the commands For example gt gt x sin 1 0 8415 In this case x sin 1 is the command that you type and x 0 8415 is the result given by MATLAB Finally you can send bug reports comments and suggestions to sostoolsQcds caltech edu Any feedback is greatly appreciated Chapter 3 Solving Sum of Squares Programs SOSTOOLS can solve two kinds of sum of squares programs the feasibility and optimization problems as formulated in Chapter 2 To define and solve an SOSP using SOSTOOLS you simply need to follow these steps 1 Initialize the SOSP 2 Declare the SOSP variables 3 Define the SOSP constraints 4 Set objective function for optimization pro
38. except when noted otherwise Many more application examples and customized files will be included in the near future Note For some of the problems here in particular copositivity and equality constrained ones such as MAXCUT the SDP formulations obtained by SOSTOOLS are not the most efficient ones as the special structure of the resulting polynomials is not fully exploited in the current distribution This will be incorporated in the next release of SOSTOOLS whose development is already in progress 4 1 Sum of Squares Test As mentioned in Chapter 1 testing if a polynomial p x is nonnegative for all x R is a hard problem but can be relaxed to the problem of checking if p x is an SOS This can be solved using SOSTOOLS by casting it as a feasibility problem SOSDEMO1 Given a polynomial p x determine if is feasible Notice that even though there are no explicit decision variables in this SOSP we still need to solve a semidefinite programming problem to decide if the program is feasible or not The MATLAB code for solving this SOSP can be found in sosdemo1 m shown in Figure 4 1 and sosdemo1p m using polynomial objects where we consider p x 21f 2xjxo 212 5x3 Since the program is feasible it follows that p x gt 0 In addition SOSTOOLS provides a function named findsos to find an SOS decomposition of a polynomial p x This function returns the coefficient matrix Q and the monomial vector Z x1 which are
39. f structured singular value u a crucial object in robust control theory see e g 6 13 The following conditions can be derived from Proposition 8 25 of 6 and Theorem 6 1 of 14 Given a matrix M C and structured scalar uncertainties A dae dy 509420 n s 6 C the structured singular value u M A is less than y if there exists solutions Q gt 0 R T R27x2R and rij gt 0 such that X Qi ajAs a So rijAi o JAj a I x gt 0 4 10 i 1 1 lt i lt j lt n where x R Oz a Qu 4 11 2n MS 4 12 1 1 Aix a Aja 4 13 A Im H Re H dd H M eje M y exe 4 15 and e is the i th unit vector in C Thus the SOSP for this problem can be formulated as follows 40 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING SOSDEMO4 Matrix Copositivity Section 3 4 of SOSTOOLS User s Manual clear echo on syms x1 x2 x3 x4 x5 vartable x1 x2 x3 x4 x5 The matrix under consideration J 1 1 1 1 1 1 1 1 1 41 1 1 1 1 1 1 1 1 1 1 s 4 1 1 il Y First initialize the sum of squares program prog sosprogram vartable No decision variables Y Next define SOSP constraints Constraint r x J x p x 0 J x172 x272 x3 2 x4 2 x5 2 J x1 2 x2 2 x3 2 x4 2 x5 2 r xi72 x2 2 x3 2 x4 2 x5 2 prog sosineq prog r J And call solver prog sossolve prog Program
40. gorithm for sums of squares of real polynomials Journal of Pure and Applied Linear Algebra 127 99 104 1998 A Rantzer and P A Parrilo On convexity in stabilization of nonlinear systems In Proceedings of the 39th IEEE Conf on Decision and Control volume 3 pages 2942 2945 2000 B Reznick Extremal PSD forms with few terms Duke Mathematical Journal 45 2 363 374 1978 B Reznick Some concrete aspects of Hilbert s 17th problem In Contemporary Mathematics volume 253 pages 251 272 American Mathematical Society 2000 K Schmidgen The k moment problem for compact semialgebraic sets Math Ann 289 203 206 1991 N Z Shor Class of global minimum bounds of polynomial functions Cybernetics 23 6 731 734 1987 J F Sturm Using SeDuMi 1 02 a MATLAB toolbox for optimization over sym metric cones Optimization Methods and Software 11 12 625 653 1999 Available at http fewcal kub nl sturm software sedumi html B Sturmfels Polynomial equations and convex polytopes American Mathematical Monthly 105 10 907 922 1998 K C Toh R H T t nc and M J Todd SDPT3 a MATLAB soft ware package for semidefinite quadratic linear programming Available from http www math nus edu sg mattohkc sdpt3 html G Valmorbida S Tarbouriech and G Garcia Design of polynomial control laws for poly nomial systems subject to actuator saturation IEEE Transactions on Automatic Control 58 7 1758 1770 2013 L V
41. has been a surge of activity in the field of numerical optimization methods and there are now numerous Semidefinite Program SDP solvers available This latest version of SOSTOOLS now includes interfaces to three new solvers CSDP 2 SDPNAL 29 and SDPA 28 in addition to maintaining support for SeDuMi 23 and SDPT3 25 The highlights of the latest SOSTOOLS release are listed below Compatibility with MuPAD MATLAB s symbolic engine Interface to additional SDP solvers e Direct specification of polynomial matrix inequalities Simultaneous multiple decision variable declaration Sum of Squares matrix decomposition Interface to the new multivariate polynomial toolbox e Additional illustrative examples CHAPTER 1 ABOUT SOSTOOLS V3 00 Chapter 2 Getting Started with SOSTOOLS SOSTOOLS is a free third party MATLAB toolbox for solving sum of squares programs The techniques behind it are based on the sum of squares decomposition for multivariate polynomials 5 which can be efficiently computed using semidefinite programming 27 SOSTOOLS is devel oped as a consequence of the recent interest in sum of squares polynomials 14 15 22 5 20 12 11 partly due to the fact that these techniques provide convex relaxations for many hard problems such as global constrained and boolean optimization Besides the optimization problems mentioned above sum of squares polynomials and hence SOSTOOLS find applications in many
42. hat each 58 CHAPTER 5 INSIDE SOSTOOLS field in prog solinfo contains Recall that the dual canonical form of an SDP takes the form maximize bly y st c ATyEK 5 3 Intuitively prog solinfo x and prog solinfo y contain the primal and dual decision variables x and y respectively Note however that prog solinfo x and prog solinfo y contain the solution vectors to the whole SDP which will typically be a concatenation of multiple smaller SDPs for each constraint For the SOSDEMO2 example the field prog solinfo x will contain not only the coefficients to the polynomial V but also the coefficients of the positive semidefi nite matrix corresponding to the negativity of the derivative condition The matrix coefficients are stored in vectorized form To extract the coefficients of V directly one can use the field prog solinfo var primal gt gt prog solinfo var primal ans 6 6582 4 5965 2 0747 Clearly these are verified as the coefficients of V as given above For the case where there are multiple variables prog solinfo var primal will return an array of vectors The dual variables y from 5 3 can be accessed in much the same way using prog solinfo var dual Indeed it is the field prog var idx and prog extravar idx that were alluded to earlier that extract the relevant coefficients for each of the polynomial decision variables In certain instances it may be desirable to obtain the sum of squares decomposition in order to certify
43. hich many specific problems can be solved as we will see later in Chapter 4 2 2 What SOSTOOLS Does Currently sum of squares programs are solved by reformulating them as semidefinite programs SDPs which in turn are solved efficiently e g using interior point methods Several commercial as well as non commercial software packages are available for solving SDPs While the conversion from SOSPs to SDPs can be manually performed for small size instances or tailored for specific problem classes such a conversion can be quite cumbersome to perform in general It is therefore desirable to have a computational aid that automatically performs this conversion for general SOSPs This is exactly where SOSTOOLS comes to play It automates the conversion from SOSP to SDP calls the SDP solver and converts the SDP solution back to the solution of the original 10 CHAPTER 2 GETTING STARTED WITH SOSTOOLS SOSTOOLS AT n na T SOSP SDP J k AN a o ms 3 AA SDP Solver yo Sa Pad E A SOSP gt SDP xa LA to SOSTOOLS Figure 2 1 Diagram depicting relations between sum of squares program SOSP semidefinite program SDP SOSTOOLS and SeDuMi SDPT3 CSDP SDPNAL SDPA SOSP At present there is an interface between SOSTOOLS and the following free MATLAB based SDP solvers i SeDuMi 23 ii SDPT3 25 iii CSDP 2 iv SDPNAL 29 and SDPA 28 This whole process is depicted in Figure 2 1 In the original release of SOSTOOLS polyn
44. ibed in the previous chapter As described in Chapter 3 an SOSP is initialized using the command gt gt syms x y Z gt gt prog sosprogram x y z The command above will initialize an empty SOSP called prog with variables x y and z and returns the following structure gt gt prog prog var 1x1 struct expr 1x1 struct extravar 1x1 struct objective solinfo 1x1 struct vartable x y z symvartable 3x1 sym varmat decvartable symdecvartable The various fields above are populated by the addition of new decision variables polynomials and sum of squares polynomials constraints equality and inequality and the inclusion of an objective function The contents and structure of each of these fields will now be described and specifically related to the construction of the underlying SDP We will illustrate the program structure by constructing a typical sum of squares program that is similar to SOSDEMO2 The first fields to be populated are prog symvartable and prog vartable The following output will be seen Recall that the inequality h x gt 0 is interpreted as h x having a sum of squares decomposition 21t is assumed that the symbolic toolbox is being used 53 54 CHAPTER 5 INSIDE SOSTOOLS gt gt prog symvartable prog symvartable x y z gt gt prog vartable prog vartable x y z Note that if the symbolic toolbox is not being used then the prog sym
45. ill be second order in y and will only contain one variable x the resulting positive semidefinite biform is always a sum of squares 4 In this manner a SOS matrix in several variables can be converted to a SOS polynomial whose decomposition is computed using semidefinite programming Because of the bipartite structure 3 4 ADDING CONSTRAINTS 25 only monomials in the form ay will appear in the vector Z as mentioned earlier For example the above sum of squares matrix can be verified as follows gt gt syms x yl y2 real gt gt S x72 2 x 2 x x x 2 gt y y1 y21 gt p y rSxyvi gt gt prog sosprogram x y1 y2 gt gt prog sosineq prog p sparsemultipartite x ly1 y2 gt gt prog sossolve prog 3 4 5 Matrix Inequality Constraints New to SOSTOOLS v3 00 is the function sosmatrixineq which allows users to specify polynomial matrix inequalities Matrix inequality constraints are interpreted in SOSTOOLS as follows We recall that for a given symmetric matrix M R 6 we say that M gt 0 if yT M 0 y gt 0 for all y where y y1 Wr Alternatively given a symmetric polynomial matrix M R 0 we say that M 0 is a sum of squares matrix if there exist a polynomial matrix H 0 R 9 for some s N such that M 0 H 0 H 0 This is equivalent to y M 0 y being a sum of squares in R 6 y 10 In SOSTOOLS v3 00 both of the formulations mentioned above are a
46. imal form where the field prog expr At refers to the transposition of the matrix A in 5 1 and likewise prog expr b refers to the vector b in 5 1 Finally the field prog expr Z contains the matrices of monomial exponents corresponding to the two inequalities These take exactly the same form as described above for the field prog var Z Thus far in the example we have not described the decision variables i e the unknown polyno mial coefficients This will now be illustrated through the constraint h y y 2 V a y 2 gt 0 where V contains only quadratic terms This inequality is interpreted as a sum of squares in equality of the form T x T Mea y Qly 2 FA 56 CHAPTER 5 INSIDE SOSTOOLS where the decision variable is the positive semidefinite matrix Q consisting of the coefficients of the polynomial V x y 22 Here the matrix Q is constrained to be of the form coeff_1 0 0 C 0 coeff_2 0 5 2 0 0 coeff_3 and thus the decision variables are the three non zero coefficients in Q The decision variables can be seen through the prog symdecvartable field gt gt prog symdecvartable prog symdecvartable coeff_1 coeff_2 coeff_3 In a similar manner prog decvartable contains the same information but stored as a character array This particular example is an SOS feasibility problem i e no objective function has been set An objective function to be minimised can be set using the function sossetobj i
47. information can be easily accessed through the MATLAB field accessing operators p coefficient p degmat and p varname The access to fields uses a case insensitive 3 2 INITIALIZING A SUM OF SQUARES PROGRAM 15 partial match Thus abbreviations such as p coef can also be used to obtain the coefficients degrees and variable names A few additional operations exist in this initial version of the toolbox such as trace transpose determinant differentiation logical equal and logical not equal The input to the SOSTOOLS commands can be specified using either the symbolic objects or the new polynomial objects although they cannot be mixed There are some minor variations in performance depending on the degree number of variables of the polynomials due the fact that the new implementation always keeps an expanded internal representation but for most reasonable sized problems the difference is minimal 3 2 Initializing a Sum of Squares Program A sum of squares program is initialized using the command sosprogram A vector containing independent variables in the program has to be given as an argument to this function Thus if the polynomials in our program have x and y as the independent variables then we initialize the SOSP using gt gt Programl sosprogram x y The command above will initialize an empty SOSP called Program 3 3 Variable Declaration After the program is initialized the SOSP decision variables have to be declare
48. ix G pe ee coeff_2 coeff_4 3 3 will be created by the function When this matrix is substituted into the expression for p x y we obtain p x y coeff 1x coeff 2 coeff_3 1y coeff_4y 3 4 which is exactly what sossosvar returns gt gt p p coeff_4 y 2 coeff_2 coeff_3 x y coeff_1 x72 We would like to note that at first the coefficient matrix does not appear to be symmetric especially because the number of decision variables which seem to be independent is the same as the number of entries in the coefficient matrix However some constraints are internally imposed by the semidefinite programming solver SeDuMi SDPT3 which are used by SOSTOOLS on some of these decision variables such that the solution matrix obtained by the solver will be symmetric The primal formulation of a semidefinite program in SeDuMi SDPT3 uses n decision variables to represent an n x n positive semidefinite matrix which is the reason why SOSTOOLS also uses n decision variables for its n x n coefficient matrices SOSTOOLS includes a custom function findsos that will compute if feasible the sum of squares decomposition of a polynomial p x into the sum of m polynomials f2 x as in 2 1 the Gram matrix Q and vector of monomials Z corresponding to 3 1 The function is called as shown below gt gt Q Z f findsos P where f is a vector of length m rank Q containing the functions f If the problem is infeasible then empty ma
49. lyvar prog x 2 y72 z 2 x y z x 2xy gt gt full prog var Z 2 ans 2 0 0 0 2 0 0 0 2 1 1 1 2 1 0 Note that by default this matrix is stored as a sparse matrix Define the vector of monomials without coefficients that describes V by Z ie Z x2 y2 22 Further define W to be the vector of pairwise different monomials of the entries of the matrix ZZ The exponents of all such monomials are then stored in the degree matrix prog var ZZ where the rows corresponding to the unique set of monomials are ordered lexicographically The field prog var idx contains indexing information that is required for constructing the SDP We will expand upon this indexing further when describing the prog extravar fields The next field of interest is prog expr which is the primary field where SOSTOOLS stores the user s constraints Continuing on with the example we see that there are two constraints in the programme and that both are sum of squares This can be seen by inspecting prog expr num and prog expr type respectively gt gt prog expr prog expr num 2 type ineq ineq At 3x3 double 3x10 double b 3x1 double 10x1 double Z 3x3 double 10x3 double Recall that the canonical primal SDP takes the form minimize cx T s t Arad 5 1 eK where K denotes the symmetric cone of positive semidefinite matrices Here the two inequalities imposed in the SOSP are converted into their SDP pr
50. n nodes Given f x and y then max 2_ f x lt y if there exists sum of squares p x and polynomials p2 2 Pn 1 1 such that pl He ola 1 1 Hm gt 0 4 16 i 1 This can be proved by a contradiction Suppose there exists x 1 1 such that f x gt y Then the first term in 4 16 will be negative the terms under summation will be zero and the last term will be negative Thus we have a contradiction 42 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING SOSDEMO5 Upper bound for the structured singular value mu Section 3 5 of SOSTOOLS User s Manual h clear echo on syms x1 x2 x3 x4 x5 x6 x7 x8 vartable x1 x2 x3 x4 x5 x6 x7 x8 The matrix under consideration alpha 3 sqrt 3 beta sqrt 3 1 sqrt 2 alpha 1 sqrt alpha b sqrt beta alpha 1 i esgrt 1 alphaxbeta a 0 bb c i c d f 0 a b b c ixc i f d U V lt sahe o op Constructing A x s gam 0 8724 on maple convert 1 float Z monomials vartable 1 for i 1 4 H M i M i gam 2 sparse i i 1 4 4 1 H real H imag H imag H real H Ati Z H Z end Initialize the sum of squares program prog sosprogram vartable VA SSS SSS SSS SS SSS SSS SSS SSS SSS SSS SSS SSS SSS o o a S gt Define SOSP variables h Q x s sums of squares Monomial vector x1 x8 for i 1 4
51. n which case the field prog objective would contain the relevant data Recall that for both an SDP and SOSP the objective function must be a linear function SOSTOOLS will automatically set the weighting vector c in 5 1 this is exactly what is contained in prog objective while the x corresponds to the decision variables i e the unknown polynomial coefficients in 5 2 Many SOSPs may include matrix inequality constraints that is constraints of the form x M x gt 0 or more accurately that the previous expression is a sum of squares polynomial in x and 6 When setting such constraints the user does not need to declare the independent variable vector x as this is handled internally by SOSTOOLS The following code sets the matrix constraint gt gt sym theta gt gt prog M sospolymatrixvar prog monomials theta 0 2 3 3 symmetric gt gt prog sosmatrixineq prog M quadraticMineq which then populates the field prog varmat gt gt prog varmat prog varmat vartable Mvar_1 Mvar_2 Mvar_3 symvartable 3x1 sym count 3 Here prog varmat symvartable is the 3x1 vector of symbolic variables Mvar_1 Mvar_2 Mvar 3 which correspond to the independent variables 2 in the above example The field prog varmat symvartable likewise contains a character array of the vector of variables while prog varmat count indicates the number of variables used Note that in order to save memory the variables Mvar_1 may
52. nd input argument to it and then constructs a polynomial variable from these coefficients and monomials This polynomial variable is returned as the second output argument of sospolyvar NOTE 3 3 VARIABLE DECLARATION 17 1 sospolyvar and sossosvar see Section 2 3 4 name the unknown coefficients in a polyno mial SOS variable by coeff_nnn where nnn is a number Names that begin with coeff_ are reserved for this purpose and therefore must not be used elsewhere 2 By default the decision variables coeff_nnn created by sospolyvar or sossosvar will only be available in the function workspace and therefore cannot be manipulated in the MATLAB workspace Sometimes it is desirable to have these decision variables available in the MATLAB workspace such as when we want to set an objective function of an SOSP that involves one or more of these variables In this case a third argument wscoeff has to be given to sospolyvar or sossosvar For example using gt gt Program7 v sospolyvar Program7 x 2 x y y 2 wscoeff gt gt v coeff_1 x 2 coeff_2 xx y coeff_3 y 2 you will be able to directly use coeff_1 and coeff_2 in the MATLAB workspace as shown below gt gt w coeff_1 coeff_2 coeff_1 coeff_2 3 SOSTOOLS requires monomials that are given as the second input argument to sospolyvar and sossosvar to be unique meaning that there are no repeated monomials 3 3 3 An Aside Constructing Vectors of Monomials We
53. o x s A x s such that the degree of the whole expression is no greater than degree For this example a lower bound of the opti mization problem is gam 1 3911 corresponding to the optimal solution x 0 5682 12 0 8229 which can be extracted from the output argument opt 4 4 Matrix Copositivity The matrix copositivity problem can be stated as follows Given a matrix J R check if it is copositive i e if y Jy gt 0 for all y R yi 0 It is known that checking copositivity of a matrix is a co NP complete problem However there exist computationally caian relaxations for copositivity checking One relaxation 14 is per formed by writing y x7 and checking if n m at j s J amp R x 4 8 is an SOS Now consider the matrix 1 1 1 1 1 1 1 1 J 1 1 1 ll 1 1 1 1 1 1 1 1 1 1 4 5 UPPER BOUND OF STRUCTURED SINGULAR VALUE 39 It is known that the matrix above is copositive This will be proven using SOSTOOLS For this purpose we have the following SOSP SOSDEMO4 Determine if is feasible where R x is as in 4 8 Choosing m 0 does not prove that J is copositive However DEMO4 is feasible for m 1 and therefore it proves that J is copositive The MATLAB code that implements this is given in sosdemo4 m and shown in Figure 4 4 4 5 Upper Bound of Structured Singular Value Now we will show how SOSTOOLS can be used for computing upper bound o
54. omials are implemented solely as symbolic objects making full use of the capabilities of the MATLAB Symbolic Math Toolbox This gives to the user the benefit of being able to do all polynomial manipulations using the usual arithmetic operators as well as operations such as differentiation integration point evaluation etc In addition this provides the possibility of interfacing with the Maple symbolic engine and the Maple library which is very advantageous On the other hand this prohibited those without access to the Symbolic Toolbox such as those using the student edition of MATLAB from using SOSTOOLS In the current SOSTOOLS release the user has the option of using an alternative custom built polynomial object along with some basic polynomial manipulation methods to represent and manipulate polynomials The user interface has been designed to be as simple as easy to use and as transparent as possible while keeping a large degree of flexibility An SOSP is created by declaring SOSP variables e g the p x s in Section 1 1 adding SOSP constraints setting the objective function and so forth After the program is created one function is called to run the solver and finally the solutions to SOSP are retrieved using another function These steps will be presented in more details in Chapter 2 Alternatively customized functions for special problem classes such as Lyapunov function computation etc can be direc
55. onstruction MONOMIALS Construct a vector of monomials with prespecified degrees MPMONOMIALS Construct a vector of multipartite monomials with prespecified degrees h General purpose sum of squares program SOSP solver SOSPROGRAM Initialize a new SOSP SOSDECVAR Declare new decision variables in an SOSP SOSPOLYVAR Declare a new polynomial variable in an SOSP SOSSOSVAR Declare a new sum of squares variable in an SOSP SOSPOLYMATRIXVAR Declare a new matrix of polynomial variables in an SOSP SOSSOSMATRIXVAR Declare a new matrix of sum of squares polynomial h variables in an SOSP SOSEQ Add a new equality constraint to an SOSP SOSINEQ Add a new inequality constraint to an SOSP SOSMATRIXINEQ Add a new matrix inequality constraint to an SOSP SOSSETOBJ Set the objective function of an SOSP h SOSSOLVE Solve an SOSP SOSGETSOL Get the solution from a solved SOSP h Customized functions FINDSOS Find a sum of squares decomposition of a given polynomial or a given polynomial matrix FINDLYAP Find a Lyapunov function for a dynamical system FINDBOUND Find a global constrained lower bound for a polynomial h Demos 61 SOSDEMO1 SOSDEMO2 SOSDEMO3 SOSDEMO4 SOSDEMOS SOSDEMOG SOSDEMO7 SOSDEMOS SOSDEMO9 SOSDEMO10 and and and and and and SOSDEMO1P SOSDEMO2P SOSDEMO3P SOSDEMO4P SOSDEMO5P SOSDEM
56. or dual infeasibility e numerr 1 gives a warning of numerical inaccuracy This is usually accompanied by large Residual norm On the other hand numerr 2 is a sign of complete failure because of numerical problem Size 10 5 SeDuMi 1 05 by Jos F Sturm 1998 2001 Alg 2 xz corrector Step Differentiation theta 0 250 beta 0 500 eqs m 5 order n 9 dim 13 blocks 3 nnz A 13 O nnz ADA 11 nnz L 8 it i bey gap delta rate t tP t tD feas cg cg O 7 00E 000 0 000 1 3 03E 000 1 21E 000 0 000 0 1734 0 9026 0 9000 0 64 1 1 2 4 00E 000 6 36E 003 0 000 0 0052 0 9990 0 9990 0 94 1 1 3 4 00E 000 2 19E 004 0 000 0 0344 0 9900 0 9786 1 00 1 1 4 4 00E 000 1 99E 005 0 234 0 0908 0 9459 0 9450 1 00 1 1 5 4 00E 000 2 37E 006 0 000 0 1194 0 9198 0 9000 0 91 1 2 6 4 00E 000 3 85E 007 0 000 0 1620 0 9095 0 9000 1 00 3 3 7 4 00E 000 6 43E 008 0 000 0 1673 0 9000 0 9034 1 00 4 4 8 4 00E 000 2 96E 009 0 103 0 0460 0 9900 0 9900 1 00 3 4 9 4 00E 000 5 16E 010 0 000 0 1743 0 9025 0 9000 1 00 5 5 10 4 00E 000 1 88E 011 0 327 0 0365 0 9900 0 9905 1 00 5 5 iter seconds digits Cx bx y 10 0 4 Inf 4 0000000000e 000 4 0000000000e 000 Ax b 9 2e 011 Ay c _ 1 1E 011 x 9 2e 000 lyl 6 8e 000 Max norms b l 2 lcl 5 Cholesky ladd 0 Iskipl 1 L L 2 00001 Residual norm 9 2143e 011 cpusec 0 3900 iter 10 feasratio 1 0000 pinf O dinf O numerr O Figure 3 2 Output of SO
57. other areas This includes control theory problems such as search for Lyapunov functions to prove stability of a dynamical system computation of tight upper bounds for the structured singular value y 14 and stabilization of nonlinear systems 18 Some examples related to these problems as well as several other optimization related examples are provided and solved in the demo files that are distributed with SOSTOOLS In the next two sections we will provide a quick overview on sum of squares polynomials and programs and show the role of SOSTOOLS in sum of squares programming 2 1 Sum of Squares Polynomials and Sum of Squares Programs A multivariate polynomial p z1 n p x is a sum of squares SOS for brevity if there exist polynomials fi x fm x such that p x Y flo 2 1 i 1 It is clear that f x being an SOS naturally implies f x gt 0 for all x R For a partial converse statement we remind you of the equivalence proven by Hilbert between nonnegativity and sum of squares in the following cases e Univariate polynomials any even degree e Quadratic polynomials in any number of variables e Quartic polynomials in two variables see 20 and the references therein In the general multivariate case however f x gt 0 in the usual sense does not necessarily imply that f x is SOS Notwithstanding this fact the crucial 1A registered trademark of The MathWorks Inc 8 CHAPTER
58. raints be 1 x1 2 1 bc 2 x272 1 be 3 x372 1 bc 4 x472 1 bc 5 x5 2 1 Y First initialize the sum of squares program prog sosprogram vartable Sf a a a re Y Then define SOSP variables p1 x sum of squares Monomial vector 5 independent variables degree lt 1 Z monomials vartable 0 1 prog p 1 sossosvar prog Z p2 x p6 x polynomials Monomial vector 5 independent variables degree lt 2 Z monomials vartable 0 2 for i 1 5 prog p 1 i sospolyvar prog Z end a Next define SOSP constraints Constraint pi x gamma f x p2 x bc1 x p6 x bc5 x gamma f x 72 gt 0 gamma 4 expr p 1 gamma f for i 2 6 expr expr p i bcf i 1 expr gamma f 2 D tal Jo R ll prog sosineq prog expr Y S And call solver prog sossolve prog Yo gt Program is feasible thus 4 is an upper bound for the cut echo off Figure 4 7 MAX CUT sosdemo6 m 45 46 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING SOSDEMO7 Chebyshev polynomials Section 3 7 of SOSTOOLS User s Manual clear echo on ndeg 8 Degree of Chebyshev polynomial syms X gam First initialize the sum of squares program prog sosprogram x gam
59. rformance and to reduce the amount of memory needed To give an illustrative figure of the computational load all examples in Chapter 4 except the u upper bound example are solved in less than 10 seconds by SOSTOOLS running on a PC with Intel Celeron 700 MHz processor and 96 MBytes of RAM Even the u upper bound example is solved in less than 25 seconds using the same system SOSTOOLS is available for free under the GNU General Public License The software and its user s manual can be downloaded from http www eng ox ac uk control sostools or http www cds caltech edu sostools or http www mit edu parrilo sostools Once you download the zip file you should extract its contents to the directory where you want to install SOSTOOLS In UNIX you may use unzip U SOSTOOLS nnn zip d your_dir where nnn is the version number and your_dir should be replaced by the directory of your choice In Windows operating systems you may use programs like Winzip to extract the files After this has been done you must add the SOSTOOLS directory and its subdirectories to the MATLAB path This is done in MATLAB by choosing the menus File gt Set Path gt Add with Subfolders and then typing the name of SOSTOOLS main directory This completes the SOSTOOLS installation Alternatively run the script addsostools m from the SOSTOOLS directory 2 4 Other Things You Need to Know The directory in which you install SOSTOOLS contains several subdirectori
60. rix Furthermore if P is determined to be SOS then it is shown how the matrix decomposition P x H 1 H x can be computed SOSDEMOS Given a symmetric polynomial matrix P R x determine if P is an SOS matrix and if so compute the polynomial matrix H z such that P x HT H x 4 18 The above feasibility problem is implemented in sosdemo9 m for the matrix LI tal ata x12915 exo aja ez 2x2 P x 1 172 173 3 1 2 3 11915 vias 1129 2 225 vias vir x3 223 The code in Figure 4 10 can be used to compute a matrix decomposition The findsos function returns the arguments Q Z and Hsol such that H z 1 9 Z 2 QU 8 Z x where 1 is the r x r identity matrix Q is a positive semidefinite matrix and Z x is a vector of monomials SOSDEMO9 Matrix SOS decomposition Section 3 9 of SOSTOOLS User s Manual clear echo on syms x1 x2 x3 vartable x1 x2 x3 J E E gt iS 2 SS SiS First initialize the sum of squares program prog sosprogram vartable No decision variables A Consider the following candidate sum of squares matrix P x P x174 x172 xx2 2 x172 x372 x1 x2 x372 x1 3 x2 x1 x2 x27 2 2 x3 2 x1 x2 x372 x173 x2 x1 x2 x27 2 2 x3 2 x172x xx27 2 x27 2x xx3 2 x27 2 2 xx372 72 h Test if P x1 x2 x3 is an SOS matrix and return H so that P H H Q Z H findsos P Program is feasible thus P x1
61. s which can be used to prove the nonexistence of real solutions of systems of polynomial equalities and inequalities see 15 for details The basic feasibility problem in SOS programming will be formulated as follows FEASIBILITY Find polynomials p x for i 1 2 N sums of squares p x for i N 1 N such that 00 5 Dome wa j x 0 for j 1 2 J a0 1 Ent 2 a 1 are sums of squares gt 0 for j J 1 J 2 4 J In this formulation the a x are given scalar constant coefficient polynomials The p 2 s will be termed SOSP variables and the constraints 2 3 2 4 are termed SOSP constraints The feasible set of this problem is convex and as a consequence SOS programming can in principle be solved using the powerful tools of convex optimization 3 It is obvious that the same program can be formulated in terms of constraints 2 3 only by introducing some extra sums of squares as slack program variables However we will keep this Whenever constraint f x gt 0 is encountered in an SOSP it should always be interpreted as f x is an SOS 2 2 WHAT SOSTOOLS DOES 9 more explicit notation for its added flexibility since in most cases it will help make the problem statement clearer Since many problems are more naturally formulated using inequalities we will call the con straints 2 4 inequality constraints and denote them by gt 0 It is important however
62. section that when considering the SOS decomposition of a sparse polynomial in which many of the coefficients ca are zero the nonzero monomials in Z x xf are the ones for which 28 belongs to the convex hull of the degrees a 19 What distinguishes this case from the general one is that the Newton polytope of p x is the Cartesian product of the individual Newton polytopes corresponding to the blocks of variables Hence the convex hull should only be computed for the individual a which significantly reduces the complexity and avoids ill conditioning in the computation of a degenerate convex hull in a higher dimensional space A specific kind of multipartite polynomials important in practice is the one that appears when considering sum of squares matrices These are matrices with polynomial entries that are positive semi definite for every value of the indeterminates Suppose S R x is a symmetric matrix and let y y1 Ym be new indeterminates The matrix S is a sum of squares SOS matriz if the bipartite scalar polynomial y Sy is a sum of squares in R x y For example the matrix S R z given by a2 21 2 zx Es x a is a SOS matrix since yn f 2 1017 9wm T LY 1 1 00 LY Yy a 0 0 00 y TY2 1 0 0 1 TY2 y y any Note that SOS matrices for which n 1 i e S R x are positive semidefinite for all real x if and only if they are SOS matrices this is because the resulting polynomial w
63. ting Started with SOSTOOLS 2 1 Sum of Squares Polynomials and Sum of Squares Programs 2 2 What SOSTOOLS Does xs i ie eee eRe RG ee Ee pe a G 2 3 System Requirements and Installation Instruction 0 2 4 Other Things You Need to Know 0 e Solving Sum of Squares Programs 3 1 Polynomial Representation and Manipulations 0004 3 2 Initializing a Sum of Squares Program e 3 3 Variable Declaration 3 3 1 Scalar Decision Variables e e e 3 3 2 Scalar Polynomial Variables o 2000002 epee 3 3 3 An Aside Constructing Vectors of Monomials 3 3 4 Sum of Squares Variables 2 a d tea a e 3 3 0 Matrix Variables 2 3 06404 dis Som Roe E ebm be a Be E E E 3A Adding Constraints rs Qc 9 6 ka Fok eae aa ee Pd ek ias 3 4 1 Equality Constraints co oro 2 0 rd endag doa diaaa 3 4 2 Inequality Constraints qa s ci Eua E GE 4 e ae ee eee i 3 43 Exploiting Sparsity da aa p a a Ep EO R e a e E G 3 4 4 Multipartite Structure s icsi agy ea a mane A ea 3 4 5 Matrix Inequality Constraints a 3 5 Setting an Objective Function a a a a 36 Calling Solver setos A a ta a er 2 3 7 Getting Solutions s sir seras a a a ee a ES Applications of Sum of Squares Programming 4 1 Sum of Squares Test ee 4 2 Lyapunov Function Search e s se e s se soa a e a a 4 3 Global and
64. tly used with no user programming whatsoever required These are presented in the first three sections of Chapter 3 2 3 System Requirements and Installation Instruction To install and run SOSTOOLS v3 00 MATLAB R2009a or later and the Symbolic Math Toolbox version 5 7 or later are required Older versions of both MATLAB and the symbolic toolbox may 3A registered trademark of Waterloo Maple Inc 2 4 OTHER THINGS YOU NEED TO KNOW 11 be sufficient however SOSTOOLS v3 00 has only been tested on versions 2009a 2011b and 2012a Here is a list of requirements e MATLAB R2009a or later e Symbolic Math Toolbox version 5 7 which uses the MuPAD engine e One of the following SDP solvers SeDuMi SDPT3 CSDP SDPNAL and SDPA Each solver must be installed before SOSTOOLS can be used The user is referred to the relevant documentation to see how this is done The solvers can be downloaded from SeDuMi http sedumi ie lehigh edu SDPT3 http www math nus edu sg mattohkc sdpt3 html CSDP https projects coin or org Csdp SDPNAL http www math nus edu sg mattohkc SDPNAL html SDPA http sdpa sourceforge net index html Note that if you do not have access to the Symbolic Toolbox then SOSTOOLS v2 05 can be used with the multivariate polynomial toolbox and any version of MATLAB SOSTOOLS can be easily run on a UNIX workstation on a Windows PC desktop or even a laptop It utilizes MATLAB sparse matrix representation for good pe
65. trices are returned This example is expanded upon in SOSDEMO1 in Chapter 4 3 3 5 Matrix Variables For many problems it may be necessary to construct matrices of polynomial or sum of squares polynomials decision variables i e matrices whose elements are themselves polynomials or sum of squares polynomials with unknown coefficients Such decision variables can be respectively 20 CHAPTER 3 SOLVING SUM OF SQUARES PROGRAMS declared using the sospolymatrixvar or the sossosmatrixvar function The sospolymatrixvar or the sossosmatrixvar functions take three compulsory input arguments and an optional fourth symmetry argument The first two arguments are of the same form as sospolyvar and sossosvar the first being the sum of squares program prog and the second the vector of monomials Z x The third argument is a row vector specifying the dimension of the matrix We now illustrate a few simple examples of the use of the sospolymatrixvar function First a SOSP must be initialized gt gt syms x1 x2 gt gt x xi x2 gt gt prog sosprogram x We will now declare two matrices P and Q both of dimension 2 x 2 where the entries are real scalars i e a degree 0 polynomial matrix Furthermore we will add the constraint that Q must be symmetric gt gt prog P sospolymatrixvar prog monomials x 0 2 2 gt gt prog Q sospolymatrixvar prog monomials x 0 2 2 symmetric gt gt P P coeff_1 coeff_2
66. um of squares program prog sosprogram vartable No decision variables Next define the inequality p x1 x2 gt 0 p 2 x174 2 x1 3 x2 x1 2 x272 5 x274 prog sosineq prog p And call solver prog sossolve prog Program is feasible thus p x1 x2 is an SOS echo off Figure 4 1 Sum of squares test sosdemo1 m 33 34 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING with an equilibrium at the origin Notice that the linearization of 4 2 has zero eigenvalue and therefore cannot be used to analyze local stability of the equilibrium Now assume that we are interested in a quadratic Lyapunov function V x for proving stability of the system Then V x must satisfy V daiia ira gt 0 OV OV OV RA AR OM a 4 3 0x1 a 0x9 ds 0x3 e The first inequality with e being any constant greater than zero is needed to guarantee positive definiteness of V x However notice that lt 3 is a rational function and therefore 4 3 is not a valid SOSP constraint But since 23 1 gt 0 for any x3 we can just reformulate 4 3 as Vi Wo Vr Ss Ee gt 0 E 23 1 21 TA x3 Dio dm 13 Dis gt 0 Thus we have the following SOSP we choose e 1 SOSDEMO Find a polynomial V x such that V 27 3 23 Vio WV WV 5 dm x3 Di E x x3 D o 9 a x3 Diz The MATLAB code is available in sosdemo2 m or sosdemo2p m when polynomial objects are
67. uristics to reduce the set of monomials The optimal reduced set of monomials will be computed and used only if a third argument sparse is given to sosineg as illustrated by the following command gt gt Program3 sosineq Program3 x 16 2 x 8 y 2 y 4 sparse which tests whether or not x 2x8y y is a sum of squares See Section 3 4 3 for a discussion on exploiting sparsity A special sparsity structure that can be easily handled is the multipartite structure When a polynomial has this kind of structure the optimal reduced set of monomials in Z7 2 QZ x can be obtained with a low computational effort For this however it is necessary to give a third argument sparsemultipartite to sosineq as well as the partition of the indepen dent variables which form the multipartite structure As an example gt gt p x14x y172 2xx17 2 xx2 2 xy172 x2 2 y1 2 gt gt Program3 sosineq Program3 p sparsemultipartite x1 x2 y1 tests whether or not the multipartite corresponding to partitioning the independent variables to 21 22 and y1 polynomial z y 212x02y 73y is a sum of squares See Section 3 4 4 for a discussion on the multipartite structure NOTE The function sosineq will accept matrix arguments in addition to scalar arguments Matrix arguments are not treated element wise inequalities To avoid confusion it is suggested that sosmatrixineq is used when defining matrix inequalities
68. used and is also shown in Figure 4 2 The result given by SOSTOOLS is V x 5 54892 4 106822 1 794522 The function findlyap is provided by SOSTOOLS and can be used to compute a polynomial Lyapunov function for a dynamical system with polynomial vector field This function take three arguments where the first argument is the vector field of the system the second argument is the ordering of the independent variables and the third argument is the degree of the Lyapunov function Thus for example to compute a quadratic Lyapunov function V x for the system 3 t 0 29 Ta T Lo type gt gt syms x1 x2 gt gt V findlyap x1 3 x2 x1 x2 x1 x2 2 If no such Lyapunov function exists the function will return an empty V 4 3 Global and Constrained Optimization Consider the problem of finding a lower bound for the global minimum of a function f x x R This problem is addressed in 22 where an SOS based approach was first used A relaxation 4 3 GLOBAL AND CONSTRAINED OPTIMIZATION 35 SOSDEMO2 Lyapunov Function Search Section 3 2 of SOSTOOLS User s Manual h clear echo on syms x1 x2 x3 vars x1 x2 x3 Constructing the vector field dx dt f f x1 3 x1 x3 2 x2 x172 x2 x34 3 x172 x3 3 x3 x3 2 1 First initialize the sum of squares program prog sosprogram vars The Lyapunov function V x prog V sospolyvar prog x172 x272 x3 2
69. vailable to the user and are declared using sosmatrixineq For a polynomial matrix variable M 0 it allows one to either define expressions such as y M 0 y to be a sum of squares polynomial in R y 0 or to directly constrain the matrix M 0 to be a sum of squares polynomial matrix in R 0 Once a matrix variable M 0 has been declared using sospolymatrixvar we constrain y M 0 y to be a sum of squares polynomial using sosmatrixineq as illustrated below gt gt syms thetal theta2 gt gt theta thetal theta2 gt gt prog sosprogram theta gt gt prog M sospolymatrixvar prog monomials theta 0 2 3 3 symmetric gt gt prog sosmatrixineq prog M quadraticMineq Note that the user does not declare the vector of indeterminates y as this is handled internally by SOSTOOLS The naming convention used for the indeterminates is Mvar_i where the subscript i is used for indexing In order to save memory the Mvar_i variables may be used with multiple inequalities therefore i will never be greater than the dimension of the largest matrix inequality Some basic error checking has been included that ensures that the matrix argument being passed into sosmatrixineq is square and symmetric Else one can ask for M 0 to be sum of squares matrix in R 9 using the following command gt gt prog sosmatrixineq prog M Mineq A special case of polynomial matrix inequalities are Linear Matrix
70. vartable field will not exist and prog vartable which is a character array is used instead Next a polynomial variable V in the monomials x y 22 is declared using gt gt prog V sospolyvar prog x 2 y72 z 2 which sets the field prog var as follows gt gt prog var prog var num 1 type poly Zi 1 3x3 double LL 1 3x3 double T 3x3 double idx 1 4 The field prog var num is an integer that gives the number of variables declared In this case there is only one variable V as such each of the remaining fields excluding prog var idx contains a single entry As more variables are declared these fields will contain arrays where each element corresponds to exactly one variable The type of variable i e polynomial or sum of squares polynomial is indicated by prog var type for example an SOSP with two polynomials and a sum of squares polynomial variable would result in gt gt prog var type prog var type gt poly poly sos Returning to the example recall that the polynomial V consists of three monomials x y 22 with unknown coefficients The field prog var Z is the monomial degree matrix whose entries are the monomial exponents For a polynomial in n variables containing m monomials this matrix will have dimension m x n In this case V is clearly a 3 x 3 matrix with 2 s on the diagonal A more illuminating example is given below 55 gt gt prog h sospo
71. x2 x3 is an SOS matrix echo off Figure 4 10 Computing a SOS matrix decomposition sosdemo9 m 50 CHAPTER 4 APPLICATIONS OF SUM OF SQUARES PROGRAMMING 4 10 Set Containment This example illustrates how SOSTOOLS v3 00 can be used to compute the entries of a polynomial matrix P such that it is an SOS matrix It has been shown in 26 that if the matrix P x given by 9 s 2 y p x go z g x ds gota gi a 1 ai is an SOS matrix then the following set containment holds x R p x lt y x R go x gi x 0 9 go x ga x gt 0 4 20 where given are p x a positive polynomial go R x and 0 y gt 0 are positive scalars If a polynomial g 1 and SOS multiplier s x are found then the set containment holds This problem is a sum of squares feasability problem the code for this demo is given in Figure 4 11 SOSDEMO10 Given p x R z go x Riz 0 R y ER find polynomial gi x R x Sum of Squares s x such that 4 19 is a sum of squares matrix The feasibility test above is formulated and solved in sosdemo10 m for p x x7 23 y 0 1 and go 211 a sum of squares variable s x of degree 4 and a polynomial variable gy x containing monomials of degrees 2 and 3 This example illustrates the use of function sosineq having a matrix as an input argument 4 10 SET CONTAINMENT 51 Y SOSDEMO10 Set containment Section 3 10 of SOSTOOLS User s Manual

SOSTOOLS - Control & Dynamical Systems

Contents

Download Pdf Manuals

Related Search

Related Contents

SOSTOOLS - Control &amp; Dynamical Systems

Contents

Download Pdf Manuals

Related Search

Related Contents

SOSTOOLS - Control & Dynamical Systems