The approach of moments for polynomial equations

M. Laurent, P. Rostalski

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

265 Downloads (Pure)

Abstract

In this chapter 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 chapter sheds some light on the underlying theory and the link to polynomial optimization.
Original languageEnglish
Title of host publicationHandbook on Semidefinite, Cone and Polynomial Optimization
EditorsM.F. Anjos, J.B. Lasserre
Place of PublicationAmsterdam
PublisherElsevier
Pages25-60
Number of pages957
ISBN (Print)9781461407683
Publication statusPublished - 2012

Publication series

NameInternational Series in Operations Research & Management Science
Number166

Fingerprint

Polynomial equation
Moment
Polynomial
Semidefinite Optimization
Numerical Linear Algebra
Semidefinite Relaxation
Nonconvex Optimization
Nonconvex Problems
Zero set
Commutative Algebra
Sum of squares
Optimization Problem
Optimization
Computing

Cite this

Laurent, M., & Rostalski, P. (2012). The approach of moments for polynomial equations. In M. F. Anjos, & J. B. Lasserre (Eds.), Handbook on Semidefinite, Cone and Polynomial Optimization (pp. 25-60). (International Series in Operations Research & Management Science; No. 166). Amsterdam: Elsevier.
Laurent, M. ; Rostalski, P. / The approach of moments for polynomial equations. Handbook on Semidefinite, Cone and Polynomial Optimization. editor / M.F. Anjos ; J.B. Lasserre. Amsterdam : Elsevier, 2012. pp. 25-60 (International Series in Operations Research & Management Science; 166).
@inbook{f08f3cd2b83e4bf19322a70e7b5715ce,
title = "The approach of moments for polynomial equations",
abstract = "In this chapter 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 chapter sheds some light on the underlying theory and the link to polynomial optimization.",
author = "M. Laurent and P. Rostalski",
note = "Pagination: 957",
year = "2012",
language = "English",
isbn = "9781461407683",
series = "International Series in Operations Research & Management Science",
publisher = "Elsevier",
number = "166",
pages = "25--60",
editor = "M.F. Anjos and J.B. Lasserre",
booktitle = "Handbook on Semidefinite, Cone and Polynomial Optimization",
address = "Netherlands",

}

Laurent, M & Rostalski, P 2012, The approach of moments for polynomial equations. in MF Anjos & JB Lasserre (eds), Handbook on Semidefinite, Cone and Polynomial Optimization. International Series in Operations Research & Management Science, no. 166, Elsevier, Amsterdam, pp. 25-60.

The approach of moments for polynomial equations. / Laurent, M.; Rostalski, P.

Handbook on Semidefinite, Cone and Polynomial Optimization. ed. / M.F. Anjos; J.B. Lasserre. Amsterdam : Elsevier, 2012. p. 25-60 (International Series in Operations Research & Management Science; No. 166).

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review

TY - CHAP

T1 - The approach of moments for polynomial equations

AU - Laurent, M.

AU - Rostalski, P.

N1 - Pagination: 957

PY - 2012

Y1 - 2012

N2 - In this chapter 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 chapter sheds some light on the underlying theory and the link to polynomial optimization.

AB - In this chapter 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 chapter sheds some light on the underlying theory and the link to polynomial optimization.

M3 - Chapter

SN - 9781461407683

T3 - International Series in Operations Research & Management Science

SP - 25

EP - 60

BT - Handbook on Semidefinite, Cone and Polynomial Optimization

A2 - Anjos, M.F.

A2 - Lasserre, J.B.

PB - Elsevier

CY - Amsterdam

ER -

Laurent M, Rostalski P. The approach of moments for polynomial equations. In Anjos MF, Lasserre JB, editors, Handbook on Semidefinite, Cone and Polynomial Optimization. Amsterdam: Elsevier. 2012. p. 25-60. (International Series in Operations Research & Management Science; 166).