A Decomposition Method for Nonconvex Quadratically Constrained Quadratic Programs

This paper examines the nonconvex quadratically constrained quadratic programming (QCQP) problems using a decomposition method. It is well known that a QCQP can be transformed into a rank-one constrained optimization problem. Finding a rank-one matrix is computationally complicated, especially for large scale QCQPs. A decomposition method is applied to decompose the single rank-one constraint on original unknown matrix into multiple rank-one constraints on small scale submatrices. An iterative rank minimization (IRM) algorithm is then proposed to gradually approach all of the rank-one constraints. To satisfy each rank-one constraint in the decomposed formulation, linear matrix inequalities (LMIs) are introduced in IRM with local convergence analysis. The decomposition method reduces the overall computational cost by decreasing size of LMIs, especially when the problem is sparse. Simulation examples with comparative results obtained from an alternative method are presented to demonstrate advantages of the proposed method.