Name
Title | ||
|---|---|---|
A New Branch-And-Cut Algorithm For Non-Convex Quadratic Programming Via Alternative Direction Method And Semidefinite Relaxation |
Abstract | ||
|---|---|---|
We consider a non-convex quadratic program (QP) with linear and convex quadratic constraints that arises from a broad range of applications and is known to be NP-hard. In this paper, we first prove that the alternative direction method converges to a local solution of the underlying QP problem. We then propose a new branch-and-cut algorithm that finds a globally optimal solution to the underlying QP problem within a pre-specified epsilon-tolerance by integrating the alternative direction method with semidefinite relaxation and disjunctive cut techniques. We establish the global convergence of the algorithm and estimate its complexity. Preliminary numerical results demonstrate that the proposed algorithm can effectively find a globally optimal solution to medium-scale QP instances in which the number of negative eigenvalues of the Hessian matrix in the objective function is less than or equals 20. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s11075-020-01065-7 | NUMERICAL ALGORITHMS |
Keywords | DocType | Volume |
Quadratic programming, Branch-and-cut algorithm, Alternative direction method, Semidefinite relaxation, Computational complexity | Journal | 88 |
Issue | ISSN | Citations |
2 | 1017-1398 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hezhi Luo | 1 | 40 | 5.02 |
| Sikai Chen | 2 | 0 | 0.34 |
| H. X. Wu | 3 | 25 | 2.11 |