A comparison of two convex underestimation methods for quadratic functions

摘要

In this paper we compare two recently described methods for convex underestimation. The first method is a variant of the nondiagonal αBB methods studied by the authors. The second method depends on algebraic characterizations of positive polynomials. Positive polynomials on a compact semi-algebraic set can be decomposed as polynomial terms containing squares and the defining polynomials of the set. This characterization can be used for describing both the underestimation and the convexity property as semidefinite constraints and minimizing the L~1 distance between function and underestimator. The domains of the methods are C~2 functions and polynomials, respectively. We focus on differences and similarities between the methods when applied to quadratic functions, which are ubiquitous in nonlinear program modeling.