In this paper we consider a cardinality-constrained quadratic program that minimizes a convex quadratic function subject to a cardinality constraint and linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality function is first approximated by a piecewise linear DC function (difference of two convex functions) and a sequence of convex subproblems are then constructed by successively linearizing the concave terms of the DC function. Under some mild assumptions, we establish that any accumulation point of the sequence generated by the method is a KKT point of the DC approximation problem. We show that the basic algorithm can be refined by adding valid inequalities in the subproblems. We report some preliminary computational results which show that our method is promising for finding good suboptimal solutions and is competitive with some other local solution methods for cardinality-constrained quadratic programs.
Article
View Successive Convex Approximations to Cardinality-Constrained Quadratic Programs: A DC Approach