LOWER BOUNDS FOR POLYNOMIALS USING GEOMETRIC PROGRAMMING

作者：Ghasemi Mehdi^*; Marshall Murray

来源：SIAM Journal on Optimization, 2012, 22(2): 460-473.

DOI：10.1137/110836869

• positive polynomials
• sums of squares
• optimization
• geometric programming

We make use of a result of Hurwitz [J. Reine Angew. Math., 108 (1891), pp. 266-268] and Reznick [Math. Ann., 283 (1989), pp. 431-464], and a consequence of this result due to Fidalgo and Kovacec [Math. Z., 269 (2011), pp. 629-645], to establish, in Theorem 2.3, a new sufficient condition for a polynomial f is an element of R[X-1, . . . , X-n] of even degree to be a sum of squares. Theorem 2.3 yields as special cases the results of Ghasemi and Marshall in [Arch. Math. (Basel), 95 (2010), pp. 343-353] and, consequently, also those of Fidalgo and Kovacec and Lasserre [Arch. Math. (Basel), 89 (2007), pp. 390-398]. We apply Theorem 2.3 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 [SIAM J. Optim., 11 (2001), pp. 796-817] and Parrilo and Sturmfels [Algorithmic and Quantitative Real Algebraic Geometry, AMS, Providence, RI, 2003, pp. 88-99], which can be computed using semidefinite programming, but a run time comparison shows that, in practice, the computation of fgp is faster, and larger problems can be handled. The computation is simplest when the highest degree component of f has the form Sigma(n)(i=1) a(i)X(i)(2d), a(i) %26gt; 0, i = 1, . . . , n. The lower bounds for f established by Ghasemi and Marshall are obtained by evaluating the objective function of the geometric program at appropriate feasible points.

• 出版日期2012