^{1}

^{*}

^{1}

In this paper, we consider an extragradient thresholding algorithm for finding the sparse solution of mixed complementarity problems (MCPs). We establish a relaxation
l
_{1} regularized projection minimization model for the original problem and design an extragradient thresholding algorithm (ETA) to solve the regularized model. Furthermore, we prove that any cluster point of the sequence generated by ETA is a solution of MCP. Finally, numerical experiments show that the ETA algorithm can effectively solve the
l
_{1} regularized projection minimization model and obtain the sparse solution of the mixed complementarity problem.

Define a continuously differentiable function F : R n → R n , and a nonempty set

Ω : = { x ∈ R n | a ≤ x ≤ b } ,

where a = { R ∪ { − ∞ } } n , b = { R ∪ { + ∞ } } n and a < b ( a i < b i , i = 1 , 2 , ⋯ , n ) . The mixed complementarity problem is to find a vector x ∈ Ω , such that

( y − x ) T F ( x ) ≥ 0, ∀ y ∈ Ω . (1)

The mixed complementarity problem, also known as box constrained variational inequality problem, denoted by MCP (a, b, F). In particular, if Ω : = R + n , the mixed complementarity problem becomes a nonlinear complementarity problem (NCP), is to find a vertor x ≥ 0 , such that

F ( x ) ≥ 0 , F ( x ) T x = 0.

Moreover, if F ( x ) : = M x + q , where M ∈ R n × n , q ∈ R n , the nonlinear complementary problem reduces a linear complementary problem (LCP):

x ≥ 0, M x + q ≥ 0, ( M x + q ) T x = 0.

The set of solution to the mixed complementarity problem is denoted by SOL (F), throughout this paper, we assume S O L ( F ) ≠ ∅ .

The MCP has wide applications in fields of science and engineering [

In recent years, the problem of recovering an unknown sparse solution from some linear constraints has been an active topic with a range of applications including signal processing, machine learning, and computer vision [

In contrast with the fast development in sparse solutions of optimization and linear equations, there are few researches available for the sparse solutions of the complementarity problems. The sparse solution problem of linear complementarity was first studied by Chen and Xiang [

Along with the research of [

Due to the relationship between MCP and the variational inequality, we aim to seek a vector x ∈ Ω by solving the solution of l 0 norm minimization problem:

min ‖ x ‖ 0 , s .t . ( y − x ) T F ( x ) ≥ 0, (2)

for any y ∈ Ω , where ‖ x ‖ 0 stands for the number of nonzero components of x and a solution of problem (2) is called the sparse solution of MCP.

In essence, the minimization problem (2) is a sparse optimization problem with equilibrium constraints. It is not easy to get solutions due to the equilibrium constraints, even if the objective function is continuous.

To overcome the difficulty for the l 0 norm, many researchers have suggested to relax the l 0 norm and instead to consider the l 1 norm, see [

min x ∈ Ω ‖ x ‖ 1 , s .t . ( y − x ) T F ( x ) ≥ 0 (3)

for any y ∈ Ω and where ‖ x ‖ 1 = ∑ i = 1 n | x i | .

Given a vector x ∈ Ω , let P Ω ( x ) be the projection of x on Ω , for convenience, we write P Ω ( x ) = [ x ] Ω , it is well known (see, e.g., [

W ( x * ) : = x * − [ x * − F ( x * ) ] Ω = 0, (4)

and therefore problem (3) is equivalent to the following optimization problem

min x , z ∈ R n f ( x ) : = ‖ x ‖ 1 s .t . x = [ x − F ( x ) ] Ω . (5)

In order to simplify the objective function, we introduce a new variable z ∈ R n and a regularization parameter λ > 0 and establish the corresponding regularized minimization problem as follows:

min x , z ∈ R n f λ ( x , z ) : = ‖ x − z ‖ 2 + λ ‖ x ‖ 1 s .t . z = [ x − F ( x ) ] Ω . (6)

We call (6) the l 1 regularized projection minimization problem.

This paper is organized as follows. In Section 2, we study the relation between the solution of model (6) and that of problem (3), and we show theoretically that (6) is a good approximation of problem (3). In Section 3, we propose an extragradient thresholding algorithm(ETA) for (6) and analyze the convergence of this algorithm. Numerical results are given in Section 4 and conclusion is described in Section 5.

In this section, we study the relation between the solution of model (6) and that of model (3). The following theorem shows that model (6) is a good approximation of problem (3).

Theorem 2.1. For any fixed λ > 0 , the solution set of (6) is nonempty and bounded. Let { ( x λ k , z λ k ) } be a solution of (6), and { λ k } be any positive sequence converging to 0. If S O L ( F ) ≠ ∅ , then { ( x λ k , z λ k ) } has at least one accumulation point, and any accumulation point x ∗ of { x λ k } is a solution of (1.3).

Proof. For any fixed λ > 0 , since

f λ ( x , z ) → + ∞ as ‖ ( x , z ) ‖ → ∞ , (7)

which means f λ ( x , z ) is coercivity. On the other hand, it is clear that for any x ∈ R n and z ∈ R n , f λ ( x , z ) ≥ 0 . This together with (7) implies the level set

L = { ( x , z ) ∈ R n × R n | f λ ( x , z ) ≤ f λ ( x 0 , z 0 ) and z = [ x − F ( x ) ] Ω }

is nonempty and compact, where x 0 ∈ R n and z 0 = [ x 0 − F ( x 0 ) ] Ω are given points, which deduces that the solution set of problem (6) is nonempty and bounded since f λ ( x , z ) is continuous on L.

Now we consider the proof of the second part of this theorem. Let x ^ ∈ S O L ( F ) and z ^ = [ x ^ − F ( x ^ ) ] Ω . from (5), we have x ^ = z ^ . Since ( x λ k , z λ k ) is a solution of (6) with λ = λ k , where z λ k = [ x λ k − F ( x λ k ) ] Ω , it follows that

max { ‖ x λ k − z λ k ‖ 2 , λ k ‖ x λ k ‖ 1 } ≤ ‖ x λ k − z λ k ‖ 2 + λ k ‖ x λ k ‖ 1 ≤ ‖ x ^ − z ^ ‖ 2 + λ k ‖ x ^ ‖ 1 = λ k ‖ x ^ ‖ 1 . (8)

This implies that for any λ k > 0 ,

‖ x λ k ‖ 1 ≤ ‖ x ^ ‖ 1 . (9)

Hence the sequence { x λ k } is bounded and has at least one cluster point and so is { z λ k } due to ‖ x λ k − z λ k ‖ 2 ≤ λ k ‖ x ^ ‖ 1 .

Let x ∗ and z ∗ be any cluster points of { x λ k } and { z λ k } , respectively, and z λ k = [ x λ k − F ( x λ k ) ] Ω . Then there exists a subsequence of { λ k } , say { λ k j } , such that

lim k j → ∞ x λ k j = x ∗ and lim k j → ∞ z λ k j = z ∗ .

We can obtain z ∗ = [ x ∗ − F ( x ∗ ) ] Ω by letting k j → ∞ in z λ k = [ x λ k − F ( x λ k ) ] Ω . Letting λ k j → 0 , in

‖ x λ k j − z λ k j ‖ 2 ≤ λ k j ‖ x ^ ‖ 1

yields x ∗ = z ∗ . Consequently, x ∗ = [ x ∗ − F ( x ∗ ) ] Ω , which implies x ∗ ∈ S O L ( F ) . Let k j tend to ∞ in (9), we get ‖ x ∗ ‖ 1 ≤ ‖ x ^ ‖ 1 . Then by the arbitrariness of x ^ ∈ S O L ( F ) , we know x ∗ is solution of problem (3). This completes the proof. ¢

In this section, we give the extragradient thresholding algorithm (ETA) to solve l 1 regularization projection minimization problem (6) and give the convergence analysis of ETA.

First, we review some basic concepts about the monotone operator and the properties of the projection operator which can be found in [

Lemma 3.1. Let P K ( ⋅ ) be a projection from R n to K, where K is a non-empty closed convex subset on R n . Then we have

(a) For y ∈ R n ,

( y − P K [ y ] ) T ( P K [ y ] − x ) ≥ 0, ∀ x ∈ K ; (10)

(b) for any y , z ∈ R n ,

‖ P K [ y ] − P K [ z ] ‖ 2 ≤ ( y − z ) T ( P K [ y ] − P K [ z ] ) . (11)

Using Lemma 3.1, we can obtain the following properties easily.

Lemma 3.2. Define a residue funtion

H ( α ) : = P K [ x − α d ] , α ≥ 0 , d ∈ R n . (12)

Then the following statements are valid.

(a) For any α ≥ 0 , ‖ x − H ( α ) ‖ α is non-increasing;

(b) ∀ α > 0 , d T ( x − H ( α ) ) ≥ ‖ x − H ( α ) ‖ 2 α ;

(c) ∀ z ∈ R n , ‖ P K [ z ] − x ‖ 2 ≤ ‖ z − x ‖ 2 − ‖ P K [ z ] − z ‖ 2 .

In this paper, we suppose the mapping F : R n → R n is co-coercive on the set Ω , i.e., there exists a constant c > 0 such that

〈 F ( x ) − F ( y ) , x − y 〉 ≥ c ‖ F ( x ) − F ( y ) ‖ 2 , ∀ x , y ∈ Ω .

It is clear that the co-coercive mapping is monotone, namely,

〈 F ( x ) − F ( y ) , x − y 〉 ≥ 0, ∀ x , y ∈ Ω .

For a given z k ∈ Ω and λ k > 0 , we consider an unconstrained minimization subproblem:

min x ∈ R n f λ k ( x , z k ) : = ‖ x − z k ‖ 2 + λ k ‖ x ‖ 1 . (13)

Evidently, the minimizer x * of the model (13) satisfies the corresponding optimality condition

x * = S λ k ( z k ) , (14)

where the shrinkage operator S λ is defined by (see, e.g., [

( S λ ( z ) ) i = ( z i − λ 2 , z i ≥ λ 2 ; 0, − λ 2 ≤ z i ≤ λ 2 ; z i + λ 2 , z i ≤ − λ 2 . (15)

It demonstrates that a solution x ∈ R n of the subproblem (13) can be analytically expressed by (14).

In what follows, we construct the extragradient thresholding algorithm (ETA) to solve the l 1 regularized projection minimization problem (6).

Algorithm ETA

Step 0: Choose 0 ≠ z 0 ∈ Ω , λ 0 , γ > 0 , τ , l , μ ∈ ( 0 , 1 ) , ϵ > 0 and a positive integers n max > K 0 > 0 , set k = 0 .

Step 1: Compute x k = S λ k ( z k ) , y k = [ x k − α k F ( x k ) ] Ω , where α k = γ l m k with m k being the smallest nonnegative integer satisfying

‖ F ( x k ) − F ( y k ) ‖ ≤ μ ‖ x k − y k ‖ α k . (16)

Step 2: If ‖ x k − z k ‖ ≤ ϵ or the number of iterations is greater than n max , then return z k , x k , y k and stop. Otherwise, compute

z k + 1 = [ x k − α k F ( y k ) ] Ω ,

and update λ k + 1 by

λ k + 1 = ( τ λ k , if k + 1 is a multiple of K 0 , λ k , otherwise .

Step 3: Let k = k + 1 , then go to Step 1.

Define

x ( α ) = [ x − α F ( x ) ] Ω , α ≥ 0

and

e ( x , a ) = x − x ( α ) , r ( x , α ) = ‖ e ( x , α ) ‖

It is easy to see that x k is a solution for MCP if and only if e ( x k , α ) = 0 , ∀ α > 0 .

The following lemma plays an important role in the analysis of the global convergence of the Algorithm ETA.

Lemma 3.3. Suppose that mapping F is co-coercive and S O L ( F ) ≠ ∅ . If x k generated by ETA is not a solution of M C P ( F ) , then for any x ^ ∈ S O L ( F ) , we have

〈 F ( y k ) , x k − x ^ 〉 ≥ 〈 F ( y k ) , x k − y k 〉 ≥ ( 1 − μ ) ‖ x k − y k ‖ 2 γ . (17)

Proof. Since x ^ ∈ S O L ( F ) and y k ∈ Ω , it follows that 〈 F ( x ^ ) , y k − x ^ 〉 ≥ 0 . By the co-coercive of mapping F, we have 〈 F ( y k ) , y k − x ^ 〉 ≥ 0 . Hence

〈 F ( y k ) , x k − x ^ 〉 = 〈 F ( y k ) , x k − y k + y k − x ^ 〉 ≥ 〈 F ( y k ) , x k − y k 〉 = 〈 F ( x k ) , x k − y k 〉 − 〈 F ( x k ) − F ( y k ) , x k − y k 〉 ≥ 1 α k ‖ x k − y k ‖ 2 − μ α k ‖ x k − y k ‖ 2 ≥ 1 − μ γ ‖ x k − y k ‖ 2 ,

where the second inequality comes from Lemma 3.2(b) and (16), and the last inequality is based on α k ≤ γ .¢

The following theorem gives the global convergence of the algorithm ETA.

Theorem 3.4. Suppose F is co-coercive and S O L ( F ) ≠ 0 . If { x k } and { y k } are infinite columns generated by the algorithm ETA, then

lim k → ∞ ‖ x k − y k ‖ = 0. (18)

Further, { x k } converges to a solution of the problem MCP(a, b, F).

Proof. Let x ^ ∈ S O L ( F ) , by Lemma 3.2(c) and (17), we have

‖ z k + 1 − x ^ ‖ 2 ≤ ‖ ( x k − α k F ( y k ) ) − x ^ ‖ 2 − ‖ z k + 1 − x k + α k F ( y k ) ‖ 2 = ‖ x k − x ^ ‖ 2 − 2 α k F ( y k ) T ( x k − x ^ ) − 2 α k F ( y k ) T ( z k + 1 − x k ) − ‖ x k − z k + 1 ‖ 2 ≤ ‖ x k − x ^ ‖ 2 − 2 α k F ( y k ) T ( z k + 1 − y k ) − ‖ x k − z k + 1 ‖ 2 = ‖ x k − x ^ ‖ 2 − ‖ x k − y k ‖ 2 − ‖ z k + 1 − y k ‖ 2 + 2 ( x k − y k − α k F ( y k ) ) T ( z k + 1 − y k ) (19)

Now consider the last term of Equation (19), by Lemma 3.1 (a), we have

( y k − x k + α k F ( x k ) ) T ( z k + 1 − y k ) ≥ 0

It follows that

2 ( x k − y k − α k F ( y k ) ) T ( z k + 1 − y k ) ≤ 2 ( x k − y k − α k F ( y k ) ) T ( z k + 1 − y k ) + 2 ( y k − x k + α k F ( x k ) ) T ( z k + 1 − y k ) = 2 α k ( F ( x k ) − F ( y k ) ) T ( z k + 1 − y k ) ≤ α k 2 ‖ ( F ( x k ) − F ( y k ) ) ‖ 2 + ‖ z k + 1 − y k ‖ 2 (20)

Replacing (20) into (19), and by (16), we deduce

‖ z k + 1 − x ^ ‖ 2 ≤ ‖ x k − x ^ ‖ 2 − ‖ x k − y k ‖ 2 − ‖ z k + 1 − y k ‖ 2 + α k 2 ‖ ( F ( x k ) − F ( y k ) ) ‖ 2 + ‖ z k + 1 − y k ‖ 2 ≤ ‖ x k − x ^ ‖ 2 − ‖ x k − y k ‖ 2 + μ 2 ‖ x k − y k ‖ 2 = ‖ x k − x ^ ‖ 2 − ( 1 − μ 2 ) ‖ x k − y k ‖ 2 (21)

According to the definition of shrinkage operator (15), we know that

‖ x k + 1 − x ^ ‖ ≤ ‖ z k + 1 − x ^ ‖ .

Hence, { ‖ x k − x ^ ‖ 2 } has contraction properties, which means { x k } is bounded, and

( 1 − μ 2 ) ∑ k = 0 ∞ ‖ x k − y k ‖ 2 ≤ ∑ k = 0 ∞ { ‖ x k − x ^ ‖ 2 − ‖ x k + 1 − x ^ ‖ 2 } < + ∞ ,

so we get (18) holds.

Since { x k } is bounded, the sequence { x k } has at least one cluster point, let x * be a cluster points of { x k } and a subsequence { x k i } converge to x * . Next we will show x * ∈ S O L ( F ) , we consider two cases:

Case 1: assume that there is a positive low bounded α min such that α k i ≥ α min > 0 , then by inequality

min { 1, α } ‖ e ( x ,1 ) ‖ ≤ ‖ e ( x , α ) ‖ ≤ max { 1, α } ‖ e ( x ,1 ) ‖ . (22)

the continuity of e ( x , α ) for x and (18), we get

‖ e ( x * , 1 ) ‖ = lim k i → ∞ ‖ e ( x k i , 1 ) ‖ ≤ lim k i → ∞ ‖ e ( x k i , α k i ) ‖ min { 1 , α k i } ≤ lim k i → ∞ ‖ e ( x k i , α k i ) ‖ min { 1 , α min } = lim k i → ∞ ‖ x k i − y k i ‖ min { 1 , α min } = 0.

Case 2: assume α k i → 0 , for enough large k i , by the Lemma 3.2 (a) and the Arimijo search (16), we get

μ ‖ e ( x k i , 1 ) ‖ ≤ μ ‖ e ( x k i , 1 l α k i ) ‖ 1 l α k i < ‖ F ( x k i ) − F ( x k i ( 1 l α k i ) ) ‖ .

Hence, we have

‖ e ( x * , 1 ) ‖ = lim k i → ∞ ‖ e ( x k i , 1 ) ‖ ≤ lim k i → ∞ ‖ F ( x k i ) − F ( x k i ( 1 l α k i ) ) ‖ = 0. (23)

In summary, we can get x * ∈ S O L ( F ) . Replacing this formula into (21), we have

‖ x k + 1 − x * ‖ 2 ≤ ‖ z k + 1 − x * ‖ 2 ≤ ‖ x k − x * ‖ 2 − ( 1 − μ 2 ) ‖ x k − y k ‖ 2 .

Hence we get { x k } converges to the solution x * . The proof is thus complete. ¢

In this section, we present some numerical experiments to demonstrate the effectiveness of our ETA algorithm, and show the algorithm can obtain the sparse solution of the MCP (a, b, F).

We will stimulate three examples to implement the ETA algorithm. They will be ran 100 times for difference dimensions, and thus average results will be recorded. In each experiment, we set z 0 = e , γ = 2 c , l = 0.1 , μ = 1 / c , n max = 2000 and other related parameters will be given in the following test example.

The test is associated with the Z-matrix which has an important property, that is, there is a unique sparse solution of LCPs when M is a kind of Z-matrix. Let us consider LCP(q, M) where

M = I n − 1 n e e T = ( 1 − 1 n − 1 n ⋯ − 1 n − 1 n 1 − 1 n ⋯ − 1 n ⋮ ⋮ ⋱ ⋮ − 1 n − 1 n ⋯ 1 − 1 n )

and q = ( 1 n − 1, 1 n , ⋯ , 1 n ) T , here I n is the identity matrix of order n and e = ( 1,1, ⋯ ,1 ) T ∈ R n . Such a matrix M is widely used in statistics. It is clear that M is a positive semidefinite Z-matrix. For any scalar α ≥ 0 , we know that vector x = α e + e 1 is a solution to LCP(q, M), since it satisfies

x ≥ 0 , M x + q = M e 1 + q = 0 , x T ( M x + q ) = 0.

Among all the solution, the vector x ^ = e 1 = ( 1 , 0 , ⋯ , 0 ) T is the unique sparse solution.

We choose z 0 = e , c = 1 , λ 0 = 0.2 , γ = 2 c , τ = 0.75 , l = 0.1 , μ = 1 / c , ϵ = 1 e − 6 , n max = 2000 , K 0 = 5 . We will take advantage of the recovery error ‖ x − x ^ ‖ to evaluate our algorithm. Apart from that, the average cpu time (in seconds), the average number of iteration times and residual ‖ x − z ‖ will also be taken into consideration on judging the performance of the method.

As indicated in

In this subsection, we test ETA for randomly created LCPs with positive semidefinite matrices. First, we state the way of constructing LCPs and their solution. Let a matrix Z ∈ R n × r ( r < n ) be generated with the standard normal distribution and M = Z Z T . Let the sparse vector x ^ be produced by choosing randomly the s = 0.01 ∗ n nonzero components whose values are also randomly generated from a standard normal distribution. After the matrix M and the sparse vector x ^ have been generated, a vector q ∈ R n can be constructed such that x ^ is a solution of the LCP (q, M). Then x ^ can be regarded as a sparse solution of the LCP (q, M). Namely,

x ^ ≥ 0, M x ^ + q ≥ 0, x ^ T ( M x ^ + q ) = 0, and ‖ x ^ ‖ 0 = 0.01 ∗ n .

To be more specific, if x ^ i > 0 then choose q i = − ( M x ^ ) i , if x ^ i = 0 then

n | Iter | ‖ x − x ^ ‖ | ‖ x − z ‖ | ‖ x ^ ‖ 0 | ‖ x ‖ 0 | Time(sec.) |
---|---|---|---|---|---|---|

3000 | 205 | 7.7007E−06 | 7.5424E−07 | 1 | 1 | 2.89 |

5000 | 205 | 7.6995E−06 | 7.5424E−07 | 1 | 1 | 7.92 |

10,000 | 205 | 7.6986E−06 | 7.5424E−07 | 1 | 1 | 36.68 |

15,000 | 205 | 7.6983E−06 | 7.5424E−07 | 1 | 1 | 78.40 |

20,000 | 205 | 7.6981E−06 | 7.5424E−07 | 1 | 1 | 148.45 |

25,000 | 205 | 7.6980E−06 | 7.5424E−07 | 1 | 1 | 232.82 |

choose q i = | ( M x ^ ) i | − ( M x ^ ) i . Let M and q be the input to our ETA algorithm and take z 0 = e , c = max ( s v d ( M ) ) , λ 0 = 0.2 , γ = 2 c , τ = 0.75 , l = 0.1 , μ = 1 / c , ϵ = 1 e − 10 , n max = 2000 , K 0 = max ( 2 , ⌊ 10000 / n ⌋ ) , here ⌊ 10000 / n ⌋ denotes the largest integer less than 10,000/n. Then ETA will output a solution x. Similarly, the average number of iteration times, average cpu time (in seconds), and the residual ‖ x − z ‖ will also be taken into consideration on valuating our ETA algorithm.

As manifested in

We now consider a co-coercive mixed complementarity problem (MCP) with

F ( x ) = D ( x ) + M x + q (24)

where D ( x ) and M x + q are the nonlinear part and the linear part of F ( x ) , generate a linear part of M x + q in a way similar to [

x ^ ∈ Ω , ( y − x ^ ) T F ( x ^ ) ≥ 0 , ∀ y ∈ Ω , and ‖ x ^ ‖ 0 = 0.01 ∗ n .

is similar to the procedure of Section 4.2. Let M and q be the input to our ETA algorithm and take z 0 = e , c = 150 ∗ log ( n ) , λ 0 = 0.2 , γ = 2 c , τ = 0.75 , l = 0.1 , μ = 1 / c , ϵ = 1 e − 6 , n max = 2000 , K 0 = max ( 2 , 10000 / n ) , and d = − r a n d ( n ,1 ) . Then ETA will output a solution x. Similariy, the average number of iteration times, the average residual ‖ x − z ‖ , the average sparsity ‖ x ‖ 0 of x, and the average cpu time (in seconds) will also be taken into consideration on valuation our ETA algorithm.

It is not difficult to see from

n | Iter | ‖ x − z ‖ | ‖ x ^ ‖ 0 | ‖ x ‖ 0 | Time (sec.) |
---|---|---|---|---|---|

2000 | 350 | 8.0136E−11 | 20 | 20 | 18.05 |

3000 | 210 | 9.8366E−11 | 30 | 30 | 11.86 |

4000 | 142 | 8.5188E−11 | 40 | 40 | 28.65 |

5000 | 142 | 9.5243E−11 | 50 | 50 | 20.47 |

7000 | 144 | 8.4519E−11 | 70 | 70 | 43.67 |

n | Iter | ‖ x − z ‖ | ‖ x ^ ‖ 0 | ‖ x ‖ 0 | Time (sec.) |
---|---|---|---|---|---|

1000 | 468 | 8.5467E−07 | 10 | 10 | 2.64 |

3000 | 159 | 7.8034E−07 | 30 | 30 | 16.84 |

5000 | 105 | 9.4924E−07 | 50 | 50 | 37.59 |

7000 | 103 | 7.4224E−07 | 70 | 70 | 73.59 |

10,000 | 101 | 9.5524E−07 | 100 | 100 | 148.94 |

In this paper, we concentrate on finding sparse solution for co-coervice mixed complementarity problems (MCPs). An l 1 regularized projection minimization model is proposed for relaxation, and an extragradient thresholding algorithm (ETA) is then designed for this regularized model. Furthermore, we analyze the convergence of this algorithm and show any cluster point of the sequence generated by ETA is a sparse solution of MCP. Preliminary numerical results indicate that the l 1 regularized model as well as the ETA is promising to find the spare solution of MCPs.

Since data in the Network Vector Autoregression (NAR) is not public, we have not done empirical analysis.

This paper is supported by the Top Disciplines of Shanghai.

The authors declare no conflicts of interest regarding the publication of this paper.

Zhang, P. and Yu, Z.S. (2020) Sparse Solutions of Mixed Complementarity Problems. Journal of Applied Mathematics and Physics, 8, 10-22. https://doi.org/10.4236/jamp.2020.81002