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:

$$\begin{aligned} \mathrm{(SCP)}\quad&\min ~f(x)\\&\mathrm{s.t.}~x\in X,\\&\Vert x\Vert _0\le K, \end{aligned}$$

where \(f:R_n\rightarrow R\) is the objective function, X is a set constructed by constraint functions, and \(\Vert x\Vert _0\) denotes the \(\ell _0\)-(quasi) norm which is defined as the number of nonzero entries in x. The sparsity constraint \(\Vert x\Vert _0\le K\) with \(1\le 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

$$\begin{aligned} \mathrm{(SCLP)}\quad \min \quad&f(x)=c^Tx\\ \mathrm{s.t.}\quad&Ax\le b,\\&\Vert x\Vert _0\le K, \end{aligned}$$

where \(x=(x_1,x_2,\ldots ,x_n)^T\in R_n\), \(A\in R_{m\times n}\), \(c\in R_n\), \(b\in R_m\), 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:

$$\begin{aligned} \mathrm{(SLS)}\quad \min \quad&\Vert x\Vert _0\\ \mathrm{s.t.}\quad&Ax=b,\\&x\ge 0. \end{aligned}$$

The complexity result of SLS problem is NP-hard [22].

The \(l_p\) minimization problem (\(\min \Vert x\Vert ^p_p~~s.t.\{Ax=b,~x\ge 0\}\)) and the unconstraint \(l_2-l_p\) minimization problem (\(\min ~f(x):=\Vert Ax-b\Vert ^2_2+\lambda \Vert x\Vert ^p_p\)) are used as regularization methods to find sparse solutions to the equation systems (\(Ax=b\)). The two problems are both NP-hard in the strong sense for \(p\in (0,1)\) ([11, 16]). The regularized sparse minimization problem, which involves general loss functions and a nonconvex sparsity penalty function, was proved to be NP-hard in the strong sense [12].

The reverse convex problem (RP) can be describe as follows:

$$\begin{aligned} \mathrm{(RP)}\quad \min \quad&f(x)\\ \mathrm{s.t.}\quad&h_i(x)\le 0,\quad i=1,\ldots ,m,\\&g(x)\ge 0, \end{aligned}$$

where f(x), \(h_i(x)\), g(x) : \(R_n\rightarrow R\) are all convex functions on \(R_n\). The reverse convex problems have been studied actively over the last four decades (see, e.g., [13, 17, 21, 28, 29] and their references), and Saad and Jacobsen [24] show that the complexity result of the reverse convex problem is NP-hard. The reverse convex problem (RP) is applied to telecommunication, mechanics, engineering design, economics, and other fields (see [3, 7, 27, 31], and the references therein).

In this paper, we provide a new theoretical insight to these problems to prove that their complexity results are all NP-hard in the strong sense. From complexity theory perspective, there are no polynomial time algorithm for an NP-hard optimization problem with a polynomially bounded objective function , and there are even no a pseudo polynomial time algorithm for a strongly NP-hard optimization problem with a polynomially bounded objective function, unless P = NP [15].

2 Main results

Theorem 1

The sparsity constraint linear program(SCLP) is NP-hard in the strong sense.

Proof

Firstly we describe a polynomial reduction from an instance of the 3-partition problem to an instance of (\(\mathrm {SCLP}\)). The 3-partition problem can be described as follows:

Given a set \(S=\{a_1,\ldots ,a_{3m}\}\) with \(\sum _{i=1}^{3m} a_i=mB\) and \(B/4<a_i<B/2\) for each \(a_i\), where \(a_i\) and B are all positive integers, is there a partition \(\{A_1,\ldots ,A_m\}\) with \(\sum _{a_i\in A_k}a_i=B\) for \(k=1,\ldots ,m\)?

Complexity of the 3-partition problem is NP-complete in the strong sense [15].

Let \(x_{i.}=(x_{i,1},x_{i,2},\ldots ,x_{i,3m})^T\) for \(i=1,\ldots ,m\), \(x_{.j}= (x_{1,j},x_{2,j},\ldots ,x_{m,j})^T\) for \(j=1,\ldots ,3m\) and \(x=(x_{1.}^T,\ldots ,x_{m.}^T)^T\). Given the 3-partition problem mentioned above, we construct the following SCLP problem

$$\begin{aligned} \mathrm{(P1)}\quad \min \quad&\sum _{j=1}^{3m}\sum _{i=1}^mx_{ij}a_j\\ \mathrm{s.t.}\quad&\sum _{j=1}^{3m}x_{i,j}a_j\ge B,\quad i=1,\ldots ,m,\\&0\le x_{ij}\le 1,\quad i=1,\ldots ,m,\quad j=1,\ldots ,3m,\\&\sum _{i=1}^{m}x_{i,j}\le 1,\quad j=1,\ldots ,3m,\\&\Vert x\Vert _0\le 3m \end{aligned}$$

In the following, we prove that the optimal value of problem (P1) is mB if and only if the 3-partition problem has an solution. It is not difficult to see that the lower bound of the objective function of problem (P1) is mB due to \(\sum _{j=1}^{3m}x_{i,j}a_j\ge B\) for \(i=1,\ldots ,m\).

Suppose the 3-partition problem has a solution satisfying

$$\begin{aligned} A_i=\{a_{3i-2},a_{3i-1},a_{3i}\} \end{aligned}$$

and \(a_{3i-2}+a_{3i-1}+a_{3i}=B\) for \(i=1,\ldots ,m\). Let \(\tilde{x}\) be a point with \(\tilde{x}_{i,3i-2}=\tilde{x}_{i,3i-1}=\tilde{x}_{i,3i}=1\) for \(i=1,\ldots ,m\), and the other elements of \(\tilde{x}\) be 0. Then \(\sum _{j=1}^{3m}\sum _{i=1}^m\tilde{x}_{i,j}a_j=mB\) and

$$\begin{aligned}&\sum _{j=1}^{3m}\tilde{x}_{i,j}a_j= B,\quad i=1,\ldots ,m,\\&0\le \tilde{x}_{ij}\le 1,\quad i=1,\ldots ,m,\;\;j=1,\ldots ,3m,\\&\sum _{i=1}^{m}\tilde{x}_{i,j}= 1,\quad j=1,\ldots ,3m,\\&\Vert \tilde{x}\Vert _0= 3m. \end{aligned}$$

So \(\tilde{x}\) is the optimal solution to problem (P1).

Suppose problem (P1) has an optimal solution. We show next that the optimal solution is also a solution to the 3-Partition problem.

From \(0\le x_{ij}\le 1\), \(\sum _{j=1}^{3m}x_{ij}a_j\ge B\) and \(B/4\le a_i\le B/2\), we can conclude that \(\Vert x_{i.}\Vert _0\ge 3\) for \(i=1,\ldots ,m\). Combining \(\Vert x\Vert _0\le 3m\), we can infer that \(\Vert x_{i.}\Vert _0=3\) and \(\Vert x\Vert _0= 3m\).

Next we prove that the optimal solution of problem (P1) must be binary, i.e., \(x_{i,j}=0 \) or 1. By controversy, suppose there exists an optimal solution \(\bar{x}\) which is not binary, to problem (P1).

Without loss of generality, suppose \(0<\bar{x}_{1,1}<1\). From \(\sum _{j=1}^{3m}x_{i,j}a_j\ge B,~~i=1,\ldots ,m\), we can get \(\sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}_{ij}a_j\ge mB\). Moreover,

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}_{ij}a_j= & {} a_1\left( \bar{x}_{1,1}+\sum _{i=2}^m\bar{x}_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}_{i,2}}+\cdots +a_k{\sum _{i=1}^m\bar{x}_{i,k}}\\&+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}_{i,3m}}. \end{aligned}$$

We discuss the conditions of \(\sum _{i=2}^m\bar{x}_{i,1}\) as follows.

If \(\sum _{i=2}^m\bar{x}_{i,1}>0\), then \(\Vert \bar{x}_{.1}\Vert _0>1\). Thus there must exist \(i'>1\) such that \(\Vert \bar{x}_{.i'}\Vert _0 = 0\) because of \(\Vert \bar{x}\Vert _0\le 3m\). Then

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m\bar{x}_{ij}a_j= & {} a_1\left( \bar{x}_{1,1}+\sum _{i=2}^m\bar{x}_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}_{i,2}}+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}_{i,3m}}\\\le & {} a_1+a_{2}+\cdots +0a_{i'}+\cdots +a_{3m}\\< & {} mB, \end{aligned}$$

which contradicts to the feasibility of Problem (P1).

There must be \(\sum _{i=2}^m\bar{x}_{i,1}=0\). Then

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m\bar{x}_{ij}a_j= & {} a_1\left( \bar{x}_{1,1}+\sum _{i=2}^m\bar{x}_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}_{i,2}}+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}_{i,3m}}\\= & {} a_1(\bar{x}_{1,1})+a_2{\sum _{i=1}^m\bar{x}_{i,2}}+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}_{i,3m}}\\\le & {} a_1(\bar{x}_{1,1})+a_{2}+\cdots +a_{k}+\cdots +a_{3m}\\< & {} mB \end{aligned}$$

which contradicts to \(\sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}_{ij}a_j\ge mB\). Therefore, the optimal solution of problem (P1) must be binary.

Let \(x^*\) be an optimal solution to problem (P1). Then \(x^*\) must be binary, \(\Vert x_{i.}^*\Vert _0=3\) and \(\Vert x^*\Vert _0=3m\). Without loss of generality, suppose \(x^*_{i,3i-2}=x^*_{i,3i-1}=x^*_{i,3i}=1\) for \(i=1,\ldots ,m\), and the other elements of \(x^*\) are all zero. Then, we have \(a_{3i-2}+a_{3i-1}+a_{3i}\ge B\) for \(i=1,\ldots ,m\). Based on \(\sum _{i=1}^3ma_i=mB\), we can get that \(a_{3i-2}+a_{3i-1}+a_{3i}= B\) for \(i=1,\ldots ,m\). Thus, we get a solution of the 3-partition problem. Therefore, we have proved that the complexity result of SCLP problem is NP-hard in the strong sense [15]. \(\square \)

Theorem 2

The sparsity constraint problem(SCP) is NP-hard in the strong sense.

Proof

Based on the 3-partition problem, we construct the following sparsity constraint problems:

$$\begin{aligned} \mathrm{(P2)}\quad \min \quad&\sum _{j=1}^{3m}\sum _{i=1}^mx^N_{ij}a_j\\ \mathrm{s.t.}\quad&\sum _{j=1}^{3m}x^M_{i,j}a_j\ge B,\quad i=1,\ldots ,m,\\&0\le x_{ij}\le 1,\quad i=1,\ldots ,m,\;\;j=1,\ldots ,3m,\\&\sum _{i=1}^{m}x_{i,j}\le 1,\quad j=1,\ldots ,3m,\\&\Vert x\Vert _0\le 3m, \end{aligned}$$

where N and M are both positive integers. If \(N=M=1\), problem (P2) is equivalent to problem (P1), i.e., problem (P1) is a special case of problem (P2). Then we can get that the complexity result of problem (P2) is NP-hard in the strong sense. If N and M are different integers, problem (P2) have different characteristics. We prove in the following that no matter what integers N and M are, the problem (P2) is still NP-hard in the strong sense. If both N and M are even numbers, then we have a special case of sparsity constraint convex problem with a convex objective function and convex constraint functions. If N and M are odd, then we build a special case of sparsity constraint problems with non-convex objective functions and non-convex constraint functions. If one of N and M is even, and the other one is odd, then we build a special case of sparsity constraint problems with either the objective function or constraint functions is convex and the other is non-convex.

Now, we prove that any feasible solution to problem (P2) is binary.

Suppose x is feasible to problem (P2). From \(\sum _{j=1}^{3m}x^M_{ij}a_j\ge B\), we can get that

$$\begin{aligned} \sum _{i=1}^m\sum _{j=1}^{3m}x^M_{ij}a_j\ge B \end{aligned}$$
(1)

From \(0\le x_{ij}\le 1\), \(\sum _{j=1}^{3m}x^M_{ij}a_j\ge B\) and \(B/4\le a_i\le B/2\), we can conclude that \(\Vert x_{i.}\Vert _0\ge 3\) for \(i=1,\ldots ,m\). Combining \(\Vert x\Vert _0\le 3m\), we can infer that \(\Vert x_{i.}\Vert _0=3\) and \(\Vert x\Vert _0= 3m\).

Next we prove that x must be binary, i.e., \(x_{i,j}=0 \) or 1. By controversy, suppose there exists a non binary feasible solution \(\bar{x}\) to problem (P2).

Without loss of generality, suppose \(0<\bar{x}_{1,1}<1\). From \(\sum _{j=1}^{3m}x^M_{i,j}a_j\ge B,\) for \(i=1,\ldots ,m\), we can get

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}^M_{ij}a_j\ge mB, \end{aligned}$$

and

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}_{ij}^Ma_j= & {} a_1\left( \bar{x}^M_{1,1}+\sum _{i=2}^m\bar{x}^M_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}^M_{i,2}}+\cdots +a_k{\sum _{i=1}^m\bar{x}^M_{i,k}}\\&+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}^M_{i,k}}. \end{aligned}$$

If \(\sum _{i=2}^m\bar{x}^M_{i,1}>0\), then \(\Vert \bar{x}_{.1}\Vert _0>1\). Thus there must exist at least one L with \(2\le L\le 3m\) such that \(\Vert \bar{x}_{.L}\Vert =0\) due to \(\Vert \bar{x}\Vert _0= 3m\). Therefore,

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m\bar{x}^M_{ij}a_j= & {} a_1\left( \bar{x}^M_{1,1}+\sum _{i=2}^m\bar{x}^M_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}^M_{i,2}}+\cdots +a_L{\sum _{i=1}^m\bar{x}^M_{i,L}}\\&+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}^M_{i,3m}}\\= & {} a_1\left( \bar{x}^M_{1,1}+\sum _{i=2}^m\bar{x}^M_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}^M_{i,2}}+\cdots +a_{L-1}{\sum _{i=1}^m\bar{x}^M_{i,L-1}}\\&+\,a_{L+1}{\sum _{i=1}^m\bar{x}^M_{i,L+1}}+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}^M_{i,3m}}\\\le & {} a_1+\cdots +a_{L-1}+a_{L+1}+\cdots +a_{3m}\\< & {} mB, \end{aligned}$$

which contradicts with \(\sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}^M_{ij}a_j\ge mB\).

Thus there must be \(\sum _{i=2}^m\bar{x}^M_{i,1}=0\). So,

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m\bar{x}^M_{ij}a_j= & {} a_1\left( \bar{x}^M_{1,1}+\sum _{i=2}^m\bar{x}^M_{i,1}\right) +a_2{\sum _{i=1}^m\bar{x}^M_{i,2}}+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}^M_{i,k}}\\= & {} a_1(\bar{x}^M_{1,1})+a_2{\sum _{i=1}^m\bar{x}^M_{i,2}}+\cdots +a_{3m}{\sum _{i=1}^m\bar{x}^M_{i,k}}\\\le & {} a_1(\bar{x}^M_{1,1})+a_{2}+\cdots +a_{3m}\\< & {} mB \end{aligned}$$

which contradicts to \(\sum _{j=1}^{3m}\sum _{i=1}^m \bar{x}^M_{ij}a_j\ge mB\). So feasible solutions of problem (P2) must be binary. Then, problem (P2) is equivalent to problem (P1) because \(\sum _{j=1}^{3m}x^M_{i,j}a_j=\sum _{j=1}^{3m}x_{i,j}a_j\), for x is binary. We can get that problem (P2) has the optimal solutions if and only if the 3-partition problem has a solution based on the proof of Theorem 1. Therefore, we have proved that the complexity result of the cardinality constraint problem is NP-hard in the strong sense. \(\square \)

Theorem 3

Testing the feasibility of the sparsity constraint problem(SCP) is NP-complete in the strong sense.

Proof

It is easy to confirm that the problem of testing the feasibility of the sparsity constraint is in NP. Then we prove that there is a feasible solution to problem (P2) if and only if there is a solution to the 3-partition problem.

Suppose the 3-partition problem has a solution such that

$$\begin{aligned} A_i=\{a_{3i-2},a_{3i-1},a_{3i}\} \end{aligned}$$

and \(a_{3i-2}+a_{3i-1}+a_{3i}=B\) for \(i=1,\ldots ,m\). Let x be a point with \({x}_{i,3i-2}={x}_{i,3i-1}={x}_{i,3i}=1\) for \(i=1,\ldots ,m\) , and the other elements of x being 0. Then,

$$\begin{aligned}&\sum _{j=1}^{3m}x^M_{i,j}a_j= B,\quad i=1,\ldots ,m,\end{aligned}$$
(2)
$$\begin{aligned}&0\le x_{ij}\le 1,\quad i=1,\ldots ,m,\;\; j=1,\ldots ,3m,\end{aligned}$$
(3)
$$\begin{aligned}&\sum _{i=1}^{m}x_{i,j}= 1,\quad j=1,\ldots ,3m,\end{aligned}$$
(4)
$$\begin{aligned}&\Vert x\Vert _0= 3m. \end{aligned}$$
(5)

Therefore, x is a feasible solution to problem (P2).

First, suppose x is a feasible solution to problem (P2), we want to get a solution to the 3-partition problem:

$$\begin{aligned}&\sum _{j=1}^{3m}x^M_{i,j}a_j\ge B,~~i=1,\ldots ,m,\end{aligned}$$
(6)
$$\begin{aligned}&0\le x_{ij}\le 1,~~i=1,\ldots ,m,~j=1,\ldots ,3m,\end{aligned}$$
(7)
$$\begin{aligned}&\sum _{i=1}^{m}x_{i,j}\le 1,~~j=1,\ldots ,3m,\end{aligned}$$
(8)
$$\begin{aligned}&\Vert x\Vert _0\le 3m \end{aligned}$$
(9)

From (6), we get \(\sum _{i=1}^{m}\sum _{j=1}^{3m}x^M_{i,j}a_j\ge mB\). From (8) and \(\sum _{i=1}^{3m} a_i=mB\), we can conclude \(\sum _{i=1}^{m}\sum _{j=1}^{3m}x^M_{i,j}a_j\le mB\). Then, there must be

$$\begin{aligned} \sum _{i=1}^{m}\sum _{j=1}^{3m}x^M_{i,j}a_j= mB \end{aligned}$$

and \(\sum _{j=1}^{3m}x^M_{i,j}a_j= B\) for \(i=1,\ldots ,m.\) Based on the proof of Theorem 2, x is binary. Then, we get a solution to the 3-partition problem. When \(M=1\), we have proved that testing the feasibility of sparsity constraint linear problem is NP-complete in the strong sense. When \(M>1\), we have proved that testing the feasibility of the other cases of sparsity constraint problem is NP-complete in the strong sense. \(\square \)

Theorem 4

The sparsest solutions of the linear system problem (SLS) is NP-hard in the strong sense.

Proof

Based on the 3-partition problem mentioned above, we construct a sparsest solutions of linear system problem (SLP) as follows:

$$\begin{aligned} \mathrm{(P3)}\quad \min \quad&\Vert x\Vert _0\\ \mathrm{s.t.}\quad&\sum _{j=1}^{3m}x_{i,j}a_j= B,\quad i=1,\ldots ,m,\\&\sum _{i=1}^{m}x_{i,j}= 1,\quad j=1,\ldots ,3m,\\&x_{ij}\ge 0,\quad i=1,\ldots ,m,\;\; j=1,\ldots ,3m.\\ \end{aligned}$$

Next we prove that there exist a solution of problem (P3) \(\tilde{x}\) with \(\Vert \tilde{x}\Vert _0\le 3m\) if and only if the 3-partition has a solution.

Suppose the 3-partition problem has a solution satisfying

$$\begin{aligned} A_i=\{a_{3i-2},a_{3i-1},a_{3i}\} \end{aligned}$$

and

$$\begin{aligned} a_{3i-2}+a_{3i-1}+a_{3i}=B \end{aligned}$$

for \(i=1,\ldots ,m\). Let \(\tilde{x}\) be \(\tilde{x}_{i,3i-2}=\tilde{x}_{i,3i-1}=\tilde{x}_{i,3i}=1\) for \(i=1,\ldots ,m\) , and the other elements of \(\tilde{x}\) equal 0. Then if \(j=3i-2\), \(\sum _{i=1}^{m}\tilde{x}_{i,j}=\tilde{x}_{i,3i-2}=1\); if \(j=3i-1\), \(\sum _{i=1}^{m}\tilde{x}_{i,j}=\tilde{x}_{i,3i-1}=1\); if \(j=3i\), \(\sum _{i=1}^{m}\tilde{x}_{i,j}=\tilde{x}_{i,3i}=1\), for \(j=1,\ldots ,3m\). Therefore

$$\begin{aligned} \sum _{i=1}^{m}\tilde{x}_{i,j}= 1,\quad j=1,\ldots ,3m, \end{aligned}$$

and

$$\begin{aligned} \sum _{j=1}^{3m}\tilde{x}_{i,j}a_j= a_{3i-2}+a_{3i-1}+a_{3i}=B,\quad i=1,\ldots ,m, \end{aligned}$$

Thus \(\tilde{x}\) is feasible to problem (P3) and \(\Vert \tilde{x}\Vert _0= 3m\).

Suppose there is a solution to problem (P3) \(\tilde{x}\) with \(\Vert \tilde{x}\Vert _0\le 3m\). Then,

$$\begin{aligned}&\Vert \tilde{x}\Vert _0\le 3m\end{aligned}$$
(10)
$$\begin{aligned}&\sum _{j=1}^{3m}\tilde{x}_{i,j}a_j= B,\quad i=1,\ldots ,m,\end{aligned}$$
(11)
$$\begin{aligned}&\sum _{i=1}^{m}\tilde{x}_{i,j}=1,\quad j=1,\ldots ,3m\end{aligned}$$
(12)
$$\begin{aligned}&\tilde{x}_{ij}\ge 0,\quad i=1,\ldots ,m,\;\;j=1,\ldots ,3m. \end{aligned}$$
(13)

From (12) and (13), we can get \(0\le \tilde{x}_{ij}\le 1\). From (11) and (12), we have

$$\begin{aligned} \sum _{j=1}^{3m}\sum _{i=1}^m\tilde{x}_{ij}a_j=mB \end{aligned}$$

Then \(\tilde{x}\) is a feasible solution to problem (P1). Based on the proof of Theorem 1, \(\tilde{x}\) is also an optimal solution to problem (P1). Thus, we get a solution of the 3-partition problem. \(\square \)

The sparsity constraint problem (SCP), sparsity constraint linear problem (SCLP), and the sparsest solutions of linear systems (SLS) are all special cases of sparse optimization problem. Then based on Theorem 1, 2, and 4, we can get the following results:

Theorem 5

The sparse optimization problem is NP-hard in the strong sense.

Nextly we discuss the reverse convex problem.

Theorem 6

The reverse convex program is NP-hard in the strong sense, even if the objective function is linear and the constraint set except the reverse convex constraint is a polytope.

Proof

We present a transformation from the sparsity constraint to a reverse convex constraint to prove the theorem. Let \(x_{[i]}\) denote the i-th largest entry of \(x=(x_1,\ldots ,x_n)^T\). Then it is easy to see that \(\Vert x\Vert _0\le K\) is equivalent to \( x_{[K+1]}\le 0\) because of \(x\ge 0\). Note that

$$\begin{aligned} x_{[K+1]}=\sum _{i=1}^{K+1}x_{[i]}-\sum _{i=1}^{K}x_{[i]}=S_{K+1}(x)-S_{K}(x), \end{aligned}$$

where \(S_{K}(x)=\sum _{i=1}^{K}x_{[i]}\) for \(K=1,\ldots ,n\).

Because of \(x\ge 0\), \(S_{K+1}(x)-S_{K}(x)\le 0\) is equivalent to \(x_{[i]}=0\) for \(i=K+1,\ldots ,n\). And \(S_{K+1}(x)-S_{K}(x)\le 0\) is equivalent to \(\sum _{i=1}^{n}x_{i}-S_{K}(x)\le 0\) for the same reason. Then, the cardinality constraint \(\Vert x\Vert _0\le K\) is equivalent to

$$\begin{aligned} S_{K}(x)-\sum _{i=1}^{n}x_{i}\ge 0 \end{aligned}$$

Therefore, problem (SCLP) can be equivalently transformed into the following problem:

$$\begin{aligned} \mathrm{(P4)}\quad \min \quad&c^Tx\\ \mathrm{s.t.}\quad&Ax\le b,\\&S_{K}(x)- \sum _{i=1}^{n}x_{i}\ge 0,\\&x\ge 0, \end{aligned}$$

Since \(S_{K}(x)\) is a convex function [23], \(S_{K}(x)- \sum _{i=1}^{n}x_{i}\) is a convex function. Thus, the constraint \(S_{K}(x)- \sum _{i=1}^{n}x_{i}\ge 0\) is reverse convex. Therefore, we transformed the cardinality constraint linear problem into a reverse convex constraint linear problem, which means that the complexity result of the reverse convex problem is NP-hard in the strong sense even though the objective function is linear and constraint sets except the reverse convex constraint is a polytope [15]. \(\square \)

3 Conclusions

We proved that the sparse optimization problems and reverse convex problems are NP-hard in the strong sense in this paper. We gave a transformation from the 3-partition problem to prove that the sparsity constraint problem is NP-hard in the strong sense. And testing the feasibility of the sparsity constraint problem is NP-complete in the strong sense. We also prove that the sparse solution optimization problem is NP-hard in the strong sense. We then equivalently transformed the sparsity constraint to a reverse convex constraint. Based on this result and the strongly NP-hard result of the cardinality constraint problem, we present that the complexity of reverse convex problem is NP-hard in the strong sense even the objective function is linear and constraint set is a polytope except the reverse constraint.