论文标题
通过多项式根具有稀疏性约束的二次编程
Quadratic Programming with Sparsity Constraints via Polynomial Roots
论文作者
论文摘要
二次约束二次程序（QCQP）是在许多应用中自然发生的一种表现力的优化问题家族。寻找稀疏的解决方案通常是令人感兴趣的，在这些解决方案中，解决方案的许多条目为零。本文将考虑具有单个线性约束的QCQP，以及稀疏约束，要求解决方案的非零条目集很小。该问题类别包括许多感兴趣的基本问题，例如线性回归的稀疏版本和主成分分析，它们都很难近似。我们使用多项式的根引入了此类稀疏QCQP的一系列可进行的近似近似，这些QCQP可以表示为基质的主要未成年人的线性组合。这些多项式自然源自双曲线多项式的研究。我们的主要贡献是这些近似值和计算方法的制定，以找到稀疏QCQP的良好解决方案。我们还将提供数值证据，表明这些方法对实际问题有效。
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.
