Lower bounds for polynomials using geometric programming

DOI10.1137/110836869zbMATH Open1272.12004arXiv1106.1666OpenAlexW3101866124MaRDI QIDQ2910880FDOQ2910880

M. Ghasemi, Murray Marshall

Publication date: 12 September 2012

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

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.

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)

Cited In (20)

• Lower Bounds for Geometrical and Physical Problems
• Optimal Size of Linear Matrix Inequalities in Semidefinite Approaches to Polynomial Optimization
• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
• Perturbed sums-of-squares theorem for polynomial optimization and its applications
• Title not available (Why is that?)
• 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
• 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
• 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
• A Positivstellensatz for Sums of Nonnegative Circuit Polynomials
• Title not available (Why is that?)
• On sums of squares of \(K\)-nomials

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)