Optimization with nonnegative polynomials

Several optimization problems can be formulated over the cone of nonnegative polynomials. Any nonnegative polynomial in one variable can be represented as a sum-of-squares (SOS). This allows for the formulation of the optimization problems as a semidefinite programming problem. However, when considering multivariable polynomials, there are nonnegative polynomials that can not be represented as SOS. On the other hand, such a polynomial can be approximated arbitrary well by a SOS-polynomial. In this PhD research the properties of nonnegative polynomials and SOS-polynomials will be studied and efficient and accurate algorithms will be designed for solving corresponding optimization problems.

This research fits perfectly into the research of NALAG. The current research in linear algebra in the NALAGroup has emerged from the study of the theoretical properties of fast algorithms for matrices with a low displacement rank structure like Hankel and Toeplitz as well as the design of corresponding efficient and accurate methods.

It turns out that these matrices also appear as the moment matrices into a dual formulation of optimization problems involving nonnegative polynomials in one variable. Generalizations of these matrices and efficient and accurate methods are needed in the formulation and solution of these problems for multiple variables.