We consider convex relaxations for quadratic programming with continuous variables and their binary indicators, which has applications in sparse linear regression, sparse principal component analysis, digital filter design, etc. Based on a decomposition that splits a positive semidefinite (PSD) matrix into two PSD matrices, where one of them has a chosen sparsity pattern, we construct several convex relaxations. Some of them can be solved by second order cone programming, and others can be written as semidefinite programming over a sparse PSD cone (with a fixed sparsity pattern). Further we add linear inequalities that come from exploiting low dimensional convex hulls of quadratic forms including the indicator variables. We test on various problems to illustrate the trade-off between the speed of computing the relaxations and the strength of lower bounds. |