A Complementary Cutting Plane Approach for Nonconvex Quadratically Constrained Quadratic Programs

Abstract

This paper examines the nonconvex quadratically constrained quadratic programming (QCQP) problem using a complementary cutting plane method. It is well known that a QCQP can be transformed into an equivalent rank-one constrained optimization problem. Thus, we focus on searching the optimal rank-one matrix to minimize the objective while satisfying other linear matrix constraints. However, finding a rank-one matrix is computationally complicated. A cost-driven cutting plane (CDCP) method has been developed to gradually approach the rank-one constraint. To improve computational efficiency, a complementary cutting plane approach (CCPA) combing conventional intersection cut and cost-driven cut is proposed to solve QCQPs. In this new approach, a linear constraint is generated in each iteration to tighten the searching domain for a semidefinite programming problem generated from the cost-driven cut method. We further prove that adding the intersection cut in each iteration will not exclude any rank-one solution. Numerical examples with comparative results are presented and compared to verify the effectiveness and efficiency of the proposed approach.