SUMS OF SQUARES, MOMENT MATRICES AND OPTIMIZATION OVER POLYNOMIALS

SUMS OF SQUARES, MOMENT MATRICES AND OPTIMIZATION OVER POLYNOMIALS

February 5, 2008 | MONIQUE LAURENT
This paper focuses on the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. The authors present hierarchies of semidefinite relaxations involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. These hierarchies are shown to have asymptotic and finite convergence, provide optimality certificates, and extract global optimum solutions. The paper reviews the mathematical tools underlying these properties, including sums of squares representation results for positive polynomials, results about moment matrices, and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. The introduction discusses several instances of the polynomial optimization problem, such as unconstrained polynomial minimization, testing matrix copositivity, the partition problem, and the distance realization problem, highlighting their NP-hard nature. The scope of the paper is also outlined, emphasizing the NP-hardness of the polynomial optimization problem and the contributions of various researchers in the field. The preliminaries on polynomials, semidefinite programs, and the quotient algebra \(\mathbb{R}[\mathbf{x}]/\mathcal{I}\) are provided to establish the necessary background for the main results.This paper focuses on the problem of minimizing a polynomial over a semialgebraic set defined by polynomial equations and inequalities, which is NP-hard in general. The authors present hierarchies of semidefinite relaxations involving positive semidefinite moment matrices and the dual theory of sums of squares of polynomials. These hierarchies are shown to have asymptotic and finite convergence, provide optimality certificates, and extract global optimum solutions. The paper reviews the mathematical tools underlying these properties, including sums of squares representation results for positive polynomials, results about moment matrices, and the algebraic eigenvalue method for solving zero-dimensional systems of polynomial equations. The introduction discusses several instances of the polynomial optimization problem, such as unconstrained polynomial minimization, testing matrix copositivity, the partition problem, and the distance realization problem, highlighting their NP-hard nature. The scope of the paper is also outlined, emphasizing the NP-hardness of the polynomial optimization problem and the contributions of various researchers in the field. The preliminaries on polynomials, semidefinite programs, and the quotient algebra \(\mathbb{R}[\mathbf{x}]/\mathcal{I}\) are provided to establish the necessary background for the main results.
Reach us at info@study.space