Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach
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...
| Main Authors: | , , , |
|---|---|
| Format: | Journal Article |
| Published: |
Kluwer Academic Publishers
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/36727 |
| _version_ | 1848754850828910592 |
|---|---|
| author | Zheng, X. Sun, X. Li, D. Sun, Jie |
| author_facet | Zheng, X. Sun, X. Li, D. Sun, Jie |
| author_sort | Zheng, X. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T08:46:58Z |
| format | Journal Article |
| id | curtin-20.500.11937-36727 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:46:58Z |
| publishDate | 2014 |
| publisher | Kluwer Academic Publishers |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-367272019-02-19T05:35:34Z Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach Zheng, X. Sun, X. Li, D. Sun, Jie Cardinality constraint Convex programs Strengthening cuts Successive convex approximation DC approximation Portfolio selection 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. 2014 Journal Article http://hdl.handle.net/20.500.11937/36727 10.1007/s10589-013-9582-3 Kluwer Academic Publishers fulltext |
| spellingShingle | Cardinality constraint Convex programs Strengthening cuts Successive convex approximation DC approximation Portfolio selection Zheng, X. Sun, X. Li, D. Sun, Jie Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach |
| title | Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach |
| title_full | Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach |
| title_fullStr | Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach |
| title_full_unstemmed | Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach |
| title_short | Successive Convex Approximations to Cardinality-Constrained Convex Programs: A Piecewise-Linear DC Approach |
| title_sort | successive convex approximations to cardinality-constrained convex programs: a piecewise-linear dc approach |
| topic | Cardinality constraint Convex programs Strengthening cuts Successive convex approximation DC approximation Portfolio selection |
| url | http://hdl.handle.net/20.500.11937/36727 |