The complexity results of the sparse optimization problems and reverse convex optimization problems
- PDF / 244,219 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 48 Downloads / 223 Views
The complexity results of the sparse optimization problems and reverse convex optimization problems Zhongyi Jiang1,2 · Qiying Hu2 Received: 29 November 2018 / Accepted: 31 January 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we study complexity results of sparse optimization problems and reverse convex optimization problems. These problems are very important subjects of optimization problems. We prove that the complexity result of the sparsity constraint problem and sparse solution problem are all NP-hard in the strong sense and even testing feasibility of the sparsity constraint is NP-complete in the strong sense. Then the sparse optimization problem is NP-hard in the strong sense. We also prove that the reverse convex problem is NP-hard in the strong sense by transforming the sparsity constraint into a reverse convex constraint. Keywords Sparsity constraint · Sparsity constraint · Sparse solution · Reverse convex · Complexity · Strongly NP-hard
1 Introduction In this paper, we mainly consider complexity of sparsity constraint problems, sparse solution problems, and reverse convex optimization problems. The sparsity constraint problems and sparse solution problems are called sparse optimization problems. A sparsity constraint problem is given as follows: (SCP)
min f (x) s.t. x ∈ X , x0 ≤ K ,
B
Zhongyi Jiang [email protected] Qiying Hu [email protected]
1
School of Big Data, Changzhou University, Changzhou 213106, Jiangsu, China
2
School of Management, Fudan University, Shanghai 200433, China
123
Z. Jiang, Q. Hu
where f : Rn → R is the objective function, X is a set constructed by constraint functions, and x0 denotes the 0 -(quasi) norm which is defined as the number of nonzero entries in x. The sparsity constraint x0 ≤ K with 1 ≤ K < n is also called cardinality constraint. If the objective function and constraint set are both convex, then the problem is called sparsity constraint convex problem. The sparsity constraint problem is applied to portfolio selection [5,10,14,25,30,33], subset selection in multivariate regression [2,20], signal processing and compressed sensing [6]. A very important special case is the sparsity constraint linear problem (SCLP) given by (SCLP) min s.t.
f (x) = c T x Ax ≤ b, x0 ≤ K ,
where x = (x1 , x2 , . . . , xn )T ∈ Rn , A ∈ Rm×n , c ∈ Rn , b ∈ Rm , and K is a positive integer. The SCLP is used in robust optimization by [4], and also used to handle the uncertainty in health care management by [1]. It has been shown in [5] that the problem (SCP) and (SCLP) are both NP-hard, and that testing feasibility of SCLP is already NP-complete even when A has three rows. Finding the sparsest solutions of linear systems (SLS) is a very important sparse optimization problem, which has been widely used in signal and image processing (see [6,8,9,16,18,19,26,32], and the references therein). The problem can be described as follows: (SLS) min s.t.
x0 Ax = b, x ≥ 0.
The complexity result of SLS problem is NP-hard [22]. p The l p
Data Loading...
