# Generalized Newton Method for a Kind of Complementarity Problem

Authors: Shou-qiang Du
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

A generalized Newton method for the solution of a kind of complementarity problem is given. The method is based on a nonsmooth equations reformulation of the problem byF-B function and on a generalized Newton method. The merit function used is a differentiable function. The global convergence and superlinear local convergence results are also given under suitable assumptions. Finally, some numerical results and discussions are presented.


---

## Body

## 1. Introduction

This paper considers a kind of complementarity problem:(1)F(x)≥0,G(x)≥0,〈F(x),G(x)〉=0,
where F:Rn→Rn,G:Rn→Rn are two differentiable functions. Equation (1) is also denoted by GCP(F, G) in [1]. When G(x)=x, (1) reduces to the nonlinear complementarity problem, which is a general framework for optimality conditions of nonlinear optimization problems as well as some problems arising in different fields. In the past few years, several theoretical and computational results for complementarity have been established, such as [1–12]. The method is based on semismooth equations reformulation of (1). As we know, Newton-type methods are one of the fastest methods for the solution of equations and nonsmooth equations. But the methods are usually only locally convergent. In recent years, some research work has been devoted to techniques for globalizing the local methods. So, in this paper, we are interested in solving (1) by a Newton based method. The method is based on a line search and a semismooth equations reformulation of (1).This paper is organized as follows. In the next section, (1) is converted into a semismooth equation. Then, a generalized Newton method for solving the reformulation is introduced. The global convergence and the local superlinear convergence of the method are also presented. In the Section 3, numerical experimental results and some discussions are listed.


## 2. Preliminaries and Method

Firstly, we introduce some notations and propositions used in the paper (see for instance [1–5]). Given H:Rn→Rn, we use H′(x) to denote its Jacobian at x. If H is locally Lipschitzian and DH denote the set of differentiable points, theB-subdifferential and Clarke general Jacobian of H at x are defined as
(2)∂BH(x)={V∈Rm×n∣∃{xk}⊂DH:{xk}⟶x,H′(xk)⟶V};∂H(x)=conv{V∈Rm×n∣∃{xk}⊂DH:{xk}⟶x,H′(xk)⟶V}.LetH:Rn→Rn be a locally Lipschitz function. If the following limit,
(3)lim⁡V∈∂H(x+th′)h′→h,t→0+Vh′,
exists for any h∈Rn, H is said to be semismooth at x.Proposition 1.
IfH(x) is semismooth at x, the following equations are equivalent. (a)
Whenh→0,
(4)Vh-H′(x;h)=o(∥h∥).(b)
WhereV∈∂H(x+h),
(5)lim⁡x+h∈DH,h→0H′(x+h;h)-H′(x;h)∥h∥=0.Definition 2.
M
∈
R
n
×
n is called a P-matrix if its principal minors are all positive and a P0-matrix if its principal minors are all nonnegative.Definition 3.
H is called SC1 function if H is continuously differentiable and its gradient is semismooth.Definition 4.
H is BD-regular at x if ∀V∈∂BH(x) are nonsingular.In the following, we give the reformulation of (1) and the generalized Newton method. Based on theF-B function
(6)ϕ(a,b)=a2+b2-(a+b),
we consider the following reformulation of (1):
(7)φ(x)=(ϕ(F1,G1)⋮ϕ(Fn,Gn))=0.xsolves (1) ⇔x solves (7). Denoting
(8)Ω={x∈Rn∣(Fi(x))2+(Gi(x))2>0,i=1,…,n},
we know that φ is locally Lipschitz on Rn and differentiable on Ω. When x∈Ω, we have
(9)∇φ(x)=diag⁡(γi(x))∇F(x)+diag⁡(μi(x))∇G(x),
where γi(x)=Fi(x)(Fi2(x)+Gi2(x))1/2-1,μi(x)=Gi(x)(Fi2(x)+Gi2(x))1/2-1,i=1,…,n. We also know that
(10)(γi(x)+1)2+(μi(x)+1)2=1,i=1,…,n;μi(x)=-1,γi(x)=0⟺Fi(x)>0,Gi(x)=0,hhhhhhhhhhhhhhhhhhhhhhhhhhi=1,…,n;μi(x)=0,γi(x)=-1⟺Fi(x)=0,Gi(x)>0,hhhhhhhhhhhhhhhhhhhhhhhhhhi=1,…,n.Whenx is not in Ω, for V∈∂φ(x), we have
(11)V=diag⁡(γi(x))∇F(x)+diag⁡(μi(x))∇G(x),
where (γi(x)+1)2+(μi(x)+1)2≤1,i=1,…,n.Then, for∀x, we have
(12)(γi(x)+1)2+(μi(x)+1)2≤1,i=1,…,n.Defining a merit function as(13)Ψ(x)=12∥φ(x)∥2,
then solving (1) is equivalent to solving the following unconstrained minimization problem:
(14)min⁡x∈RnΨ(x),
where Ψ is continuously differentiable. We know that ∇Ψ(x)=VTφ(x), where V∈∂φ(x). Now, we give the following generalized Newton method for solving (1).Method 1 (generalized Newton method).
Givenx0∈Rn and ρ>0,p>2,β∈(0,1/2), ϵ≥0.
Step 1. If ∥∇Ψ(xk)∥≤ϵ, stop.
Step 2. Choose Vk∈∂φ(xk) and compute dk of the equation
(15)Vkd+φ(xk)=0.If the condition(16)∇Ψ(xk)Tdk+ρ∥dk∥p≤0
is not satisfied, set dk=-(Vk)Tφ(xk).Step 3. Find the smallest integer ik such that
(17)Ψ(xk)+(1-β)2-ik∇Ψ(xk)Tdk≤Ψ(xk+2-ikdk)≤Ψ(xk)+β2-ik∇Ψ(xk)Tdk.Setxk+1=xk+2-ikdk, let k:=k+1, and go to Step 1.The direction obtained by solving (15) is a descent direction for the function Ψ. This is a standard property of Newton method for the solution of a smooth equation. But it is no longer true for nonsmooth equations. In the above method, the direction obtained by solving (15) is a descent direction by the fact that ∇Ψ(xk)Tdk=-∥φ(xk)∥2. On the other hand, as we know, dk is not unique in (15) if Vk is not nonsingular. So, we will give the following proposition to ensure Vk is nonsingular.Proposition 5.
Suppose thatF,G given by (1) satisfy di∇Fi(x)d≥γ¯∥d∥2,di∇Gi(x)d≥γ¯∥d∥2, for any x∈Rn,d∈Rn,γ¯>0 and i=1,…,n; then ∀V∈∂φ(x) is nonsingular.Proof.
Let∀V∈∂φ(x) and let d solve Vd=0. By the above analysis of V, for constants γi,μi,i=1,…,n, we have
(18)diag⁡(γi(x))∇F(x)d+diag⁡(μi(x))∇G(x)d=0,hhhhhhhhhhhhhhhhhhhhhhhhhhhi=1,…,n,
and so we have
(19)μ1∇G1(x)d+γ1∇F1(x)d=0,⋮μn∇Gn(x)d+γn∇Fn(x)d=0.
Multiplying theith equation in the above equations by di, we get
(20)d1μ1∇G1(x)d+d1γ1∇F1(x)d=0,⋮dnμn∇Gn(x)d+dnγn∇Fn(x)d=0.
Ifγi=0,i=1,…,n, by (12), we have 1+(μi+1)2≤1. So,
(21)0≤(μi+1)2≤0,
and then
(22)μi=-1,i=1,…,n.
We have(23)-di∇Gi(x)d=0,i=1,…,n,0=-di∇Gi(x)d≤-γ¯∥d∥2≤0,i=1,…,n.
Thend=0. On the other hand, if γi≠0,i=1,⋯,n, we have
(24)di∇Fi(x)d=-μiγi(di∇Gi(x)d)≤-μiγiγ¯∥d∥2≤0,hhhhhhhhhhhhhhhhhhhhi=1,…,n.
Bydi∇Fi(x)d≥γ¯∥d∥2≥0, we get
(25)0≤γ¯∥d∥2≤0.
Thend=0 and the nonsingularity of V follows. This completes the proof.Ψ may have a global minimum x⋆ with Ψ(x⋆)>0 when (1) has no solution. Another point which is worth concern is that the conditions of a stationary point of Ψ are a solution of (1). Similar to [1], we give the conditions, which guarantee that every stationary point of Ψ is a solution of (1).Proposition 6.
If (1) has a nonempty solution set, then x⋆ is a solution of (1) ⇔Ψ(x⋆)=0.Proposition 7.
Ifx⋆ is a stationary point of  Ψ such that G′(x⋆) is nonsingular and F′(x⋆)G′(x⋆)-1 is a P0 matrix, then x⋆ is a solution of (1).Now, we give the global convergence theorem for Method1.Theorem 8.
Suppose that the sequence{xk} is generated by Method 1. Then each accumulation point of the sequence {xk} is a stationary point of  Ψ.Proof.
The following proof is given by two parts.
Part I. If, for an infinite set of indices K, we have dk=-(Vk)Tφ(xk), then, by Proposition 1.16 in [7], we know that any limit point of {xk} is a stationary point of Ψ.
Part II. We assume that the direction is always computed by (15). Suppose that {xk}→x⋆ and ∇Ψ(x⋆)≠0. By (15), we have
(26)∥φ(xk)∥=∥Vkdk∥≤∥Vk∥∥dk∥.
From (26), we get
(27)∥dk∥≥∥φ(xk)∥∥Vk∥.
Form>0 and M>0, we know that
(28)0<m≤∥dk∥≤M.
If{∥dk∥}K1→0 for k in K1. For Vk which is bounded and (27), we get Ψ(x⋆)=0, which is contradicting the assumption. On the other hand, taking into account that ∇Ψ(xk) is bounded and (16), ∥dk∥ cannot be unbounded. Because of (17) and the fact that Ψ is a continuously differentiable function, we have
(29){2-ik∇Ψ(xk)Tdk}⟶0,(k⟶∞).
In the following, we will prove that2-ik is bounded away from 0. Supposing the contrary,
(30)Ψ(xk+2-(ik-1)dk)-Ψ(xk)2-(ik-1)>β∇Ψ(xk)Tdk.
By (28), we can assume that {dk}→d¯,d¯≠0. Taking limit of both sides of (30), we have
(31)∇Ψ(x⋆)Td¯≥β∇Ψ(x⋆)Td¯.
From (16), we know ∇Ψ(x⋆)Td¯<0, which contradicts (31). So, we know that 2-ik is bounded away from 0. On the other hand, (16) and (29) imply that {dk}→0 and this contradicts (28). This completes the proof.In the following part of this section, we will discuss the local superlinear convergence of Method1.Remark 9.
Suppose that the sequence{xk} is generated by Method 1. If one of the limit points of the sequence {xk} is x⋆, which is a solution of (1), and x⋆ is a BD-regular solution of φ(x)=0, then, we can prove locally that the direction is always the solution of (15) and eventually the step size of one satisfies (17). So the method eventually reduces to the local method xk+1=xk+(Vk)-1φ(xk),Vk∈∂Bφ(xk).Theorem 10.
Let the BD-regular condition hold at an accumulation pointx⋆ of the sequence {xk} generated by Method 1. Then {xk} converges to x⋆ Q-superlinearly. The rate of convergence is Q-quadratic if F and G are SC1 functions.Proof.
Sincex⋆ is an accumulation point of {xk}, there exists a subsequence {xk}k∈K such that xk→x⋆,k∈K. We know xk+1=xk+(Vk)-1φ(xk) for all k sufficiently large. Therefore, the results of this theorem are guaranteed by Theorem 3.1 in [8].Remark 11.
In Method1, (17) can be replaced by the following line search:
(32)Ψ(xk+2-ikdk)≤max⁡0≤j≤m(k)Ψ(xk-j)+β2-ik∇Ψ(xk)Tdk,
where m(0)=0 and m(k)=min⁡{m(k-1)+1,M0}, and M0>0 is a integer.


## 3. Numerical Results and Discussions

In this section, we present some numerical results and also give some discussions about a method for calculating a generalized Jacobian ofφ. For solving the systems of (7), we can take ∂⋆ as a tool instead of the Clarke generalized Jacobian andB-differential. We give the following ∂⋆φ(x) for φ in (7):
(33)∂⋆φ(x)={(∂φ1(x),…,∂φn(x))T,x∈Rn},
where ∂φi(x)=∇Fi(x), if Fi(x)<Gi(x), ∂φi(x)=∇Fi(x) or ∂φi(x)=∇Gi(x) if Fi(x)=Gi(x), and ∂φi(x)=∇Gi(x), if Fi(x)>Gi(x).Proposition 12.
Suppose thatφ(x) and ∂⋆φ(x) are defined by (7) and by (33); then all V∈∂⋆φ(x) are nonsingular.Example 13.
We consider the generalized complementarity problem (1), where the functions
(34)F(x1,x2)=(x12,x22)T,G(x1,x2)=(x12+10,x22+1)T.
BothF and G are R2→R2 continuously differentiable functions.
We use Method1 to compute Example 13. Results for Example 13 with initial points x0=(10,1)T,x0=(100,100)T,x0=(1000,10000)T,x0=(100000,100000)T and x0=(10000000,10000000)T,ϵ=10-4 are presented in Table 1.Table 1
Step
Ψ
(
x
)
x
0
=
(
10
,
1
)
T
16
9.797290497304267
e
-
005
x
0
=
(
100
,
100
)
T
22
8.832183027429608
e
-
005
x
0
=
(
1000
,
10000
)
T
48
9.248483401180785
e
-
005
x
0
=
(
100000
,
100000
)
T
32
8.742500968894618
e
-
005
x
0
=
(
10000000
,
10000000
)
T
37
9.944195523003963
e
-
005In Method1, if we replace (17) by (32), we also can use this method to compute Example 13. Results for Example 13 with initial points x0=(10,1)T,x0=(1000,10000)T,x0=(100,100)T,x0=(100000,100000)T and x0=(10000000,10000000)T,ϵ=10-4 are presented in Table 2.Table 2
Step
Ψ
(
x
)
x
0
=
(
10
,
1
)
T
16
9.172858713357712
e
-
005
x
0
=
(
1000
,
10000
)
T
24
9.291914775655386
e
-
005
x
0
=
(
100
,
100
)
T
20
9.773252141220823
e
-
005
x
0
=
(
100000
,
100000
)
T
30
9.700029527337506
e
-
005
x
0
=
(
10000000
,
10000000
)
T
37
8.943237635050672
e
-
005Discussion 1.
From the numerical results for Method1 in Tables 1 and 2, we can see that (17) work as well as (32). So we can use (17) or (32) in practice.
In Method1, we also can replace (15) by (35) or (36). Then Method 1 becomes the Levenberg-Marquardt method and the modified Levenberg-Marquardt method, which were given in [4, 10]. dk was computed by
(35)((Vk)TVk+σkI)d=-(Vk)Tφ(xk),Vk∈∂φ(x)
or
(36)((Vk)TVk+diag⁡(λi(k)φi(xk)))d=-(Vk)Tφ(xk),Vk∈∂φ(x).We use Method1 (dk was computed by (15)), the Levenberg-Marquardt method (dk was computed by (35)), and the modified Levenberg-Marquardt method (dk was computed by (36)) to compute Example 13. Results for Example 13 with initial points x0=(1,1)T and x0=(10,10)T are presented in Table 3.Table 3
x
0
=
(
1
,
1
)
T
Step (dk was computed by (12))
Ψ
(
x
)
16
9.441173879087828
e
-
005
x
0
=
(
1
,
1
)
T
Step (dk was computed by (35))
Ψ
(
x
)
22
9.162651686955847
e
-
005
x
0
=
(
1
,
1
)
T
Step (dk was computed by (36))
Ψ
(
x
)
42
9.397247497289207
e
-
005
x
0
=
(
10
,
10
)
T
Step (dk was computed by (12))
Ψ
(
x
)
18
8.575708886859879
e
-
005
x
0
=
(
10
,
10
)
T
Step (dk was computed by (35))
Ψ
(
x
)
21
9.313859056403473
e
-
005
x
0
=
(
10
,
10
)
T
Step (dk was computed by (36))
Ψ
(
x
)
24
9.637003553941703
e
-
005Discussion 2.
From the numerical results for the Method1 (dk was computed by (15)), the Levenberg-Marquardt method (dk was computed by (35)), and the modified Levenberg-Marquardt method (dk was computed by (36)) in Table 3, we can see that our method in this paper works quite better than the methods in [4, 10].
From Discussion1, we can see that (17) work as well as (32). When we use line search (32) to replace (17), we give the following numerical results for Method 1 (dk was computed by (15)), the Levenberg-Marquardt method (dk was computed by (35)), and the modified Levenberg-Marquardt method (dk was computed by (36)) to compute Example 13. The numerical results are given in Table 4.Table 4
x
0
=
(
1
,
1
)
T
Step (dk was computed by (12))
Ψ
(
x
)
14
9.696887098398221
e
-
005
x
0
=
(
1
,
1
)
T
Step (dk was computed by (35))
Ψ
(
x
)
21
9.401294082644895
e
-
005
x
0
=
(
1
,
1
)
T
Step (dk was computed by (36))
Ψ
(
x
)
22
9.162651686955847
e
-
005



---

*Source: 745981-2014-04-27.xml*