Sums of squares of polynomials and their applications

ABSTRACT

A multivariate polynomial is a sum of squares (SOS) if it can be written as a sum of squares of other polynomials, i.e., p(x) = ∑ q²;_i;(x), q_i(x) ε R[x;_1;, …, x;_n;].If p(x) is SOS then p(x) ≥ 0 for all x ε ℝ ⁿ, thus making the sum of squares condition a quite natural sufficient test for polynomial nonnegativity.The existence of a decomposition of a multivariate polynomial as a sum of squares is a basic question in pure and applied mathematics. Its rich algebraic and geometric structure has been analyzed in detail in the past, notably by Reznick and coauthors [1], but until very recently the computational implications have not been fully explored. In the last few years there have been some very interesting new developments surrounding sums of squares, that have produced a wide array of results linking foundational questions in real algebra with computational possibilities arising from convex optimization. The possibility of effective computation of SOS decompositions also has important practical consequences, as they can be used in the formulation of easily verifiable certificates of the emptiness of semialgebraic sets via the Positivstellensatz, a central result in real algebraic geometry.In this talk we present an overview of this novel research area, that combines symbolic and numeric techniques from real algebra and optimization. Particularly exciting is the recent availability of efficient approaches, based on convex optimization, for its effective computation. Most of them employ semidefinite programming (SDP) [5] as the essential computational tool. SDP is a class of optimization problems, where the feasible set is the intersection of an affine subspace and the convex cone of positive semidefinite matrices. We will review the basics of SDP, emphasizing its algebraic characterization and properties, as well as some interesting open problems.Along the way, we will learn how to compute sum of squares decompositions for multivariate polynomials using semidefinite programming, how to certify the results using rounding techniques, and how to obtain structured infeasibility certificates for real solutions of systems of polynomial equations and inequalities. The developed techniques unify and generalize many well-known existing methods.The methods introduced in [3, 4] have been significantly strengthened to exploit problem-specific algebraic and numerical structure; see for instance [2]. The basic ideas and algorithms, as well as these recent extensions, will be illustrated with examples drawn from a broad range of domains, including dynamical systems, geometric theorem proving and quantum mechanics.

REFERENCES

• 1: M. D. Choi, T. Y. Lam, and B. Reznick. Sums of squares of real polynomials. Proceedings of Symposia in Pure Mathematics, 58(2):103--126, 1995.
• 2: K. Gatermann and P. A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra, to appear. Available from arXiv:math.AC/0211450, 2002.
• 3: P. A. Parrilo. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization.
• 4: P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems. Math. Prog., 96(2, Ser. B):293--320, 2003.
• 5: H. Wolkowicz, R. Saigal, and L. Vandenberghe, editors. Handbook of Semidefinite Programming. Kluwer, 2000.

INDEX TERMS

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

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

General Terms:
Algorithms, Theory

Keywords:
convex optimization, multivariate polynomials, semidefinite programming, sum of squares