2025/10/03 by Mehdi Ghasemi, Ghasemi, Mehdi, Murray Marshall +1
Mathematics · Computer Science · #Advanced Optimization Algorithms Research #Polynomial and algebraic computation #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2510.03105
Let f be a polynomial in n variables x1,…,xn with real coefficients. In [Ghasemi-Marshal], Ghasemi and Marshall give an algorithm, based on geometric programming, which computes a lower bound for f on ℝn. In [Ghasemi-Lasserre-Marshall] Ghasemi, Lasserre and Marshall show how the algorithm in [Ghasemi-Marshal] can be modified to compute a lower bound for f on the hyperellipsoid ∑i=1n xid ≤ M. Here d is a fixed even integer, d ≥ max\ 2, °(f)\ and M is a fixed positive real number. Suppose now that gj := 1-∑i∈ Ij ((xi)/(Ni))d, j=1,…,m, where d is a fixed even integer d ≥ max\ 2, °(f)\, Ni is a fixed positive real number, i=1,…,n and I1,…, Im is a fixed partition of \ 1,…,n\. The present paper gives an algorithm based on geometric programming for computing a lower bound for f on the subset of ℝn defined by the inequalities gj≥ 0, j=1,…,m. The algorithm is implemented in a SAGE program developed by the first author. The bound obtained is typically not as sharp 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. When m=1 and Ni = \root d \ofM, i=1,…,n the algorithm produces the lower bound obtained in [Ghasemi-Lasserre-Marshall]. When m=n and Ij = \ j \, j=1,…,n the algorithm produces a lower bound for f on the hypercube ∏i=1n [-Ni,Ni], which in certain cases can be computed by a simple formula.