New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation. We consider a quadratic program with a few negative eigenvalues (QP-(r)-NE) subject to linear and convex quadratic constraints that covers many applications and is known to be NP-hard even with one negative eigenvalue (QP1NE). In this paper, we first introduce a new global algorithm (ADMBB), which integrates several simple optimization techniques such as alternative direction method, and branch-and-bound, to find a globally optimal solution to the underlying QP within a pre-specified (epsilon )-tolerance. We establish the convergence of the ADMBB algorithm and estimate its complexity. Second, we develop a global search algorithm (GSA) for QP1NE that can locate an optimal solution to QP1NE within (epsilon )-tolerance and estimate the worst-case complexity bound of the GSA. Preliminary numerical results demonstrate that the ADMBB algorithm can effectively find a global optimal solution to large-scale QP-(r)-NE instances when (rle 10), and the GSA outperforms the ADMBB for most of the tested QP1NE instances. The software reviewed as part of this submission was given the DOI (digital object identifier) url{doi:10.5281/zenodo.1344739}.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element