Let C be the convex hull of points {(1;x)(1,x')| x \in F\subset R^n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. If n<5 and F is a simplex then C has a computable representation in terms of matrices X that are doubly nonnegative (positive semidefinite and componentwise nonnegative). If n=2 and F is a box, then C 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 {(x_1, x_2, x_1*x_2)| x\in F} when n=2 and F 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 {(x_1, x_2, x_1*x_2)| x\in F}. When n=3 and F is a box, a representation for C can be obtained by utilizing the simplex result for n=4 in conjunction with a triangulation of the 3-cube.
Citation
Working paper, Dept. of Management Sciences, University of Iowa, February 2007.
Article
View Computable representations for convex hulls of low-dimensional quadratic forms