Optimization Online


Weighted Thresholding Homotopy Method for Sparsity Constrained Optimization

Wenxing Zhu(wxzhu***at***fzu.edu.cn)
Huating Huang(1207088571***at***qq.com)
Lanfan Jiang(jianglanfan***at***foxmail.com)
Jianli Chen(jlchen***at***fzu.edu.cn)

Abstract: Weighted or reweighted strategies have not been considered for sparsity constrained optimization. In this paper, we reformulate the sparsity constraint as an equivalent weighted l1-norm constraint in the sparsity constrained optimization problem. To solve the reformulated problem, we investigate the problem in the Lagrange dual framework, and prove that the strong duality property holds. Then we propose a weighted thresholding method to solve the Lagrangian problem. Moreover, we analyze convergence of the method and derive an error bound of the solution under some assumptions. Furthermore, we propose a weighted thresholding homotopy method to get a suitable Lagrange multiplier and prove that this homotopy method can find an L-stationarity point of the primal problem. Computational experiments on compressed sensing and sparse logistic regression problems show that, in comparable running time the proposed weighted thresholding homotopy method works better than state-of-the-art methods on randomly generated instances of the compressed sensing problem and on the synthetic data of the logistic regression problem. Especially, the sparsity level improvement of exact recovery is 26.9% for compressed sensing, and the sparsity level improvement of exact classification is 38.5% for sparse logistic regression on randomly generated data.

Keywords: Sparsity constraint, weighted thresholding, Lagrangian method, homotopy technique.

Category 1: Integer Programming


Download: [PDF]

Entry Submitted: 12/11/2018
Entry Accepted: 12/12/2018
Entry Last Modified: 12/11/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society