Repository logo
 

Polynomial Optimization and the Moment Problem

Date

2012-09-14

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

Part Of

item.page.relation.ispartofseries

DOI

item.page.identifier.pmid

item.page.identifier.pmcid