Sparse Solutions of Mixed Complementarity Problems

Peng Zhang, Zhensheng Yu

College of Science, University of Shanghai for Science and Technology, Shanghai, China.

DOI: 10.4236/jamp.2020.81002                

Abstract

In this paper, we consider an extragradient thresholding algorithm for finding the sparse solution of mixed complementarity problems (MCPs). We establish a relaxation l₁ 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₁ regularized projection minimization model and obtain the sparse solution of the mixed complementarity problem.

Keywords

Mixed Complementarity Problem, Sparse Solution, l₁ Regularized Projection Minimization Model, Extragradient Thresholding Algorithm

1. Introduction

Define a continuously differentiable function $F\mathrm{<mo>\; :\; </mo>}{R}^n\to R^n$, and a nonempty set

$\Omega \mathrm{<mo>\; :\; </mo>}=\left\{x\in R^n\mathrm{<mo>\; |\; </mo>}a\le x\le b\right\}\mathrm{,}$

where $a={\left\{R\cup \left\{-\infty \right\}\right\}}^n,b={\left\{R\cup \left\{+\infty \right\}\right\}}^n$ and $a<b\left(a_i<b_i,i=1,2,\cdots ,n\right)$. The mixed complementarity problem is to find a vector $x\in \Omega$, such that

${\left(y-x\right)}^{\text{T}}F\left(x\right)\ge \mathrm{0,\; <mi>\; </mi>}\forall y\in \Omega \mathrm{.}$ (1)

The mixed complementarity problem, also known as box constrained variational inequality problem, denoted by MCP (a, b, F). In particular, if $\Omega :=R_{+}^n$, the mixed complementarity problem becomes a nonlinear complementarity problem (NCP), is to find a vertor $x\ge 0$, such that

$F\left(x\right)\ge 0,F{\left(x\right)}^{\text{T}}x=0.$

Moreover, if $F\left(x\right)\mathrm{<mo>\; :\; </mo>}=Mx+q$, where $M\in R^{n\times n}\mathrm{,}q\in R^n$, the nonlinear complementary problem reduces a linear complementary problem (LCP):

$x\ge \mathrm{0,}Mx+q\ge \mathrm{0,}{\left(Mx+q\right)}^{\text{T}}x=0.$

The set of solution to the mixed complementarity problem is denoted by SOL (F), throughout this paper, we assume $SOL\left(F\right)\ne \varnothing$.

The MCP has wide applications in fields of science and engineering [1] [2], and many results on its theories and algorithms have been developed (see e.g. [3] [4] [5] [6] ).

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 [7], and there are many articles available for sloving the sparse solutions of systems of linear equations [8] - [13] as well as the optimization problems [14] [15] [16].

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 [17], by using the concept of minimum $p\left(0<p<1\right)$ norm solution, they studied the characteristics and calculations of sparse solutions and minimum p-norm solutions for linear complementarity problems. Recently, some solution methods had been proposed for LCP and NCP, for examples, shrinkage-thresholding projection method [18], half thresholding projection algorithm [19] and extragradient thresholding method [20].

Along with the research of [17] [18] [19] [20], in this paper, we aim to design an extragradient thresholding Algorithm for the sparse solution of MCP, and which can be seen as an extension of the sparse solution algorithm for NCP.

Due to the relationship between MCP and the variational inequality, we aim to seek a vector $x\in \Omega$ by solving the solution of $l_0$ norm minimization problem:

$\begin{array}{l}\min {\Vert x\Vert }_0\mathrm{,}\\ \text{s}\text{.t}\text{.}{\left(y-x\right)}^{\text{T}}F\left(x\right)\ge \mathrm{0,}\end{array}$ (2)

for any $y\in \Omega$, where ${\Vert x\Vert }_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 [21]. Motivated by this outstanding work, we consider applying $l_1$ norm minimization to find the sparse solution of MCP, and we obtain the following minimization problem to approximate problem (2):

$\begin{array}{l}\underset{x\in \Omega }{\min }{\Vert x\Vert }_1\mathrm{,}\\ \text{s}\text{.t}\text{.}{\left(y-x\right)}^{\text{T}}F\left(x\right)\ge 0\end{array}$ (3)

for any $y\in \Omega$ and where ${\Vert x\Vert }_1={\displaystyle \underset{i=1}{\overset{n}{\sum }}}\left|x_i\right|$.

Given a vector $x\in \Omega$, let $P_{\Omega }\left(x\right)$ be the projection of x on $\Omega$, for convenience, we write $P_{\Omega }\left(x\right)={\left[x\right]}_{\Omega }$, it is well known (see, e.g., [22] ) that $x^{\mathrm{<mo>\; *\; </mo>}}$ is a solution point of problem (1) if and only if it satisfies the following projection equation:

$W\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\mathrm{<mo>\; :\; </mo>}=x^{\mathrm{<mo>\; *\; </mo>}}-{\left[x^{\mathrm{<mo>\; *\; </mo>}}-F\left(x^{\mathrm{<mo>\; *\; </mo>}}\right)\right]}_{\Omega }=\mathrm{0,}$ (4)

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

$\begin{array}{l}\underset{x\mathrm{,}z\in R^n}{\min }f\left(x\right)\mathrm{<mo>\; :\; </mo>}={\Vert x\Vert }_1\\ \text{s}\text{.t}\text{.}x={\left[x-F\left(x\right)\right]}_{\Omega }\mathrm{.}\end{array}$ (5)

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

$\begin{array}{l}\underset{x\mathrm{,}z\in R^n}{\min }{f}_{\lambda }\left(x\mathrm{,}z\right)\mathrm{<mo>\; :\; </mo>}={\Vert x-z\Vert }^2+\lambda {\Vert x\Vert }_1\\ \text{s}\text{.t}\text{.}z={\left[x-F\left(x\right)\right]}_{\Omega }\mathrm{.}\end{array}$ (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.

2. The l₁ Regularized Approximation

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 $\lambda >0$, the solution set of (6) is nonempty and bounded. Let $\left\{\left(x_{{\lambda }_k}\mathrm{,}{z}_{{\lambda }_k}\right)\right\}$ be a solution of (6), and $\left\{{\lambda }_k\right\}$ be any positive sequence converging to 0. If $SOL\left(F\right)\ne \varnothing$, then $\left\{\left(x_{{\lambda }_k}\mathrm{,}{z}_{{\lambda }_k}\right)\right\}$ has at least one accumulation point, and any accumulation point $x^{\ast }$ of $\left\{x_{{\lambda }_k}\right\}$ is a solution of (1.3).

Proof. For any fixed $\lambda >0$, since

$f_{\lambda }\left(x\mathrm{,}z\right)\to +\infty \text{as}\Vert \left(x\mathrm{,}z\right)\Vert \to \infty \mathrm{,}$ (7)

which means $f_{\lambda }\left(x\mathrm{,}z\right)$ is coercivity. On the other hand, it is clear that for any $x\in R^n$ and $z\in R^n$, $f_{\lambda }\left(x\mathrm{,}z\right)\ge 0$. This together with (7) implies the level set

$L=\left\{\left(x,z\right)\in R^n\times R^n|f_{\lambda }\left(x,z\right)\le f_{\lambda }\left(x_0,z_0\right)\mathrm{<mi>\; </mi>}\text{and}\mathrm{<mi>\; </mi>}z={\left[x-F\left(x\right)\right]}_{\Omega }\right\}$

is nonempty and compact, where $x_0\in R^n$ and $z_0={\left[x_0-F\left(x_0\right)\right]}_{\Omega }$ are given points, which deduces that the solution set of problem (6) is nonempty and bounded since $f_{\lambda }\left(x\mathrm{,}z\right)$ is continuous on L.

Now we consider the proof of the second part of this theorem. Let $\hat{x}\in SOL\left(F\right)$ and $\hat{z}={\left[\hat{x}-F\left(\hat{x}\right)\right]}_{\Omega }$. from (5), we have $\hat{x}=\hat{z}$. Since $\left(x_{{\lambda }_k}\mathrm{,}{z}_{{\lambda }_k}\right)$ is a solution of (6) with $\lambda ={\lambda }_k$, where $z_{{\lambda }_k}={\left[x_{{\lambda }_k}-F\left(x_{{\lambda }_k}\right)\right]}_{\Omega }$, it follows that

$\begin{array}{c}\max \left\{{\Vert x_{{\lambda }_k}-z_{{\lambda }_k}\Vert }^2\mathrm{,}{\lambda }_k{\Vert x_{{\lambda }_k}\Vert }_1\right\}\le {\Vert x_{{\lambda }_k}-z_{{\lambda }_k}\Vert }^2+{\lambda }_k{\Vert x_{{\lambda }_k}\Vert }_1\\ \le {\Vert \hat{x}-\hat{z}\Vert }^2+{\lambda }_k{\Vert \hat{x}\Vert }_1\\ ={\lambda }_k{\Vert \hat{x}\Vert }_1.\end{array}$ (8)

This implies that for any ${\lambda }_k>0$,

${\Vert x_{{\lambda }_k}\Vert }_1\le {\Vert \hat{x}\Vert }_1\mathrm{.}$ (9)

Hence the sequence $\left\{x_{{\lambda }_k}\right\}$ is bounded and has at least one cluster point and so is $\left\{z_{{\lambda }_k}\right\}$ due to ${\Vert x_{{\lambda }_k}-z_{{\lambda }_k}\Vert }^2\le {\lambda }_k{\Vert \hat{x}\Vert }_1$.

Let $x^{\ast }$ and $z^{\ast }$ be any cluster points of $\left\{x_{{\lambda }_k}\right\}$ and $\left\{z_{{\lambda }_k}\right\}$, respectively, and $z_{{\lambda }_k}={\left[x_{{\lambda }_k}-F\left(x_{{\lambda }_k}\right)\right]}_{\Omega }$. Then there exists a subsequence of $\left\{{\lambda }_k\right\}$, say $\left\{{\lambda }_{k_j}\right\}$, such that

$\underset{k_j\to \infty }{\lim }{x}_{{\lambda }_{k_j}}=x^{\ast }\text{and}\underset{k_j\to \infty }{\lim }{z}_{{\lambda }_{k_j}}=z^{\ast }.$

We can obtain $z^{\ast }={\left[x^{\ast }-F\left(x^{\ast }\right)\right]}_{\Omega }$ by letting $k_j\to \infty$ in $z_{{\lambda }_k}={\left[x_{{\lambda }_k}-F\left(x_{{\lambda }_k}\right)\right]}_{\Omega }$. Letting ${\lambda }_{k_j}\to 0$, in

${\Vert x_{{\lambda }_{k_j}}-z_{{\lambda }_{k_j}}\Vert }^2\le {\lambda }_{k_j}{\Vert \hat{x}\Vert }_1$

yields $x^{\ast }=z^{\ast }$. Consequently, $x^{\ast }={\left[x^{\ast }-F\left(x^{\ast }\right)\right]}_{\Omega }$, which implies $x^{\ast }\in SOL\left(F\right)$. Let $k_j$ tend to $\infty$ in (9), we get ${\Vert x^{\ast }\Vert }_1\le {\Vert \hat{x}\Vert }_1$. Then by the arbitrariness of $\hat{x}\in SOL\left(F\right)$, we know $x^{\ast }$ is solution of problem (3). This completes the proof. ¢

3. Algorithm and Convergence

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 [23].

Lemma 3.1. Let $P_K(\cdot )$ 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\in R^n$,

${\left(y-P_K\left[y\right]\right)}^{\text{T}}\left(P_K\left[y\right]-x\right)\ge \mathrm{0,}\forall x\in K\mathrm{<mo>\; ;\; </mo>}$ (10)

(b) for any $y\mathrm{,}z\in R^n$,

${\Vert P_K\left[y\right]-P_K\left[z\right]\Vert }^2\le {\left(y-z\right)}^{\text{T}}\left(P_K\left[y\right]-P_K\left[z\right]\right)\mathrm{.}$ (11)

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

Lemma 3.2. Define a residue funtion

$H\left(\alpha \right):=P_K\left[x-\alpha d\right],\alpha \ge 0,d\in R^n.$ (12)

Then the following statements are valid.

(a) For any $\alpha \ge 0$, $\frac{\Vert x-H\left(\alpha \right)\Vert }{\alpha }$ is non-increasing;

(b) $\forall \alpha >0$, $d^{\text{T}}\left(x-H\left(\alpha \right)\right)\ge \frac{{\Vert x-H\left(\alpha \right)\Vert }^2}{\alpha }$ ;

(c) $\forall z\in R^n$, ${\Vert P_K\left[z\right]-x\Vert }^2\le {\Vert z-x\Vert }^2-{\Vert P_K\left[z\right]-z\Vert }^2$.

In this paper, we suppose the mapping $F\mathrm{<mo>\; :\; </mo>}{R}^n\to R^n$ is co-coercive on the set $\Omega$, i.e., there exists a constant $c>0$ such that

$\langle F\left(x\right)-F\left(y\right)\mathrm{,}x-y\rangle \ge c{\Vert F\left(x\right)-F\left(y\right)\Vert }^2\mathrm{,}\forall x\mathrm{,}y\in \Omega \mathrm{.}$

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

$\langle F\left(x\right)-F\left(y\right)\mathrm{,}x-y\rangle \ge \mathrm{0,}\forall x\mathrm{,}y\in \Omega \mathrm{.}$

For a given $z^k\in \Omega$ and ${\lambda }_k>0$, we consider an unconstrained minimization subproblem:

$\underset{x\in R^n}{\min }{f}_{{\lambda }_k}\left(x\mathrm{,}{z}^k\right)\mathrm{<mo>\; :\; </mo>}={\Vert x-z^k\Vert }^2+{\lambda }_k{\Vert x\Vert }_1\mathrm{.}$ (13)

Evidently, the minimizer $x^{\mathrm{<mo>\; *\; </mo>}}$ of the model (13) satisfies the corresponding optimality condition

$x^{*}=S_{{\lambda }_k}\left(z^k\right),$ (14)

where the shrinkage operator $S_{\lambda }$ is defined by (see, e.g., [18] )

${\left(S_{\lambda }\left(z\right)\right)}_i=(\begin{array}{ll}{z}_i-\frac{\lambda }{2}\mathrm{,}\hfill & z_i\ge \frac{\lambda }{2}\mathrm{<mo>\; ;\; </mo>}\hfill \\ \mathrm{0,}\hfill & -\frac{\lambda }{2}\le z_i\le \frac{\lambda }{2}\mathrm{<mo>\; ;\; </mo>}\hfill \\ z_i+\frac{\lambda }{2}\mathrm{,}\hfill & z_i\le -\frac{\lambda }{2}\mathrm{.}\hfill \end{array}$ (15)

It demonstrates that a solution $x\in 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\ne z^0\in \Omega ,{\lambda }_0,\gamma >0,\tau ,l,\mu \in \left(0,1\right),ϵ>0$ and a positive integers $n_{\max }>K_0>0$, set $k=0$.

Step 1: Compute $x^k=S_{{\lambda }_k}\left(z^k\right),y^k={\left[x^k-{\alpha }_{k}F\left(x^k\right)\right]}_{\Omega }$, where ${\alpha }_k=\gamma l^{m_k}$ with $m_k$ being the smallest nonnegative integer satisfying

$\Vert F\left(x^k\right)-F\left(y^k\right)\Vert \le \mu \frac{\Vert x^k-y^k\Vert }{{\alpha }_k}\mathrm{.}$ (16)

Step 2: If $\Vert x^k-z^k\Vert \le ϵ$ or the number of iterations is greater than $n_{\max }$, then return $z^k\mathrm{,}{x}^k\mathrm{,}{y}^k$ and stop. Otherwise, compute

$z^{k+1}={\left[x^k-{\alpha }_{k}F\left(y^k\right)\right]}_{\Omega },$

and update ${\lambda }_{k+1}$ by

${\lambda }_{k+1}=(\begin{array}{ll}\tau {\lambda }_k,\hfill & \text{if}k+1\text{is}\text{a}\text{multiple}\text{of}{K}_0,\hfill \\ {\lambda }_k,\hfill & \text{otherwise}.\hfill \end{array}$

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

Define

$x\left(\alpha \right)={\left[x-\alpha F\left(x\right)\right]}_{\Omega }\mathrm{,}\alpha \ge 0$

and

$e\left(x,a\right)=x-x\left(\alpha \right),r\left(x,\alpha \right)=\Vert e\left(x,\alpha \right)\Vert$

It is easy to see that $x^k$ is a solution for MCP if and only if $e\left(x^k,\alpha \right)=0,\forall \alpha >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 $SOL\left(F\right)\ne \varnothing$. If $x^k$ generated by ETA is not a solution of $MCP\left(F\right)$, then for any $\hat{x}\in SOL\left(F\right)$, we have

$\langle F\left(y^k\right)\mathrm{,}{x}^k-\hat{x}\rangle \ge \langle F\left(y^k\right)\mathrm{,}{x}^k-y^k\rangle \ge \left(1-\mu \right)\frac{{\Vert x^k-y^k\Vert }^2}{\gamma }\mathrm{.}$ (17)

Proof. Since $\hat{x}\in SOL\left(F\right)$ and $y^k\in \Omega$, it follows that $\langle F\left(\hat{x}\right)\mathrm{,}{y}^k-\hat{x}\rangle \ge 0$. By the co-coercive of mapping F, we have $\langle F\left(y^k\right)\mathrm{,}{y}^k-\hat{x}\rangle \ge 0$. Hence

$\begin{array}{c}\langle F\left(y^k\right)\mathrm{,}{x}^k-\hat{x}\rangle =\langle F\left(y^k\right),x^k-y^k+y^k-\hat{x}\rangle \\ \ge \langle F\left(y^k\right),x^k-y^k\rangle \\ =\langle F\left(x^k\right),x^k-y^k\rangle -\langle F\left(x^k\right)-F\left(y^k\right),x^k-y^k\rangle \\ \ge \frac{1}{{\alpha }_k}{\Vert x^k-y^k\Vert }^2-\frac{\mu }{{\alpha }_k}{\Vert x^k-y^k\Vert }^2\\ \ge \frac{1-\mu }{\gamma }{\Vert x^k-y^k\Vert }^2,\end{array}$

where the second inequality comes from Lemma 3.2(b) and (16), and the last inequality is based on ${\alpha }_k\le \gamma$.¢

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

Theorem 3.4. Suppose F is co-coercive and $SOL\left(F\right)\ne 0$. If $\left\{x^k\right\}$ and $\left\{y^k\right\}$ are infinite columns generated by the algorithm ETA, then

$\underset{k\to \infty }{\lim }\Vert x^k-y^k\Vert =0.$ (18)

Further, $\left\{x^k\right\}$ converges to a solution of the problem MCP(a, b, F).

Proof. Let $\hat{x}\in SOL\left(F\right)$, by Lemma 3.2(c) and (17), we have

$\begin{array}{l}{\Vert z^{k+1}-\hat{x}\Vert }^2\\ \le {\Vert \left(x^k-{\alpha }_{k}F\left(y^k\right)\right)-\hat{x}\Vert }^2-{\Vert z^{k+1}-x^k+{\alpha }_{k}F\left(y^k\right)\Vert }^2\\ ={\Vert x^k-\hat{x}\Vert }^2-2{\alpha }_{k}F{\left(y^k\right)}^{\text{T}}\left(x^k-\hat{x}\right)-2{\alpha }_{k}F{\left(y^k\right)}^{\text{T}}\left(z^{k+1}-x^k\right)-{\Vert x^k-z^{k+1}\Vert }^2\\ \le {\Vert x^k-\hat{x}\Vert }^2-2{\alpha }_{k}F{\left(y^k\right)}^{\text{T}}\left(z^{k+1}-y^k\right)-{\Vert x^k-z^{k+1}\Vert }^2\\ ={\Vert x^k-\hat{x}\Vert }^2-{\Vert x^k-y^k\Vert }^2-{\Vert z^{k+1}-y^k\Vert }^2+2{\left(x^k-y^k-{\alpha }_{k}F\left(y^k\right)\right)}^{\text{T}}\left(z^{k+1}-y^k\right)\end{array}$ (19)

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

${\left(y^k-x^k+{\alpha }_{k}F\left(x^k\right)\right)}^{\text{T}}\left(z^{k+1}-y^k\right)\ge 0$

It follows that

$\begin{array}{l}2{\left(x^k-y^k-{\alpha }_{k}F\left(y^k\right)\right)}^{\text{T}}\left(z^{k+1}-y^k\right)\\ \le 2{\left(x^k-y^k-{\alpha }_{k}F\left(y^k\right)\right)}^{\text{T}}\left(z^{k+1}-y^k\right)+2{\left(y^k-x^k+{\alpha }_{k}F\left(x^k\right)\right)}^{\text{T}}\left(z^{k+1}-y^k\right)\\ =2{\alpha }_k{\left(F\left(x^k\right)-F\left(y^k\right)\right)}^{\text{T}}\left(z^{k+1}-y^k\right)\\ \le {\alpha }_k^2{\Vert \left(F\left(x^k\right)-F\left(y^k\right)\right)\Vert }^2+{\Vert z^{k+1}-y^k\Vert }^2\end{array}$ (20)

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

$\begin{array}{c}{\Vert z^{k+1}-\hat{x}\Vert }^2\le {\Vert x^k-\hat{x}\Vert }^2-{\Vert x^k-y^k\Vert }^2-{\Vert z^{k+1}-y^k\Vert }^2\\ +{\alpha }_k^2{\Vert \left(F\left(x^k\right)-F\left(y^k\right)\right)\Vert }^2+{\Vert z^{k+1}-y^k\Vert }^2\\ \le {\Vert x^k-\hat{x}\Vert }^2-{\Vert x^k-y^k\Vert }^2+{\mu }^2{\Vert x^k-y^k\Vert }^2\\ ={\Vert x^k-\hat{x}\Vert }^2-\left(1-{\mu }^2\right){\Vert x^k-y^k\Vert }^2\end{array}$ (21)

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

$\Vert x^{k+1}-\hat{x}\Vert \le \Vert z^{k+1}-\hat{x}\Vert \mathrm{.}$

Hence, $\left\{{\Vert x^k-\hat{x}\Vert }^2\right\}$ has contraction properties, which means $\left\{x^k\right\}$ is bounded, and

$\left(1-{\mu }^2\right){\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\Vert x^k-y^k\Vert }^2\le {\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}\left\{{\Vert x^k-\hat{x}\Vert }^2-{\Vert x^{k+1}-\hat{x}\Vert }^2\right\}<+\infty ,$

so we get (18) holds.

Since $\left\{x^k\right\}$ is bounded, the sequence $\left\{x^k\right\}$ has at least one cluster point, let $x^{\mathrm{<mo>\; *\; </mo>}}$ be a cluster points of $\left\{x^k\right\}$ and a subsequence $\left\{x^{k_i}\right\}$ converge to $x^{\mathrm{<mo>\; *\; </mo>}}$. Next we will show $x^{\mathrm{<mo>\; *\; </mo>}}\in SOL\left(F\right)$, we consider two cases:

Case 1: assume that there is a positive low bounded ${\alpha }_{\min }$ such that ${\alpha }_{k_i}\ge {\alpha }_{\min }>0$, then by inequality

$\min \left\{\mathrm{1,}\alpha \right\}\Vert e\left(x\mathrm{,1}\right)\Vert \le \Vert e\left(x\mathrm{,}\alpha \right)\Vert \le \max \left\{\mathrm{1,}\alpha \right\}\Vert e\left(x\mathrm{,1}\right)\Vert \mathrm{.}$ (22)

the continuity of $e\left(x\mathrm{,}\alpha \right)$ for x and (18), we get

$\begin{array}{c}\Vert e\left(x^{*},1\right)\Vert =\underset{k_i\to \infty }{\lim }\Vert e\left(x^{k_i},1\right)\Vert \le \underset{k_i\to \infty }{\lim }\frac{\Vert e\left(x^{k_i},{\alpha }_{k_i}\right)\Vert }{\min \left\{1,{\alpha }_{k_i}\right\}}\\ \le \underset{k_i\to \infty }{\lim }\frac{\Vert e\left(x^{k_i},{\alpha }_{k_i}\right)\Vert }{\min \left\{1,{\alpha }_{\min }\right\}}=\underset{k_i\to \infty }{\lim }\frac{\Vert x^{k_i}-y^{k_i}\Vert }{\min \left\{1,{\alpha }_{\min }\right\}}=0.\end{array}$

Case 2: assume ${\alpha }_{k_i}\to 0$, for enough large $k_i$, by the Lemma 3.2 (a) and the Arimijo search (16), we get

$\mu \Vert e\left(x^{k_i},1\right)\Vert \le \mu \frac{\Vert e\left(x^{k_i},\frac{1}{l}{\alpha }_{k_i}\right)\Vert }{\frac{1}{l}{\alpha }_{k_i}}<\Vert F\left(x^{k_i}\right)-F\left(x^{k_i}\left(\frac{1}{l}{\alpha }_{k_i}\right)\right)\Vert .$

Hence, we have

$\Vert e\left(x^{*},1\right)\Vert =\underset{k_i\to \infty }{\lim }\Vert e\left(x^{k_i},1\right)\Vert \le \underset{k_i\to \infty }{\lim }\Vert F\left(x^{k_i}\right)-F\left(x^{k_i}\left(\frac{1}{l}{\alpha }_{k_i}\right)\right)\Vert =0.$ (23)

In summary, we can get $x^{\mathrm{<mo>\; *\; </mo>}}\in SOL\left(F\right)$. Replacing this formula into (21), we have

${\Vert x^{k+1}-x^{\mathrm{<mo>\; *\; </mo>}}\Vert }^2\le {\Vert z^{k+1}-x^{\mathrm{<mo>\; *\; </mo>}}\Vert }^2\le {\Vert x^k-x^{\mathrm{<mo>\; *\; </mo>}}\Vert }^2-\left(1-{\mu }^2\right){\Vert x^k-y^k\Vert }^2\mathrm{.}$

Hence we get $\left\{x^k\right\}$ converges to the solution $x^{\mathrm{<mo>\; *\; </mo>}}$. The proof is thus complete. ¢

4. Numerical Experiments

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$, $\gamma =2c$, $l=0.1$, $\mu =1/c$, $n_{\max }=2000$ and other related parameters will be given in the following test example.

4.1. Test for LCPs with Z-Matrix [18]

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-\frac{1}{n}e{e}^{\text{T}}=\left(\begin{array}{cccc}1-\frac{1}{n}& -\frac{1}{n}& \cdots & -\frac{1}{n}\\ -\frac{1}{n}& 1-\frac{1}{n}& \cdots & -\frac{1}{n}\\ ⋮& ⋮& \ddots & ⋮\\ -\frac{1}{n}& -\frac{1}{n}& \cdots & 1-\frac{1}{n}\end{array}\right)$

and $q={\left(\frac{1}{n}-\mathrm{1,}\frac{1}{n}\mathrm{,}\cdots \mathrm{,}\frac{1}{n}\right)}^{\text{T}}$, here $I_n$ is the identity matrix of order n and $e={\left(\mathrm{1,1,}\cdots \mathrm{,1}\right)}^{\text{T}}\in 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 $\alpha \ge 0$, we know that vector $x=\alpha e+e_1$ is a solution to LCP(q, M), since it satisfies

$x\ge 0,Mx+q=M{e}_1+q=0,x^{\text{T}}\left(Mx+q\right)=0.$

Among all the solution, the vector $\hat{x}=e_1={\left(1,0,\cdots ,0\right)}^{\text{T}}$ is the unique sparse solution.

We choose $z^0=e$, $c=1$, ${\lambda }_0=0.2$, $\gamma =2c$, $\tau =0.75$, $l=0.1$, $\mu =1/c$, $ϵ=1e-6$, $n_{\max }=2000$, $K_0=5$. We will take advantage of the recovery error $\Vert x-\hat{x}\Vert$ to evaluate our algorithm. Apart from that, the average cpu time (in seconds), the average number of iteration times and residual $\Vert x-z\Vert$ will also be taken into consideration on judging the performance of the method.

As indicated in Table 1, the ETA algorithm behaves very robust because the average number of times of iteration is identically equal to 205, the recovered error $\Vert x-\hat{x}\Vert$ and residual $\Vert x-z\Vert$ are basically similar. In addition, the sparsity ${\Vert x\Vert }_0$ of the recovered solution x is in all cases equivalents to 1, which means the recover is successful.

4.2. Text for LCPs with Positive Semidefinite Matrices

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\in R^{n\times r}\left(r<n\right)$ be generated with the standard normal distribution and $M=Z{Z}^{\text{T}}$. Let the sparse vector $\hat{x}$ be produced by choosing randomly the $s=0.01\ast n$ nonzero components whose values are also randomly generated from a standard normal distribution. After the matrix M and the sparse vector $\hat{x}$ have been generated, a vector $q\in R^n$ can be constructed such that $\hat{x}$ is a solution of the LCP (q, M). Then $\hat{x}$ can be regarded as a sparse solution of the LCP (q, M). Namely,

$\hat{x}\ge \mathrm{0,}M\hat{x}+q\ge \mathrm{0,}{\hat{x}}^{\text{T}}\left(M\hat{x}+q\right)=\mathrm{0,}\text{and}{\Vert \hat{x}\Vert }_0=0.01\ast n\mathrm{.}$

To be more specific, if ${\hat{x}}_i>0$ then choose $q_i=-{\left(M\hat{x}\right)}_i$, if ${\hat{x}}_i=0$ then

Table 1. ETA’s computational results on LCPs with Z-matrices.

choose $q_i=\left|{\left(M\hat{x}\right)}_i\right|-{\left(M\hat{x}\right)}_i$. Let M and q be the input to our ETA algorithm and take $z^0=e$, $c=\max \left(svd\left(M\right)\right)$, ${\lambda }_0=0.2$, $\gamma =2c$, $\tau =0.75$, $l=0.1$, $\mu =1/c$, $ϵ=1e-10$, $n_{\max }=2000$, $K_0=\max \left(2,\lfloor 10000/n\rfloor \right)$, here $\lfloor 10000/n\rfloor$ 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 $\Vert x-z\Vert$ will also be taken into consideration on valuating our ETA algorithm.

As manifested in Table 2, the ETA algorithm performs quite efficiently. Furthermore, the sparsity ${\Vert x\Vert }_0$ of recovered solution x is in all cases equal to the sparsity ${\Vert \hat{x}\Vert }_0$, which means the recover is exact.

4.3. Test for Co-Coercive Mixed Complementarity Problem

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

$F\left(x\right)=D\left(x\right)+Mx+q$ (24)

where $D\left(x\right)$ and $Mx+q$ are the nonlinear part and the linear part of $F\left(x\right)$, generate a linear part of $Mx+q$ in a way similar to [24]. The matrix $M=A^{\text{T}}A+B$, where A is an $n\times n$ matrix whose entries are randomly generated in the interval $\left(-\mathrm{5,5}\right)$, and a skew-symmetric matrix B is generated in the same way. In $D\left(x\right)$, the nonlinear part of $F\left(x\right)$, the components are $D_j\left(x\right)=d_j\ast \arctan \left(x_j\right)$, and $d_j$ is a random variable in $\left(-\mathrm{1,0}\right)$, see similar example [25]. Then the sequent part of generating the sparse vector $\hat{x}$ and vector $q\in R^n$ such that

$\hat{x}\in \Omega ,{\left(y-\hat{x}\right)}^{\text{T}}F\left(\hat{x}\right)\ge 0,\forall y\in \Omega ,\text{and}{\Vert \hat{x}\Vert }_0=0.01\ast 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\ast \log \left(n\right)$, ${\lambda }_0=0.2$, $\gamma =2c$, $\tau =0.75$, $l=0.1$, $\mu =1/c$, $ϵ=1e-6$, $n_{\max }=2000$, $K_0=\max \left(2,10000/n\right)$, and $d=-rand\left(n\mathrm{,1}\right)$. Then ETA will output a solution x. Similariy, the average number of iteration times, the average residual $\Vert x-z\Vert$, the average sparsity ${\Vert x\Vert }_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 Table 3 that the ETA algorithm also performs quite efficiently in such mixed complementarity problems. The sparsity ${\Vert x\Vert }_0$ of the recovered solution x are all equal to the sparsity ${\Vert \hat{x}\Vert }_0$, that is, the recover is exact.

Table 2. Results on randomly created LCPs with positive semidefinite matrices.

Table 3. Results on co-coercive mixed complementarity problems.

5. Conclusion

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.

Data Availability

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

Acknowledgements

This paper is supported by the Top Disciplines of Shanghai.

Conflicts of Interest

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

References

[1]	Ferris, M.C. and Pang, J.S. (1997) Engineering and Economic Applications of Complementarity Problem. SIAM Review, 39, 669-713. https://doi.org/10.1137/S0036144595285963
[2]	Harker, P.T. and Pang, J.S. (1990) Finite-Dimensional Variational Inequality and Nonlinear Complementarity Problems: A Survey of Theory, Algorithms and Applications. Mathematical Programming, 48, 161-220. https://doi.org/10.1007/BF01582255
[3]	Billups, S.C., Dirkse, S.P. and Ferris, M.C. (1997) A Comparison of Algorithms for Large-Scale Mixed Complementarity Problems. Computational Optimization and Applications, 7, 3-25. https://doi.org/10.1007/978-0-585-26778-4_2
[4]	Facchinei, F. and Pang, J.S. (2003) Finite-Dimensional Variational Inequality and Complementarity Problems I. Springer Series in Operations Research, Springer, New York. https://doi.org/10.1007/b97544
[5]	Facchinei, F. and Pang, J.S. (2003) Finite-Dimensional Variational Inequality and Complementarity Problems II. Springer Series in Operations Research, Springer, New York. https://doi.org/10.1007/b97544
[6]	Zhou, Z.Y. and Peng, Y.C. (2019) The Locally Chen-Harker-Kanzow-Smale Smoothing Functions for Mixed Complementarity Problems. Journal of Global Optimization, 74, 169-193. https://doi.org/10.1007/s10898-019-00739-4
[7]	Eldar, Y.C. and Kutyniok, G. (2012) Compressed Sensing: Theory and Applications. Cambridge University Press, Cambridge.
[8]	Bruckstein, A.M., Donoho, D.L. and Elad, M. (2009) From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images. SIAM Review, 51, 34-81. https://doi.org/10.1137/060657704
[9]	Candes, E.J., Romberg, J. and Tao, T. (2006) Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52, 489-509. https://doi.org/10.1109/TIT.2005.862083
[10]	Candes, E. and Tao, T. (2005) Decoding by Linear Programming. IEEE Transactions on Information Theory, 51, 4203-4215. https://doi.org/10.1109/TIT.2005.858979
[11]	Foucart, S. and Rauhut, H. (2013) A Mathematical Introduction to Compressive Sensing. Springer, Basel. https://doi.org/10.1007/978-0-8176-4948-7
[12]	Ge, D., Jiang, X. and Ye, Y. (2011) A Note on the Complexity of Minimization. Mathematical Programming, 129, 285-299. https://doi.org/10.1007/s10107-011-0470-2
[13]	Natarajan, B. (1995) Sparse Approximate Solutions to Linear Systems. SIAM Journal on Computing, 24, 227-234. https://doi.org/10.1137/S0097539792240406
[14]	Chen, X., Xu, F. and Ye, Y. (2010) Lower Bound Theory of Nonero Entries in Solutions of Minimization. SIAM Journal on Scientific Computing, 32, 2832-2852. https://doi.org/10.1137/090761471
[15]	Beck, A. and Eldar, Y. (2013) Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms. SIAM Journal on Optimization, 23, 1480-1509. https://doi.org/10.1137/120869778
[16]	Lu, Z. (2014) Iterative Hard Thresholding Methods for Regularized Convex Cone Programming. Mathematical Programming, 147, 125-154. https://doi.org/10.1007/s10107-013-0714-4
[17]	Chen, X. and Xiang, S. (2016) Sparse Solutions of Linear Complementarity Problems. Mathematical Programming, 159, 539-556. https://doi.org/10.1007/s10107-015-0950-x
[18]	Shang, M. and Nie, C. (2014) A Shrinkage-Thresholding Projection Method for Sparsest Solutions of LCPs. Journal of Inequalities and Applications, 2014, Article No. 51. https://doi.org/10.1186/1029-242X-2014-51
[19]	Shang, M., Zhang, C., Peng, D. and Zhou, S. (2015) A Half Thresholding Projection Algorithm for Sparse Solutions of LCPs. Optimization Letters, 9, 1231-1245. https://doi.org/10.1007/s11590-014-0834-7
[20]	Shang, M., Zhou, S. and Xiu, N. (2015) Extragradient Thresholding Methods for Sparse Solutions of Co-Coercive NCPs. Journal of Inequalities and Applications, 2015, Article No. 34. https://doi.org/10.1186/s13660-015-0551-5
[21]	Shang, M., Zhang, C. and Xiu, N. (2014) Minimal Zero Norm Solutions of Linear Complementarity Problems. Journal of Optimization Theory and Applications, 163, 795-814. https://doi.org/10.1007/s10957-014-0549-z
[22]	Gabriel, S.A. and More, J.J. (1997) Smoothing of Mixed Complementarity Problems in Complementarity and Variational Problems.
[23]	Zarantonello, E.H. (1971) Projections on Convex Sets in Hilbert Space and Spectral Theory. In: Zarantonello, E.H., Ed., Contributions to Nonlinear Functional Analysis, Academic Press, New York.
[24]	Harker, P.T. and Pang, J.S. (1990) A Damped-Newton for the Linear Complementarity Problems. In: Allgower, E.L. and Georg, K., Eds., Computational Solution of Nonlinear Systems of Equations: AMS Lectures on Applied Mathematics, 26th Edition, American Mathematical Society, Providence, 265-284.
[25]	Taji, K., Fukushima, M. and Ibaraki, T. (1993) A Globally Convergent Newton Method for Solving Strongly Monotone Variational Inequalities. Mathematical Programming, 58, 369-383. https://doi.org/10.1007/BF01581276