On Non-Convex Quadratic Programming with Box Constraints

Samuel Burer (samuel-bureruiowa.edu)
Adam Letchford (a.n.letchfordlancaster.ac.uk)

Abstract: Non-Convex Quadratic Programming with Box Constraints is a fundamental NP-hard global optimisation problem. Recently, some authors have studied a certain family of convex sets associated with this problem. We prove several fundamental results concerned with these convex sets: we determine their dimension, characterise their extreme points and vertices, show their invariance under certain affine transformations, and show that various linear inequalities induce facets. We also show that the sets are closely related to the boolean quadric polytope, a fundamental polytope in the field of polyhedral combinatorics. Finally, we present a `recursive' result that enables one to interpret certain complex valid inequalities in terms of simpler valid inequalities.

Keywords: global optimization, polyhedral combinatorics, convex analysis

Category 1: Global Optimization (Theory )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Category 3: Integer Programming (0-1 Programming )

Citation: S. Burer & A.N. Letchford (2009) On non-convex quadratic programming with box constraints. SIAM J. on Opt., 20(2), 1073-1089.

Download:

Entry Submitted: 07/07/2008
Entry Accepted: 07/07/2008
Entry Last Modified: 04/22/2010

Modify/Update this entry