12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > On non-convex quadratic programming with box co...
View graph of relations

« Back

On non-convex quadratic programming with box constraints

Research output: Contribution to journalJournal article

Published

Journal publication date2009
JournalSIAM Journal on Optimization
Journal number2
Volume20
Number of pages17
Pages1073-1089
Original languageEnglish

Abstract

Nonconvex quadratic programming with box constraints is a fundamental NP-hard global optimization 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, characterize 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 give a classification of valid inequalities and show that this yields a finite recursive procedure to check the validity of any proposed inequality.