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

geometric programming lower bound nonnegative polynomial semidefinite programming simplex sparsity sum of nonnegative circuit polynomials sum of squares

Mathematics Subject Classification ID

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.

Review text

There is much interest nowadays to find lower bounds for polynomials \(f=\sum_\alpha f_\alpha x^\alpha \in \mathbb R[x_1,\dots,x_n]\) on \(\mathbb R^n\). An already classical technique is to bound \(f_*:=\inf \{f(x): x\in \mathbb{R}^n\}\) by means of computing \(f_{\mathrm{sos}}=\sup \{r: f(x)-r \text{ is sum of squares} \}\) via semidefinite programming. A pioneer in this area is Lasserre. \textit{M. Ghasemi} and \textit{M. Marshall} [SIAM J. Optim. 22, No. 2, 460--473 (2012; Zbl 1272.12004)], still using sos-representations have shown how geometric programming can be used to find bounds \(f_{gp}\) so that \(f_{gp}\leq f_{\mathrm{sos}}\leq f_*.\) These bounds are thus usually not as good but much faster to compute. The current paper extends the Ghasemi-Marshall results in two important aspects: i. Rather than searching for sos-representations it searches for sonc-representations (sums of nonnegative circuit polynomials). ii. The constraints for the geometric programs are not anymore formulated in terms of the particular coefficients \(f_{2de_i}\) of monomials \(x_i^{2d}\). Here are some more details.NEWLINENEWLINENEWLINENEWLINEBy a simplex-tail (st) polynomial the authors understand a polynomial \(f\) that can be written in the form \(f=f_0+\sum_{j=1}^n f_{\alpha_j} x^{\alpha_j} + \sum_{\alpha\in \Delta} f_\alpha x^\alpha\), where the essential requirements are these: the set \(V=\{\alpha_0=0, \alpha_1,\dots,\alpha_n\} \subset (2\mathbb{N})^n\) is (usually) the vertex set of the Newton polytope New\((f)\) of \(f;\) the \(f_{\alpha_j}\) are nonnegative; the set \(\Delta \subseteq \text{conv} V\) comprises the \(\alpha\) for which \(f_\alpha x^\alpha\) are not squares. An st-polynomial is called circuit polynomial if \(\Delta\) is a singleton or empty. In their marvelous work [Res. Math. Sci. 3, Paper No. 9, 35 p. (2016; Zbl 1415.11071)] connecting amoeba theory and nonnegative real polynomials, the authors gave necessary and sufficient conditions for a circuit polynomial to be nonnegative which are very much similar to those \textit{C. Fidalgo} and \textit{A. Kovacec} [Math. Z. 269, No. 3--4, 629--645 (2011; Zbl 1271.11045)] gave for an elementary diagonal minus tail form to be nonnegative. An important difference and extension is that nonnegative circuit polynomials need not be sos. The theorem is recorded here as Theorem 2.3. A necessary and sufficient condition in order that a circuit polynomial is sos or a sum of binomial squares (sobs) is that its unique \(\alpha\in \Delta\) is in New\((f)^*,\) the unique maximal New\((f)\)-mediated set in the sense of \textit{B. Reznick} [Math. Ann. 283, No. 3, 431--464 (1989; Zbl 0637.10015)]. Next the authors show an analogue to Ghasemi and Marshall's [loc. cit., Theorem 2.3].NEWLINENEWLINENEWLINENEWLINETheorem 3.1. If for every pair \((\alpha,j)\in \Delta \times \{1,\dots,n\}\) there exists a real \(a_{\alpha,j}\geq 0\) such that \quad \(|f_\alpha| \leq \prod_{j=1}^n (a_{\alpha,j}/\lambda_j^\alpha)^{\lambda_j^\alpha};\) and \quad \(f_{\alpha_j} \geq \sum_{\alpha \in \Delta} a_{\alpha,j}\) for all \(j\) \quad hold, then \(f\) is a sonc. Here \((\lambda_1^\alpha,\dots,\lambda_n^\alpha)\) are the barycentric coordinates of \(\alpha\) and undefined factors in the product are understood to be 1.NEWLINENEWLINENEWLINENEWLINEWith this theorem they connect their theory to geometric programming. Theorem 3.4 is formulated for soncs and is roughly similar to Ghasemi and Marshall's [loc. cit., Theorem 3.1] for sobs.NEWLINENEWLINENEWLINENEWLINEThese theorems form the base for section 4 where the geometric programming problems are formulated in detail and the correctness proofs are given. In subsection 4.1 the authors present a number of examples and recount a number of nice features and surprises: Due to the generality of their approach, polynomials where the Ghasemi-Marshall programs cannot be applied, can be treated with their geometric programs geared towards computing \(f_{gp}=\sup\{r: f-r \text{ is sonc }\}\); an example with an acceleration factor of about 10000 over semidefinite programming is given; and finally, while geometric programming in the authors' setting remains fast when compared with semidefinite programming, geometric programming aiming for sonc representations often yields bounds \(f_{gp}>f_{sos},\) that is, they are sometimes better than \(f_{sos}.\) In Section 5 the authors give initial applications to constrained polynomial optimization following the setup \textit{M. Ghasemi} and \textit{M. Marshall} have given in [``Lower bounds for a polynomial on a basic closed semialgebraic set using geometric programming, Preprint, \url{arXiv:1311.3726}].NEWLINENEWLINENEWLINENEWLINEThe reviewer should inform that a recent paper by \textit{Van Doat Dang} and \textit{Thi Thao Nguyen} [Kodai Math. J. 39, No. 2, 253--275 (2016; Zbl 1398.12004)] similarly presents results ridded of conditions on \(f_{2de_i}\) for sums of squares estimates and geometric programming. That paper has a similar principal bibliography as the present one, and there is some overlap in the results; but it is apparent that the authors didn't know of each other's work.

Recommendations

Cites work

Cited in

(25)

Describes a project that uses

Uses Software

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)