Paper Menu >>
Journal Menu >>
Applied Mathematics, 2011, 2, 309-314 doi:10.4236/am.2011.23036 Published Online March 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM On Decompositions of Real Polynomials Using Mathematical Programming Methods Janez Povh Faculty of Information Studies Novo Mesto, Novo mesto, Slovenia Institute of Mathematics, Physics and Mechanics Ljubljana, Ljubljana, Slovenia E-mail: janez.povh@fis.unm.si Received March 5, 2010; revised January 11, 2011; accepted January 15, 2011 Abstract We present a procedure that gives us an SOS (sum of squares) decomposition of a given real polynomial in n variables, if there exists such decomposition. For the case of real polynomials in n non-commutative variables we extend this procedure to obtain a sum of hermitian squares SOHS) decomposition whenever there exists any. This extended procedure is the main scientific contribution of the paper. Keywords: Commutative Polynomial, Noncommutative Polynomial, Sum Of Squares, Semidefinite Programming, Newton Polytope 1. Introduction Operations research, especially mathematical program- ming as subfield, very often makes progress by using re- sults from other (“pure”) areas of mathematics, such as analysis, algebra, probability etc. Rarely happens the contrary, i.e. that the new methods, developed by mathe- matical programming commu nity, in spires fu rther resear- ch in pure mathematics. One of the main breakthrough in operations research in last decades was development of theoretically and pra- ctically efficient interior-point methods for convex opti- mization problems. These methods were initially deve- loped for linear programming (LP) problems and later extended to many other convex optimization problems. The first non-trivial class of optimization problems, to which the interior point methods were extended, was the class of linear programs over the cone of positive semi- definite matrices or over the second order cone (see Sec- tion 2 and [1]). Once we became able to solve semidefinite programs efficiently (i.e. we can find -optimal solution in the time, which is a polynomial function of log and the size of the input data), the class of instances of the pro- blems of this type and the methods to so lve them (called semidefinite programming ) became very important tool in optimization, control and also many other areas of applied mathematics and engineering, see e.g. [1]. Computing global minimum of a given real polyno- mial over the set, defined by po lynomial inequalities (we call such set a semi-algebraic set) is an NP-hard problem, since it includes linear binary problems. Several authors, in particular Lasserre [2-4], Parillo [5], Parrilo and Stur- mfels [6] and Schweighofer [7,8] have shown how to solve such a problem approximately by a sequence of se- midefinite progr a ms. The main results needed to construct such a sequence are the fact that if a given polynomial is a sum of squares (SOS), then it is non-negative, and the dual theory of moments [2]. Precise and comprehensive overview of the results about topic has been done by M. Laurent in [9]. Checking whether given polynomial is non-negative is an NP-hard problem, but checking if given polynomial is SOS can be done efficiently in theory and practise by se- midefinite programming. This topic has been well explo- ited in recent years and currently there are available soft- ware packages to detect SOS polynomials and to do po- lynomial opti mizatio n. Readers in terested in so lvin g sums of squares problems for commuting polynomials are re- ferred to one of the great existing packages SOSTOOLS [10,11], GloptiPoly [12], YALMIP [13,14], and Sparse- POP [15]. Comparing to commuta tive po lynomials is t he problem of writing a on-commutative polynomial as a sum of her- mitian squares (SOHS) much less exploited—theoreti- cally and practically. However, several results show that this area is interesting and important. Helton [16] proved that real given polynomial in NC J. POVH Copyright © 2011 SciRes. AM 310 variables is SOHS if and only if it yields a positive semi- definite matrix (PSD) after substituting the variable by symmetric real matrices of the same size. For a beautiful exposition, we refer the reader to [17]. Together with coworkers Helton pursued line of re- search of NC polynomials further, studied positivity and convexity of NC polynomials and gave applications to control theory, optimization, systems engineering, etc.; see [18] for a nice survey of these beginnings of free se- mialgebraic geometry. The first author in [19] connected sums of hermitian squares of NC polynomials to an old open problem of Connes on von Neumann algebras, and, somewhat related, found applications to mathematical physics [20]. Many of these results were obtained with the aid of computer programs written in an ad-hoc man- ner. Despite the fast rise of free semialgebraic geometry, it seems that [21] is the first publication about theoretical algorithm and publicly available software for computing (or determining existence) of sums of hermitian squares (SOHS) decompositions of NC polynomials. In this paper we illustrate the procedures mentioned above on a number of well-chosen examples. 1.1. Notation In the paper we use standard notation from optimization and algebra. By 0X we denote that X is positive se- midefinite (i.e. X is symmetric and has only non-negative eigenvalues). The scalar product of two matrices X and Y of the same size is , , ,= = Tiji j ij X YtraceXY xy .By I we denote the identity matrix. A set of real polynomials in n (commutative) vari- ables (algebraists call this set algebra of real polyno- mials) is denoted by 1 =,, n x xx. Elements of x are therefore polynomials, which can be written as follows 12 12 == , n iiii ii n ii pxcxcx xx where i are vectors from n , which define the expo- nents of monomials. The degree of monomial x is =i deg xi and the degree of polynomial px =i i icx is =ii j deg pj max . If all monomials in p have the same degree d, we say that p is d-form. Note that the coefficient i c and the exponent vectors i completely determine the polynomial. Example 1. Polynomial 53 27 ,=10 2pxyxyxy has vectors of exponents 1=5,3 and 2=2,7 . We have =9deg p. The set (free algebra) of non-commutative polynomi- als in variables 12 =,,, n x xx x is denoted by x and consists of linear combinations of all finite words with letters 1,, n x x. We endow x with the invo- lution *, which reverses the order of the letters in any word, i.e. it holds *** =pq p+qand *** =pqq p . The degree of polynomial is length of the longest word. Example 2. Let 222 =1,pxxy xyxxy. We have *222 =1pyxxyx and =5deg p. Remark 1. In the non-commutative case we can not express monomials simply by the vectors of exponents, since monomials 2 x y and 2 y x, which are in commut- ative case equal with the same exponent 21,, are no more equal in the non-commutative case. Instead of this we keep working with monomials, i.e. with the words. 2. Semidefinite Programming Semidefinite programming consists of problems, where we are inte rested for the optimum of a linear function su- bject to linear constraints and additional constraint that all variables are taken from positive semidefinite matrix. More precisely, given symmetric matrices 1 ,,, m CA A and vector m b, we formulate semidefinite program in standard primal form (in the sequel we refer to prob- lems of this type by PSDP) as follows: min , ..,=,=1,, , 0. ii CX PSDP stA Xbim X The conic dual problem to PSDP is the semidefinite program in the standard dual form (DSDP) max ..= , ,0. T ii i m by s tyAZCDSDP yZ As we already mentioned, the importance of semidefi- nite programming was spurred by development of effici- ent methods, which can find -optimal solution in a po- lynomial time of ,nm and log , where n is the or- der of matrix variables Z and X . There exist several freeware package, which also in practice find such solu- tions. If the problem is of the medium size (i.e. 1000n and 10.000m ), these packages are based on the interior point methods, while packages for larger semidefinite programs use some variant of the first order methods (see web page [22] with a comprehensive list of state-of-the-art SDP solvers and also [23]). 3. SOS Decompositions of Commutative Polynomials by SDP SOS decomposition appears naturally when we are in- terested in finding the global optimum of a given poly- J. POVH Copyright © 2011 SciRes. AM 311 nomial. Indeed, the problem =min: n p optpxx (1) is equivalent to max:0 .px Both problems are in general very difficult (i.e. NP- hard), therefore we are forced to relax the problems in order to obtain a tractable one. One of the possibilities is using the SOS decomposition. Definition 1. Polynomial px has a sum of squares decomposition if there exist polynomials 1,, k qq such that 2 =i i pq . If the polynomial p can be written as a sum of squares, then clearly we h ave 0p, while the converse is in general not true. This leads to the following lower bound for the problem (1): max: . p optpxis SOS The inequality from above might be strict, as also fol- lows from the following example. Example 3. Polynomial 42 24 6222 12312 12 3123 ,, =3 M xxxxxxxx xxx is well-known as Motzkin form and is defined by four coefficients and four vectors: 112 233 =1, =4,2,0, =1, =2,4,0, =1, =0,0,6cc c in 44 =3, =2,2,2c It has been shown (see [24, 25]) that 123 ,, 0Mxxx while M has no SOS de- composition. There exist only few sets of polynomials where it holds that a polynomial from this set is non-negative if and only if it has SOS decomposition. This is true for all polynomials in two variables, for all 2-forms and for 4- forms in 3 variables. Obviously the Motzkin form from above is not in any of these sets. Testing whether a given polynomial has SOS decom- position can be done efficiently by semidefinite program- ming, as follows from the following theorem. For the proof see e.g. a proof of non-commutative version [21, Prop. 2.1]. Theorem 1. Polynomial px has SOS decom- position if and only if there exists a positive semidefinite matrix Q such that =, T px UQU where U is the column containing all monomials of degree 2degp. We demonstrate this theorem by the following exam- ple. Example 4. Let us consider 43 224 12112 122 ,=2 25pxxxxx xxx. Since p if 4-form, it follows from above that p has SOS decomposition if and only if it is non-negative. Moreover, in the SOS decomposition we can have only monomials 22 1212 ,, x xxx . Polynomial p has therefore the SOS decomposition if there exists positive semidefinite matrix Q such that 12 ,= T pxx UQU, for 22 1212 =,, T x xxxU. For the ma- trix Q we have linear constraints that its components must coincide with the coefficients of p. We have in p monomial 4 1 x with coefficient 2, therefore it must hold 1,1 =2q and similarly 2,2 =5q. Monomial 3 12 x x has coefficient 2 in and can be obtained as 2 112 x xx, hence we have also constraint 1,33,1 =2qq or equiva- lently 1,3 3,1 ==1qq . Monomial 22 12 x x can be obtained as a product of 2 1 x in 2 2 x or as a square of 12 x x, there- fore 1,22,13,3 =1qqq . Monomial 3 12 x x does not appear p, hence 2,33,2 =0qq and since Q is sym- metric: 2,3 3,2 ==0qq . If we put things together, we are looking for a positive semidefinite matrix Q with com- ponents satisfying the constraints above. Note that the objective function is not important here, i.e. we have the semidefinite feasibility problem. We can solve it by heart: by setting 3,3 =5q we obtain 1,2 2,1 ==3qq. The ma- trix is now completely defined: 231 231 231 1 =350=013 013 2 105 T Q We have the following SOS decomposition: 22 22 2 121212212 1 ,=2 33. 2 pxxxxxxxxx Remark 2. Even though we have an SDP feasibility problem, we usually use the follo wing objective fun ction trace Q, since it is widely accepted as an efficient heu- ristics to obtain the feasible solution with lowest rank. This is important since the rank of Q is exactly the number of factors in SOS decomposi tion. In general we must include in the vector U all mono- mials of degree d, if the polynomial is 2d-form. We have 1nd d of such monomials. If the polynomial has degree 2d, but is not 2d-form, the vector U contains all possible monomials of degree d-there are nd d many of them. We can find examples, where we indeed need all these monomials. If =4n and =10d, we ob- tain 1286 nd d and nd d 1001, hence the re- sulting SDPs are already on the boundary of the set of in- stances, solvable by interior point methods. Nevertheless, very often, especially if the polynomial J. POVH Copyright © 2011 SciRes. AM 312 is sparse (has only few monomials) it is possible to con- siderable decrease the number of monomials in U. We can use a result, first formulated in [26], that characteri- zes the monomials that can appear in a sum of squares repre- sentation. Define the Newton polytope p of given polynomial p of degree 2d as the integer lattice poi n ts in th e co nv ex hull of th e d egr ees , which appear in p. Then, it can be shown that the only mono- mials x that can appear in a sum of squares represen- tation are those such that 2 is in the p (or equivalently p 2 1 ). Example 5. If p is from Example 4, we have 2 =4,0,3,1,2,2,0,4 pCONV and 1=2,0,1,1,0,2 2 hence it defines exactly the monomials which appear in the SOS decomposition. The package SO Stools and some other packages for SOS decompositions are essentially based on the Newton polytope algorithm. 4. SOHS Decompositions for Non-Commutative Polynomials A non-commutative polynomial px has a sum- of-Hermitian-squares (SOHS) decomposition if there exist polynomials 1,, k qq such that * =ii i pqq . One can prove a result, similar to Theorem 1: px of degree 2d has S OH S decomposition if and only if * =,pUQU (2) for some 0Q, where U is vector of all monomials of degree d. If we consider all possible monomials of degree d, then vector U has 111 d nd components. This is much larger comparing to the commutative case. Ne- vertheless, we have also many criteria which tell us when we can leave out some of the monomials from U. We demonstrate the procedure to find SOHS decomposition by the following example. Example 6. Let 12 222 112121 12121212 ,= 136 3 pxx x xxxxxxx xxxxx x Since p has degree 4, there are 3 21=7 monomi- als which might appear in the vector U from the SOHS decomposition: 22 1212211 2 =1, ,,,,,. T xxxxxxx xU Due to the structure of p we can cross out some com- ponents of U: for any monomial from U of (maxi- mum) degree 2 it must hold that its hermitian square mus t be in p. If this is note the case for some monomial, we can eliminate it from U. Therefore we can cross out 2 1 x in 2 2 x from U to obtain 121221 =1, ,,,. T xxxxxxU We have * 12 ,=pxx UQU (3) if and only if Q satisfies equations: 1,1 2,2 2,33,21,44,1 1,55,1 2,5 5,2 5,5 4,4 =1 =3 =2 =6 =3 =1. q q qqqqqq qq q q Beside these constraints we get also a bunch of homo- genous equations: since 2 2 x does not appear in p, Q must satisfy 3,3 =0q. We also miss 2 12 x x and 2 21 x x in p, hence 2,43,5 4,2 5,3=0qqqq . We obtain 13 equa- tions in total, hence we have to solve SDP of order 5 with 13 linear constraints. By using objective trace Q (note Remark 2) our SDP solver (Sedumi [27]) gives the following optimal solution 10010 0300 3 == 00000 1001 0 03003 T QPP where 10010 =. 0300 3 P Therefore we obtain 12 12121 211 21 ,= 113 ** pxx x xxxxxxxxx. Note that 2 x does not appear in the SOHS decompo- sition, therefore we could eliminate it from U. Previous example clearly shows the main steps of the general algorithm to obtain the SOHS decomposition, presented in Figure 1. We can obtain in general case much larger SDP in the non-commutative case, but we have also much more pos- sibilities to exploit th e fact that the polynomials are non- commutative in order to reduce the size of the SDP. In J. POVH Copyright © 2011 SciRes. AM 313 INPUT: p x 1) Construct the vector of possible monomials U. 2) Construct linear equatio n s o n matrix Q. 3) Solve SDP in variable Q. 4) IF the SDP is infeasible, then p has no SOHS decomposition. RETURN. 5) ELSE compute p such that T =QPP. Let i q be the ith component of P X. OUTPUT: SOHS decomposition * =ii i p qq . Figure 1. Algorithm to obtain the SOHS decomposition. particular, we can execute the following: If monomial m appears in the SOHS decompo- sition and must therefore appear in U, then there should exist a symmetric monomial in p which coincides with m in the ||m rightmost variables (letters). At least one of the monomials of highest and of lowest degree must be symmetric. p must be symmetric, i.e. *=pp. For every variable i x the monomial, where i x has highest/lowest degree, must be symmetric. The first observation is very important: it leads to the so-called Newton chip method [21], where we obtain the vector U simply by taking all possible right chips (tails) of all possible symmetric monomials in p, which have length between half of the minimum and half of the maximum degree in p, see also paper [21]. We have also written a Matlab based software package NCsostools, which is a non-commutative version of the Sostools package. It includes an implementation of the algorithm from above and also implementations of most important operations from x . It is freely available from http://ncsostools.fis.unm.si, see also the detailed description of commands [28]. However, since all cons- traints in the resulting SDP are always orthogonal, we see a strong potential in the boundary poin t method [23], which performs very good on such SDP problems, espe- cially if we have large scale SDP. 5. Conclusions In this paper we demonstrated the power of mathematical programming in other, more pure areas of mathematics. Semidefinite programming turned out to be a very strong tool in approximating optimal values of polynomials, since it gives SOS or SOHS decompositions of real polynomials, when they exist. The next step of the re- search will be publishing the NCsostools package, which will contain implementation of the algorithm for finding the SOHS decompositions and also implementations of most important operations in x . A very challenging task for future research is a pr oce- dure to extract an exact rational solution of the SDP from the numerical solution Q, obtained by SDP solver. It is very important since in practice SDP solvers return only approximately feasible so lutions, which ar e sufficient for most purposes. But if we want to have correct proof for SOS or SOHS decomposition, we need an exact rational solution. This is in general very difficult problem (NP- hard) and not much research has been done in this dire- ction. 6. Acknowledgements We gratefully acknowledge financial supported by the Slovenian Research Agency (project No. 1000-08- 210518). 7. References [1] H. Wolkowicz, R. Saigal and L. Vandenberghe, “Hand- Book of Semidefinite Programming,” Kluwer, Academic Publishers, Boston, 2000. [2] J. B. Lasserre, “Global Optimization with Polynomials and the Problem of Moments,” SIAM Journal on Optimi- zation, Vol. 11, No. 3, January 2000, pp. 796-817. doi:10.1137/S1052623400366802 [3] J. -B. Lasserre, “A Sum of Squares Approximation of Nonnegative Polynomials, SIAM Journal on Optimization, Vol. 16, No. 3, 2006, pp. 751-765. doi:10.1137/04061413X [4] D. Henrion and J. -B. Lasserre, “GloptiPoly: Global Op- timization over Polynomials with Matlab and SeDuMi,” ACM Transactions on Mathematical Software, Vol. 29, No. 2, 2003, pp. 165-194. doi:10.1145/779359.779363 [5] P. A. Parrilo, “Semidefinite Programming Relaxations for Semialgebraic Problems,” Mathematical Programming, Vol. 96, No. 2, Series B, 2003, pp. 293-320. [6] P. A. Parrilo and B. Sturmfels, “Minimizing Polynomial Functions,” In Algorithmic and Quantitative Real Alge- braic Geometry (Piscataway, NJ, 2001), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence, RI, Vol. 60, 2003, pp. 83-99. [7] M. Schweighofer, “Optimization of Polynomials on Compact Semialgebraic Sets,” SIAM Journal on Optimi- zation, Vol. 15, No. 3, 2005, pp. 805-825. doi:10.1137/S1052623403431779 [8] M. Schweighofer, “Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares,” SIAM Journal on Optimization, Vol. 17, No. 3, 2006, pp. 920-942. doi:10.1137/050647098 [9] M. Laurent, “Sums of Squares, Moment Matrices and Optimization over Polynomials,” In Emerging Applica- tions of Algebraic Geometry, IMA Volumes in Mathe- matics and Its Applications, Springer, New York, Vol. J. POVH Copyright © 2011 SciRes. AM 314 149, 2009, pp. 157-270. [10] SOSTools, 2011. http://www.cds.caltech.edu/sostools/. [11] S. Prajna, A. Papachristodoulou, P. Seiler and P. A. Par- rilo, “SOSTOOLS and Its Control Applications,” Positive Polynomials in Control, Lecture Notes in Control and In- formation and Science, Springer, Berlin, Vol. 312, 2005, pp. 273-292. [12] D. Henrion, J.-B. Lasse rre and J. Löfberg, “GloptiPoly 3: Moments, Optimiz ation and Semidefinite Progra mming,” 2011. http://www.laas.fr/~henrion/software/ gloptipoly3/ [13] YALMIP, 1 March 2009. http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php [14] J. Löfberg, “YALMIP: A Toolbox for Modeling and Op- timization in MATLAB,” Proceedings of the CACSD Conference, Taipei, 2004. http://control.ee.ethz.ch/~joloef/yalmip.php. [15] H. Waki, S. Kim, M. Kojima and M. Muramatsu, “Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Spar- sity,” SIAM Journal on Optimization, Vol. 17, No. 1, 2006, pp. 218-242. doi:10.1137/050623802 [16] J. W. Helton, ““Positive” Noncommutative Polynomials are Sums of Squares,” Annals of Mathematics, Vol. 156, No. 2, 2002, pp. 675-694. doi:10.2307/3597203 [17] S. McCullough and M. Putinar, “Noncommutative Sums of Squares,” Pacific Journal of Mathematics, Vol. 218, No. 1, 2005, pp. 167-171. doi:10.2140/pjm.2005.218.167 [18] M. C. de Oliveira, J. W. Helton, S. McCullough and M. Putinar, “Engineering Systems and Free Semi-Algebraic Geometry,” Emerging Applications of Algebraic Geome- try, IMA Volumes in Mathematics and Its Applications, Springer, Vol. 149, 2008, pp. 17-62. [19] I. Klep and M. Schweighofer, “Connes’ Embedding Conjecture and Sums of Hermitian Squares,” Advances in Mathematics, Vol. 217, No. 4, 2008, pp. 1816-1837. doi:10.1016/j.aim.2007.09.016 [20] I. Klep and M. Schweighofer, “Sums of Hermitian Squares and the BMV Conjecture,” Journal of Statistical Physics, Vol. 133, No. 4, 2008, pp. 739-760. doi:10.1007/s10955-008-9632-x [21] I. Klep and J. Povh, “Semidefinite Programming and Sums of Hermitian Squares of Noncommutative Polyno- mials,” Journal of Pure and Applied Algebra, Vol. 214, No. 6, 2010, pp. 740-749. doi:10.1016 /j.jpaa.2009.07.003 [22] H. Mittelman, 2011. http://plato.asu.edu/sub/pns.html. [23] J. Povh, F. Rendl and A. Wiegele, “A Boundary Point Method to Solve Semidefinite Programs,” Computing, Vol. 78, No. 3, 2006, pp. 277-286. doi:10.1007/s00607-006-0182-2 [24] P. Parrilo, “Structured Semidefinite Programs and Se- mialgebraic Geometry Methods in Robustness and Opti- mization,” PhD Thesis, California Institute of Technolo- gy, California, 2000. [25] B. Reznick, “Some Concrete Aspects of Hilbert’s 17th Problem,” In Real Algebraic Geometry and Ordered Structures (Baton Rouge, LA, 1996), Contemporary Ma- thematics, American Mathematical Society, Providence, RI, Vol. 253, 2000, pp. 251-272. [26] B. Reznick, “Extremal PSD Forms with Few Terms,” Duke Mathematical Journal, Vol. 45, No. 2, 1978, pp. 363-374. doi:10.1215/S0012-7094-78-04519-2 [27] SeDuMi, 29 June 2009. http://sedumi.ie.lehigh.edu/ [28] K. Cafuta, I. Klep and J. Povh, “NCSOStools: A Com- puter Algebra System for Symbolic and Numerical Computation with Noncommutative Polynomials,” 2011. http: //ncsostools.fis.unm.si |