# A New Smoothing Conjugate Gradient Method for Solving Nonlinear Nonsmooth Complementarity Problems

^{*}

Previous Article in Journal

College of Mathematics, Qingdao University, 308 Qingdao Ningxia Road, Qingdao 266071, China

Author to whom correspondence should be addressed.

Academic Editor: Louxin Zhang

Received: 13 October 2015 / Revised: 27 November 2015 / Accepted: 11 December 2015 / Published: 17 December 2015

In this paper, by using the smoothing Fischer-Burmeister function, we present a new smoothing conjugate gradient method for solving the nonlinear nonsmooth complementarity problems. The line search which we used guarantees the descent of the method. Under suitable conditions, the new smoothing conjugate gradient method is proved globally convergent. Finally, preliminary numerical experiments show that the new method is efficient.

We consider the nonlinear nonsmooth complementarity problem, which is to find a vector in ${R}^{n}$ satisfying the conditions
where $F:{R}^{n}\to {R}^{n}$ is a locally Lipschitz continuous function. If F is continuously differentiable, then Problem (1) is called the nonlinear complementarity problems NCP(F). As we all know, Equation (1) is a very useful general mathematics model, which is closely related to the mathematical programming, variational inequalities, fixed point problems and mixed strategy problems (such as [1,2,3,4,5,6,7,8,9,10,11,12,13]). The methods for solving NCP(F) are classified into three categories: nonsmooth Newton methods, Jacobian smoothing methods and smoothing methods (see [14,15,16,17,18,19]). Conjugate gradient methods are widely and increasingly used for solving unconstrained optimization problem, especially in large-scale cases. There are few scholar has investigated the problem how to use the conjugate gradient method to solve NCP(F) (such as [10,20]). Moreover, in these papers, F is required to be a continuous differentiable ${P}_{0}+{R}_{0}$ function. In this paper, we present a new smoothing conjugate gradient method for solving Equation (1), where F is only required to be a locally Lipschitz continuous function.

$$x\ge 0,F(x)\ge 0,{x}^{T}F(x)=0$$

In this paper, we also define the generalized gradient of F at x is
where $\prime \prime conv\prime \prime $ denotes the convex hull of a set, ${D}_{F}$ denotes the set of points at which F is differentiable (see [21]). In the following, we introduce the definition of the smoothing function.

$$\partial F(x)=conv\{\underset{{x}_{k}\u27f6x,{x}_{k}\in {D}_{F}}{lim}\u25bdF({x}_{k})\}$$

(see [22]) Let $F:{R}^{n}\u27f6{R}^{n}$ be a locally Lipschitz continuous function. We call $\tilde{F}:{R}^{n}\times {R}_{+}\u27f6{R}^{n}$ is a smoothing function of F, if $\tilde{F}(x,\mu )$ is continuously differentiable in ${R}^{n}$ for any fixed $\mu >0$, and
for any fixed $x\in {R}^{n}$. If
for any ${x}_{k}\in {R}^{n}$, we say F satisfies gradient consistency property.

$$\underset{\mu \u27f60}{lim}\tilde{F}(x,\mu )=F(x)$$

$$\underset{{x}_{k}\u27f6x,\mu \downarrow 0}{lim}\u25bd\tilde{F}({x}_{k},\mu )\in \partial F(x)$$

In the following sections of our paper, we also use the Fischer-Burmeister function (see [23]) and the smoothing Fischer-Burmeister function. (1) The Fischer-Burmeister function
where $\phi :{R}^{2}\u27f6R$. From the definition of $\phi $, we know that it is twice continuously differentiable besides ${(0,0)}^{T}$. Moreover, it is a complementarity function, which satisfies

$$\phi (a,b)=\sqrt{{a}^{2}+{b}^{2}}-a-b,{(a,b)}^{T}\in {R}^{2}$$

$$\phi (a,b)=0\u27faa\ge 0,b\ge 0,ab=0$$

Denote

$$H(x)=\left(\begin{array}{c}\hfill \phi ({x}_{1},{F}_{1}(x))\hfill \\ \hfill \vdots \hfill \\ \hfill \phi ({x}_{n},{F}_{n}(x))\hfill \end{array}\right)$$

It is obvious that $H(x)$ is zero at a point x if and only if x is a solution of Equation (1). Then Equation (1) can be transformed into the following unconstrained optimization problem

$$min\Psi (x)=\frac{1}{2}{\parallel H(x)\parallel}^{2}$$

We know that the optimal value of $\Psi $ is zero, and $\Psi $ is called the value function of Equation (1).

(2) The smoothing Fischer-Burmeister function
where $\phi :{R}^{3}\u27f6R$ and $\mu >0.$

$${\phi}_{\mu}(a,b)=\sqrt{{a}^{2}+{b}^{2}+\mu}-a-b$$

Let
where ${\tilde{F}}_{i}(x,\mu )$ is the smoothing function of ${F}_{i}(x),i=1,\cdots ,n$.

$${H}_{\mu}(x)=\left(\begin{array}{c}\hfill {\phi}_{\mu}({x}_{1},{\tilde{F}}_{1}(x,\mu ))\hfill \\ \hfill \vdots \hfill \\ \hfill {\phi}_{\mu}({x}_{n},{\tilde{F}}_{n}(x,\mu ))\hfill \end{array}\right)$$

$${\Psi}_{\mu}(x)=\frac{1}{2}{\parallel {H}_{\mu}(x)\parallel}^{2}$$

The rest of this work is organized as follows. In Section 2, we describe the new smoothing conjugate gradient method for the solution of Problem (1). It is shown that this method has global convergence properties under fairly mild assumptions. In Section 3, preliminary numerical results and some discussions for this method are presented.

The new smoothing conjugate gradient direction is defined as
where ${\beta}_{k}$ is a scalar. Here, we use ${\beta}_{k}$ (see [24]) which is defined as
where ${y}_{k-1}=\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})-\nabla {\Psi}_{{\mu}_{k-2}}({x}_{k-1})$. When $k=1$, we set ${\mu}_{k-2}={\mu}_{0}$. The line search is Armijo-type line search (see [25]), where ${\alpha}_{k}={\eta}^{{m}_{k}},0<\eta <1,{m}_{k}$ is the smallest nonnegative integer satisfies

$${d}_{k}=\left\{\begin{array}{cc}-\nabla {\Psi}_{{\mu}_{0}}({x}_{0}),\hfill & k=0\hfill \\ -\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})+{\beta}_{k}{d}_{k-1},\hfill & k\ge 1\hfill \end{array}\right.$$

$${\beta}_{k}^{DY}=\frac{\parallel \nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}){\parallel}^{2}}{{d}_{k-1}^{T}{y}_{k-1}}$$

$${\Psi}_{{\mu}_{k}}({x}_{k}+{\alpha}_{k}{d}_{k})\le {\Psi}_{{\mu}_{k}}({x}_{k})+\delta {\alpha}_{k}{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}$$

$${(\nabla {\Psi}_{{\mu}_{k}}({x}_{k}+{\alpha}_{k}{d}_{k}))}^{T}{d}_{k+1}\le -\sigma {\parallel \nabla {\Psi}_{{\mu}_{k}}({x}_{k}+{\alpha}_{k}{d}_{k})\parallel}^{2},0<\sigma \le 1,0<\delta <1$$

Then, we give the new smoothing conjugate gradient method for solving Equation (1).

Algorithm 1: Smoothing Conjugate Gradient Method |

(S.0) Choose ${x}_{0}\in {R}^{n},\epsilon >0,{\mu}_{0}>0,m>0,\sigma ,\delta ,{m}_{1}\in (0,1),$${d}_{0}=-\nabla {\Psi}_{{\mu}_{0}}({x}_{0})$. Set $k=0$. |

(S.1) If $\Psi ({x}_{k})\le \epsilon $, then stop, otherwise go to Step 2. |

(S.2) Compute ${\alpha}_{k}$ by Equations (4) and (5), where ${d}_{k+1}=-\nabla {\Psi}_{{\mu}_{k}}({x}_{k}+{\alpha}_{k}{d}_{k})+{\beta}_{k+1}{d}_{k}$ and ${\beta}_{k+1}$ is given by Equation (3). Let ${x}_{k+1}={x}_{k}+{\alpha}_{k}{d}_{k}$. |

(S.3) If $\parallel \nabla {\Psi}_{{\mu}_{k}}({x}_{k+1})\parallel \ge m{\mu}_{k}$, then set ${\mu}_{k+1}={\mu}_{k}$, otherwise set ${\mu}_{k+1}={m}_{1}{\mu}_{k}$. |

(S.4) Let $k=k+1$, go back to Step 1. |

Algorithm 2: Algorithm Framework of Algorithm 1 |

PROGRAM ALGORITHM |

INITIALIZE ${x}_{0}\in {R}^{n},\epsilon >0,{\mu}_{0}>0,m>0,{m}_{1}\in (0,1)$; |

Set $k=0$ and ${d}_{0}=-\nabla {\Psi}_{{\mu}_{0}}({x}_{0})$. |

WHILE the termination condition |

$\Psi ({x}_{k})\le \epsilon $ is not met |

Find step sizes ${\alpha}_{k}$; |

Set ${x}_{k+1}={x}_{k}+{\alpha}_{k}{d}_{k}$ |

Evaluate $\nabla {\Psi}_{{\mu}_{k}}({x}_{k+1})$ and ${d}_{k+1}$; |

IF $\parallel \nabla {\Psi}_{{\mu}_{k}}({x}_{k+1})\parallel \ge m{\mu}_{k}$ THEN |

Set ${\mu}_{k+1}={\mu}_{k}$; |

ELSE |

Set ${\mu}_{k+1}={m}_{1}{\mu}_{k}$; |

END IF |

Set $k=k+1$; |

END WHILE |

RETURN final solution ${x}_{k}$; |

END ALGORITHM |

In the following, we will give the analysis about the global convergence of Algorithm 1. (The Algorithm 2 is the algorithm framework of Algorithm 1.) Before doing this work, we need the following basic assumptions.

(i) For any $x\in {R}^{n}$, $0<\mu \le {\mu}_{0}$, the level set ${L}_{\mu}(c)=\{x\in {R}^{n}|{\Psi}_{\mu}(x)\le c\}$ is bounded.

(ii) $\nabla {\Psi}_{{\mu}_{k}}({x}_{k+1})$ is Lipschitz continuous, that is, there exists a constant $L>0$ such that

$$\parallel \nabla {\Psi}_{{\mu}_{k}}({x}_{k+1})-\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})\parallel \le L\parallel {x}_{k+1}-{x}_{k}\parallel ,\forall {x}_{k+1},{x}_{k}\in {L}_{\mu}(c)$$

Suppose that $\left\{{d}_{k}\right\}$ is an infinite sequence of directions generated by Algorithm 1, then

$$-{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}\ge \overline{c}{\parallel \nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})\parallel}^{2},\forall k\ge 0,\overline{c}<\sigma $$

$\phantom{\rule{3.33333pt}{0ex}}\phantom{\rule{3.33333pt}{0ex}}\phantom{\rule{3.33333pt}{0ex}}\mathrm{If}$ $k=0$, by Equation (2) and $\overline{c}<1$, we can know that Equation (6) holds. If $k>0$, by Equation (5) and $\overline{c}<\sigma $, we can conclude that Equation (6) holds.

Suppose that Assumption 1 holds. Then, there exists ${\alpha}_{k}>0$ for every k, and
with ω is a positive constant.

$${\alpha}_{k}\ge \omega \frac{|{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}|}{\parallel {d}_{k}{\parallel}^{2}}$$

$\phantom{\rule{3.33333pt}{0ex}}\phantom{\rule{3.33333pt}{0ex}}\phantom{\rule{3.33333pt}{0ex}}\mathrm{From}$ Step 0 of Algorithm 1, we know that ${d}_{0}=-\nabla {\Psi}_{{\mu}_{0}}({x}_{0})$, i.e., ${d}_{0}$ is a descent direction. Suppose that ${d}_{k}$ is satisfied
for any ${\tilde{\alpha}}_{k}$. We denote

$${(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}\le -\sigma {\parallel \nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})\parallel}^{2}\le 0$$

$${\tilde{x}}_{k+1}={x}_{k}+{\tilde{\alpha}}_{k}{d}_{k}$$

$${\tilde{d}}_{k+1}=-\nabla {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1})+{\tilde{\beta}}_{k+1}{d}_{k}$$

By

$${(\nabla {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1}))}^{T}{\tilde{d}}_{k+1}=-\parallel \nabla {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1}){\parallel}^{2}+{\tilde{\beta}}_{k+1}[{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}+\phantom{\rule{0ex}{0ex}}{(\nabla {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1})-\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}]$$

We know that ${\beta}_{k}$ in Equation (3) is equivalent to (see [24])

$${\beta}_{k}=\frac{{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}}{{(\nabla {\Psi}_{{\mu}_{k-2}}({x}_{k-1}))}^{T}{d}_{k-1}}>0$$

Since Assumption 1, Equations (10) and (11) yield
by Mean Value Theorem, we have

$${(\nabla {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1}))}^{T}{\tilde{d}}_{k+1}\le -\sigma {\parallel \nabla {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1})\parallel}^{2},{\tilde{\alpha}}_{k}\in (0,\frac{|{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}|}{L\parallel {d}_{k}{\parallel}^{2}})$$

$$\begin{array}{cc}\hfill {\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1})-{\Psi}_{{\mu}_{k}}({x}_{k})& ={\int}_{0}^{1}{\tilde{\alpha}}_{k}{(\nabla {\Psi}_{{\mu}_{k}}({x}_{k}+t{\tilde{\alpha}}_{k}{d}_{k}))}^{T}{d}_{k}dt\hfill \\ \hfill ={\tilde{\alpha}}_{k}{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}& {d}_{k}+{\int}_{0}^{1}{\tilde{\alpha}}_{k}{[\nabla {\Psi}_{{\mu}_{k}}({x}_{k}+t{\tilde{\alpha}}_{k}{d}_{k})-\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})]}^{T}{d}_{k}dt\hfill \\ & \le {\tilde{\alpha}}_{k}{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}+{\int}_{0}^{1}L{\tilde{\alpha}}_{k}^{2}{\parallel {d}_{k}\parallel}^{2}tdt\hfill \\ & \le {\tilde{\alpha}}_{k}{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}+\frac{1}{2}L{\tilde{\alpha}}_{k}^{2}{\parallel {d}_{k}\parallel}^{2}\hfill \end{array}$$

Then, we obtain that

$${\Psi}_{{\mu}_{k}}({\tilde{x}}_{k+1})-{\Psi}_{{\mu}_{k}}({x}_{k})\le \delta {\tilde{\alpha}}_{k}{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k},\phantom{\rule{0ex}{0ex}}\forall {\tilde{\alpha}}_{k}\in (0,\frac{2(1-\delta )}{L}\frac{|{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}|}{\parallel {d}_{k}{\parallel}^{2}})$$

By Equations (12) and (13), we know that Equations (4) and (5) determine a positive stepsize ${\alpha}_{k}$. And there must exists a constant $\xi \in (0,1)$ yields

$$\xi \xb7\frac{|{(\nabla {\Psi}_{{\mu}_{k-1}}({x}_{k}))}^{T}{d}_{k}|}{L\parallel {d}_{k}{\parallel}^{2}}<1$$

Denote $\omega =min\{\frac{\xi}{L},\frac{2\xi (1-\delta )}{L}\}$, then Equation (7) holds. And Equation (5) implies that Equation (8) holds for $k+1$. Hence, the proof is completed.

Suppose that for any fixed $\mu >0$, ${\Psi}_{\mu}$ satisfies Assumption 1, then the infinite sequence $\left\{{x}_{k}\right\}$ generated by Algorithm 1 satisfies

$$\underset{k\u27f6\infty}{lim}{\mu}_{k}=0,\phantom{\rule{3.33333pt}{0ex}}\underset{k\u27f6\infty}{lim\; inf}\parallel \nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})\parallel =0$$

$\phantom{\rule{3.33333pt}{0ex}}\phantom{\rule{3.33333pt}{0ex}}\phantom{\rule{3.33333pt}{0ex}}\mathrm{Denote}$ $K=\left\{k\right|{\mu}_{k+1}={m}_{1}{\mu}_{k}\}$, we first show that K is an infinite set.

If K is a finite set, there exists an integer $\overline{k}$ such that
for all $k>\overline{k}$. We also have ${\mu}_{k}={\mu}_{\overline{k}}=:\overline{\mu}$ for all $k>\overline{k}$ and

$$\parallel \nabla {\Psi}_{{\mu}_{k-1}}({x}_{k})\parallel \ge m{\mu}_{k-1}$$

$$\underset{k\u27f6\infty}{lim\; inf}\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k})\parallel >0$$

In the following, we will proof

$$\underset{k\u27f6\infty}{lim\; inf}\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k})\parallel =0$$

By Lemma 1 and Assumption 1, we know that $\left\{{\Psi}_{\overline{\mu}}({x}_{k})\right\}$ is a monotone decreasing sequence and the limit of $\left\{{\Psi}_{\overline{\mu}}({x}_{k})\right\}$ is exist. Summing Equation (7), we get

$$\sum _{k\ge \overline{k}+1}\frac{{(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k}{)}^{2}}{\parallel {d}_{k}{\parallel}^{2}}<\infty $$

Due to Equation (2), we also have

$${d}_{k}+\nabla {\Psi}_{\overline{\mu}}({x}_{k})={\beta}_{k}{d}_{k-1},\forall k\ge \overline{k}+1$$

Square both sides of Equation (18), we get

$$\parallel {d}_{k}{\parallel}^{2}={({\beta}_{k})}^{2}\parallel {d}_{k-1}{\parallel}^{2}-2{(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k}-{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k})\parallel}^{2}$$

Divided both sides of Equation (19) by ${({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}$, we have

$$\begin{array}{cc}\hfill \frac{\parallel {d}_{k}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}& =\frac{{({\beta}_{k})}^{2}{\parallel {d}_{k-1}\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}-\frac{2{(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}-\frac{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k}){\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}\hfill \\ & =\frac{{({\beta}_{k})}^{2}{\parallel {d}_{k-1}\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}-{(\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k})\parallel}+\frac{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k})\parallel}{{(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k}})}^{2}+\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k}){\parallel}^{2}}\hfill \\ & \le \frac{{({\beta}_{k})}^{2}{\parallel {d}_{k-1}\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}+\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k}){\parallel}^{2}}\hfill \\ & =\frac{\parallel {d}_{k-1}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k-1}))}^{T}{d}_{k-1})}^{2}}+\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k}){\parallel}^{2}}\hfill \\ & \le \frac{\parallel {d}_{k-2}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k-2}))}^{T}{d}_{k-2})}^{2}}+\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k-1}){\parallel}^{2}}+\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k}){\parallel}^{2}}\hfill \\ & \le \cdots \hfill \\ & \le \frac{\parallel {d}_{\overline{k}+1}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{\overline{k}+1}))}^{T}{d}_{\overline{k}+1})}^{2}}+\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{\overline{k}+2}){\parallel}^{2}}+\cdots +\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k}){\parallel}^{2}}\hfill \end{array}$$

Denote

$$\frac{\parallel {d}_{\overline{k}+1}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{\overline{k}+1}))}^{T}{d}_{\overline{k}+1})}^{2}}=\lambda >0$$

Then

$$\frac{\parallel {d}_{k}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}\le \lambda +\sum _{i=\overline{k}+2}^{k}\frac{1}{\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{i}){\parallel}^{2}}$$

If Equation (16) is not hold, there exists $\gamma >0$ such that

$$\parallel \nabla {\Psi}_{\overline{\mu}}({x}_{k})\parallel \ge \gamma ,\forall k>\overline{k}+1$$

We obtain from Equations (20) and (21) that

$$\frac{\parallel {d}_{k}{\parallel}^{2}}{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}\le \frac{\lambda {\gamma}^{2}+k-\overline{k}-1}{{\gamma}^{2}}$$

Because of
provies
which leads to a contradiction with Equation (17). This show that Equation (16) holds. There are conflicts between Equations (16) and (15). This show that K must be an infinite set and

$$\frac{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}{\parallel {d}_{k}{\parallel}^{2}}\ge \frac{{\gamma}^{2}}{\lambda {\gamma}^{2}+k-\overline{k}-1}$$

$$\sum _{k\ge \overline{k}+1}\frac{{({(\nabla {\Psi}_{\overline{\mu}}({x}_{k}))}^{T}{d}_{k})}^{2}}{\parallel {d}_{k}{\parallel}^{2}}=+\infty $$

$$\underset{k\u27f6\infty}{lim}{\mu}_{k}=0$$

Then, we can assume that $K=\{{k}_{0},{k}_{1},...\}$ with ${k}_{0}<{k}_{1}<...$ Hence, we get
and completes the proof.

$$\underset{i\u27f6\infty}{lim}\parallel \nabla {\Psi}_{{\mu}_{{k}_{i}}}({x}_{{k}_{i}+1})\parallel \le m\underset{i\u27f6\infty}{lim}{\mu}_{{k}_{i}}=0$$

In this section, we intend to test the efficiency of Algorithm 1 by numerical experiments. We use Algorithm 1 to solve eleven examples, some of them are proposed the first time, some of them are modified by the examples of the references (such as [26,27]).

The smoothing function of F as ${\tilde{F}}_{i}(x,\mu )=\sqrt{{F}_{i}{(x)}^{2}+\mu}$ is used in solving Examples 1–4. From Example 5 to Example 11, the smoothing function of F is defined by (see [26]). $\tilde{F}(x,\mu )=\mu ln{\sum}_{i=1}^{m}exp(\frac{{f}_{i}(x)}{\mu}),$ where $F(x)=max\{{f}_{1}(x),\cdots ,{f}_{m}(x)\}$, $i=1,\cdots m$.

Throughout the experiments, we set $\sigma ={10}^{-2},m=1.5,{m}_{1}=0.5.$ In Examples 1–3 and Examples 5–8, we set $\epsilon ={10}^{-4},\delta ={10}^{-3},\eta =0.4,{\mu}_{0}=0.2$. Example 4, in which we set parameters $\epsilon ={10}^{-3},\delta ={10}^{-2},\eta =0.1,{\mu}_{0}=0.02$. In the case of Examples 9–11, we set $\epsilon ={10}^{-2},\delta ={10}^{-3},\eta =0.4,{\mu}_{0}=0.2$. We choose $\Psi (x)\le \epsilon $ as the termination criterion. Our numerical results are summaried in Table 1, Table 2, Table 3, Table 4, Table 5, Table 6, Table 7, Table 8, Table 9, Table 10 and Table 11, where all components of ${x}_{0}$ are randomly selected from 0 to 10. We randomly generate 10 initial points, then implement Algorithm 1 to solve the test problem for each initial point. By the numerical of results of Examples 10–11, we can see that Algorithm 1 is suitably to solve the large scale problems.

We consider Equation (1), where F is defined by $F(x)=|2x-1|$. The exact solutions of this problem are 0 and $0.5$.

x_{0} | x^{*} | $\Psi $(x^{*}) | k |
---|---|---|---|

0.9713 | 5.053658e−1 | 5.636783e−5 | 1 |

1.7119 | 4.977618e−1 | 9.929266e−6 | 11 |

2.7850 | −1.295343e−2 | 8.495830e−5 | 8 |

3.1710 | 5.422178e−3 | 1.461954e−5 | 8 |

4.0014 | 5.562478e−3 | 1.538368e−5 | 8 |

5.4688 | −7.521520e−3 | 2.849662e−5 | 7 |

6.5574 | 5.926470e−3 | 1.745635e−5 | 10 |

7.9221 | 1.276205e−2 | 8.037197e−5 | 7 |

8.4913 | −1.994188e−3 | 1.992344e−6 | 7 |

9.3399 | 1.723553e−3 | 1.482749e−6 | 7 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill |2{x}_{1}-1|\hfill \\ \hfill |4{x}_{2}+{x}_{1}-\frac{1}{2}|\hfill \end{array}\right).$ There are three exact solutions as ${(\frac{1}{2},0)}^{T},{(0,\frac{1}{8})}^{T}$ and ${(0,0)}^{T}$.

x_{0} | x^{*} | $\Psi $(x^{*}) | k |
---|---|---|---|

${(4.6939,0.1190)}^{T}$ | ${(-0.0058,0.0031)}^{T}$ | 2.162427e−5 | 7 |

${(5.2853,1.6565)}^{T}$ | ${(0.0077,0.1233)}^{T}$ | 2.974655e−5 | 13 |

${(9.9613,0.7818)}^{T}$ | ${(0.0030,0.1248)}^{T}$ | 7.106107e−6 | 5 |

${(4.9836,9.5974))}^{T}$ | ${(0.4979,-0.0097)}^{T}$ | 6.744680e−5 | 12 |

${(1.4495,8.5303)}^{T}$ | ${(0.4978,0.0080)}^{T}$ | 3.327241e−5 | 13 |

${(0.4965,9.0272)}^{T}$ | ${(0.0045,0.1221)}^{T}$ | 3.348105e−5 | 15 |

${(9.1065,1.8185)}^{T}$ | ${(-0.0045,0.1296)}^{T}$ | 9.857281e−5 | 6 |

${(4.0391,0.9645)}^{T}$ | ${(0.0087,0.1247)}^{T}$ | 6.417282e−5 | 10 |

${(7.7571,4.8679)}^{T}$ | ${(0.0045,-0.0043)}^{T}$ | 1.946526e−5 | 13 |

${(7.0605,0.3183)}^{T}$ | ${(0.0086,0.122)}^{T}$ | 4.037476e−5 | 8 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill |5{x}_{1}+{x}_{2}-{x}_{3}|\hfill \\ \hfill {x}_{1}^{2}+4{x}_{2}-{x}_{3}-2\hfill \\ \hfill 5{x}_{2}^{2}-6{x}_{1}-2{x}_{3}\hfill \end{array}\right).$ ${(0,\frac{1}{2},0)}^{T}$ is one of the exact solutions of this problem.

x_{0} | x^{*} | $\Psi $(x^{*}) | k |
---|---|---|---|

${(1.9175,7.3843,2.4285)}^{T}$ | ${(0.0087,0.5021,-0.0026)}^{T}$ | 9.785244e−5 | 21 |

${(1.1921,9.3983,6.4555)}^{T}$ | ${(0.0047,0.5019,0.0102)}^{T}$ | 6.577107e−5 | 25 |

${(1.8687,4.8976,4.4559)}^{T}$ | ${(-0.0055,0.4974,-0.0109)}^{T}$ | 7.552798e−5 | 19 |

${(2.7029,2.0846,5.6498)}^{T}$ | ${(0.0099,0.4998,0.0028)}^{T}$ | 5.759549e−5 | 26 |

${(7.2866,7.3784,0.6340)}^{T}$ | ${(0.0099,0.5003,-0.0063)}^{T}$ | 9.612693e−5 | 36 |

${(1.2991,5.6882,4.6939)}^{T}$ | ${(-0.0115,0.5009,0.0065)}^{T}$ | 9.216436e−5 | 31 |

${(5.3834,9.9613,0.7818)}^{T}$ | ${(0.0022,0.4952,-0.0083)}^{T}$ | 9.798255e−5 | 26 |

${(9.5613,5.7521,0.5978)}^{T}$ | ${(0.0089,0.5029,0.0074)}^{T}$ | 7.570081e−5 | 28 |

${(7.7571,4.8679,4.3586)}^{T}$ | ${(0.0048,0.5025,-0.0008)}^{T}$ | 6.774521e−5 | 24 |

${(3.8827,5.5178,2.2895)}^{T}$ | ${(-0.0047,0.4981,-0.0111)}^{T}$ | 7.903206e-5 | 25 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill |2{x}_{1}-{x}_{2}+3{x}_{3}+2{x}_{4}-6|\hfill \\ \hfill 3{x}_{1}-3{x}_{2}+3{x}_{3}+2{x}_{4}-5\hfill \\ \hfill 3{x}_{1}-{x}_{2}-{x}_{3}+2{x}_{4}-3\hfill \\ \hfill 3{x}_{1}-{x}_{2}+3{x}_{3}-{x}_{4}-4\hfill \end{array}\right).$ ${(\frac{31}{13},\frac{22}{13},0,\frac{19}{13})}^{T}$, ${(\frac{7}{4},0,0,\frac{5}{4})}^{T}$, ${(0,0,\frac{11}{5},\frac{13}{5})}^{T}$, ${(3,0,0,0)}^{T}$ are four of the exact solutions of this problem.

x_{0} | x^{*} | $\Psi $(x^{*}) | k |
---|---|---|---|

${(5.6743,9.6878,8.2450,9.5961)}^{T}$ | ${(0.0062,-0.0249,2.1692,2.5652)}^{T}$ | 4.436641e-4 | 21 |

${(0.1485,1.5669,4.7157,5.4299)}^{T}$ | ${(0.0009,0.0320,2.2173,2.6291)}^{T}$ | 5.987181e−4 | 37 |

${(0.5969,6.5803,8.8964,1.0963)}^{T}$ | ${(3.0522,0.0031,-0.0202,-0.0151)}^{T}$ | 3.790585e−4 | 23 |

${(8.7494,1.2100,8.5635,8.9978)}^{T}$ | ${(0.0296,-0.0290,2.1300,2.5000)}^{T}$ | 9.638295e−4 | 17 |

${(7.7836,0.6937,2.7878,3.7937)}^{T}$ | ${(3.0003,0.0096,0.0154,-0.0158)}^{T}$ | 3.052065e−4 | 13 |

${(0.6837,0.8497,0.6834,4.0982)}^{T}$ | ${(3.0055,0.0333,-0.0050,0.0131)}^{T}$ | 7.098848e−4 | 21 |

${(7.6034,5.8410,4.0295,5.1004)}^{T}$ | ${(2.4048,1.7076,-0.0096,1.4753)}^{T}$ | 4.242339e−4 | 25 |

${(9.8754,9.2271,5.6426,4.3146)}^{T}$ | ${(3.0166,0.0148,-0.0271,0.0280)}^{T}$ | 8.913504e−4 | 20 |

${(8.5061,1.4453,3.7049,6.2239)}^{T}$ | ${(2.9635,0.0040,0.0176,0.0220)}^{T}$ | 5.981987e−4 | 26 |

${(2.7744,0.0611,3.7471,4.3693)}^{T}$ | ${(0.0132,-0.0399,2.1529,2.5310)}^{T}$ | 9.794091e−4 | 21 |

We consider Equation (1), where $F=max\{(x-2),(2x-5)\}$. There are two exact solutions as 0 and 2.

x_{0} | x^{*} | $\Psi $(x^{*}) | k |
---|---|---|---|

0.2922 | 2.0024 | 2.787626e−6 | 5 |

1.7071 | 1.9894 | 5.621467e−5 | 3 |

2.2766 | 2.0075 | 2.836408e−5 | 3 |

3.1110 | 2.0001 | 2.938429e−9 | 1 |

4.3570 | 2.0101 | 5.061011e−5 | 4 |

5.7853 | 2.0109 | 5.937701e−5 | 5 |

6.2406 | 1.9871 | 8.325445e−5 | 6 |

7.1122 | 2.0116 | 6.635145e−5 | 3 |

8.8517 | 1.9970 | 4.557770e−6 | 6 |

9.7975 | 1.9928 | 2.607803e−5 | 4 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill {f}_{1}(x)\hfill \\ \hfill {f}_{2}(x)\hfill \\ \hfill {f}_{3}(x)\hfill \\ \hfill {f}_{4}(x)\hfill \end{array}\right).$ ${f}_{i}(x)=max\{{x}_{1}^{2},{x}_{2}^{2},{x}_{3}^{2},{x}_{4}^{2}\}$, $i=1,2,3,4.$ The exact solution of this problem is ${(0,0,0,0)}^{T}$.

x_{0} | x^{*} | $\Psi $(x^{*}) | k |
---|---|---|---|

${(7.4003,2.3483,7.3496,9.7060)}^{T}$ | ${(0.0825,0.0842,0.0825,0.0830)}^{T}$ | 9.228501e−5 | 29 |

${(1.3393,0.3089,9.3914,3.0131)}^{T}$ | ${(0.0858,0.0629,0.0484,0.0414)}^{T}$ | 9.446089e−5 | 22 |

${(7.3434,0.5133,0.7289,0.8853)}^{T}$ | ${(0.0852,0.0817,0.0801,0.0607)}^{T}$ | 9.546345e−5 | 36 |

${(6.7865,4.9518,1.8971,4.9501)}^{T}$ | ${(0.0431,0.0800,0.0733,0.0801)}^{T}$ | 7.428734e−5 | 34 |

${(1.4761,0.5497,8.5071,5.6056)}^{T}$ | ${(0.0774,0.0691,0.0717,0.0655)}^{T}$ | 6.591548e−5 | 39 |

${(0.5670,5.2189,3.3585,1.7567)}^{T}$ | ${(0.0244,0.0421,0.0575,0.0604)}^{T}$ | 2.433055e−5 | 25 |

${(7.6903,5.8145,9.2831,5.8009)}^{T}$ | ${(0.0477,0.0739,0.0745,0.0766)}^{T}$ | 6.280631e−5 | 32 |

${(6.9475,7.5810,4.3264,6.5550)}^{T}$ | ${(0.0846,0.0819,0.0566,0.0850)}^{T}$ | 9.476538e−5 | 21 |

${(2.8785,4.1452,4.6484,7.6396)}^{T}$ | ${(0.0637,0.0802,0.0742,0.0012)}^{T}$ | 5.739573e−5 | 33 |

${(2.9735,0.6205,2.9824,0.4635)}^{T}$ | ${(0.0854,0.0727,0.0831,0.0542)}^{T}$ | 9.575717e−5 | 22 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill {f}_{1}(x)\hfill \\ \hfill \vdots \hfill \\ \hfill {f}_{10}(x)\hfill \end{array}\right)$ with ${f}_{i}(x)=max\{{x}_{1}^{2},\cdots ,{x}_{10}^{2}\}$, $i=1,\cdots ,10.$ The exact solution of this problem is ${(0,0,0,0,0,0,0,0,0,0)}^{T}$.

x_{0} | $\Psi $(x^{*}) | k |
---|---|---|

${(8.2408,8.2798,2.9337,3.0937,5.2303,3.2530,8.3184,8.1029,5.5700,2.6296)}^{T}$ | 9.719070e−5 | 27 |

${(9.5089,4.4396,0.6002,8.6675,6.3119,3.5507,9.9700,2.2417,6.5245,6.0499)}^{T}$ | 9.957464e−5 | 45 |

${(4.1705,9.7179,9.8797,8.6415,3.8888,4.5474,2.4669,7.8442,8.8284,9.1371)}^{T}$ | 8.965459e−5 | 39 |

${(8.3975,3.7172,8.2822,1.7652,1.2952,8.7988,0.4408,6.8672,7.3377,4.3717)}^{T}$ | 9.644608e−5 | 47 |

${(9.7209,0.3146,8.3540,8.3571,0.4986,5.4589,9.4317,3.2147,8.0647,6.0140)}^{T}$ | 9.737485e−5 | 37 |

${(8.3336,4.0363,3.9018,3.6045,1.4026,2.6013,0.8682,4.2940,2.5728,2.9756)}^{T}$ | 9.240212e−5 | 47 |

${(4.8267,3.7601,5.2378,2.6487,0.6836,4.3633,1.7385,0.2611,9.5468,4.3060)}^{T}$ | 8.801643e−5 | 44 |

${(0.5398,0.2062,6.8148,5.9863,1.1403,7.9625,6.1785,0.7021,0.6928,1.3601)}^{T}$ | 8.946151e−5 | 44 |

${(5.7099,1.6977,1.4766,4.7608,9.0810,5.5218,0.3294,0.5386,8.0506,4.5137)}^{T}$ | 8.815143e−5 | 45 |

${(2.1647,7.8620,7.2309,2.7884,5.8243,4.2101,0.9207,0.2403,4.9115,2.7827)}^{T}$ | 6.697806e−5 | 39 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill {f}_{1}(x)\hfill \\ \hfill \vdots \hfill \\ \hfill {f}_{4}(x)\hfill \end{array}\right)$ with ${f}_{i}(x)={\sum}_{j=1}^{4}max\{-{x}_{j}-{x}_{j+1},-{x}_{j}-{x}_{j+1}+({x}_{j}^{2}+{x}_{j+1}^{2}+1)\}$, $i=1,2,3,4.$ The exact solution of this problem is ${(0,0,0,0)}^{T}$.

x_{0} | $\Psi $(x^{*}) | k |
---|---|---|

${(4.1131,8.2898,9.3511,3.9907)}^{T}$ | 3.670149e−5 | 4 |

${(0.5221,5.7119,7.4767,3.2024)}^{T}$ | 4.216994e−5 | 4 |

${(5.4000,2.2106,0.9595,0.6017)}^{T}$ | 6.167554e−5 | 7 |

${(6.6015,0.5231,5.5683,7.1203)}^{T}$ | 3.838925e−5 | 4 |

${(1.6924,2.5845,1.9791,6.0569)}^{T}$ | 6.272257e−5 | 6 |

${(3.3969,1.9786,5.0683,9.5076)}^{T}$ | 7.097729e−5 | 5 |

${(4.2175,4.1131,9.5914,7.5025)}^{T}$ | 2.693701e−5 | 4 |

${(8.8728,0.5585,1.3822,8.6306)}^{T}$ | 9.021922e−5 | 7 |

${(9.8100,2.3352,0.9623,3.8458)}^{T}$ | 4.687797e−5 | 5 |

${(9.6426,6.7115,2.9917,5.3113)}^{T}$ | 8.657057e−5 | 6 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill {f}_{1}(x)\hfill \\ \hfill \vdots \hfill \\ \hfill {f}_{4}(x)\hfill \end{array}\right)$ with ${f}_{i}(x)={\sum}_{j=1}^{4}max\{-{x}_{j}-{x}_{j+1},-{x}_{j}-{x}_{j+1}+({x}_{j}^{2}+{x}_{j+1}^{2}-1)\}$, $i=1,2,3,4.$ The exact solution of this problem is ${(0,0,0,0)}^{T}$.

x_{0} | $\Psi $(x^{*}) | k |
---|---|---|

${(1.5290,1.5254,1.5555,0.8957)}^{T}$ | 9.777886e−3 | 8 |

${(4.5442,6.6890,8.3130,7.9024)}^{T}$ | 3.912481e−3 | 5 |

${(9.0150,3.1834,5.9708,2.9780)}^{T}$ | 9.081688e−3 | 3 |

${(3.1781,9.8445,5.4825,7.4925)}^{T}$ | 6.868711e−3 | 7 |

${(8.4185,1.6689,9.0310,1.0512)}^{T}$ | 5.318627e−3 | 4 |

${(7.4509,7.2937,7.1747,1.3343)}^{T}$ | 7.203761e−3 | 9 |

${(4.4579,5.0879,5.3049,8.5972)}^{T}$ | 9.500345e−3 | 4 |

${(6.7772,8.0584,5.3124,9.5590)}^{T}$ | 9.421194e−3 | 4 |

${(0.6668,5.4152,2.8166,4.8090)}^{T}$ | 6.718722e−3 | 7 |

${(6.8486,2.0826,6.0816,3.2618)}^{T}$ | 3.494877e−3 | 4 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill {f}_{1}(x)\hfill \\ \hfill \vdots \hfill \\ \hfill {f}_{n}(x)\hfill \end{array}\right)$ with ${f}_{i}(x)=max\{{x}_{1}^{2}-6{x}_{1},\cdots ,{x}_{n}^{2}-6{x}_{n}\}$, $i=1,\cdots ,n.$ n represents the problem dimension. The solution is ${x}^{*}={(\lambda \cdots \lambda )}^{T}$ (λ is no more than 6). In this problem, we intend to check the efficiency of Algorithm 1 with the dimension of test problem is $50,100,$ and 200. We randomly selected ten initial values when $n=50,$ $n=100$ and $n=200$.

n = 50 | n = 100 | n = 200 | |||
---|---|---|---|---|---|

$\Psi ({x}^{*})$ | k | $\Psi ({x}^{*})$ | k | $\Psi ({x}^{*})$ | k |

1.625691e−3 | 9 | 9.444914e−3 | 11 | 9.897292e−3 | 15 |

4.082584e−3 | 7 | 5.358975e−5 | 9 | 3.937758e−4 | 5 |

6.082289e−3 | 7 | 4.734809e−3 | 9 | 5.800944e−3 | 16 |

2.042082e−3 | 9 | 3.249863e−3 | 6 | 3.289200e−3 | 11 |

3.765484e−3 | 9 | 6.587880e−3 | 10 | 4.674659e−3 | 10 |

7.553578e−3 | 13 | 2.632872e−3 | 10 | 1.450852e−3 | 13 |

4.208302e−4 | 14 | 4.177174e−3 | 3 | 9.461359e−3 | 16 |

4.250316e−3 | 9 | 9.744427e−3 | 7 | 3.778464e−3 | 15 |

2.634965e−5 | 10 | 5.854241e−6 | 10 | 1.501579e−3 | 8 |

3.445498e−3 | 11 | 4.209193e−3 | 6 | 1.984871e−3 | 25 |

We consider Equation (1), where $F=\left(\begin{array}{c}\hfill {f}_{1}(x)\hfill \\ \hfill \vdots \hfill \\ \hfill {f}_{n}(x)\hfill \end{array}\right)$ with ${f}_{i}(x)=max\{{x}_{1}^{2},\cdots ,{x}_{n}^{2}\}$, $i=1,\cdots ,n.$ The problem has only unique solution ${x}^{*}={(0,\cdots ,0)}^{T}$. We randomly selected ten initial values when $n=100,$$n=200$ and $n=500$.

n = 100 | n = 200 | n = 500 | |||
---|---|---|---|---|---|

$\Psi ({x}^{*})$ | k | $\Psi ({x}^{*})$ | k | $\Psi ({x}^{*})$ | k |

9.152621e−03 | 17 | 9.040255e−03 | 9 | 7.682471e−3 | 14 |

4.383679e−3 | 15 | 6.976857e−3 | 9 | 8.861191e−3 | 15 |

5.172738e−3 | 15 | 6.902897e−3 | 10 | 8.892858e−3 | 12 |

5.796109e−3 | 12 | 7.686345e−3 | 12 | 9.210427e−3 | 14 |

7.613768e−3 | 16 | 8.400876e−3 | 10 | 9.843579e−3 | 10 |

5.398565e−3 | 12 | 8.066523e−3 | 10 | 9.717126e−3 | 13 |

3.403516e−3 | 15 | 9.097423e−3 | 12 | 8.999900e−3 | 15 |

8.701785e−3 | 13 | 7.208014e−3 | 11 | 9.970099e−3 | 12 |

8.302172e−3 | 11 | 7.822304e−3 | 13 | 9.391355e−3 | 15 |

6.610621e−3 | 13 | 7.278306e-3 | 9 | 9.624919e−3 | 10 |

In this paper, we have presented a new smoothing conjugate gradient method for the nonlinear nonsmooth complementarity problems. The method is based on a smoothing Fischer-Burmeister function and Armijo-type line search. With careful analysis, we are able to show that our method is globally convergent. Numerical tests illustrate that the method can efficiently solve the given test problems, therefor the new method is promising. We might consider more effective ways of choosing smoothing functions and line search methods for our method. This remains under investigation.

The authors wish to thank the anonymous referees for their helpful comments and suggestions, which led to great improvement of the paper. This work is also supported by National Natural Science Foundation of China (NO. 11101231, 11401331), Natural Science Foundation of Shandong (No. ZR2015AQ013) and Key Issues of Statistical Research of Shandong Province (KT15173).

Ajie Chu prepared the manuscript. Yixiao Su assisted in the work. Shouqiang Du was in charge of the overall research of the paper.

The authors declare no conflict of interest.

- Facchinei, F.; Pang, J.S. Finite-Demensional Variational Inequalities and Complementarity Problems; Spring-Verlag: New York, NY, USA, 2003. [Google Scholar]
- Luca, T.D.; Facchinei, F.; Kanzow, C. A semismooth equation approach to the solution of nonlinear complementarity problems. Math. Programm.
**1996**, 75, 407–439. [Google Scholar] [CrossRef] - Ferris, M.C.; Pang, J.S. Engineering and economic applications of complementarity problems. SIAM Rev.
**1997**, 39, 669–713. [Google Scholar] [CrossRef] - Zhao, Y.B.; Li, D. A new path-following algorithm for nonlinear complementarity problems. Comp. Optim. Appl.
**2005**, 34, 183–214. [Google Scholar] [CrossRef] - Yu, Q.; Huang, C.C.; Wang, X.J. A combined homotopy interior point method for the linear complementarity problem. Appl. Math. Comp.
**2006**, 179, 696–701. [Google Scholar] [CrossRef] - Wang, Y.; Zhao, J.X. An algorithm for a class of nonlinear complementarity problems with non-Lipschitzianfunctions. Appl. Numer. Math.
**2014**, 82, 68–79. [Google Scholar] [CrossRef] - Fischer, A.; Jiang, H. Merit functions for complementarity and related problems: A survey. Comp. Optim. Appl.
**2000**, 17, 159–182. [Google Scholar] [CrossRef] - Chen, J.S.; Pan, S.H. A family of NCP functions and a descent method for the nonlinear complementarity problem. Comp. Optim. Appl.
**2008**, 40, 389–404. [Google Scholar] [CrossRef] - Luca, T.D.; Facchinei, F.; Kanzow, C. A theoretical and numerical comparison of some semismooth algorithm for complementarity problems. Comp. Optim. Appl.
**2000**, 16, 173–205. [Google Scholar] [CrossRef] - Wu, C.Y. The Conjugate Gradient Method for Solving Nonlinear Complementarity Problems; Inner Mongolia University: Hohhot, China, 2012. [Google Scholar]
- Qi, L.; Sun, D. Nonsmooth and smoothing methods for nonlinear complementarity problems and variational inequalities. Encycl. Optim.
**2009**, 1, 2671–2675. [Google Scholar] - Facchinei, F.; Kanzow, C. A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems. Math. Programm.
**1997**, 76, 493–512. [Google Scholar] [CrossRef] - Yang, Y.F.; Qi, L. Smoothing trust region methods for nonlinear complementarity problems with P
_{0}-functions. Ann. Op. Res.**2005**, 133, 99–117. [Google Scholar] [CrossRef] - Chen, B.; Xiu, N. A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions. SIAM J. Optim.
**1999**, 9, 605–623. [Google Scholar] [CrossRef] - Chen, B.; Chen, X.; Kanzow, C. A penalized Fischer-Burmeister NCP-function: Theoretical investigation and numerical results. Math. Programm.
**2000**, 88, 211–216. [Google Scholar] [CrossRef] - Kanzow, C.; Kleinmichel, H. A new class of semismooth Newton-type methods for nonlinear complementarity problems. Comp. Optim. Appl.
**1998**, 11, 227–251. [Google Scholar] [CrossRef] - Chen, X.; Qi, L.; Sun, D. Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities. Math. Comp.
**1998**, 67, 519–540. [Google Scholar] [CrossRef] - Kanzow, C.; Pieper, H. Jacobian smoothing methods for general nonlinear complementarity problems. SIAM J. Optim.
**1999**, 9, 342–372. [Google Scholar] [CrossRef] - Chen, B.; Harker, P.T. Smoothing approximations to nonlinear complementarity problems. SIAM J. Optim.
**1997**, 7, 403–420. [Google Scholar] [CrossRef] - Wu, C.Y.; Chen, G.Q. A smoothing conjugate gradient algorithm for nonlinear complementarity problems. J. Sys. Sci. Sys. Engin.
**2008**, 17, 460–472. [Google Scholar] [CrossRef] - Clarke, F.H. Optimization and Nonsmooth Analysis; John Wiley and Sons, Inc.: New York, NY, USA, 1983. [Google Scholar]
- Chen, X.J. Smoothing methods for nonsmooth, nonconvex minimization. Math. Programm.
**2012**, 134, 71–99. [Google Scholar] [CrossRef] - Fischer, A. A special Newton-type optimization method. Optimization
**1992**, 24, 269–284. [Google Scholar] [CrossRef] - Dai, Y.H.; Yuan, Y. An efficient hybrid conjugate gradient method for unconstrained optimization. Ann. Oper. Res.
**2001**, 103, 33–47. [Google Scholar] [CrossRef] - Dai, Y.H. Conjugate gradient methods with Armijo-type line searches. Acta Math. Appl. Sin.
**2002**, 18, 123–130. [Google Scholar] [CrossRef] - Xu, S. Smoothing method for minimax problem. Comp. Optim. Appl.
**2001**, 20, 267–279. [Google Scholar] [CrossRef] - Haarala, M. Large-Scale Nonsmooth Optimization: Variable Metric Bundle Method with Limited Memory. Ph.D. Thesis, University of Jyväskylä, Jyväskylä, Finland, 13 November 2004. [Google Scholar]

© 2015 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/4.0/).