Polynomial Optimization and the Moment Problem

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.

Name thesis:degree_name

Doctor of Philosophy (Ph.D.)

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Saskatchewan

Year dc:date.issued

2012

Author dc:creator

• Ghasemi, Mehdi

Advisors dc:contributor.advisor

• Kuhlmann, Salma
• Marshall, Murray

Committee members dc:contributor.committeemember

• Bremner, Murray
• Samei, Ebrahim
• Sarty, Gordon
• Soteros, Chris

• Optimization
• Moment Problem
• sums of squares
• linear functional

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/10388/ETD-2012-08-590

OAI identifier oai:identifier

oai:harvest.usask.ca:10388/ETD-2012-08-590