Name
Abstract | ||
|---|---|---|
Nonconvex quadratic programming with box constraints is a fundamental $\mathcal{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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/080729529 | SIAM Journal on Optimization |
Keywords | Field | DocType |
fundamental polytope,fundamental result,Boolean quadric polytope,certain affine transformation,certain family,convex set,hard global optimization problem,Nonconvex quadratic programming,box constraint,extreme point,Box Constraints,Nonconvex Quadratic Programming | Extreme point,Discrete mathematics,Combinatorics,Mathematical optimization,Convex polytope,Polytope,Quadratic programming,Vertex enumeration problem,Linear inequality,Mathematics,Convex analysis,Polyhedral combinatorics | Journal |
Volume | Issue | ISSN |
20 | 2 | 1052-6234 |
Citations | PageRank | References |
1 | 0.35 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Burer | 1 | 1148 | 73.09 |
| Adam N. Letchfordy | 2 | 1 | 0.35 |