A new semidefinite relaxation for ℓ₁-constrained quadratic optimization and extensions

Original · EN

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 ℓ₁ 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 ℓₚ (1< p<2) unit ball and then show the dominance of the new relaxation.