Sums of squares, moment matrices and optimization over polynomials

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

303 Downloads (Pure)

Abstract

We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background.
Original languageEnglish
Title of host publicationEmerging Applications of Algebraic Geometry
EditorsM. Putinar, S. Sullivant
Place of PublicationNew York
PublisherSpringer Verlag
Pages155-270
ISBN (Print)9780387096858
Publication statusPublished - 2009

Publication series

NameThe IMA Volumes in Mathematics and its Applications Series
Number149

Fingerprint

Moment Matrix
Polynomial equation
Sum of squares
Finite Convergence
Positive Polynomials
Semidefinite Relaxation
Semi-algebraic Sets
Polynomial
Asymptotic Convergence
Optimization
Zero-dimensional
Positive semidefinite
Global Optimum
Certificate
Optimality
NP-complete problem
Eigenvalue
Approximation
Hierarchy
Review

Cite this

Laurent, M. (2009). Sums of squares, moment matrices and optimization over polynomials. In M. Putinar, & S. Sullivant (Eds.), Emerging Applications of Algebraic Geometry (pp. 155-270). (The IMA Volumes in Mathematics and its Applications Series; No. 149). New York: Springer Verlag.
Laurent, M. / Sums of squares, moment matrices and optimization over polynomials. Emerging Applications of Algebraic Geometry. editor / M. Putinar ; S. Sullivant. New York : Springer Verlag, 2009. pp. 155-270 (The IMA Volumes in Mathematics and its Applications Series; 149).
@inbook{9fef820b69d243f2a501e933b30bd977,
title = "Sums of squares, moment matrices and optimization over polynomials",
abstract = "We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background.",
author = "M. Laurent",
year = "2009",
language = "English",
isbn = "9780387096858",
series = "The IMA Volumes in Mathematics and its Applications Series",
publisher = "Springer Verlag",
number = "149",
pages = "155--270",
editor = "M. Putinar and S. Sullivant",
booktitle = "Emerging Applications of Algebraic Geometry",
address = "Germany",

}

Laurent, M 2009, Sums of squares, moment matrices and optimization over polynomials. in M Putinar & S Sullivant (eds), Emerging Applications of Algebraic Geometry. The IMA Volumes in Mathematics and its Applications Series, no. 149, Springer Verlag, New York, pp. 155-270.

Sums of squares, moment matrices and optimization over polynomials. / Laurent, M.

Emerging Applications of Algebraic Geometry. ed. / M. Putinar; S. Sullivant. New York : Springer Verlag, 2009. p. 155-270 (The IMA Volumes in Mathematics and its Applications Series; No. 149).

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

TY - CHAP

T1 - Sums of squares, moment matrices and optimization over polynomials

AU - Laurent, M.

PY - 2009

Y1 - 2009

N2 - We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background.

AB - We consider the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. Hierarchies of semidefinite relaxations have been proposed in the literature, involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. We present these hierarchies of approximations and their main properties: asymptotic/finite convergence, optimality certificate, and extraction of global optimum solutions. We review the mathematical tools underlying these properties, in particular, some sums of squares representation results for positive polynomials, some results about moment matrices (in particular, of Curto and Fialkow), and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. We try whenever possible to provide detailed proofs and background.

M3 - Chapter

SN - 9780387096858

T3 - The IMA Volumes in Mathematics and its Applications Series

SP - 155

EP - 270

BT - Emerging Applications of Algebraic Geometry

A2 - Putinar, M.

A2 - Sullivant, S.

PB - Springer Verlag

CY - New York

ER -

Laurent M. Sums of squares, moment matrices and optimization over polynomials. In Putinar M, Sullivant S, editors, Emerging Applications of Algebraic Geometry. New York: Springer Verlag. 2009. p. 155-270. (The IMA Volumes in Mathematics and its Applications Series; 149).