A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity
针对目标函数Hessian矩阵有r个负特征值的非凸二次规划问题，提出一种基于双凸规划重构的分支定界算法，能在有限迭代内得到近似解，数值实验显示对较小r效率优于现有方法。
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 [Formula: see text]-approximate solution of (QP 1 ) in at most [Formula: see text] 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.