Weighted thresholding homotopy method for sparsity constrained optimization

Wenxing Zhu, Huating Huang, Lanfan Jiang () and Jianli Chen
Additional contact information
Wenxing Zhu: Fuzhou University
Huating Huang: Fuzhou University
Lanfan Jiang: Fuzhou University
Jianli Chen: Fuzhou University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 3, No 29, 1924-1952

Abstract: Abstract 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 $$l_1$$ l 1 -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 an L-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.

Keywords: Sparsity-constrained optimization; Mixed-integer programming; Lagrangian method; Weighted thresholding; Homotopy technique (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00563-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:3:d:10.1007_s10878-020-00563-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00563-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().