 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 ). 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. . 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 , Parrilo and Stur- mfels  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 . Precise and comprehensive overview of the results about topic has been done by M. Laurent in . 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 , YALMIP [13,14], and Sparse- POP . 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  proved that real given polynomial in NC J. POVH Copyright © 2011 SciRes. AM 310variables 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 . 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  for a nice survey of these beginnings of free se- mialgebraic geometry. The first author in  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 . 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  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 jijXYtraceXY 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=,,nxxx. Elements of x are therefore polynomials, which can be written as follows   1212== ,niiiiii niipxcxcx xx  where i are vectors from n, which define the expo- nents of monomials. The degree of monomial x is =ideg xi and the degree of polynomialpx =iiicx is =iijdeg pjmax. If all monomials in p have the same degree d, we say that p is d-form. Note that the coefficient ic 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=,,,nxxx x is denoted by x and consists of linear combinations of all finite words with letters 1,,nxx. We endow x with the invo-lution *, which reverses the order of the letters in any word, i.e. it holds***=pq p+qand ***=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 2xy and 2yx, 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,,,mCA A and vector mb, 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.iiCX PSDPstA XbimX The conic dual problem to PSDP is the semidefinite program in the standard dual form (DSDP) max..= ,,0.TiiimbystyAZCDSDPyZ 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  with a comprehensive list of state-of-the-art SDP solvers and also ). 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 311nomial. Indeed, the problem =min: npoptpxx  (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,,kqq such that 2=iipq. 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: .poptpxis SOS The inequality from above might be strict, as also fol- lows from the following example. Example 3. Polynomial 42 24 622212312 12 3123,, =3Mxxxxxxxx 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 =,Tpx 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 22412112 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 221212,,xxxx. Polynomial p has therefore the SOS decomposition if there exists positive semidefinite matrix Q such that 12,=Tpxx UQU, for 221212=,, TxxxxU. For the ma- trix Q we have linear constraints that its components must coincide with the coefficients of p. We have in p monomial 41x with coefficient 2, therefore it must hold 1,1 =2q and similarly 2,2 =5q. Monomial 312xx has coefficient 2 in and can be obtained as 2112xxx, hence we have also constraint 1,33,1 =2qq or equiva- lently 1,3 3,1==1qq . Monomial 2212xx can be obtained as a product of 21x in 22x or as a square of 12xx, there- fore 1,22,13,3 =1qqq. Monomial 312xx 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 2311=350=013 0132105T   Q We have the following SOS decomposition:  2222 21212122121,=2 33.2pxxxxxxxxx  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 1ndd 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 ndd many of them. We can find examples, where we indeed need all these monomials. If =4n and =10d, we ob- tain 1286ndd and ndd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 312is 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 , 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21). Example 5. If p is from Example 4, we have 2=4,0,3,1,2,2,0,4pCONV and 1=2,0,1,1,0,22 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,,kqq such that *=iiipqq. 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 0Q, where U is vector of all monomials of degree d. If we consider all possible monomials of degree d, then vector U has 111dnd 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 12222112121 12121212,=136 3pxxxxxxxxxx xxxxx x   Since p has degree 4, there are 321=7 monomi- als which might appear in the vector U from the SOHS decomposition: 221212211 2=1, ,,,,,.Txxxxxxx 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 21x in 22x from U to obtain 121221=1, ,,,.TxxxxxxU We have *12,=pxx UQU (3) if and only if Q satisfies equations: 1,12,22,33,21,44,1 1,55,12,5 5,25,54,4=1=3=2=6=3=1.qqqqqqqqqqqq  Beside these constraints we get also a bunch of homo- genous equations: since 22x does not appear in p, Q must satisfy 3,3 =0q. We also miss 212xx and 221xx 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 ) gives the following optimal solution 100100300 3==000001001 003003TQPP where 10010=.0300 3P Therefore we obtain   1212121 211 21,=113**pxxxxxxxxxxxx.  Note that 2x 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 313INPUT: px 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 iq be the ith component of PX. OUTPUT: SOHS decomposition *=iiipqq. 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 ix the monomial, where ix has highest/lowest degree, must be symmetric. The first observation is very important: it leads to the so-called Newton chip method , 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 . 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 . However, since all cons- traints in the resulting SDP are always orthogonal, we see a strong potential in the boundary poin t method , 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  H. Wolkowicz, R. Saigal and L. Vandenberghe, “Hand-Book of Semidefinite Programming,” Kluwer, Academic Publishers, Boston, 2000.  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  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  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  P. A. Parrilo, “Semidefinite Programming Relaxations for Semialgebraic Problems,” Mathematical Programming, Vol. 96, No. 2, Series B, 2003, pp. 293-320.  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.  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  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  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 314149, 2009, pp. 157-270.  SOSTools, 2011. http://www.cds.caltech.edu/sostools/.  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.  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/  YALMIP, 1 March 2009. http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php  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.  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  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  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  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.  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  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  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  H. Mittelman, 2011. http://plato.asu.edu/sub/pns.html.  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  P. Parrilo, “Structured Semidefinite Programs and Se-mialgebraic Geometry Methods in Robustness and Opti-mization,” PhD Thesis, California Institute of Technolo-gy, California, 2000.  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.  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  SeDuMi, 29 June 2009. http://sedumi.ie.lehigh.edu/  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