Computable representations for convex hulls of low-dimensional quadratic forms

Kurt Anstreicher(kurt-anstreicheruiowa.edu)
Samuel Burer(samuel-bureruiowa.edu)

Abstract: 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.

Keywords: Nonconvex quadratic programming, reformulation-linearization technique, convex envelope

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Bound-constrained Optimization )

Citation: Working paper, Dept. of Management Sciences, University of Iowa, February 2007.

Download: [PDF]

Entry Submitted: 02/07/2007
Entry Accepted: 02/16/2007
Entry Last Modified: 02/07/2007

Modify/Update this entry