Abstract
Let \({\mathcal{C}}\) be the convex hull of points \({{\{{1 \choose x}{1 \choose x}^T \,|\, x\in \mathcal{F}\subset \Re^n\}}}\). Representing or approximating \({\mathcal{C}}\) is a fundamental problem for global optimization algorithms based on convex relaxations of products of variables. We show that if n ≤ 4 and \({\mathcal{F}}\) is a simplex, then \({\mathcal{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 \({\mathcal{F}}\) is a box, then \({\mathcal{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_1x_2)\,|\, x\in\mathcal{F}\}}}\) when \({\mathcal{F}\subset\Re^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_1x_2)\,|\, x\in\mathcal{F}\}}}\). When n = 3 and \({\mathcal{F}}\) is a box, we show that a representation for \({\mathcal{C}}\) can be obtained by utilizing the simplex result for n = 4 in conjunction with a triangulation of the 3-cube.
Similar content being viewed by others
References
Anstreicher K.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43, 471–484 (2009)
Bomze I.: Branch-and-bound approaches to standard quadratic optimization problems. J. Glob. Optim. 22, 27–37 (2002)
Bomze I., Dür M., de Klerk E., Roos C., Quist A., Terlaky T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 18, 301–320 (2000)
Bomze I., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite, and copositive programming. J. Glob. Optim. 24, 163–185 (2002)
Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Prog. 120, 479–495 (2009)
Jach M., Michaels D., Weismantel R.: The convex envelope of (n − 1)-convex functions. SIAM. J. Optim. 19, 1451–1466 (2008)
Kogan N., Berman A.: Characterization of completely positive graphs. Discrete Math. 114, 297–304 (1993)
Linderoth J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Prog. 103, 251–282 (2005)
Motzkin T., Straus E.: Maxima for graphs and a new proof of a theorem of Túran. Can. J. Math. 17, 533–540 (1965)
Pataki G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23, 339–358 (1998)
Sahinidis N.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996)
Sherali H., Adams W.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1998)
Sherali H., Alameddine A.: A new reformulation-linearization technique for bilinear programming problems. J. Glob. Optim. 2, 379–410 (1992)
Sherali H., Tuncbilek C.: A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim. 7, 1–31 (1995)
Vandenbussche D., Nemhauser G.: A branch-and-cut algorithm for nonconvex quadratic programming with box constraints. Math. Prog. 102, 559–575 (2005)
Ye Y.: Approximating quadratic programming with bound and quadratic constraints. Math. Prog. 84, 219–226 (1999)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Anstreicher, K.M., Burer, S. Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124, 33–43 (2010). https://doi.org/10.1007/s10107-010-0355-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-010-0355-9