Lower bounds for polynomials with simplex Newton polytopes based on geometric programming

DOI10.1137/140962425zbMATH Open1380.12001arXiv1402.6185OpenAlexW2962954083MaRDI QIDQ2805707FDOQ2805707

Authors: Sadik Iliman, Timo de Wolff 

Publication date: 13 May 2016

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

Abstract: In this article, we propose a geometric programming method in order to compute lower bounds for real polynomials. We provide new sufficient conditions for polynomials to be nonnegative as well as to have a sum of binomial squares representation. These criteria rely on the coefficients and the support of a polynomial and generalize all previous ones by Lasserre, Ghasemi, Marshall, Fidalgo and Kovacec to polynomials with arbitrary simplex Newton polytopes. This generalization yields a geometric programming approach for computing lower bounds for polynomials that significantly extends the geometric programming method proposed by Ghasemi and Marshall. Furthermore, it shows that geometric programming is strongly related to nonnegativity certificates based on sums of nonnegative circuit polynomials, which were recently introduced by the authors.

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

Recommendations

• Lower bounds for polynomials using geometric programming
• scientific article; zbMATH DE number 697092
• scientific article; zbMATH DE number 3984992
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
• scientific article; zbMATH DE number 3952498
• scientific article; zbMATH DE number 4133835
• Geometric optimization and the polynomial hierarchy
• scientific article; zbMATH DE number 3965441
• Lower bound theorems for general polytopes
• Exponential lower bounds for polytopes in combinatorial optimization

zbMATH Keywords

sparsitysemidefinite programmingsimplexlower boundsum of squaresgeometric programmingnonnegative polynomialsum of nonnegative circuit polynomials

Mathematics Subject Classification ID

Convex programming (90C25) Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry) (52B20) Fields related with sums of squares (formally real fields, Pythagorean fields, etc.) (12D15) Real algebraic and real-analytic geometry (14P99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Moments, positive polynomials and their applications
• GloptiPoly 3: moments, optimization and semidefinite programming
• Sums of squares, moment matrices and optimization over polynomials
• Semidefinite Optimization and Convex Algebraic Geometry
• Forms derived from the arithmetic-geometric inequality
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Lower bounds for polynomials using geometric programming
• Positive semidefinite diagonal minus tail forms are sums of squares
• A tutorial on geometric programming
• On the computational complexity of membership problems for the completely positive cone and its dual
• Sufficient conditions for a real polynomial to be a sum of squares

Cited In (19)

• Initial steps in the classification of maximal mediated sets
• Reducing nonnegativity over general semialgebraic sets to nonnegativity over simple sets
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
• Approximating nonnegative polynomials via spectral sparsification
• Title not available (Why is that?)
• Real zeros of SONC polynomials
• Amoebas, nonnegative polynomials and sums of squares supported on circuits
• Lower bounds on the global minimum of a polynomial
• Nonnegative Polynomials and Circuit Polynomials
• Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
• Symmetry reduction in AM/GM-based optimization
• Symmetric SAGE and SONC forms, exactness and quantitative gaps
• The dual cone of sums of non-negative circuit polynomials
• Parameter Region for Multistationarity in \({\boldsymbol{n-}}\)Site Phosphorylation Networks
• On minimal extended representations of generalized power cones
• Duality of sum of nonnegative circuit polynomials and optimal SONC bounds
• SONC optimization and exact nonnegativity certificates via second-order cone programming
• Newton polytopes and relative entropy optimization
• Lower bounds for polynomials using geometric programming

Uses Software

• GloptiPoly
• POEM

This page was built for publication: Lower bounds for polynomials with simplex Newton polytopes based on geometric programming

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