Lower bounds for polynomials using geometric programming

DOI10.1137/110836869MaRDI QIDQ2910880zbMATH OpenOpenAlexFDO

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

geometric programing optimization sum of squares

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

f i n m a t h b b R [X_{1}, ..., 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_{g p}

for

f

, and we explain how

f_{g p}

can be computed using geometric programming. The lower bound

f_{g p}

is generally not as good as the lower bound

f_{s o s}

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_{g p}

is much faster. The computation is simplest when the highest degree term of

f

has the form

s u m_{i = 1}^{n} a_{i} X_{i}^{2 d}

,

a_{i} > 0

,

i = 1, ..., 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.

Review text

The authors introduce in theorem 2.3 a new sufficient condition for a polynomial \(f\in \mathbb{R}[\underline{X}]=\mathbb{R}[X_1,\dots, X_n]\) to be a sum of squares (sos), generalizing and improving their previous results in [Arch. Math. 95, No. 4, 343--353 (2010; Zbl 1205.12001)] which in turn improved results of \textit{J. B. Lasserre} [SIAM J. Optim. 11, No. 3, 796--817 (2001; Zbl 1010.90061)] and \textit{C. Fidalgo} and \textit{A. Kovačec} [Math. Z. 269, No. 3--4, 629--645 (2011; Zbl 1271.11045)]. The most important contribution is that their versatile theorem allows them to introduce geometric programming which yields lower bounds \(f_{\mathrm{gp}}\) for \(f_{\mathrm{sos}}=\sup\{r: f-r \text{ is sos}\},\) and hence for \(f_*=\inf\{f(\underline{a}):\underline{a} \in \mathbb{R}^n\},\) which are better than the lower bounds \(r_{\mathrm{L}},r_{\mathrm{FK}}, r_{\mathrm{dmt}},\) given in their previous paper.NEWLINENEWLINEAfter giving in Theorem 2.1 and Corollary 2.2 interesting new proofs of a result of Hurwitz-Reznick and the consequence thereof given by Fidalgo-Kovačec [loc. cit.] concerning the representability of positive semidefinite forms of the type \(\sum_{i=1}^n \beta_i X_i^{2d} - \mu \underline{X}^\alpha \) with \(|\alpha|=2d,\) \(\beta_i\geq 0,\) and \(\underline{X}^\alpha=X_1^{\alpha_1} \cdots X_n^{\alpha_n},\) as sums of squares of binomials, they prove their first main result, Theorem 2.3.NEWLINENEWLINENEWLINEWrite a polynomial \(f\) as \(f=f_0+\sum_{\alpha \in \Omega} f_\alpha \underline{X}^\alpha +\sum_{i=1}^n f_{2d,i} X_i^{2d},\) where \(\Omega=\Omega(f)= \{\alpha\in \mathbb{N}^n: f_\alpha \neq 0 \}\setminus \{\underline{0},2de_1,\dots ,2de_n\}\) with standard vectors \(e_i,\) and let \(\Delta(f)=\{\alpha \in \Omega(f): f_\alpha \underline{X}^\alpha\) is not a square in \(\mathbb{R}[\underline{X}]\}.\)NEWLINENEWLINENEWLINETheorem 2.3: Let \(f\) be a form of degree \(2d\). A sufficient condition for \(f\) to be a sum of (binomial) squares (sobs) is that there exists for every \(\alpha\in \Delta\) a nonnegative real \(n\)-tuple \(a_\alpha=(a_{\alpha,1},\dots, a_{\alpha,n})\) so thatNEWLINENEWLINE(i) For all \(\alpha \in \Delta\), NEWLINE\[NEWLINE(2d)^{2d} a_{\alpha}^\alpha =f_\alpha^{2d}\alpha^\alpha,NEWLINE\]NEWLINENEWLINENEWLINENEWLINE\[NEWLINEf_{2d,i} \geq \sum_{\alpha \in \Delta} a_{\alpha,i},\quad i=1,\dots ,n. \tag{ii}NEWLINE\]NEWLINENEWLINENEWLINENEWLINEBy suitable choices of the \(a_\alpha,\) they get in corollaries 2.5, 2.6, 2.7 and 2.9 simplified sufficient conditions for sobs-ness of forms and inhomogeneous polynomials partially obtained by the aforementioned authors, but also new results. Example 2.10 shows that Theorem 2.3 is strictly stronger than these corollaries.NEWLINENEWLINENEWLINEFor section 3, given \(f\in \mathbb{R}[\underline{X}]\), note that since \(f-f_{\mathrm{sos}}\) is sos, and hence \(\geq 0\) and \(f_*\) the largest real so that \(f-f_*\geq 0,\) we have \(f_{\mathrm{sos}}\leq f_*.\) By obtaining lower bounds for \(f_{\mathrm{sos}}\), the authors get lower bounds for \(f_*\) and hence for \(f\).NEWLINENEWLINENEWLINEView Theorem 2.3 as a criterion \(\Phi(\underline{f},f_0)\) in terms of the coefficients \(\underline{f}\) of a polynomial \(f\) in order to be sos. Then for \(f_\Phi:=\sup\{r: \Phi(\underline{f}, f_0-r)\},\) we get \(f_\Phi \leq f_{\mathrm{sos}} \leq f_*.\) Note that in criterion \(\Phi\) there enter \(a_\alpha,\) \(\alpha \in \Delta\) as parameters with which one can play. These observations lead to the formulation of a geometric program aiming at good bounds \(f_{\mathrm{gp}}\) for \(f_{\mathrm{sos}}\). The author's \(f_{\mathrm{gp}}=\sup\{f_\Phi:\) there exists \(a_\alpha\) with \(\alpha\in \Delta\) so that \(\Phi( \underline{f}, f_0-f_\Phi).\}\)NEWLINENEWLINENEWLINEAlthough the authors report to have found sometimes large gaps between \(f_{\mathrm{gp}}\) and \(f_{\mathrm{sos}}\) they prove gapfreeness in the case \(|\Omega|=1\) and show that some other examples are gapfree as well. Runtime experiments comparing \textsc{SosTools} and \textsc{GPposy} show that the running time for geometric programming can be dramatically shorter than for semidefinite programming, even in gapfree examples.NEWLINENEWLINEAs mentioned, in their paper cited above, the authors have already given lower bounds for \(f_{\mathrm{sos}},\) called there, \(r_L, r_{\mathrm{FK}},\) and \(r_{\mathrm{dmt}}.\) It turns out that the formulae given there are intimately connected with particular choices of the \(a_\alpha\) in the objective function of the geometric program, and hence all weaker than than \(f_{\mathrm{gp}},\) that is \(\max\{r_L, r_{\mathrm{FK}},r_{\mathrm{dmt}}\} \leq f_{\mathrm{gp}}\) for any \(f,\) where typically the inequality is strict.

Recommendations

Cited in

(21)

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)