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

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.