Abstract: |
We present a new algorithm for computing a new lower bound for a polynomial f in R}[X] by geometric programming. This bound is typically not as good as the lower bound obtained using Lasserre's algorithm but, on the other hand, the algorithm takes full advantage of sparsity of coefficients and it works in cases where the degree and/or number of variables is large, cases where Lasserre's algorithm breaks down. There is also variant of the algorithm which computes a lower bound for f on the semialgebraic set in real n-space defined by X_1^{2d}+\dots+X_n^{2d}<= N, where 2d is any upper bound for the degree of f. |