# A Superlinearly Convergent Method for the Generalized Complementarity Problem over a Polyhedral Cone

Authors: Fengming Ma; Gang Sheng; Ying Yin
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Making use of a smoothing NCP-function, we formulate the generalized complementarity problem (GCP) over a polyhedral cone as an equivalent system of equations. Then we present a Newton-type method for the equivalent system to obtain a solution of the GCP. Our method solves only one linear system of equations and performs only one line search at each iteration. Under mild assumptions, we show that our method is both globally and superlinearly convergent. Compared to the previous literatures, our method has stronger convergence results under weaker conditions.


---

## Body

## 1. Introduction

The generalized complementarity problem, denoted by GCP, is to find a vectorx*∈Rn such that
(1)F(x*)∈𝒦,G(x*)∈𝒦∘,F(x*)⊤G(x*)=0,
where F and G are continuous functions from Rn to Rm, 𝒦 is a nonempty closed convex cone in Rm, and 𝒦∘ denotes the polar cone of 𝒦.This problem has many interesting applications and its solution using special techniques has been considered extensively in the literature. See [1–3] and references therein. In particular, if 𝒦=R+n and G(x)=x, then the GCP reduces to the classical nonlinear complementarity problem [4]. Furthermore, the GCP is closely related to the variational inequality problem in the sense that x* is a solution of GCP if and only if F(x*) is a solution of VI(G∘F-1,𝒦) if F is invertible (see Lemma  6 in [5]).To solve the GCP, one usually reformulates it as a minimization problem over a simple set or an unconstrained optimization problem; see [3] for the case that 𝒦 is a general cone and see [1, 2] for the case that 𝒦=R+n. The conditions under which a stationary point of the reformulated optimization is a solution of GCP were provided in this literature.In this paper, we consider the case thatm=n, F and G are both continuously differentiable on Rn, and 𝒦 is a polyhedral cone in Rn; that is, there exist A∈Rs×n,B∈Rt×n such that
(2)𝒦={u∈Rn∣Au≥0,Bu=0},
where s and t are both positive integers. It is easy to verify that its polar cone 𝒦∘ has the following representation:
(3)𝒦∘={v∈Rn∣v=ATλ1+BTλ2,λ1≥0,λ1∈Rs,λ2∈Rt}.Obviously, ifA is an identity matrix and B=0, then this version of the GCP reduces to the case considered in [2].From now on, the GCP is specialized over a polyhedral cone.For the GCP, Wang et al. and Zhang et al. [6, 7], respectively, established some constrained or unconstrained optimization reformulation for the case F and G are both linear functions and gave some Newton-type method for the problem. Later, Ma et at. [8] established a potential reduction method for the same case.In this paper, we give a new smoothing Newton method for solving the GCP based on a smoothing NCP-function. This method is proved to be convergent globally and superlinearly under suitable assumptions. Furthermore, the method needs only to solve one linear system of equations and perform one line search per iteration.The rest of this paper is organized as follows. In Section2, we give some preliminaries and results of a smoothing NCP-function based on the Fischer-Burmeister function. In Section 3, we present a one-step smoothing Newton method for the GCP and state some preliminary results. In Section 4, we establish the global and superlinear convergence of the proposed method. Conclusions are given in Section 5.To end this section, we will give some notations used in this paper. All vectors are column ones. The inner product of vectorsx,y∈Rn is denoted by xTy. For convenience, vector (xT,yT)T is denoted by (x,y), where x,y are both column vectors. Let ∥·∥ denote the Euclidean norm of a vector or a matrix. For vector u∈Rn, Du=diag(u) denotes the diagonal matrix with the ith diagonal element being ui. Vector e denotes the vector of all ones whose dimension is defined by the context of its use.


## 2. Preliminaries

To establish our method for the solution of the GCP, we now formulate the GCP as a system of equations via the following smoothing NCP-function based on the Fischer-Burmeister function [9]:
(4)ϕ(μ,a,b)={a+b-a2+b2,ifa2+b2≥μ,a+b-a2+b22μ-μ2,ifa2+b2<μ,
where μ>0 is a smoothing parameter. By simple calculation, we have
(5)ϕμ′(μ,a,b)={0ifa2+b2≥μ,a2+b22μ2-12ifa2+b2<μ,ϕa′(μ,a,b)={1-aa2+b2ifa2+b2≥μ,1-aμifa2+b2<μ,ϕb′(μ,a,b)={1-ba2+b2ifa2+b2≥μ,1-bμifa2+b2<μ.The smoothing NCP-function possesses a few nice properties [10].Lemma 1.
The NCP-functionϕ(μ,a,b) defined by (4) has the following properties:(i)
for any(μ,a,b)∈R++×R2, one has
(6)limμ→0ϕ(μ,a,b)=ϕFB(a,b),
where ϕFB(a,b)=a+b-a2+b2, a basic property of which is that ϕFB(a,b)=0⇔a≥0,b≥0,ab=0;(ii)
for anyμ1,μ2∈R++, one has |ϕ(μ1,a,b)-ϕ(μ2,a,b)|<|μ1-μ2|;(iii)
for any(μ,a,b)∈R++×R2, one has 0<ϕa′(μ,a,b)<2,0<ϕb′(μ,a,b)<2;(iv)
let{ak},{bk} be any two sequences such that ak,bk→+∞ or ak→-∞ or bk→-∞. Then, for any μ∈R++, one has limk→∞|ϕ(μ,ak,bk)|=+∞.From Lemma1, we can find that the function ϕ(μ,a,b) is indeed a smoothing approximation function of the Fischer-Burmeister function ϕFB(a,b).For the GCP, we have the following equivalent statements:xis a solution of the GCP,⇔F(x)∈𝒦,G(x)∈𝒦∘, and F(x)TG(x)=0,⇔ there existλ1∈Rs,λ2∈Rt, such thatAF(x)≥0,BF(x)=0,G(x)=ATλ1+BTλ2,λ1≥0,F(x)TG(x)=0,⇔ there existλ1∈Rs,λ2∈Rt, such thatAF(x)≥0,λ1≥0,(λ1)TAF(x)=0,BF(x)=0,G(x)-ATλ1-BTλ2=0.Letz:=(μ,x,λ1,λ2)∈R++×Rn×Rs×Rt and define a vector-valued function H:R++×Rn+s+t→Rn+s+t+1 as follows:
(7)H(z):=H(μ,x,λ1,λ2):=(eμ-1Φ(μ,λ1,AF(x))BF(x)G(x)-ATλ1-BTλ2),
where
(8)Φ(μ,λ1,AF(x))=(ϕ(μ,[λ1]1,[AF(x)]1)ϕ(μ,[λ1]2,[AF(x)]2)⋮ϕ(μ,[λ1]s,[AF(x)]s)).Then, by Lemma1, the following result is straightforward.Theorem 2.
x is a solution of the GCP if and only if there exist λ1∈Rs,λ2∈Rt such that
(9)H(z)=0.Theorem2 means that the GCP is equivalent to an equation system in the sense that their solution sets are coincident.By (5)–(7), it is not difficult to see that the Jacobian of H(z) has the following form:
(10)H′(z)=(eμ000vec{v}DaAF′(x)Db00BF′(x)000G′(x)-AT-BT),
where
(11)vec{v}≔(ϕμ′(μ,[λ1]1,[AF(x)]1),ϕμ′(μ,[λ1]2,[AF(x)]2),…,ϕμ′(μ,[λ1]s,[AF(x)]s))T,Da:=diag(a1(z),a2(z),…,as(z)),ai(z)={1-[AF(x)]i[λ1]i2+[AF(x)]i2i∉α(z),1-[AF(x)]iμi∈α(z),Db:=diag(b1(z),b2(z),…,bs(z)),bi(z)={1-[λ1]i[λ1]i2+[AF(x)]i2i∉α(z),1-[λ1]iμi∈α(z),α(z)={i∈{1,2,…,s}∣[λ1]i2+[AF(x)]i2<μ}.And for the functionsH and Φ, they have the following nice properties.Lemma 3.
LetH and Φ be defined by (7) and (8), respectively. Then(i)
Φ is continuously differentiable at any z∈R++×Rn+s+t,(ii)
H is continuously differentiable at any z∈R++×Rn+s+t with its Jacobian H′(z) being defined by (10). If matrix B has full row rank and G′(x)[F′(x)]-1 is positive definite, then H′(z) is nonsingular on R++×Rn+s+t.Proof.
From Lemma1, it is not difficult to see that Φ is continuously differentiable at any z∈R++×Rn+s+t.
Next we prove (ii). It follows from the definition ofH and (i) that H is continuously differentiable on R++×Rn+s+t. And by simple calculation, we obtain the Jacobian H′(z) defined by (10). Now we prove the nonsingularity of H′(z).
Sinceμ>0, it follows that eμ>1. And thus we know that to prove the nonsingularity of H′(z), it is sufficient to prove the nonsingularity of D:=(DaAF′(x)Db0BF′(x)00G′(x)-AT-BT).
SinceF′(x) is nonsingular, we make the following transformation to D without changing its rank:
(12)D(F′(x)-100-Db-1DaAIs000It)=(0Db0B00G′(x)F′(x)-1+ATDb-1DaA-AT-BT).
Since Db is nonsingular, to prove the nonsingularity of D, it suffices to show the nonsingularity of the following submatrix of it:
(13)(B0G′(x)F′(x)-1+ATDb-1DaA-BT).
Let
(14)(B0G′(x)F′(x)-1+ATDb-1DaA-BT)(d1d2)=0,
where d1∈Rn,d2∈Rt. Then we obtain,
(15)Bd1=0(G′(x)F′(x)-1+ATDb-1DaA)d1-BTd2=0.
That is,
(16)d1=(G′(x)F′(x)-1+ATDb-1DaA)-1BTd2,B(G′(x)F′(x)-1+ATDb-1DaA)-1BTd2=0.
Since G′(x)F′(x)-1 is positive definite and ATDb-1DaA is semipositive definite, it holds that (G′(x)F′(x)-1+ATDb-1DaA)-1 is also positive definite. Premultiplying (16) by d2T yields
(17)(BTd2)T(G′(x)F′(x)-1+ATDb-1DaA)-1(BTd2)=0.
Noting that (G′(x)F′(x)-1+ATDb-1DaA)-1 is positive definite and B has full row rank, we obtain d2=0, and thus d1=0. Hence, we complete the proof.


## 3. Algorithm and Preliminaries

In this section we propose our smoothing Newton method for theGCP.Letγ∈(0,1). Define the following real-valued functions θ,ρ:R++×Rn+s+t→R+ by
(18)θ(z)=∥H(z)∥2,ρ(z)=γmin{1,∥H(z)∥,θ(z)}.
And for convenience, let zk=(μk,xk,λ1k,λ2k) in what follows.Algorithm 4.
Consider the following.Step 1.
Choose parametersδ∈(0,1),σ∈(0,1/2),μ0>0, and γ∈(0,1) such that γμ0<1/2. Let μ-:=(μ0,0)∈R++×Rn+s+t and let z0 be an arbitrary initial point. Set k:=0.Step 2.
If||H(zk)||=0, stop; otherwise, compute ρk:=ρ(zk).Step 3.
ComputeΔzk:=(Δμk,Δxk,Δλ1k,Δλ2k)∈Rn+s+t+1by
(19)H(zk)+H′(zk)Δzk=ρkμ-eμk.Step 4.
Letτk=δmk, where mk is the smallest nonnegative integer m such that
(20)θ(zk+δmΔzk)-θ(zk)≤-2σ(1-2γμ0)δmθ(zk).Step 5.
Letzk+1:=zk+τkΔzk,k:=k+1; go to Step 2.The following theorem shows that Algorithm4 is well defined and generates an infinite sequence with some good features. Define the set
(21)Ω:={z=(μ,x,λ1,λ2)∈R++×Rn+s+t∣μ≥ρ(z)μ0}.Theorem 5.
Letz0=(μ0,x0,λ10,λ20)∈R++×Rn+s+t be given in Algorithm 4. Then Algorithm 4 is well defined and generates an infinite sequence {zk} with μk∈R++ and zk∈Ω for all k.Proof .
We firstly prove that Algorithm4 is well defined. Obviously, if μk>0 for all k, it follows from Lemma 3(ii) that the matrix H′(zk) is nonsingular. So, Step 3 of Algorithm 4 is well defined at the kth iteration. Now we prove that μk>0 by mathematical induction on k.
Obviously,μ0>0. Assume μk>0 for k; next we prove μk+1>0.
By Step3, we have
(22)Δμk=e-μk(eμkρkμ0-eμk+1)=e-μk-1+ρkμ0>-μk+ρkμ0,
where the last inequality follows from μ>1-e-μ for all μ>0. Therefore, for any α∈(0,1] we obtain that
(23)μk+αΔμk>μk+α(-μk+ρkμ0)=(1-α)μk+αρkμ0>0,
which means that, for τk∈(0,1), μk+1=μk+τkΔμk>0. And thus we prove the desired result.
Next we prove that Step4 is well defined. Let
(24)ω(α):=θ(zk+αΔzk)-θ(zk)-2αH(zk)TH′(zk)Δzk.
From Lemma 3 we can know that θ(·) is continuously differentiable around zk. Hence, (24) implies that
(25)ω(α)=o(α).
So, for any α∈(0,1], we obtain from (19), (24), and (25) that
(26)θ(zk+αΔzk)-θ(zk)=2αH(zk)TH′(zk)Δzk+ω(α)=2αH(zk)T[ρkμ-eμk-H(zk)]+o(α)=2αeμkρkH(zk)Tμ--2αH(zk)TH(zk)+o(α)=2αeμkρk·μ0(eμk-1)-2αθ(zk)+o(α)=2αμ0ρk(eμk-1)2+2αμ0ρk(eμk-1)-2αθ(zk)+o(α)≤2αμ0ρkθ(zk)+2αγμ0θ(zk)-2αθ(zk)+o(α)≤(4αγμ0-2α)θ(zk)+o(α)=-2(1-2γμ0)αθ(zk)+o(α),
where the first inequality follows from the fact that eμk-1≤∥H(zk)∥,ρk≤γ∥H(zk)∥ and the second inequality follows from the fact that ρk≤γ. This indicates that Step 4 of Algorithm 4 is well defined at the kth iteration.
Now we prove the second part of conclusion; that is,zk∈Ω for all k. We prove this result also by mathematical induction on k.
Obviously, from the definition ofρ(·) and the choice of γ, it holds that ρ(z0)≤γ<1; that is, μ0≥ρ0μ0. So, z0∈Ω. Suppose that zk∈Ω; that is, μk≥ρkμ0. Then, by (22), we have
(27)μk+1-ρk+1μ0=μk+τkΔμk-ρk+1μ0>(1-τk)μk+τkρkμ0-ρk+1μ0≥(1-τk)ρkμ0+τkρkμ0-ρk+1μ0=μ0(ρk-ρk+1).
By Step 4 and the definition of ρ(·), we obtain
(28)θ(zk+1)≤θ(zk),ρk+1≤γ,ρk+1≤γθ(zk+1).
So, if ∥H(zk)∥≤1, then ∥H(zk+1)∥≤∥H(zk)∥≤1, and hence
(29)ρk+1=γθ(zk+1)≤γθ(zk)=ρk.
On the other hand, if ∥H(zk)∥>1, then
(30)ρk=γ≥ρk+1.
Thus, from (27), we complete the proof.


## 4. Global and Superlinear Convergence

Theorem 6.
Assume that the sequence{zk} is generated by Algorithm 4; then any accumulation point of {zk} is a solution of (9).Proof.
Without loss of generality, we assume that{zk} converges to z*=(μ*,x*,λ1*,λ2*). It follows from (20) that {θ(zk)} is monotonically decreasing. We assume that {θ(zk)} converges to θ(z*). Then, to prove the result, it is sufficient to prove that θ(z*)=0, which will be proved by reduction to absurdity. Assume that θ(z*)>0; then we obtain
(31)ρ*:=ρ(z*)=γmin{1,∥H(z*)∥,θ(z*)}>0,0<ρ*μ0≤μ*≤μ0,limk→∞λk=0.
On the one hand, from Step 4 of Algorithm 4, it holds that
(32)θ(zk+δmk-1Δzk)-θ(zk)>-2σ(1-2γμ0)δmk-1θ(zk).
That is,
(33)θ(zk+δmk-1Δzk)-θ(zk)2δmk-1>-σ(1-2γμ0)θ(zk).
Let k→∞; we obtain
(34)H(z*)TH′(z*)Δz*≥-σ(1-2γμ0)θ(z*).
On the other hand, by (19) and the definitions of ρ, H, and θ, we have that
(35)H(z*)TH′(z*)Δz*=-H(z*)TH(z*)+ρ*eμ*H(z*)Tμ-=-θ(z*)+ρ*eμ*(eμ*-1)μ0=-θ(z*)+ρ*μ0(eμ*-1)2+ρ*μ0(eμ*-1)≤-θ(z*)+ρ*μ0∥H(z*)∥2+ρ*μ0∥H(z*)∥≤-θ(z*)+2γμ0θ(z*)=-(1-2γμ0)θ(z*).
Combining (34) and (35), we deduced that
(36)-(1-2γμ0)θ(z*)≥-σ(1-2γμ0)θ(z*).
From the assumption that θ(z*)>0, it is implied that
(37)(1-σ)(1-2γμ0)≤0,
which contradicts the fact that σ<1,2γμ0<1. Thus, we have θ(z*)=0; that is, H(z*)=0. And this completes the proof.Assumption 7.
The solution setS={x∈Rn∣F(x)∈𝒦,G(x)∈𝒦∘,F(x)⊤G(x)=0} of GCP is nonempty and bounded.Theorem 8.
Suppose that Assumption7 is satisfied and z*=(μ*,x*,λ1*,λ2*) is an accumulation point of the iteration sequence {zk} generated by Algorithm 4. If all V∈∂H(z*) are nonsingular, then(i)
τk≡1, for all zk sufficiently close to z*;(ii)
the whole sequence{zk} converges to z*; that is, limk→∞zk=z*;(iii)
{zk} converges to z* superlinearly; that is, ∥zk+1-z*∥=o∥zk-z*∥. Moreover, μk+1=o(μk).Proof.
It follows from Theorem6 that H(z*)=0 and x*∈S. Because all V∈∂H(z*) are nonsingular, it follows from Proposition  3.1 in [11] that, for all zk sufficiently close to z*, we have
(38)∥H′(zk)-1∥≤C,
where C>0 is some constant. By Theorem  19 in [12], it is easy to see from Lemma 3 that H(·) is semismooth. Hence, for all zk sufficiently close to z*, we get
(39)∥H(zk)-H(z*)-H′(zk)(zk-z*)∥=o(∥zk-z*∥).
On the other hand, the fact that H(·) is semismooth implies that H(·) is locally Lipschitz continuous near z*. Therefore, for all zk sufficiently close to z*, we have
(40)∥H(zk)∥2=∥H(zk)-H(z*)∥2=O(∥zk-z*∥2).
Thus, we obtain from (40) and the definition of ρ(·) that
(41)ρkμ0≤γμ0θ(zk)=O(∥H(zk)∥2)=O(∥zk-z*∥2).
Then, by (38), (39), and (41), we have
(42)∥zk+Δzk-z*∥=∥zk+H′(zk)-1(-H(zk)+ρkμ-eμk)-z*∥≤∥H′(zk)-1∥[ρkμ0eμk∥-H′(zk)(zk-z*)H(zk)-H(z*)-H′(zk)(zk-z*)∥+ρkμ0eμk]=o(∥zk-z*∥).
Similar to the proof of Theorem  3.1 in [13], for all zk sufficiently close to z*, we get
(43)∥zk-z*∥=O(∥H(zk)-H(z*)∥).
Then, combining this with (42), since H(·) is semismooth at z*, for all zk sufficiently close to z*, we have
(44)∥H(zk+Δzk)∥=O(∥zk+Δzk-z*∥)=o(∥zk-z*∥)=o(∥H(zk)-H(z*)∥)=o(∥H(zk)∥).
By Theorem 6, limk→∞∥H(zk)∥=0. Hence, (44) implies that when zk is sufficiently close to z*, τk=1 can satisfy (20), which proves (i). Thus, for all zk sufficiently close to z*, we have
(45)zk+1=zk+Δzk,
which together with (42) proves (ii) and
(46)∥zk+1-z*∥=o(∥zk-z*∥).
Next, from (i), (ii), and (41), we obtain for all sufficiently large k that
(47)μk+1=μk+Δμk=μk+(e-μk-1)+ρkμ0=O(μk2)+O(∥H(zk)∥2),
where the third equality follows from the fact e-μ-1+μ=o(μ2). Therefore, for all zk sufficiently close to z*, we obtain
(48)μk+1=o(μk),
which completes the whole proof.


## 5. Conclusion

For the generalized complementarity problem over a polyhedral cone, we formulated it as a system of equations via modified smoothing NCP-function based on the Fischer-Burmeister function. Then we presented a Newton-type method to solve the equivalent system of equations. The proposed method is shown to be globally and superlinearly convergent under mild assumptions. Furthermore, our method solves only one linear system of equations and performs only one line search at each iteration. Compared to the previous literatures, our method has stronger convergence results under weaker conditions.



---

*Source: 671402-2013-08-25.xml*