Optimization Online


The Approach of Moments for Polynomial Equations

Monique Laurent(M.Laurent***at***cwi.nl)
Philipp Rostalski(philipp***at***math.berkeley.edu)

Abstract: In this article we present the moment based approach for computing all real solutions of a given system of polynomial equations. This approach builds upon a lifting method for constructing semidefinite relaxations of several nonconvex optimization problems, using sums of squares of polynomials and the dual theory of moments. A crucial ingredient is a semidefinite characterization of the real radical ideal, consisting of all polynomials with the same real zero set as the system of polynomials to be solved. Combining this characterization with ideas from commutative algebra, (numerical) linear algebra and semidefinite optimization yields a new class of real algebraic algorithms. This article sheds some light on the underlying theory as well as on various extensions and research directions.

Keywords: Zero-dimensional ideal, real root finding, semidefinite optimization, method of moments

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: This article was submitted as a chapter for the "Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications"

Download: [Postscript][PDF]

Entry Submitted: 08/12/2010
Entry Accepted: 08/12/2010
Entry Last Modified: 08/12/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society