DC formulations and algorithms for sparse optimization problems
In: Mathematical Programming, Jg. 169 (2017-07-26), S. 141-176
Online
unknown
Zugriff:
We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA) is presented, where the dual step at each iteration can be efficiently carried out due to the accessible subgradient of the largest-k norm. Furthermore, we can solve each DCA subproblem in linear time via a soft thresholding operation if there are no additional constraints. The framework is extended to the rank-constrained problem as well as the cardinality- and the rank-minimization problems. Numerical experiments demonstrate the efficiency of the proposed DCA in comparison with existing methods which have other penalty terms.
Titel: |
DC formulations and algorithms for sparse optimization problems
|
---|---|
Autor/in / Beteiligte Person: | Gotoh, Jun-ya ; Takeda, Akiko ; Tono, Katsuya |
Link: | |
Zeitschrift: | Mathematical Programming, Jg. 169 (2017-07-26), S. 141-176 |
Veröffentlichung: | Springer Science and Business Media LLC, 2017 |
Medientyp: | unknown |
ISSN: | 1436-4646 (print) ; 0025-5610 (print) |
DOI: | 10.1007/s10107-017-1181-0 |
Schlagwort: |
|
Sonstiges: |
|