Sparse Solutions of a Class of Constrained Optimization Problems

Lei Yang (), Xiaojun Chen () and Shuhuang Xiang ()
Additional contact information
Lei Yang: Department of Mathematics, National University of Singapore, Singapore, Singapore 119076
Xiaojun Chen: Department of Applied Mathematics, The Hong Kong Polytechnic University, Kowloon, Hong Kong, China
Shuhuang Xiang: School of Mathematics and Statistics, INP-LAMA, Central South University, Changsha, Hunan 410083, China

Mathematics of Operations Research, 2022, vol. 47, issue 3, 1932-1956

Abstract: In this paper, we consider a well-known sparse optimization problem that aims to find a sparse solution of a possibly noisy underdetermined system of linear equations. Mathematically, it can be modeled in a unified manner by minimizing | | x | | p p subject to | | A x − b ‖ q ≤ σ for given A ∈ R m × n , b ∈ R m , σ ≥ 0 , 0 ≤ p ≤ 1 and q ≥ 1 . We then study various properties of the optimal solutions of this problem. Specifically, without any condition on the matrix A , we provide upper bounds in cardinality and infinity norm for the optimal solutions and show that all optimal solutions must be on the boundary of the feasible set when 0 < p ≤ 1 . Moreover, for q ∈ { 1 , ∞ } , we show that the problem with 0 < p < 1 has a finite number of optimal solutions and prove that there exists 0 < p * < 1 such that the solution set of the problem with any 0 < p < p * is contained in the solution set of the problem with p = 0, and there further exists 0 < p ¯ < p * such that the solution set of the problem with any 0 < p ≤ p ¯ remains unchanged. An estimation of such p * is also provided. In addition, to solve the constrained nonconvex non-Lipschitz L p - L 1 problem ( 0 < p < 1 and q = 1), we propose a smoothing penalty method and show that, under some mild conditions, any cluster point of the sequence generated is a stationary point of our problem. Some numerical examples are given to implicitly illustrate the theoretical results and show the efficiency of the proposed algorithm for the constrained L p - L 1 problem under different noises.

Keywords: Primary: 90C26; 90C30; secondary: 65K05; sparse optimization; nonconvex non-Lipschitz optimization; cardinality minimization; penalty method; smoothing approximation (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1194 (application/pdf)

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:inm:ormoor:v:47:y:2022:i:3:p:1932-1956

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().