Lower bounds for polynomials using geometric programming

DOI10.1137/110836869MaRDI QIDQ2910880zbMATH OpenOpenAlexFDO

Authors M. Ghasemi, Murray Marshall

Publication date 12 September 2012

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1106.1666

zbMATH Keywords

optimizationsum of squaresgeometric programing

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebraic and real-analytic geometry (14P99)

Abstract: 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 $finmathbbR[X_1,\mathrm{...},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 the improvements of these results given in [6]. 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 $su{m}_{i=1}^n{a}_i{X}_i^{2d}$, $a_i>0$, $i=1,\mathrm{...},n$. The lower bounds for $f$ established in [6] are obtained by evaluating the objective function of the geometric program at the appropriate feasible points.

Recommendations

• Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
• Lower bounds for a polynomial in terms of its coefficients
• Lower bounds on the global minimum of a polynomial
• Sufficient conditions for a real polynomial to be a sum of squares of polynomials
• Optimization of Polynomial Functions

Cited in

(21)

• Lower Bounds for Geometrical and Physical Problems
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• Perturbed sums-of-squares theorem for polynomial optimization and its applications
• scientific article; zbMATH DE number 4133835 (Why is no real title available?)
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure
• A Positivstellensatz for sums of nonnegative circuit polynomials
• Lower bounds on the global minimum of a polynomial
• Relative entropy relaxations for signomial optimization
• A new bounded degree hierarchy with SOCP relaxations for global polynomial optimization and conic convex semi-algebraic programs
• Minkowski's inequality and sums of squares
• TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
• Optimal size of linear matrix inequalities in semidefinite approaches to polynomial optimization
• Sufficient conditions for a real polynomial to be a sum of squares of polynomials
• Sums of Squares of Polynomials
• Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
• Newton polytopes and relative entropy optimization
• Lower bounds for polynomials with simplex Newton polytopes based on geometric programming
• scientific article; zbMATH DE number 3984992 (Why is no real title available?)
• On sums of squares of \(K\)-nomials

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: Lower bounds for polynomials using geometric programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910880)