DC formulations and algorithms for sparse optimization problems

• 成果类型: Article
• 署名作者: Gotoh, Jun-ya; Takeda, Akiko; Tono, Katsuya
• 署名单位: Chuo University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; RIKEN; NEC Corporation
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1181-0
• 发表日期: 2018
• 页码: 141-176
• 关键词: VARIABLE SELECTION; thresholding algorithm; subset-selection; NORM; shrinkage; EQUATIONS

摘要

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.