# A Smoothing Inexact Newton Method for Nonlinear Complementarity Problems

Authors: Zhong Wan; HuanHuan Li; Shuai Huang
Journal: Abstract and Applied Analysis
 (2015)

---

## Abstract

A smoothing inexact Newton method is presented for solving nonlinear complementarity problems. Different from the existing exact methods, the associated subproblems are not necessary to be exactly solved to obtain the search directions. Under suitable assumptions, global convergence and superlinear convergence are established for the developed inexact algorithm, which are extensions of the exact case. On the one hand, results of numerical experiments indicate that our algorithm is effective for the benchmark test problems available in the literature. On the other hand, suitable choice of inexact parameters can improve the numerical performance of the developed algorithm.


---

## Body

## 1. Introduction

In the study of equilibria problems from economics, engineering, and management sciences, a complementarity problem (CP) often appears as the prominent mathematical model of the equilibria problems. Thus, it is the most practical interest to develop a robust and efficient algorithm for solving CP in the past decades (see the very recently published book [1] and the references therein). In this paper, we consider a nonlinear complementarity problem (denoted by NCP(
F
), for short): find a vector x
∈
R
n such that
(1)
x
≥
0
,
F
(
x
)
≥
0
,
x
T
F
(
x
)
=
0
,
where F
:
R
n
→
R
n is continuously differentiable function. Due to the extensive applications, NCP(
F
) has attracted great attention of researchers (see, e.g., [2, 3] and the references therein). On the one hand, there have been many theoretical results on the existence of solutions and their structural properties. On the other hand, many attempts have been made to develop implementable algorithms for the solution of NCP(
F
).A popular way to solve the NCP(
F
) is to reformulate 1 to a nonsmooth equation via an NCP-function. Function ϕ
:
R
2
→
R is said to be the NCP-function if
(2)
ϕ
(
a
,
b
)
=
0
⟺
a
≥
0
,
b
≥
0
,
a
b
=
0
.
Define Φ
:
R
n
→
R
n, given by
(3)
Φ
x
=
ϕ
x
1
,
F
1
x
ϕ
x
2
,
F
2
x
⋮
ϕ
x
n
,
F
n
x
.
Then, problem 1 is equivalent to
(4)
Φ
(
x
)
=
0
.
Thus, any efficient algorithm for solving 4 can be directly applied to find the solution of problem 1.Smoothing method is a fundamental approach to solve the nonsmooth equation4. In this connection, one can see, for example, [4–16]. The basic idea of this method is to construct a smooth function to approximate Φ. Let μ
>
0 be a given smoothing parameter. We define a continuously differentiable function Φ
μ
:
R
n
→
R
n such that for any μ
>
0 and x
∈
R
n there holds
(5)
Φ
(
x
)
-
Φ
μ
(
x
)
⟶
0
,
as
μ
⟶
0
.
Then, problem 4 is approximated by a smooth equation:
(6)
Φ
μ
(
x
)
=
0
.
Let {
μ
k
} be a given positive sequence which tends to 0. Then, we can obtain an approximate solution of 4 by solving 6 with μ
=
μ
k.Recently, there are many different smoothing functions being employed to smooth the problem4. Among them, the Fischer-Burmeiste function and the minimum function are two popular ones, which are defined by
(7)
ϕ
(
a
,
b
)
=
a
+
b
-
a
2
+
b
2
,
∀
(
a
,
b
)
∈
R
2
,
(8)
ϕ
(
a
,
b
)
=
min
⁡
{
a
,
b
}
,
∀
(
a
,
b
)
∈
R
2
,
respectively. With the 2-norm of (
a
,
b
) in the Fischer-Burmeiste function being replaced by a more general p-norm with p
∈
(
1
,
∞
), Chen and Pan proposed a family of new NCP-function in [6]. By combining the Fischer-Burmeiste function and the minimum function, Liu and Wu presented a smoothing function in [11] as follows:
(9)
ϕ
θ
a
,
b
=
a
+
b
-
θ
a
-
b
2
+
(
1
-
θ
)
(
a
2
+
b
2
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
θ
∈
[
0,1
]
∀
(
a
,
b
)
∈
R
2
.
In [13], a symmetric perturbed Fischer-Burmeister function is constructed:
(10)
ϕ
μ
,
a
,
b
=
(
1
+
μ
)
(
a
+
b
)
-
a
+
μ
b
2
+
b
+
μ
a
2
+
μ
2
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
∀
(
μ
,
a
,
b
)
∈
R
3
.
Very recetly, in [15], a more general smoothing function with the p-norm (p
∈
(
1
,
∞
)) was presented. It is shown that for the nonmonotone smoothing Newton algorithm developed in [14] the numerical performance of algorithm is greatly improved if p
=
1.1.In this paper, we first write8 as
(11)
min
⁡
⁡
a
,
b
=
1
2
a
+
b
-
a
-
b
,
∀
(
a
,
b
)
∈
R
2
,
then, we intend to investigate a new smoothing method of ·, and in virtue of this new method, we will design a smoothing inexact Newton algorithm to solve the obtained smooth equations. Since an inexact parameter at each iteration is admissive to obtain an inexact Newton search direction, the developed algorithm is more helpful to numerical computation than the similar ones available in the literature. By suitably choosing a sequence of inexact parameters in advance, numerical performance of the developed algorithm in this paper can be improved. On the other hand, without the assumption of strict complementarity, we can establish the theory of convergence for our algorithm, which is weaker than that in the existing results.The rest of this paper is organized as follows. In Section2, we study a smoothing method of the absolute function. Section 3 is devoted to development of a smoothing inexact Newton algorithm to solve the nonlinear complementarity problem. In Section 4, the global convergence and the superlinear convergence are established. Numerical results are reported in Section 5. Some final remarks are made in Section 6.The following notions will be used throughout this paper. For any vector or matrixA, A
T denotes the transposition of A. R
n denotes the space of n-dimensional real vectors. R
+
n and R
+
+
n denote the nonnegative and the positive subspaces in R
n, respectively. For any vector ν
∈
R
n, diag
⁡
{
ν
i
:
i
∈
N
} denotes a diagonal matrix, whose ith diagonal element is ν
i and vec
⁡
{
ν
i
:
i
∈
N
} the vector ν, N represents the set {
1,2
,
…
,
n
}. I represents the identity matrix with a suitable dimension. · stands for the 2-norm. For any α
,
β
∈
R
+
+, α
=
O
(
β
) and α
=
o
(
β
) represent that α
/
β is uniformly bounded and that α
/
β tends to zero as β
→
0, respectively.


## 2. Smoothing the Absolute Function

In this section, we will study a smoothing method of the absolute function.We first present a functionφ
μ
:
R
→
R, given by
(12)
φ
μ
(
t
)
=
2
π
arctan
t
μ
.
It is clear that
(13)
lim
⁡
μ
→
0
+
φ
μ
(
t
)
=
1
,
if
t
>
0
,
0
,
if
t
=
0
,
-
1
,
if
t
<
0
.Note that the generalized derivative of the absolution function· is calculated by
(14)
sign
⁡
(
t
)
=
1
,
if
t
>
0
,
[
-
1,1
]
,
if
t
=
0
,
-
1
,
if
t
<
0
.We can conclude that, except fort
=
0, φ
μ
(
t
) is a good approximation to the generalized derivative of t with a sufficiently small μ. Actually, the following result was proved in [17].Proposition 1.
For any given constantα
>
0, there is a constant M
α
>
0 independent of μ and t such that
(15)
0
≤
sign
⁡
(
t
)
-
φ
μ
(
t
)
≤
M
α
μ
,
∀
t
:
t
≥
α
,
∀
μ
>
0
,
0
≤
φ
μ
(
t
)
-
sign
⁡
(
t
)
≤
M
α
μ
,
∀
t
:
t
≤
-
α
,
∀
μ
>
0
.By Proposition1, to obtain an approximation of t, we calculate the integral of φ
μ:
(16)
∫
φ
μ
(
t
)
d
t
=
2
π
∫
‍
arctan
t
μ
d
t
=
t
φ
μ
(
t
)
-
1
π
μ
ln
⁡
1
+
t
2
μ
2
≜
ϕ
μ
(
t
)
.
Then, it is natural that we use ϕ
μ
(
t
) to approximate t. Actually, we have the following result (see [17]).Proposition 2.
(1) For anyμ
>
0, it holds that
(17)
|
t
|
≤
ϕ
μ
(
t
)
,
∀
t
∈
R
.
The above inequality holds strictly for allt
≠
0.
(2) For anyt
∈
R
n, lim
⁡
μ
→
0
+
⁡
ϕ
μ
(
t
)
=
|
t
|.
(3)lim
⁡
μ
→
0
+
dist
⁡
(
ϕ
μ
′
(
t
)
,
∂
h
(
t
)
)
=
0, where h
(
t
)
=
t and dist
⁡
(
v
,
S
) denotes the distance from the point v to the set S.


## 3. A Smoothing Inexact Newton Algorithm for NCP(
F
)

In this section, we will develop a smoothing inexact Newton algorithm for solving a smooth equation obtained by reformulating the NCP(F).Since(18)
min
⁡
x
i
,
F
i
x
=
1
2
x
i
+
F
i
x
-
x
i
-
F
i
x
≜
ϕ
i
(
x
)
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
(
i
∈
N
)
,
we construct an approximation of ϕ
i
(
x
) by Proposition 2, defined by
(19)
ϕ
i
μ
,
x
=
1
2
x
i
+
F
i
(
x
)
-
ϕ
μ
x
i
-
F
i
x
=
1
2
x
i
+
F
i
(
x
)
-
2
π
x
i
-
F
i
x
arctan
x
i
-
F
i
(
x
)
μ
1
+
x
i
-
F
i
x
2
μ
2
h
h
h
h
h
h
h
+
1
π
μ
ln
⁡
1
+
x
i
-
F
i
x
2
μ
2
.DefineΦ
μ
:
R
n
→
R
n, given by
(20)
Φ
μ
(
x
)
=
ϕ
1
(
μ
,
x
)
⋮
ϕ
n
(
μ
,
x
)
.
Then, Φ
(
x
)
=
0 is approximated by a smooth equation:
(21)
Φ
μ
(
x
)
=
0
.Remark 3.
The above smoothing method has been used to deal with NCP(F) in [17]. Then, by solving a generalized Newton equation:
(22)
∇
Φ
μ
x
k
T
d
+
Φ
(
x
k
)
=
0
,
so as to obtain a search direction d at k-iteration for the developed algorithm in [17]. Different from the standard Newton method, Φ
(
x
k
) is employed to replace Φ
μ
(
x
k
) in 22.Taking into account the advantage of the standard smoothing Newton method (see, e.g., [12, 15, 16, 18]) in adjusting the the value of smoothing parameter automatically, we further transform problem 21 into a smooth optimization problem.Denotez
=
(
μ
,
x
)
∈
R
+
+
×
R
n. We define a function H
:
R
+
+
×
R
n
→
R
+
+
×
R
n by
(23)
H
(
z
)
=
μ
Φ
(
z
)
with Φ
(
z
)
=
(
ϕ
1
(
z
)
,
ϕ
2
(
z
)
,
…
,
ϕ
n
(
z
)
)
T. Then, corresponding to any solution x
* of  21, z
*
=
(
0
,
x
*
) is an optimal solution of the following minimization problem:
(24)
min
⁡
Ψ
(
z
)
≜
H
(
z
)
2
=
μ
2
+
Φ
(
z
)
2
.
Conversely, if z
*
=
(
μ
*
,
x
*
) is an optimal solution of problem 24 with Ψ
(
z
*
)
=
0, then, x
* solves the system of 21.Next, we focus on developing an efficient algorithm to solve problem24. Before presentation of such an algorithm, we further investigate the properties of problem 24. The following definitions are useful to describe the properties of H.Definition 4.
A matrixM
∈
R
n
×
n is said to be a P
0 matrix if all principal minors of M are nonnegative.Definition 5.
A functionF
:
R
n
→
R
n is said to be a P
0 function if for all x
,
y
∈
R
n with x
≠
y, there holds that
(25)
max
⁡
i
∈
N
x
i
-
y
i
F
i
x
-
F
i
y
≥
0
.Definition 6 (see [19, 20]).
Suppose thatΨ
:
R
n
→
R
n is a locally Lipschitz continuous function, which has the generalized Jacobian ∂
Ψ
(
x
) in the sense of Clarke [21], it is said to be semismooth (or strongly semismooth) at a point x
∈
R
n if and only if for any V
∈
∂
Ψ
(
x
+
h
), as h
→
0,
(26)
V
h
-
Ψ
′
(
x
,
h
)
=
o
(
h
)
,
or
O
h
2
,
Ψ
x
+
h
-
Ψ
x
-
Ψ
′
(
x
,
h
)
=
o
(
h
)
,
or
O
h
2
.We now prove the following results.Lemma 7.
Letz
=
(
μ
,
x
) and H be defined by 23. Then, consider the following:(i)
H is continuously differentiable at any z
=
(
μ
,
x
)
∈
R
+
+
×
R
n with its Jacobian matrix
(27)
H
′
(
z
)
=
1
0
A
(
z
)
B
(
z
)
,
where(28)
A
(
z
)
=
1
2
vec
⁡
1
π
ln
⁡
1
+
x
i
-
F
i
x
2
μ
2
:
i
∈
N
,
B
(
z
)
=
1
2
I
-
D
z
+
I
+
D
z
F
′
x
,
D
(
z
)
=
2
π
diag
⁡
arctan
x
i
-
F
i
(
x
)
μ
:
i
∈
N
.
Furthermore, ifF is a P
0-function, then, H
′ is nonsingular for any μ
>
0.
(ii)
H is locally Lipschitz continuous and semismooth on R
n
+
1.Proof.
(i) SinceΦ is continuous differentiable at any z
=
(
μ
,
x
)
∈
R
+
+
×
R
n, then H is continuous differentiable. For any μ
>
0, by straightforward calculation, it yields 27 from the definition of H.
Note that, for alli
∈
N, -
1
<
D
(
z
)
i
i
<
1. It is clear that I
-
D
(
z
) and I
+
D
(
z
) are two positive diagonal matrices. Since F is a P
0-function, F
′ is also a P
0-matrix for all x
∈
R
n. Thus, the principal minors of the matrix (
I
+
D
(
z
)
)
F
′
(
x
) are nonnegative. By Definition 4, we know that the matrix (
I
+
D
(
z
)
)
F
′
(
x
) is a P
0-matrix. From Theorem  3.3 in [7], it follows that the matrix B
(
z
) is nonsingular. Then, it is concluded that the matrix H
′
(
z
) is nonsingular.
(ii) It is clear thatH is locally Lipschitz continuous and semismooth on R
n
+
1. The proof is completed.With the properties ofH in Lemma 7, we first present an algorithm to solve problem 24 similar to the idea in [18, 22–25].Algorithm 8 (a smoothing inexact Newton method).
Step 0. Choose constants δ, γ
∈
(
0,1
), σ
∈
(
0
,
1
/
2
), μ
0
>
0 such that μ
0
γ
<
1. Given an initial point x
0
∈
R
n, choose a sequence {
θ
k
}
⊂
R
+
+ such that θ
k
∈
(
0,1
-
μ
0
γ
). Set z
0
:
=
(
μ
0
,
x
0
) and k
:
=
0.
Step 1. If H
(
z
k
)
=
0, then the algorithm stops. Otherwise, compute
(29)
β
(
z
k
)
:
=
γ
min
⁡
1
,
Ψ
z
k
,
h
(
z
k
)
:
=
μ
0
β
z
k
,
θ
k
Φ
z
k
.
Step 2. Compute Δ
z
k
:
=
(
Δ
μ
k
,
Δ
x
k
)
∈
R
×
R
n by
(30)
H
(
z
k
)
+
H
′
(
z
k
)
Δ
z
k
=
h
(
z
k
)
.
Step 3. Set α
k
:
=
δ
m
k, where m
k is the smallest nonnegative integer m such that
(31)
Ψ
z
k
+
δ
m
Δ
z
k
≤
1
-
2
σ
1
-
μ
0
γ
-
θ
k
δ
m
Ψ
(
z
k
)
.
Step 4. Set z
k
+
1
:
=
z
k
+
α
k
Δ
z
k and k
:
=
k
+
1. Return to Step 1.Remark 9.
Similar to the idea in [26], we develop Algorithm 8 by incorporating an inexact parameter θ
k at each iteration to obtain an inexact Newton direction of search in 30. Generally, we choose a sequence {
θ
k
} in advance, such that lim
⁡
k
→
∞
⁡
θ
k
=
0. Suitable choice of {
θ
k
} can be used to improve the numerical performance of Algorithm 8 by generating an inexact Newton direction Δ
z
k in Step 2 of Algorithm 8. The difference between Algorithm 8 and that developed in [26] lies in the distinct smoothing method. In [26], instead of the smoothing function 19, the Fischer-Burmeister function is adopted.
On the other hand, without the assumption of strict complementarity, we will establish the theory of global and local superlinearly convergences for Algorithm8 in Section 4 under weaker conditions than the existing results.
Ifθ
k
≡
0, then, Algorithm 8 reduces to a smoothing Newton algorithm, which is similar to that developed in [18]. However, the definition of h in this paper is different from that in [18].Denote(32)
Ω
:
=
z
=
μ
,
x
∈
R
n
+
1
:
μ
≥
μ
0
β
z
.The following result shows that Algorithm8 is well-defined.Theorem 10.
Suppose thatF is a continuous differentiable P
0-function. (1)
For the system of linear equations30 in the unknown variable Δ
z
k, there exists a unique solution.
(2)
In finitely many back-tracking steps,α
k in Step 3 of Algorithm 8 is obtained to satisfy 31.
(3)
Let{
z
k
} be the sequence generated by Algorithm 8. Then, for all k
>
0, z
k
∈
Ω.Proof.
We prove the first result.
SinceF is a continuously differentiable P
0-function, it follows from Lemma 7 that the matrix H
′ is nonsingular at z
k as μ
k
>
0. It implies that the system of linear equations 30 in the unknown variable Δ
z
k has a unique solution. Thus, Step 2 of Algorithm 8 is well-defined.
We now prove the second result.
By30, we have
(33)
Δ
μ
k
=
-
μ
k
+
μ
0
β
(
z
k
)
.
From the definitions of Ψ
(
z
k
) and β
(
z
k
), it follows that, for all k
≥
0,
(34)
β
(
z
k
)
≤
γ
Ψ
z
k
1
/
2
,
μ
k
≤
Ψ
z
k
1
/
2
.
Thus, for any α
∈
(
0,1
)
(35)
μ
k
+
α
Δ
μ
k
2
=
1
-
α
μ
k
+
α
μ
0
β
z
k
2
=
1
-
α
2
μ
k
2
+
2
(
1
-
α
)
α
μ
0
μ
k
β
(
z
k
)
+
α
2
μ
0
2
β
z
k
2
≤
1
-
α
2
μ
k
2
+
2
α
μ
0
γ
Ψ
(
z
k
)
+
O
(
α
2
)
.
Denote
(36)
φ
(
α
)
=
Φ
(
z
k
+
α
Δ
z
k
)
-
Φ
(
z
k
)
-
α
Φ
′
(
z
k
)
Δ
z
k
.
Since Φ is continuous differentiable at z
∈
R
+
+
×
R
n, then φ
(
α
)
=
o
(
α
); we conclude from 36 that
(37)
Φ
(
z
k
+
α
Δ
z
k
)
2
=
Φ
(
z
k
)
+
α
Φ
′
(
z
k
)
Δ
z
k
+
φ
(
α
)
2
=
(
1
-
α
+
α
θ
k
)
Φ
(
z
k
)
+
φ
(
α
)
2
≤
1
-
α
+
α
θ
k
2
Φ
(
z
k
)
2
+
o
(
α
)
.
It yields
(38)
Ψ
(
z
k
+
α
Δ
z
k
)
=
μ
k
+
1
2
+
Φ
(
z
k
+
α
Δ
z
k
)
2
≤
1
-
α
2
μ
k
2
+
2
α
μ
0
γ
Ψ
(
z
k
)
+
1
-
α
+
α
θ
k
2
Φ
(
z
k
)
2
+
o
(
α
)
+
O
(
α
2
)
≤
1
-
α
+
α
θ
k
2
Ψ
(
z
k
)
+
2
α
μ
0
γ
Ψ
(
z
k
)
+
o
(
α
)
≤
Ψ
(
z
k
)
-
2
α
(
1
-
θ
k
)
Ψ
(
z
k
)
+
α
2
1
-
θ
k
2
Ψ
(
z
k
)
+
2
α
μ
0
γ
Ψ
(
z
k
)
+
o
(
α
)
≤
1
-
2
1
-
μ
0
γ
-
θ
k
α
Ψ
(
z
k
)
+
o
(
α
)
.
Since θ
k
<
1
-
μ
0
γ, there exists a constant α
¯
∈
(
0,1
) such that, for any α
∈
(
0
,
α
¯
] and σ
∈
(
0,1
), there holds that
(39)
Ψ
(
z
k
+
α
Δ
z
k
)
≤
[
1
-
2
σ
(
1
-
μ
0
γ
-
θ
k
)
α
]
Ψ
(
z
k
)
.
This demonstrates that Step 3 of Algorithm 8 is well-defined at each iteration.
Finally, we provez
k
∈
Ω for all k
>
0.
It is clear thatμ
0
β
(
z
0
)
≤
μ
0
γ
≤
μ
0. In other words, z
0
∈
Ω. Suppose that z
k
∈
Ω as k
≥
1. Then, μ
k
≥
μ
0
β
(
z
k
). By 31, we get Ψ
(
z
k
)
≥
Ψ
(
z
k
+
1
); then β
(
z
k
)
≥
β
(
z
k
+
1
). By 33, we have
(40)
μ
k
+
1
=
(
1
-
α
)
μ
k
+
α
μ
0
β
(
z
k
)
≥
(
1
-
α
)
μ
0
β
(
z
k
)
+
α
μ
0
β
(
z
k
)
≥
μ
0
β
(
z
k
)
≥
μ
0
β
(
z
k
+
1
)
.
The last inequality implies that the desired result holds for k
+
1. By mathematical induction method, we concluded that z
k
∈
Ω for all k
>
0.
We have completed the proof of Theorem10.Remark 11.
By Theorem10, we know that Algorithm 8 is well-defined, and either it stops in finitely many steps or generates an infinite sequence {
z
k
=
(
μ
k
,
x
k
)
} with μ
∈
R
+
+ and z
k
∈
Ω for all k
≥
0. In the subsequent section, we will analyze the convergence of this sequence.


## 4. Convergence

In this section, we will establish the global convergence and the superlinear convergence for Algorithm8.We first prove the following result.Lemma 12.
LetΦ
μ be defined by 20. If F is a P
0-function, then, for any μ
>
0, Φ
μ is coercive in x. That is,
(41)
lim
⁡
x
→
∞
Φ
μ
(
x
)
⟶
+
∞
.Proof.
Asx
→
∞, there exists a vector sequence {
x
k
} which is unbounded. Then, there is a component i
0
∈
{
1,2
,
…
,
n
} such that {
x
i
0
k
} is unbounded.
Define an index setJ
=
{
i
∈
N
:
{
x
i
k
}
is
unbounded
}. Then, J is a nonempty set. Without loss of generality, we assume that {
x
j
k
}
→
+
∞, for all j
∈
J.
Let the sequencex
^
k be defined by
(42)
x
^
i
k
=
0
,
if
i
∈
J
,
x
i
k
,
if
i
∉
J
,
i
∈
N
.
Then, it is clear that{
x
^
k
} is bounded. Since F is a P
0-function, by Definition 5, we have
(43)
0
≤
max
⁡
i
∈
N
{
(
x
i
k
-
x
^
i
k
)
[
F
i
(
x
k
)
-
F
i
(
x
^
k
)
]
}
=
max
⁡
i
∈
J
{
x
i
k
[
F
i
(
x
k
)
-
F
i
(
x
^
k
)
]
}
=
x
j
k
[
F
j
(
x
k
)
-
F
j
(
x
^
k
)
]
,
where j is one of the indices at which the max is attained. Since j
∈
J, and j can be supposed to be independent of k, we know x
j
k
→
+
∞ as k
→
+
∞.
Next, we continue the proof in the following six directions.
Case 1 (x
j
k
→
+
∞ and x
j
k
-
F
j
(
x
k
)
→
+
∞). Since {
F
j
(
x
^
k
)
,
k
∈
N
} is bounded by the continuity of F
j and the definition of x
^
k, we know that F
j
(
x
k
)
↛
-
∞ from 43. Thus,
(44)
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
⟶
+
∞
.
It yields
(45)
ϕ
j
μ
,
x
k
=
1
2
x
j
k
+
F
j
x
k
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
h
h
h
-
2
π
x
j
k
-
F
j
(
x
k
)
arctan
x
j
k
-
F
j
(
x
k
)
μ
h
h
h
+
1
π
μ
ln
⁡
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
⟶
+
∞
.
Case 2 (x
j
k
→
-
∞ and x
j
k
-
F
j
(
x
k
)
→
+
∞). It is clear that
(46)
F
j
(
x
k
)
-
x
j
k
⟶
-
∞
,
ln
⁡
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
⟶
+
∞
.
In virtue of
(47)
lim
⁡
u
→
-
∞
ln
⁡
(
1
+
u
2
)
u
=
0
,
we obtain
(48)
ϕ
j
μ
,
x
k
=
1
2
x
j
k
+
F
j
(
x
k
)
1
+
x
j
k
-
F
j
x
k
2
μ
2
h
h
h
-
2
π
x
j
k
-
F
j
(
x
k
)
arctan
x
j
k
-
F
j
(
x
k
)
μ
h
h
h
+
1
π
μ
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
=
F
j
x
k
-
x
j
k
1
+
x
j
k
-
F
j
x
k
2
μ
2
h
h
h
+
μ
2
π
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
+
x
j
k
⟶
+
∞
.
Case 3 (x
j
k
→
+
∞ and x
j
k
-
F
j
(
x
k
)
→
-
∞). In the same reason as in Case 1, F
j
(
x
k
)
↛
-
∞. Thus,
(49)
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
⟶
+
∞
.
It yields
(50)
ϕ
j
μ
,
x
k
=
1
2
x
j
k
+
F
j
(
x
k
)
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
h
h
h
-
2
π
x
j
k
-
F
j
(
x
k
)
arctan
x
j
k
-
F
j
(
x
k
)
μ
h
h
h
+
1
π
μ
ln
⁡
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
=
x
j
k
+
μ
2
π
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
⟶
+
∞
.
Case 4 (x
j
k
→
-
∞ and x
j
k
-
F
j
(
x
k
)
→
-
∞). Similar to Case 2, we can obtain
(51)
ϕ
j
μ
,
x
k
=
1
2
x
j
k
+
F
j
(
x
k
)
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
h
h
h
-
2
π
x
j
k
-
F
j
(
x
k
)
arctan
x
j
k
-
F
j
(
x
k
)
μ
h
h
h
+
1
π
μ
ln
⁡
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
=
x
j
k
+
μ
2
π
ln
⁡
1
+
x
j
k
-
F
j
(
x
k
)
2
μ
2
=
x
j
k
-
F
j
x
k
+
μ
2
π
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
h
h
h
1
+
x
j
k
-
F
j
x
k
2
μ
2
+
F
j
x
k
⟶
+
∞
.
Case 5 (x
j
k
→
+
∞ and x
j
k
-
F
j
(
x
k
) is bounded). On the one hand, it is clear that
(52)
w
=
-
2
π
(
x
j
k
-
F
j
(
x
k
)
)
arctan
x
j
k
-
F
j
(
x
k
)
μ
+
1
π
μ
ln
⁡
1
+
x
j
k
-
F
j
x
k
2
μ
2
is bounded. On the other hand, x
j
k
→
+
∞ and x
j
k
-
F
j
(
x
k
) is bounded; we know F
j
(
x
k
)
→
+
∞. Thus, x
j
k + F
j
(
x
k
)
→
+
∞. It yields
(53)
ϕ
j
μ
,
x
k
=
1
2
x
j
k
+
F
j
x
k
+
w
⟶
+
∞
.
Case 6 (x
j
k
→
-
∞ and x
j
k
-
F
j
(
x
k
) is bounded). Similar to Case 5, it is easy to prove that ϕ
j
μ
,
x
k
→
+
∞.
The proof is completed.Remark 13.
By Lemma12, we can remove the assumption that the level set of the merit function is bounded. In addition, different from [13, 22, 27], the result of Lemma 12 is obtained in this paper for the nonsymmetric smoothing function.Before statement of main results, we need the following assumption.Assumption 14.
The solution setS of NCP(
F
)  1 is nonempty and bounded.Remark 15.
Assumption14 is a relatively weak condition to ensure the convergence of Algorithm 8. For example, in [26], it is assumed that the level sets
(54)
L
(
z
0
)
=
{
z
∈
R
n
+
1
,
Φ
(
z
)
≤
Φ
(
z
0
)
}
are bounded to prove the convergence of algorithm. Up to our knowledge, for the Fischer-Burmeister smoothing function, 54 is proved to be true under the condition that F in NCP(
F
)  1 is a uniform P-function.
However, with our smoothing method, we can prove that54 holds. Since the proof is only involved with the condition that F is a P
0-function, Assumption 14 is weaker than that in [26].With Lemma12 and Assumption 14, we are now in a position to establish the convergence theory for Algorithm 8.Theorem 16.
Let{
z
k
=
(
μ
k
,
x
k
)
} be the iteration sequence generated by Algorithm 8. Under Assumption 14, the following statements are true. (i)
{
Ψ
(
z
k
)
} and {
μ
k
} generated by Algorithm 8 are two monotonically decreasing and bounded sequences, whose limits are 0.
(ii)
Any accumulation point of{
z
k
} is a solution of  24.
(iii)
Under Assumption14, {
z
k
} has at least one accumulation point z
*
=
(
μ
*
,
x
*
) with H
(
z
*
)
=
0 and x
*
∈
S.Proof.
(i) From Steps 2 and 3 of Algorithm8, it is clear that {
Ψ
(
z
k
)
}, {
β
(
z
k
)
}, and {
μ
k
} are three monotonically decreasing and bounded sequences.
(ii) By Lemma12, we conclude that the sequence {
z
k
} is bounded. Then, without loss of generality, we suppose that as k
→
∞, there exists z
* such that
(55)
z
k
⟶
z
*
,
β
(
z
k
)
⟶
β
*
,
Ψ
(
z
k
)
⟶
Ψ
*
,
μ
k
⟶
μ
*
.
If Ψ
*
>
0, then, by the definition of β
(
z
k
), β
*
>
0 and μ
*
>
0. From Lemma 7, it follows that H
′
(
z
*
) is nonsingular. Thus, there exist a closed neighborhood N
(
z
*
) and a constant α
¯
∈
(
0,1
], such that, for any z
∈
N
(
z
*
) and nonnegative integer m satisfying δ
m
∈
(
0
,
α
¯
], the following inequality holds true:
(56)
Ψ
z
k
+
δ
m
Δ
z
k
≤
[
1
-
2
σ
(
1
-
μ
0
γ
-
θ
k
)
δ
m
]
Ψ
(
z
k
)
.
If k is large enough such that m
k
≤
m and δ
m
k
≥
δ
m, then,
(57)
Ψ
z
k
+
1
≤
[
1
-
2
σ
(
1
-
μ
0
γ
-
θ
k
)
δ
m
k
]
Ψ
(
z
k
)
≤
[
1
-
2
σ
(
1
-
μ
0
γ
-
θ
k
)
δ
m
]
Ψ
(
z
k
)
.
Therefore, as k
→
∞, it follows from Ψ
*
>
0 that
(58)
2
σ
(
1
-
μ
0
γ
-
θ
k
)
≤
0
.
It contradicts (
1
-
μ
0
γ
-
θ
k
)
>
0. We conclude that Ψ
(
z
k
)
→
0 and μ
k
→
0.
(iii) By Assumption14, we know that Φ
-
1
(
0
) is nonempty and bounded. Thus, {
z
k
} has at least one accumulation point z
*
=
(
μ
*
,
x
*
) with H
(
z
*
)
=
0 and x
*
∈
S.Theorem 17.
Suppose that Assumption14 is satisfied and z
*
=
(
μ
*
,
x
*
) is an accumulation point of the sequence {
z
k
} generated by Algorithm 8. If all V
∈
∂
H
(
z
*
) are nonsingular, then, {
z
k
} converges to z
* superlinearly; that is, z
k
+
1
-
z
*
=
o
(
z
k
-
z
*
). Moreover, μ
k
+
1
=
o
(
μ
k
).Proof.
By Theorem16, we have H
(
z
*
)
=
0 and x
*
∈
S. Because all V
∈
∂
H
(
z
*
) are nonsingular, it follows that for all z
k sufficiently close to z
*,(59)
H
′
z
k
-
1
=
O
(
1
)
.
From Lemma 7, it follows that H
(
·
) is semismooth at z
*. Hence, for all z
k sufficiently close to z
*, we have
(60)
H
(
z
k
)
-
H
(
z
*
)
-
H
′
(
z
k
)
(
z
k
-
z
*
)
=
o
z
k
-
z
*
.
On the other hand, Lemma 7 implies that H
(
·
) is locally Lipschitz continuous near z
*. Therefore, for all z
k sufficiently close to z
*, we have
(61)
H
(
z
k
)
=
O
z
k
-
z
*
.
Since lim
⁡
k
→
∞
⁡
θ
k
=
0, it is concluded that θ
k
H
(
z
k
)
=
o
z
k
-
z
*. Thus, by the definitions of h
(
z
) and β
(
z
), we have
(62)
h
(
z
k
)
≤
μ
0
β
z
k
+
θ
k
Φ
z
k
≤
μ
0
γ
Ψ
(
z
k
)
+
θ
k
H
z
k
=
o
z
k
-
z
*
.
Then, in view of 59, 60, and 62, it is obtained that
(63)
z
k
+
Δ
z
k
-
z
*
=
z
k
+
H
′
z
k
-
1
[
-
H
(
z
k
)
+
h
(
z
k
)
]
-
z
*
≤
H
′
z
k
-
1
·
H
z
k
-
H
z
*
-
H
′
z
k
z
k
-
z
*
+
h
z
k
=
o
(
z
k
-
z
*
)
.
On the other hand, from61, it follows that
(64)
Ψ
z
k
+
Δ
z
k
=
H
(
z
k
+
Δ
z
k
)
2
=
O
(
z
k
+
Δ
z
k
-
z
*
2
)
=
o
z
k
-
z
*
2
=
o
(
H
z
k
2
)
=
o
Ψ
z
k
.
Thus, as z
k sufficiently close to z
*, we have z
k
+
1
=
z
k
+
Δ
z
k. It yields
(65)
μ
k
+
1
=
μ
k
+
Δ
μ
k
=
μ
0
γ
H
(
z
k
)
2
.
In virtue of 65, we obtain
(66)
μ
k
+
1
μ
k
=
H
(
z
k
)
2
H
(
z
k
-
1
)
2
=
o
Ψ
z
k
-
1
Ψ
(
z
k
-
1
)
.
As z
k sufficiently close to z
*, we know μ
k
+
1
=
o
(
μ
k
). The proof has been completed.


## 5. Numerical Experiments

In this section, we test the numerical performance of Algorithm8 for solving benchmark test problems in NCP.Algorithm8 is implemented in MATLAB2008a on a PC 2.00 GHZ CPU with 2.00 GB RAM with the operation system of Windows 7. Throughout the experiments, the parameters in Algorithm 8 are chosen as follows:
(67)
μ
0
=
0.01
,
σ
=
0.25
,
δ
=
0.85
,
γ
=
0.2
,
θ
k
=
1
4
k
+
1
.
We use H
(
z
k
)
<
1
0
-
8 as the termination criterion.Numerical results are reported in Tables1–9, where we use the following denotations for conciseness:IT: the number of iterations,
ST: the initial pointx
0,
CT: the CPU time depleted by the algorithm,
x
*: a solution of the NCP,
x
k: the final value of x,
o: zero vector with n dimension,
e: unit vector with n dimension,
F: The algorithm fails to get a solution.Table 1
Numerical results of Problem1.
ST
IT
x
k
x
T
y
H
k
CPU
o
4
(
0,0.0000,0
)
4.83
E
-
09
8.38
E
-
09
0.085
e
5
(
0,0.4998,0
)
3.44
E
-
11
3.97
E
-
11
0.103
10
e
6
(
0,1.0000,0
)
1.05
E
-
11
9.09
E
-
12
0.124
-
e
5
(
0,0.0023,0
)
2.09
E
-
09
3.61
E
-
09
0.105
-
10
e
6
(
0,0.0071,0
)
2.49
E
-
11
4.28
E
-
11
0.124
-
100
e
6
(
0,0.0399,0
)
1.50
E
-
09
2.50
E
-
09
0.125Table 2
Numerical results of Problem2.
ST
IT
x
k
x
T
y
H
k
CPU
e
5
(
0.37,0
,
3,0
)
1.27
E
-
08
3.91
E
-
09
0.304
o
5
(
0,0
,
0,0
)
6.59
E
-
11
3.81
E
-
11
0.292
-
2
e
6
(
0.002,0
,
0,0
)
1.32
E
-
08
3.31
E
-
09
0.356
-
11
e
6
(
1.85,0
,
0,0
)
1.06
E
-
08
2.64
E
-
09
0.416
-
20
e
6
(
0.05,0
,
0,0
)
1.38
E
-
08
3.46
E
-
09
0.366Table 3
Numerical results of Problem3.
ST
IT
x
k
x
T
y
H
k
CPU
e
6
x
2
2.99
E
-
08
1.42
E
-
09
0.679
10
e
7
x
2
3.54
E
-
08
1.77
E
-
09
0.729
1
0
2
e
8
x
2
3.02
E
-
08
1.54
E
-
09
0.877
1
0
3
e
9
x
1
1.07
E
-
08
9.99
E
-
09
0.965Table 4
Solution of Problem4 with random initial points.
ST
IT
x
T
y
H
k
CPU
e
18
8.52
E
-
10
1.49
E
-
10
5.539
o
22
2.50
E
-
10
4.38
E
-
11
6.538
-
e
38
3.41
E
-
09
5.96
E
-
10
11.306
rand
(
5,1
)
16
4.20
E
-
10
7.35
E
-
11
4.796Table 5
Numerical results of Problem5.
ST
IT
x
T
y
H
k
CPU
o
6
1.38
E
-
08
4.97
E
-
09
0.858
e
7
5.21
E
-
09
1.89
E
-
09
1.109
-
e
7
1.32
E
-
08
4.77
E
-
09
1.003
-
10
e
7
1.32
E
-
08
4.77
E
-
09
0.990
-
1
0
2
e
8
1.32
E
-
08
4.76
E
-
09
1.142
-
1
0
3
e
8
1.32
E
-
08
4.76
E
-
09
1.079
-
1
0
4
e
9
1.40
E
-
08
2.47
E
-
09
1.268Table 6
Numerical results of Problem6.
ST
IT
x
T
y
H
k
CPU
e
7
4.01
E
-
11
1.39
E
-
11
0.248
10
e
9
8.61
E
-
09
2.97
E
-
09
0.358
1
0
2
e
10
1.13
E
-
09
3.91
E
-
10
0.316
1
0
3
e
9
2.45
E
-
09
8.48
E
-
10
0.359
-
e
8
2.46
E
-
11
8.51
E
-
12
0.294
-
10
e
15
9.46
E
-
12
3.28
E
-
12
0.504
-
1
0
3
e
24
8.96
E
-
10
3.10
E
-
10
0.759Table 7
Numerical results of Problem7.
n
IT
x
T
y
H
k
CPU
128
8
1.30
E
-
10
1.48
E
-
09
0.040
256
8
1.15
E
-
10
1.90
E
-
09
0.155
512
9
1.55
E
-
11
3.50
E
-
10
1.010
800
10
1.99
E
-
11
6.44
E
-
10
2.701
1000
10
1.58
E
-
11
4.99
E
-
10
4.738Table 8
Effect of inexact parameter in Problem3.
ST
θ
k
IT
x
T
y
H
k
CPU
e
0
6
7.95
E
-
09
3.89
E
-
10
0.70
0.2
6
1.46
E
-
08
7.27
E
-
10
0.66
0.4
7
1.30
E
-
09
8.41
E
-
11
0.73
0.6
9
4.77
E
-
09
4.60
E
-
10
0.91
0.8
13
7.14
E
-
08
4.05
E
-
09
1.33
10
^
2
e
0
F
F
F
F
0.2
8
2.97
E
-
08
1.52
E
-
09
0.92
0.4
10
4.25
E
-
12
1.71
E
-
12
1.12
0.6
10
8.98
E
-
09
1.43
E
-
09
1.01
0.8
15
3.66
E
-
08
6.99
E
-
09
1.57Table 9
Effect of inexact parameter in Problem6.
ST
θ
0
IT
x
T
y
H
k
CPU
e
0
6
2.01
E
-
09
6.78
E
-
10
0.22
0.2
6
1.18
E
-
08
4.06
E
-
09
0.22
0.4
7
7.50
E
-
11
4.66
E
-
11
0.27
0.6
9
1.32
E
-
11
1.99
E
-
10
0.27
0.8
13
9.29
E
-
09
7.16
E
-
09
0.39
10
e
0
F
F
F
F
0.2
8
9.13
E
-
09
3.15
E
-
09
0.28
0.4
10
9.03
E
-
11
3.11
E
-
11
0.34
0.6
11
7.19
E
-
12
4.06
E
-
11
0.36
0.8
14
8.25
E
-
09
9.51
E
-
09
0.44The test problems are from the literature (see, e.g., [22, 27, 28]).Problem 1.
In problem1, x
∈
R
3 and F
(
x
)
:
R
3
→
R
3 is given by
(68)
F
(
x
)
=
x
2
x
3
-
x
2
+
x
3
+
1
.This problem has infinitely many solutions(
0
,
λ
,
0
), where λ
∈
[
0,1
]. The test results are listed in Table 1 by using different initial points.Problem 2 (modified Mathiesen problem).
In problem1, x
∈
R
4 and F
(
x
)
:
R
4
→
R
4 is given by
(69)
F
(
x
)
=
-
x
2
+
x
3
+
x
4
x
1
-
(
4.5
x
3
+
2.7
x
4
)
(
x
2
+
1
)
5
-
x
1
-
(
0.5
x
3
+
0.3
x
4
)
(
x
3
+
1
)
3
-
x
1
.This problem has infinitely many solutions(
λ
,
0,0
,
0
), where λ
∈
[
0,3
]. The solutions are degenerate for λ
=
0 or λ
=
3 and nondegenerate for λ
∈
(
0,3
). With different starting points, we report results in Table 2.Problem 3 (Kojima-Shindo problem).
In problem1, x
∈
R
4 and F
(
x
)
:
R
4
→
R
4 is given by
(70)
F
(
x
)
=
3
x
1
2
+
2
x
1
x
2
+
2
x
2
2
+
x
3
+
3
x
4
-
6
2
x
1
2
+
x
1
+
x
2
2
+
10
x
3
+
2
x
4
-
2
3
x
1
2
+
x
1
x
2
+
2
x
2
2
+
2
x
3
+
9
x
4
-
9
x
1
2
+
x
2
2
+
2
x
3
+
3
x
4
-
3
.This problem has one degenerate solutionx
1
=
6
/
2
,
0,0
,
1
/
2
T and one nondegenerate solution x
2
=
(
1,0
,
3,0
)
T. We use different initial points and the test results are listed in Table 3.Problem 4.
In problem1, x
∈
R
5 and F
(
x
)
=
(
F
1
(
x
)
,
…
,
F
5
(
x
)
)
T where
(71)
F
i
x
=
2
exp
⁡
∑
i
=
1
5
‍
x
i
-
i
+
2
2
x
i
-
i
+
2
,
i
=
1
,
…
,
5
.This problem has one solution(
0,0
,
1,2
,
3
). We use different starting points and the last initial point x
0 is randomly generated whose elements are in the interval (
0,1
). The test results are listed in Table 4.Problem 5.
In problem1, x
∈
R
7 and F
(
x
)
:
R
7
→
R
7 is given by
(72)
F
(
x
)
=
2
x
1
-
x
3
+
x
5
+
3
x
6
-
1
x
2
+
2
x
5
+
x
6
-
x
7
-
3
-
x
1
+
2
x
3
+
x
4
+
x
5
+
2
x
6
-
4
x
7
+
1
x
3
+
x
4
+
x
5
-
x
6
-
1
-
x
1
-
2
x
2
-
x
3
-
x
4
+
5
-
3
x
1
-
x
2
-
2
x
3
+
x
4
+
4
x
2
+
4
x
3
-
1.5
.The test results are listed in Table5 by using different initial points.Problem 6.
In problem1, x
∈
R
4 and F
(
x
)
:
R
4
→
R
4 is given by
(73)
F
(
x
)
=
x
1
3
-
8
x
2
-
x
3
+
x
2
3
+
3
x
2
+
x
3
+
2
x
3
3
-
3
x
4
+
2
x
4
3
.
In this problem, F
(
x
) is a P
0-function. It has only one solution (
2,0
,
1,0
). With different initial points, the results are listed in Table 6.Problem 7.
In problem1, x
∈
R
n and F
(
x
)
=
M
x
+
q with
(74)
M
i
i
=
4
i
-
1
+
1
,
i
=
1,2
,
…
,
n
,
M
i
j
=
M
i
i
+
1
,
i
=
1,2
,
…
,
n
-
1
,
j
=
i
+
1
,
…
,
n
,
M
j
i
=
M
j
j
+
1
,
j
=
1,2
,
…
,
n
-
1
,
i
=
j
+
1
,
…
,
n
,
q
=
-
1
,
-
1
,
…
,
-
1
T
.This problem has only solutionsx
*
=
(
1,0
,
…
,
0
)
T. From the initial point x
0
=
(
1,1
,
…
,
1
)
T, we solve this problem with different dimensions. The test results are listed in Table 7.In the end of this section, we intend to test the effect of the inexact parameterθ
k on the efficiency of Algorithm 8.In Tables8 and 9, for Problems 3 (not a P
0-function) and 6, we take different values of θ
k, θ
k
=
0,0.2,0.4,0.6,0.8, and implement Algorithm 8 to find the solutions of Problems 3 and 6, respectively.From Tables8 and 9, it is revealed that, for θ
k
=
0 (which corresponds to the smoothing exact Newton method), Algorithm 8 may fail for some initial points. On the other hand, a suitable value of inexact parameter may greatly improve the efficiency of Algorithm 8.From the numerical results, we conclude as follows:(1)
In Tables1–7, the choice of initial point only incurs weak impact on the CPU time and the iteration number of Algorithm 8. It indicates that the developed algorithm in this paper is robust even if for the randomly generated initial point.
(2)
From the results in Tables8 and 9, the inexact parameter θ
k may play critical role in improve the numerical performance of Algorithm 8.


## 6. Final Remarks

In this paper, a smoothing inexact Newton method has been proposed for solving nonlinear complementarity problems based on a new smoothing function. Then, an implementable algorithm was developed. Under a suitable assumption, the global convergence and the superlinear convergence have been established for the algorithm. Results of numerical experiments indicate that our algorithm is effective for the benchmark test problems available in the literature.



---

*Source: 731026-2015-04-15.xml*