On Decompositions of Real Polynomials Using Mathematical Programming Methods

Janez Povh
DOI: 10.4236/am.2011.23036                

Abstract

We present a procedure that gives us an SOS (sum of squares) decomposition of a given real polynomial in variables, if there exists such decomposition. For the case of real polynomials in 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

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	H. Wolkowicz, R. Saigal and L. Vandenberghe, “Handbook of Semidefinite Programming,” Kluwer, Academic Publishers, Boston, 2000.
[2]	J. B. Lasserre, “Global Optimization with Polynomials and the Problem of Moments,” SIAM Journal on Optimization, 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 Optimization 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 Algebraic 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 Optimization, 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 Applications of Algebraic Geometry, IMA Volumes in Mathematics and Its Applications, Springer, New York, Vol. 149, 2009, pp. 157-270.
[10]	SOSTools, 2011. http://www.cds.caltech.edu/sostools/.
[11]	S. Prajna, A. Papachristodoulou, P. Seiler and P. A. Parrilo, “SOSTOOLS and Its Control Applications,” Positive Polynomials in Control, Lecture Notes in Control and Information and Science, Springer, Berlin, Vol. 312, 2005, pp. 273-292.
[12]	D. Henrion, J. -B. Lasserre and J. L?fberg, “GloptiPoly 3: Moments, Optimization and Semidefinite Programming,” 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 Optimization 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 Sparsity,” 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 Geometry, 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 Polynomials,” 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 Semialgebraic Geometry Methods in Robustness and Optimization,” PhD Thesis, California Institute of Technology, 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 Mathematics, 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 Computer Algebra System for Symbolic and Numerical Computation with Noncommutative Polynomials,” 2011. http: //ncsostools.fis.unm.si