Journal article
Computable representations for convex hulls of low-dimensional quadratic forms
Mathematical programming, Vol.124(1-2), pp.33-43
07/01/2010
DOI: 10.1007/s10107-010-0355-9
Abstract
Let C be the convex hull of points {(1 x) ((1) x)(T) [x is an element of F subset of R-n}. Representing or approximating C is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if 17 <= 4 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). We also prove that 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)) vertical bar x is an element of F} when F subset of R-2 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)) vertical bar x is an element of F}. When n = 3 and F is a box, we show that a representation for C can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube.
Details
- Title: Subtitle
- Computable representations for convex hulls of low-dimensional quadratic forms
- Creators
- Kurt M. Anstreicher - University of IowaSamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.124(1-2), pp.33-43
- Publisher
- Springer Nature
- DOI
- 10.1007/s10107-010-0355-9
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Number of pages
- 11
- Grant note
- CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 07/01/2010
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380544902771
Metrics
1 Record Views