Algorithm for Polynomial Optimization and Interpolation based on Hyponormality

Cedric Josz
Seminar

On one hand, we consider the problem of extracting globally optimal solutions from a polynomial optimization problem and, on the other hand, we consider the problem of interpolating a set of points with a complex exponential function. We propose a single algorithm to address both problems that draws on the operator theoretic notion of hyponormality. Concerning optimization, it seems to be the first algorithm this is capable of extraction globally optimal solutions from a polynomial optimization problem where the variables and data are complex numbers. It also applies to real polynomial optimization, a special case of complex polynomial optimization, and thus extends the work of Henrion and Lasserre implemented in GloptiPoly. Concerning interpolation, our algorithm provides an alternative to Prony's method based on the Autonne-Takagi factorization and it avoids solving a Vandermonde system. The algorithm and its proof are based exclusively on linear algebra. They are devoid of notions from algebraic geometry, contrary to existing methods for interpolation. The algorithm is tested on a series of examples, each illustrating a different facet of the approach. One of the examples demonstrates that hyponormality can be enforced numerically to strengthen a convex relaxation and to force its solution to have rank one.