Convex underestimators of polynomials

Convex underestimators of a polynomial on a box. Given a non convex polynomial f ∈ ℝ[x] and a box B ⊂ ℝⁿ, we construct a sequence of convex polynomials (f_dk) ⊂ ℝ[x], which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator f*_d of f. Indeed, f*_d minimizes the L₁-norm ∥f - g∥₁ on B, over all convex degree-d polynomial underestimators g of f. On a sample of problems with non convex f, we then compare the lower bounds obtained by minimizing the convex underestimator of f computed as above and computed via the popular αBB method. In all examples we obtain significantly better results.