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 $\left|\right|\mathit{x}|{|}_p^p$ subject to $\left|\right|A\mathit{x}-\mathit{b}{\Vert }_q\le \sigma$ for given $A\in {\mathbb{R}}^{m\times n},\hspace{0.17em}\mathit{b}\in {\mathbb{R}}^m,\hspace{0.17em}\sigma \ge 0,\hspace{0.17em}0\le p\le 1$ and $q\ge 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\le 1$. Moreover, for $q\in \{1,\infty \}$, 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<\overline{p}<p^{*}$ such that the solution set of the problem with any $0<p\le \overline{p}$ remains unchanged. An estimation of such $p^{*}$ is also provided. In addition, to solve the constrained nonconvex non-Lipschitz L_p-L₁ 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₁ problem under different noises.