Sparse Solutions of a Class of Constrained Optimization Problems

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.