Principal Component Hierarchy for Sparse Quadratic Programs
From MaRDI portal
Publication:6368507
arXiv2105.12022MaRDI QIDQ6368507
Author name not available (Why is that?)
Publication date: 25 May 2021
Abstract: We propose a novel approximation hierarchy for cardinality-constrained, convex quadratic programs that exploits the rank-dominating eigenvectors of the quadratic matrix. Each level of approximation admits a min-max characterization whose objective function can be optimized over the binary variables analytically, while preserving convexity in the continuous variables. Exploiting this property, we propose two scalable optimization algorithms, coined as the "best response" and the "dual program", that can efficiently screen the potential indices of the nonzero elements of the original program. We show that the proposed methods are competitive 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 with both synthetic and real datasets.
Has companion code repository: https://github.com/RVreugdenhil/sparseQP
This page was built for publication: Principal Component Hierarchy for Sparse Quadratic Programs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6368507)
