Quadratic Programming with Sparsity Constraints via Polynomial Roots

Quadratically constrained quadratic programs (QCQPs) are an expressive family of optimization problems that occur naturally in many applications. It is often of interest to seek out sparse solutions, where many of the entries of the solution are zero. This paper will consider QCQPs with a single linear constraint, together with a sparsity constraint that requires that the set of nonzero entries of a solution be small. This problem class includes many fundamental problems of interest, such as sparse versions of linear regression and principal component analysis, which are both known to be very hard to approximate. We introduce a family of tractable approximations of such sparse QCQPs using the roots of polynomials which can be expressed as linear combinations of principal minors of a matrix. These polynomials arose naturally from the study of hyperbolic polynomials. Our main contributions are formulations of these approximations and computational methods for finding good solutions to a sparse QCQP. We will also give numerical evidence that these methods can be effective on practical problems.Comment: The original version of this paper was replaced because we found a substantially more efficient algorithm for the main result of this pape