Quadratic Programming with Sparsity Constraints via Polynomial Roots
From MaRDI portal
Publication:6408613
arXiv2208.11143MaRDI QIDQ6408613FDOQ6408613
Authors: Kevin Shu 
Publication date: 23 August 2022
Abstract: 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.
Has companion code repository: https://github.com/ootks/sparse_qcqps
This page was built for publication: Quadratic Programming with Sparsity Constraints via Polynomial Roots
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6408613)
