Fast Projection-Based Solvers for the Non-Convex Quadratically Constrained Feasibility Problem

Abstract

Quadratically constrained quadratic programming (QCQP) forms an important class of optimization tasks in various engineering disciplines. Fast identification of a feasible point under low computational complexity load is critical for several approximation techniques which have been developed to solve non-convex QCQPs. This paper introduces two projection-based techniques to compute feasible points of non-convex QCQPs with low computational complexity footprints: The first one employs successive projection mappings, while the second one builds on a composition of successive and averaged projection steps. Extensive experiments on synthetically generated instances of non-convex quadratically constrained feasibility problems demonstrate that the simple successive-projection based technique compares favorably against state-of-the-art feasible point pursuit methods which capitalize on successive convex approximation, parallel projections and computationally demanding interior-point techniques.