Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach
MetadataShow full item record
In this paper we consider cardinality-constrained convex programs that minimize a convex function subject to a cardinality constraint and other 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 convexfunctions) and a sequence of convex subproblems is 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 strengthening cuts in the subproblems. Finally, we report some preliminary computational results on cardinality-constrained portfolio selection problems.
The final publication is available at Springer via http://doi.org/10.1007/s10589-013-9582-3.
Showing items related by title, author, creator and subject.
Ruan, Ning (2012)Duality is one of the most successful ideas in modern science  . It is essential in natural phenomena, particularly, in physics and mathematics   . In this thesis, we consider the canonical duality ...
Loxton, Ryan Christopher (2010)In this thesis, we develop numerical methods for solving five nonstandard optimal control problems. The main idea of each method is to reformulate the optimal control problem as, or approximate it by, a nonlinear programming ...
Li, Bin (2011)In this thesis, we consider several types of optimal control problems with constraints on the state and control variables. These problems have many engineering applications. Our aim is to develop efficient numerical methods ...