Weighted thresholding homotopy method for sparsity constrained optimization
Weighted thresholding homotopy method for sparsity constrained optimization
复制标题
DOI：
10.1007/s10878-020-00563-7
复制
发表时间：
2020-04
影响因子：
1
通讯作者：
Wen-xing Zhu;Huating Huang;Lanfan Jiang;Jianli Chen
中科院分区：
文献类型：
--
作者：
Wen-xing Zhu;Huating Huang;Lanfan Jiang;Jianli Chen
针对稀疏约束优化问题，提出了一种新的加权阈值方法。通过将问题等价地转化为一个混合整数规划问题，我们研究了关于an范数约束的Lagrange对偶问题，并证明了它的强对偶性质。然后，我们给出了求解内拉格朗日问题的一种加权阈值方法，并分析了该方法的收敛特性。另外，在一定的假设条件下，给出了解的误差界。在此基础上，提出了一种变稀疏度和拉格朗日乘子的同伦算法，并证明了该算法在一定条件下收敛于原问题的一个非平稳点。计算实验表明，该算法在求解稀疏约束优化问题时具有较好的性能。
We propose in this paper a novel weighted thresholding method for the sparsity-constrained optimization problem. By reformulating the problem equivalently as a mixed-integer programming, we investigate the Lagrange duality with respect to an-norm constraint and show the strong duality property. Then we derive a weighted thresholding method for the inner Lagrangian problem, and analyze its convergence. In addition, we give an error bound of the solution under some assumptions. Further, based on the proposed method, we develop a homotopy algorithm with varying sparsity level and Lagrange multiplier, and prove that the algorithm converges to anL-stationary point of the primal problem under some conditions. Computational experiments show that the proposed algorithm is competitive with state-of-the-art methods for the sparsity-constrained optimization problem.