Complexity of unconstrained minimization

• 成果类型: Article
• 署名作者: Chen, Xiaojun; Ge, Dongdong; Wang, Zizhuo; Ye, Yinyu
• 署名单位: Hong Kong Polytechnic University; Shanghai Jiao Tong University; University of Minnesota System; University of Minnesota Twin Cities; Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0613-0
• 发表日期: 2014
• 页码: 371-383
• 关键词: sparse; selection

摘要

We consider the unconstrained - minimization: find a minimizer of for given , and parameters , and . This problem has been studied extensively in many areas. Especially, for the case when , this problem is known as the minimization problem and has found its applications in variable selection problems and sparse least squares fitting for high dimensional data. Theoretical results show that the minimizers of the - problem have various attractive features due to the concavity and non-Lipschitzian property of the regularization function . In this paper, we show that the - minimization problem is strongly NP-hard for any and , including its smoothed version. On the other hand, we show that, by choosing parameters carefully, a minimizer, global or local, will have certain desired sparsity. We believe that these results provide new theoretical insights to the studies and applications of the concave regularized optimization problems.