Convex underestimators of polynomials

Convex underestimators of a polynomial on a box. Given a non convex polynomial $${f\in \mathbb{R}[{\rm x}]}$$ and a box $${{\rm B}\subset \mathbb{R}^n}$$ , we construct a sequence of convex polynomials $${(f_{dk})\subset \mathbb{R}[{\rm 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 1 -norm $${\Vert f-g\Vert_1}$$ 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 and some of its other refinements. In most of all examples we obtain significantly better results even with the smallest value of k. Copyright Springer Science+Business Media, LLC. 2013