Heuristics for Finding Sparse Solutions of Linear Inequalities

Yichen Yang () and Zhaohui Liu
Additional contact information
Yichen Yang: Department of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China
Zhaohui Liu: Department of Mathematics, East China University of Science and Technology, Shanghai 200237, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2023, vol. 40, issue 01, 1-20

Abstract: In this paper, we consider the problem of finding a sparse solution, with a minimal number of nonzero components, for a set of linear inequalities. This optimization problem is combinatorial and arises in various fields such as machine learning and compressed sensing. We present three new heuristics for the problem. The first two are greedy algorithms minimizing the sum of infeasibilities in the primal and dual spaces with different selection rules. The third heuristic is a combination of the greedy heuristic in the dual space and a local search algorithm. In numerical experiments, our proposed heuristics are compared with the weighted-l1 algorithm and DCA programming with three different non-convex approximations of the zero norm. The computational results demonstrate the efficiency of our methods.

Keywords: Sparse optimization; zero norm; greedy heuristic (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021759592240005X
Access to full text is restricted to subscribers

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:wsi:apjorx:v:40:y:2023:i:01:n:s021759592240005x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021759592240005X

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().