A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity

We consider the classical convex constrained nonconvex quadratic programming problem where the Hessian matrix of the objective to be minimized has r negative eigenvalues, denoted by (QPr). Based on a biconvex programming reformulation in a slightly higher dimension, we propose a novel branch-and-bound algorithm to solve (QP1) and show that it returns an ϵ-approximate solution of (QP1) in at most O(1/√ ϵ) iterations. We further extend the new algorithm to solve the general (QPr) with r > 1. Computational comparison shows the efficiency of our proposed global optimization method for small r. Finally, we extend the explicit relaxation approach for (QP1) to (QPr) with r > 1. Summary of Contribution: Nonconvex quadratic program (QP) is a classical optimization problem in operations research. This paper aims at globally solving the QP where the Hessian matrix of the objective to be minimized has r negative eigenvalues. It is known to be nondeterministic polynomial-time hard even when r = 1. This paper presents a novel algorithm to globally solve the QP for r = 1 and then extends to general r. Numerical results demonstrate the superiority of the proposed algorithm in comparison with state-of-the-art algorithms/software for small r.