Convex underestimators of a polynomial on a box. Given a non convex polynomial <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$${f\in \mathbb{R}[{\rm x}]}$$</EquationSource> </InlineEquation> and a box <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$${{\rm B}\subset \mathbb{R}^n}$$</EquationSource> </InlineEquation>, we construct a sequence of convex polynomials <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$${(f_{dk})\subset \mathbb{R}[{\rm x}]}$$</EquationSource> </InlineEquation>, which converges in a strong sense to the “best” (convex and degree-d) polynomial underestimator <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$${f^{*}_{d}}$$</EquationSource> </InlineEquation> of f. Indeed, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$${f^{*}_{d}}$$</EquationSource> </InlineEquation> minimizes the L <Subscript>1</Subscript>-norm <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$${\Vert f-g\Vert_1}$$</EquationSource> </InlineEquation> on <Emphasis Type="Bold">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 α <Emphasis Type="Bold">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
