- 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/2007Entry Accepted: 02/16/2007Entry Last Modified: 02/07/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.