Real Algebraic and Analytic Geometry

Preprint Server

Previous   Next
325. Mehdi Ghasemi, Murray Marshall:
Lower bounds for polynomials using geometric programming.

e-mail: ,

Submission: 2011, June 25.

We make use of a result of Hurwitz and Reznick, and a consequence of this result due to Fidalgo and Kovacec, to determine a new sufficient condition for a polynomial f in R[X_1,...,X_n] of even degree to be a sum of squares. This result generalizes a result of Lasserre and a result of Fidalgo and Kovacec, and it also generalizes recent improvements of these results due to the authors. We apply this result to obtain a new lower bound f_{gp} for f, and we explain how f_{gp} can be computed using geometric programming. The lower bound f_{gp} is generally not as good as the lower bound f_{sos} introduced by Lasserre and Parrilo and Sturmfels, which is computed using semidefinite programming, but a run time comparison shows that, in practice, the computation of f_{gp} is much faster. The computation is simplest when the highest degree term of f has the form a_1X_1^{2d}+...+a_nX_n^{2d}, a_i>0, i=1,...,n. The lower bounds for f established earlier by the authors are obtained by evaluating the objective function of the geometric program at the appropriate feasible points.

Mathematics Subject Classification (2000): 12D15, 14P99, 90C25.

Keywords and Phrases: Positive polynomials, sums of squares, optimization, geometric programming.

Full text, 14p.: dvi 75k, pdf 362k.

Server Home Page