LOWER BOUNDS FOR A POLYNOMIAL ON A BASIC CLOSED SEMIALGEBRAIC SET USING GEOMETRIC PROGRAMMING

Abstract. Let f, g1,..., gm be elements of the polynomial ring R[x1,..., xn]. The paper deals with the general problem of computing a lower bound for f on the subset of Rn defined by the inequalities gi ≥ 0, i = 1,...,m. The paper shows that there is an algorithm for computing such a lower bound, based on geometric programming, which applies in a large number of cases. For example, the algorithm computes a lower bound for f on a hypercube ∏n i=1[−Ni, Ni], or, more generally, on any product of hyperellipsoids of a suitable form. The algorithm extends and generalizes earlier algorithms of Ghasemi and Marshall, dealing with the case m = 0, and of Ghasemi, Lasserre and Marshall, dealing with the case m = 1 and g1 = M − (xd1 + · · ·+ xdn). Here, d is required to be an even integer ≥ max{2, deg(f)}. The algorithm is implemented in a SAGE program developed by the first author. The bound obtained is typically not as good as the bound obtained using semidefinite programming, but it has the advantage that it is computable rapidly, even in cases where the bound obtained by semidefinite programming is not computable. 1