Computable representations for convex hulls of low-dimensional quadratic forms

摘要

Let be the convex hull of points . Representing or approximating is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if n ≤ 4 and is a simplex, then has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). We also prove that if n = 2 and is a box, then has a representation that combines semidefiniteness with constraints on product terms obtained from the reformulation-linearization technique (RLT). The simplex result generalizes known representations for the convex hull of when is a triangle, while the result for box constraints generalizes the well-known fact that in this case the RLT constraints generate the convex hull of . When n = 3 and is a box, we show that a representation for can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube.