A COMPUTATIONAL STUDY ON THE GLOBAL SOLUTION OF NONCONVEX QUADRATIC CONSTRAINTS AND QUADRATIC PROGRAMMING PROBLEMS

ABSTRACT Quadratically constrained quadratic programming (QCQP) problems appear in a wide range of engineering fields, including computer science, communication engineering, and finance. A key difficulty in solving these problems lies in efficiently finding global solutions, especially for large-scale and nonconvex instances. To address this, Wen & Yin (2013) proposed a method that reformulates semidefinite programming (SDP) relaxations of QCQPs into a nonlinear and nonconvex low-rank problem. This reformulated problem can be efficiently solved using a curvilinear search method combined with Barzilai-Borwein (BB) steps, known as the CSBB algorithm. In this study, we compare two approaches for solving QCQPs: the conventional convex SDP relaxation and the nonconvex low-rank reformulation introduced by Wen and Yin. We propose a set of general QCQP models that are compatible with the low-rank framework and conduct a series of numerical experiments to evaluate their performance. This study evaluates performance using several classes of NP-hard problems, including Binary Integer Quadratic (BIQ) problems, Max-Cut problems, Boolean Least Squares (BLS) problems, and 0-1 Quadratic Knapsack Problems (QKP). The results demonstrate that the low-rank approach offers competitive performance and shows strong potential for solving large-scale QCQPs more efficiently than traditional convex methods.