A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity
INFORMS Journal on Computing · 2021 · Volume 33 · Issue 4
Abstract
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 (QP r ). Based on a biconvex programming reformulation in a slightly higher dimension, we propose a novel branch-and-bound algorithm to solve (QP 1 ) and show that it returns an ɛ ɛ -approximate solution of (QP 1 ) in at most 𝑂 ( 1 / √ ɛ ) O ( 1 / ɛ ) iterations. We further extend the new algorithm to solve the general (QP r ) 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 (QP 1 ) to (QP r ) 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 .
Keywords
quadratic programming, quadratically constrained quadratic programming, branch and bound
Enable JavaScript for citation tools and additional paper interactions.