### 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 language | English |
---|---|

Title of host publication | Emerging Applications of Algebraic Geometry |

Editors | M. Putinar, S. Sullivant |

Place of Publication | New York |

Publisher | Springer Verlag |

Pages | 155-270 |

ISBN (Print) | 9780387096858 |

Publication status | Published - 2009 |

### Publication series

Name | The IMA Volumes in Mathematics and its Applications Series |
---|---|

Number | 149 |

## Fingerprint Dive into the research topics of 'Sums of squares, moment matrices and optimization over polynomials'. Together they form a unique fingerprint.

## 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). Springer Verlag.