Polynomial Optimization and the Moment Problem
Date
2012-09-14
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
ORCID
Type
Degree Level
Doctoral
Abstract
There are a wide variety of mathematical problems in different areas which are classified under the title of Moment Problem. We are interested in the moment
problem with polynomial data and its relation to real algebra and real algebraic geometry. In this direction, we consider two different variants of moment problem.
The first variant is the global polynomial optimization problem, i.e., finding the minimum of a polynomial f in R[X1,...,Xn] on R^n.
It is known that this problem is NP-hard.
One of the most successful approaches to this problem is semidefinite programming (SDP), which gives a polynomial time method to
approximate the largest real number $r$ such that f-r is a sum of squares of polynomials.
But current implementations of SDP are not able to minimize polynomials in rather small number of variables (>6) of degree >8.
We make use of a result due to Hurwitz, to give a criterion in terms of coefficients of a polynomial to be a sum of squares. Then, using this
criterion, we introduce a much faster method to approximate a lower bound, in this case using geometric programming.
The second variant is where we wish to determine when a given multi-sequence of reals comes from a Borel measure supported on a given subset K of R^n.
This is the so called K-Moment Problem. Using Jacobi's Theorem for archimedean quadratic modules, we generalize a result of Berg
et al. which states that the closure of the cone sums of squares in a weighted l1-topology consists of nonnegative polynomials on a hypercube.
Then we substitute l1-topology with a locally convex topology tau, sums of squares by a cone C and the hypercube by a closed set K, and study the relation
between closure of C in tau and nonnegative polynomials on K to solve the moment problem for a tau-continuous linear functional on R[X1,...,Xn].
We investigate the moment problem for weighted lp-continuous psd functionals and coefficientwise convergence
topology on R[X1,...,Xn]. Then, we fix a set K, and find an appropriate locally convex topology tau, such that sums of 2d powers, solves the K-moment problem
for tau-continuous linear functionals. In other words, we prove that a tau-continuous linear functional nonnegative on sums of 2d powers is representable
by a Borel measure on K.
Description
Keywords
Optimization, Moment Problem, sums of squares, linear functional
Citation
Degree
Doctor of Philosophy (Ph.D.)
Department
Mathematics and Statistics
Program
Mathematics