Lagrange Dual Method for Sparsity Constrained Optimization
Lagrange Dual Method for Sparsity Constrained Optimization
复制标题
DOI：
10.1109/access.2018.2836925
复制
发表时间：
2018
期刊：
影响因子：
3.9
通讯作者：
Wen-xing Zhu;Zhengshan Dong;Yuanlong Yu;Jianli Chen
中科院分区：
文献类型：
--
作者：
Wen-xing Zhu;Zhengshan Dong;Yuanlong Yu;Jianli Chen
本文研究了拉格朗日对偶框架下的$L{0}$拟范数约束优化问题，证明了该问题具有强对偶性质。受此启发，我们提出了一种求解稀疏约束优化问题的拉格朗日对偶方法。该方法采用二分搜索技术来最大化拉格朗日对偶函数。对于每个拉格朗日乘子，我们采用迭代硬阈值方法来最小化拉格朗日函数。我们证明了所提出的方法收敛于原问题的$L$-驻点。计算实验和对多个测试实例(包括随机压缩感知实例和随机和真实稀疏Logistic回归实例)的比较表明，该方法能够准确地生成稀疏解。
In this paper, we investigate the $l_{0}$ quasi-norm constrained optimization problem in the Lagrange dual framework and show that the strong duality property holds. Motivated by the property, we propose a Lagrange dual method for the sparsity constrained optimization problem. The method adopts the bisection search technique to maximize the Lagrange dual function. For each Lagrange multiplier, we adopt the iterative hard thresholding method to minimize the Lagrange function. We show that the proposed method converges to an $L$ -stationary point of the primal problem. Computational experiments and comparisons on a number of test instances (including random compressed sensing instances and random and real sparse logistic regression instances) demonstrate the effectiveness of the proposed method in generating sparse solution accurately.