Principal Component hierarchy for sparse quadratic programs

Abstract

We propose a novel approximation hierarchy for cardinality-constrained, convex quadraticprograms that exploits the rank-dominating eigenvectors of the quadratic matrix. Each levelof approximation admits a min-max characterization whose objective function can be op-timized over the binary variables analytically, while preserving convexity in the continuousvariables. Exploiting this property, we propose two scalable optimization algorithms, coinedas the “best response” and the “dual program”, that can efficiently screen the potential indicesof the nonzero elements of the original program. We show that the proposed methods arecompetitive with the existing screening methods in the current sparse regression literature,and it is particularly fast on instances with high number of measurements in experiments withboth synthetic and real datasets.