Sparse Solutions of a Class of Constrained Optimization Problems

• 成果类型: Article; Early Access
• 署名作者: Yang, Lei; Chen, Xiaojun; Xiang, Shuhuang
• 署名单位: National University of Singapore; Hong Kong Polytechnic University; Central South University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.1194
• 发表日期: 2021
• 关键词: VARIABLE SELECTION; minimization; RECOVERY; signals; Penalty; systems

摘要

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 parallel to x parallel to(p)(p) subject to parallel to Ax - b parallel to(q) <= sigma for given A is an element of R-mxn, b is an element of R-m, sigma >= 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 infin-ity 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 is an element of{1, infinity}, 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) over bar < 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) over bar 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.