Optimization Online


Computable representations for convex hulls of low-dimensional quadratic forms

Kurt Anstreicher(kurt-anstreicher***at***uiowa.edu)
Samuel Burer(samuel-burer***at***uiowa.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society