We address Quadratically Constrained Quadratic Programs (QCQP) having a quadratic objective function, quadratic equality constraints and linear inequality constraints. The main purpose of this paper is to exhibit an approximating reformulation, such that its size is much smaller than the size of the original formulation. This is useful when confronted with QCQPs that are too large to solve with current solver technology. Then one can solve the smaller approximation in order to construct an approximately feasible solution of the original QCQP that is not too far from optimality. The approximated reformulation is obtained using random projections, i.e., random matrices which satisfy the Johnson-Lindenstrauss Lemma. We consider two random projections T and R which, respectively, reduce the number of variables and constraint of the original QCQP.
The two main results of the paper show that the objective value of the projected formulation is close to the objective value of the original formulation with arbitrarily high probability (wahp) and that a solution to the projected version is feasible for the original formulation up to an error which can be bounded wahp.