Algorithm for Polynomial Optimization and Interpolation based on Hyponormality

Event Sponsor: 
Mathematics and Computer Science Division LANS Seminar
Start Date: 
Mar 22 2017 - 3:00pm
Building 240/Room 1404
Argonne National Laboratory
Cédric Josz
Speaker(s) Title: 
Laboratory for Analysis & Architecture of Systems (LAAS-CNRS France)

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.

Miscellaneous Information: 

Coffee and goodies will be served.

Please click below to add this event to your calendar.