Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On non-convex quadratic programming with box constraints
AU - Burer, S
AU - Letchford, A N
PY - 2009
Y1 - 2009
N2 - 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.
AB - 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.
KW - non-convex quadratic programming
KW - global optimisation
KW - polyhedral combinatorics
KW - convex analysis
U2 - 10.1137/080729529
DO - 10.1137/080729529
M3 - Journal article
VL - 20
SP - 1073
EP - 1089
JO - SIAM Journal on Optimization
JF - SIAM Journal on Optimization
SN - 1095-7189
IS - 2
ER -