A Macaulay 2 package for computing sum of squares decompositions of polynomials with rational coefficients

ABSTRACT

In recent years semideffinite programming (SDP) has become the standard technique for computing sum of squares (SOS) decompositions of nonnegative polynomials. Due to the nature of the underlying methods, the solutions are computed numerically, and thus are never exact. In this paper we present a software package for Macaulay 2, which aims at computing an exact SOS decomposition from a numerical solution.

REFERENCES

• 1: M. D. Choi, T. Y. Lam, and B. Reznick. Sums of squares of real polynomials. In K-theory and algebraic geometry: connections with quadratic forms and division algebras, volume 58 of Proc. Sympos. Pure Math., pages 103--126. Amer. Math. Soc., Providence, RI, 1995.
• 2: G. Golub and C. van Loan. Matrix Computations, chapter 4, pages 133--148. Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore Maryland, 2nd edition, 1989.
• 3: D. R. Grayson and M. E. Stillman. Macaulay 2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/
• 4: E. Landau. Über die Darstellung de niter Funktionen als Summe von Quadraten. Math. Ann., 62:290--329, 1906.
• 5: P. A. Parrilo. Structured Semide nite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, 2000.
• 6: H. Peyrl and P. A. Parrilo. SOS.m2, a sum of squares package for Macaulay 2. Available at decompo-http://www.control.ee.ethz.ch/~hpeyrl 2007.
• 7: B. Reznick. Some concrete aspects of Hilbert's 17th problem. In Real algebraic geometry and ordered structures, volume 253 of Contemporary Mathematics, pages 251--272. Amer. Math. Soc., Providence, RI, 2000.
• 8: M. Schweighofer. Algorithmische Beweise für Nichtnegativ-und Positivstellensätze.Master's thesis, Universität Passau, 1999.
• 9: N. Z. Shor. Class of global minimum bounds of polynomial functions. Cybernetics, 23(6):731--734, 1987.
• 10: Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms

Keywords:
algebraic geometry, semideffinite programming, sum of squares, symbolic/numerical methods