Abstract | ||
---|---|---|
We present semidefinite relaxations of nonconvex, box-constrained quadratic programming, which incorporate the first- and second-order necessary optimality conditions, and establish theoretical relationships between the new relaxations and a basic semidefinite relaxation due to Shor. We compare these relaxations in the context of branch-and-bound to determine a global optimal solution, where it is shown empirically that the new relaxations are significantly stronger than Shor's. An effective branching strategy is also developed. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1007/s10589-009-9273-2 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
Quadratic Programming,Test Scenario,Complementary Slackness,Semidefinite Relaxation,Nonconvex Quadratic Program | Mathematical optimization,Quadratically constrained quadratic program,Scenario testing,Quadratic programming,Mathematics,Branching (version control) | Journal |
Volume | Issue | ISSN |
48 | 3 | 0926-6003 |
Citations | PageRank | References |
3 | 0.38 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Samuel Burer | 1 | 1148 | 73.09 |
Jieqiu Chen | 2 | 37 | 2.20 |