A new semidefinite relaxation for ${\mathrm{\ell }}_1$-constrained quadratic optimization and extensions

In this paper, by improving the variable-splitting approach, we propose a new semidefinite programming (SDP) relaxation for the nonconvex quadratic optimization problem over the ${\mathrm{\ell }}_1$ unit ball (QPL1). It dominates the state-of-the-art SDP-based bound for (QPL1). As extensions, we apply the new approach to the relaxation problem of the sparse principal component analysis and the nonconvex quadratic optimization problem over the ${\mathrm{\ell }}_p$ ($1<p<2$) unit ball and then show the dominance of the new relaxation.