An Eigenvalue Decomposition Method for Low-rank and Non-convex Quadratically Constrained Quadratic Programming

The quadratically constrained quadratic programming (QCQP) problems have a wide range of applications and been intensively studied in the fields of information science, control and automation engineering. Currently, one of the main challenge is to solve non-convex QCQP problem efficiently. In certain applications, the quadratic constraint coefficient matrix of QCQP problems is exactly or approximately low-rank, which can be utilized to solve the problem. In this work, we study the low-rank non-convex QCQP problems. First, a general optimization proposed. Next, we propose an eigenvalue decomposition based method to transform the low-rank non-convex quadratic constraint into a pair of linear constraints. The computational complexity is then reduced by solving a linearly constrained quadratic programming. Simulation results show that the proposed method outperforms the conventional nonlinear numerical search algorithms for QCQP in terms of optimality and computing time.

I. Introduction

The quadratically constrained quadratic programming (QCQP) [1] is a mathematical optimization problem with quadratic objective and constraint functions. The QCQP problem has an increasingly wide range of applications in the field of information science, control and automation engineering, including but not limited to network security [2], wireless communication [3], target tracking [4], sensor networks [5], signal processing [6], etc.