SUMS OF SQUARES, MOMENT MATRICES AND OPTIMIZATION OVER POLYNOMIALS

SUMS OF SQUARES, MOMENT MATRICES AND OPTIMIZATION OVER POLYNOMIALS

February 5, 2008 | MONIQUE LAURENT
The paper discusses polynomial optimization over semialgebraic sets, which is NP-hard in general. It presents hierarchies of semidefinite relaxations based on positive semidefinite moment matrices and sums of squares of polynomials. These relaxations provide asymptotic or finite convergence, optimality certificates, and extraction of global optima. Key mathematical tools include sums of squares representation for positive polynomials, moment matrices (Curto and Fialkow), and algebraic eigenvalue methods for solving polynomial systems. The paper reviews the polynomial optimization problem, its instances, and the scope of the paper. It covers algebraic preliminaries, positive polynomials and sums of squares, moment sequences and matrices, and the application of these concepts to polynomial optimization. The paper also discusses the connection between positive polynomials and sums of squares, the theory of moments, and the use of semidefinite programming for optimization. It provides detailed proofs and background on these topics, emphasizing the role of algebraic geometry and semidefinite programming in solving polynomial optimization problems. The paper concludes with an overview of the contents and the main results of the survey.The paper discusses polynomial optimization over semialgebraic sets, which is NP-hard in general. It presents hierarchies of semidefinite relaxations based on positive semidefinite moment matrices and sums of squares of polynomials. These relaxations provide asymptotic or finite convergence, optimality certificates, and extraction of global optima. Key mathematical tools include sums of squares representation for positive polynomials, moment matrices (Curto and Fialkow), and algebraic eigenvalue methods for solving polynomial systems. The paper reviews the polynomial optimization problem, its instances, and the scope of the paper. It covers algebraic preliminaries, positive polynomials and sums of squares, moment sequences and matrices, and the application of these concepts to polynomial optimization. The paper also discusses the connection between positive polynomials and sums of squares, the theory of moments, and the use of semidefinite programming for optimization. It provides detailed proofs and background on these topics, emphasizing the role of algebraic geometry and semidefinite programming in solving polynomial optimization problems. The paper concludes with an overview of the contents and the main results of the survey.
Reach us at info@study.space
Understanding Sums of Squares%2C Moment Matrices and Optimization Over Polynomials