Non-negative Polynomials, Sums of Squares & The Moment Problem

Abstract

This thesis studies polynomial optimization, that is, the problem of minimizing the value of a polynomial over a semi-algebraic set. Such polynomial optimization problems arise in a wide variety of contexts, both in mathematics, and more generally in science and engineering.

In the first part of this thesis, we study a polynomial optimization problem which arises when solving the separability problem in Quantum Information Theory. Our approach is via sums of squares decompositions for polynomials, which provide a natural relaxation for polynomial optimization. Our focus is on the development of practical computational methods to address these problems. We review classical sum of squares relaxations, and give a comparison of the computational complexities between some of the modern state-of-the-art relaxations. Using the insights gained from this analysis we develop a MATLAB package which is able to solve the separability problem in cases which were beyond the reach of previously existing software implementations.

In the second part of this thesis, we study the tracial moment problem, which can be thought of as a dual problem to non-commutative polynomial optimization. For the bivariate quartic tracial moment problem, the problem is well understood when the associated Hankel matrix (which has size 7x7) is positive definite, or positive semi-definite and of rank at most 4. Here we examine the Hankel matrix when it is of rank 5 or 6 and show that there are four canonical cases to study. In two out of the four rank 6 cases, we reformulate the existence of a representing measure, to a feasibility problem of three small linear matrix inequalities and a rank constraint. Our results significantly improve previous approaches to the bivariate quartic tracial moment problem.

Finally, we also study the tracial moment problem on elliptic curves, giving a reduction to the classical moment problem in two out of the three cases. Furthermore, for the classical moment problem on elliptic curves, we give sufficient conditions for a representing measure to exist. Show more