  


Computable representations for convex hulls of lowdimensional quadratic forms
Kurt Anstreicher(kurtanstreicheruiowa.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 reformulationlinearization 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 wellknown 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 3cube. Keywords: Nonconvex quadratic programming, reformulationlinearization technique, convex envelope Category 1: Global Optimization (Theory ) Category 2: Nonlinear Optimization (Boundconstrained Optimization ) Citation: Working paper, Dept. of Management Sciences, University of Iowa, February 2007. Download: [PDF] Entry Submitted: 02/07/2007 Modify/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  