Complexity of unconstrained minimization
Complexity of unconstrained minimization
复制标题
DOI：
10.1007/s10107-012-0613-0
复制
发表时间：
2014-02-01
影响因子：
2.7
通讯作者：
Ye, Yinyu
中科院分区：
文献类型：
--
作者：
Chen, Xiaojun;Ge, Dongdong;Ye, Yinyu
我们考虑无约束极小化：找到给定的、参数和的极小元。这个问题在许多领域都得到了广泛的研究。特别是对于极小化问题，它在高维数据的变量选择问题和稀疏最小二乘拟合问题中得到了应用。理论结果表明，由于正则化函数的凹性和非Lipschitz性，问题的极小值具有各种吸引人的特征。在这篇文章中，我们证明了-最小化问题对任何AND，包括它的光滑化版本都是强NP难的。另一方面，我们证明了，通过谨慎地选择参数，极小值，无论是全局的还是局部的，都将具有一定的期望稀疏性。我们相信，这些结果为凹正则优化问题的研究和应用提供了新的理论见解。
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.