# A Sharper Global Error Bound for the Generalized Nonlinear Complementarity Problem over a Polyhedral Cone

Authors: Hongchun Sun; Yiju Wang
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We revisit the global error bound for the generalized nonlinear complementarity problem over a polyhedral cone (GNCP). By establishing a new equivalent formulation of the GNCP, we establish a sharper global error bound for the GNCP under weaker conditions, which improves the existing error bound estimation for the problem.


---

## Body

## 1. Introduction

Let𝒦={v∈Rm∣Av≥0,Bv=0} be a polyhedral cone in Rm for matrices A∈Rs×m, B∈Rt×m, and let 𝒦∘ be its dual cone; that is,
(1)𝒦∘={u∈Rm∣u=A⊤λ1+B⊤λ2,λ1∈R+s,λ2∈Rt}.
For continuous mappings F,G:Rn→Rm, the generalized nonlinear complementarity problem, abbreviated as GNCP, is to find vector x*∈Rn such that
(2)F(x*)∈𝒦,G(x*)∈𝒦∘,F(x*)⊤G(x*)=0.
Throughout this paper, the solution set of the GNCP, denoted by X*, is assumed to be nonempty.The GNCP is a direct generalization of the classical nonlinear complementarity problem and a special case of the general variational inequalities problem [1]. The GNCP was deeply discussed [2–5] after the work in [6]. The GNCP plays a significant role in economics, operation research, nonlinear analysis, and so forth (see [7, 8]). For example, the classical Walrasian law of competitive equilibria of exchange economies can be formulated as a generalized nonlinear complementarity problem in the price and excess demand variables (see [8]).For the GNCP, the solution existence and the numerical solution methods for the GNCP were discussed [2, 3, 6]. As an important tool for a mathematical problem, the global error bound estimation for GNCP with the mapping being γ-strongly monotone and Hölder continuous was discussed in [5], and a global error bound for the GNCP for the linear and monotonic case was established in [4].In this paper, we will establish a global error bound for the problem (2) without the Hölder continuity of the underlying mapping. To this end, we first develop some new equivalent reformulations of the GNCP under weaker conditions and then establish a sharper global error bound for the GNCP in terms of some easier computed residual functions. The results obtained in this paper can be taken as an improvement of the existing results for GNCP and variational inequalities problem [4, 5, 9–11].To end this section, we give some notations used in this paper. Vectors considered in this paper are taken in the Euclidean spaceRn equipped with the usual inner product, and the Euclidean 2-norm and 1-norm of vector in Rn are, respectively, denoted by ∥·∥ and ∥·∥1. We use R+n to denote the nonnegative orthant in Rn and use x+ and x- to denote the vectors composed by elements (x+)i:=max{xi,0}, (x-)i:=max{-xi,0}, 1≤i≤n, respectively. For simplicity, we use (x;y) to denote vector (x⊤,y⊤)⊤, use I to denote the identity matrix with appropriate dimension, use x≥0 to denote a nonnegative vector x∈Rn, and use dist(x,X*) to denote the distance from point x to the solution set X*.


## 2. Global Error Bound for the GNCP

First, we give some concepts used in the subsequent.Definition 1.
The mappingF:Rn→Rm is said to be(i)
monotone with respect toG:Rn→Rm if
(3)〈F(x)-F(y),G(x)-G(y)〉≥0,∀x,y∈Rn;(ii)
γ-strongly G-monotone with respect to G:Rn→Rm if there are constants c1>0, γ>0 such that
(4)〈F(x)-F(y),G(x)-G(y)〉≥c1∥G(x)-G(y)∥1+γ,〈F(x)-F(y),G(x)-G(y)〉≥c15555.∀x,y∈Rn.Remark 2.
Based on this definition,γ-strongly G-monotone implies monotonicity, and if F(x)=Mx+p, G(x)=Nx+q with M,N∈Rm×n, p,q∈Rm, then the above Definition 1(i) is equivalent to that the matrix M⊤N is positive semidefinite.Now, we give some assumptions for our analysis based on Definition1.Assumption 3.
For mappingsF, G and matrix A involved in the GNCP, we assume that(A1)
mappingF is monotone with respect to mapping G;(A2)
matrixA⊤ has full-column rank.Remark 4.
Under (A2) in the assumption, matrixA⊤ has left inverse (AA⊤)-1A, that is, its pseudoinverse of A⊤. Certainly, the assumption on matrix A⊤ is weaker than that on matrix (A⊤,B⊤) which has full-column rank [4]. In addition, when the mappings F, G are both linear, then Assumption 3(A1) coincides with Assumption (A1) in [4].In the following, we will establish a new equivalent reformulation to the GNCP. First, we give the following conclusion established in [2].Theorem 5.
A pointx*∈Rn is a solution of the GNCP if and only if there exist λ1*∈Rs, λ2*∈Rt, such that
(5)AF(x*)≥0,BF(x*)=0,λ1*≥0,(F(x*))⊤G(x*)=0,G(x*)=A⊤λ1*+B⊤λ2*.From Theorem5, under Assumption 3(A2), we can transform the system into a new system in which neither λ1 nor λ2 is involved. To this end, we need the following conclusion [12].Lemma 6.
If the linear systemHy=b is consistent, then y=H+b is the solution with the minimum 2-norm, where H+ is the pesudo-inverse of H.Lemma 7.
Suppose that Assumption3(A2) holds. Then, for any x∈Rn, the following statements are equivalent.(1)
There existλ1∈R+s, λ2∈Rt such that G(x)=A⊤λ1+B⊤λ2.(2)
Consider(6){-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}G(x)≥0,{A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}+B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]-I}G(x)=0,where AL-1=(AA⊤)-1A.Proof.
The proof follows that of Lemma 2.1 in [4], and for completeness, we include it.
Set(7)X1∶={orsomeλ1∈R+s,λ2∈Rtforsomeλ1∈R+s,λ2∈Rtx∈Rn∣G(x)=A⊤λ1+B⊤λ2forsomeλ1∈R+s,λ2∈Rt},X2≔{[A⊤AL-1-I]+AL-1×[A⊤AL-1-I]x∈Rn∣{[A⊤AL-1-I]+AL-1-AL-1B⊤[(A⊤AL-1-I)B⊤]+×[A⊤AL-1-I]+AL-1[A⊤AL-1-I]+AL-1-AL-1B⊤[(A⊤AL-1-I)B⊤]+}G(x)≥0,{A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+×[A⊤AL-1-I]+AL-1A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+}+B⊤[(A⊤AL-1-I)B⊤]+×[A⊤AL-1-I]-IA⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+}G(x)=0[(A⊤AL-1-I)B⊤]+{[A⊤AL-1-I]+AL-1-AL-1B⊤[(A⊤AL-1-I)B⊤]+}.
Now, we show that these two sets are equal.
First, for anyx∈X1, there exist λ1∈R+s, λ2∈Rt such that
(8)G(x)=A⊤λ1+B⊤λ2.
Premultiplying (8) by AL-1:=(AA⊤)-1A gives
(9)AL-1G(x)=λ1+AL-1B⊤λ2.
Combining this with (8) yields that
(10)G(x)=A⊤(AL-1G(x)-AL-1B⊤λ2)+B⊤λ2=A⊤AL-1G(x)-[A⊤AL-1B⊤-B⊤]λ2;
that is,
(11)[A⊤AL-1B⊤-B⊤]λ2=[A⊤AL-1-I]G(x).
Recalling Lemma 6, we further have
(12)λ2=[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]G(x).
Combining this with (9) yields that
(13)λ1={-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}×G(x).
Using (8),  (12), and (13), we have
(14){A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}+B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]-I}G(x)=0.
From the fact that λ1≥0, by (13), one has
(15){-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}G(x)≥0.
Combining this with (14) leads to that x∈X2. This shows that X1⊆X2.
Second, for anyx∈X2, let
(16)λ1={-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}×G(x),λ2={[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]}G(x).
Then, λ1∈R+s, λ2∈Rt. From (14), one has
(17)G(x)=A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1}×G(x)+B⊤{[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]}G(x)=A⊤λ1+B⊤λ2;
that is, x∈X1. Hence, X2⊆X1, and the desired result follows.Combining this conclusion with Theorem5, we can establish the following equivalent formulation of the GNCP:
(18)AF(x)≥0,BF(x)=0,(F(x))⊤G(x)=0,UG(x)≥0,VG(x)=0,
where
(19)U={-AL-1B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]+AL-1},V={A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+×[A⊤AL-1-I]+AL-1[(A⊤AL-1-I)B⊤]+}+B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]-I}.For the ease of description, we denoteμ=F(x), ν=G(x). Thus, system (18) can be written as
(20)Aμ≥0,Bμ=0,μ⊤ν=0,Uν≥0,Vν=0.For system (20), one has
(21)μ⊤ν=μ⊤{A⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+×[A⊤AL-1-I]+AL-1-AL-1B⊤[(A⊤AL-1-I)B⊤]+}+B⊤[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]}ν=[Aμ]⊤{-AL-1B⊤[(A⊤AL-1-I)B⊤]+×[A⊤AL-1-I]+AL-1-AL-1B⊤[(A⊤AL-1-I)B⊤]+}ν+[Bμ]⊤{[(A⊤AL-1-I)B⊤]+[A⊤AL-1-I]}ν=[Aμ]⊤[Uν],
where the first equality follows from the last equality in (20), and the last equality uses the second equality in (20). Thus, system (20) can be further written as
(22)Aμ≥0,Bμ=0,(Aμ)⊤(Uν)=0,Uν≥0,Vν=0.
Furthermore, for any (μ,ν)∈Rm×Rm with Aμ≥0, Uν≥0, it holds from (21) that
(23)μ⊤ν≥0.Now, consider the following optimization problem:(24)minf(ω)=[(I,0)ω]⊤[(0,I)ω]s.t.ω∈Ω,
where ω=(μ,ν), Ω={ω∈R2m∣A(I,0)ω≥0,B(I,0)ω=0,U(0,I)ω≥0,V(0,I)ω=0}. Denote the solution set of (24) by Ω*.Lemma 8.
Under Assumption3(A1), f(ω) is a convex function.Proof.
For anyω1,ω2∈R2m, τ∈[0,1], we have
(25)f(τω1+(1-τ)ω2)-τf(ω1)-(1-τ)f(ω2)=[(I,0)(τω1+(1-τ)ω2)]⊤×[(0,I)(τω1+(1-τ)ω2)]-τ[(I,0)ω1]⊤[(0,I)ω1]-(1-τ)[(I,0)ω2]⊤[(0,I)ω2]=τ2[(I,0)ω1]⊤[(0,I)ω1]+(1-τ)2[(I,0)ω2]⊤[(0,I)ω2]+τ(1-τ)[(I,0)ω1]⊤[(0,I)ω2]+τ(1-τ)[(I,0)ω2]⊤[(0,I)ω1]-τ[(I,0)ω1]⊤[(0,I)ω1]-(1-τ)[(I,0)ω2]⊤[(0,I)ω2]=-τ(1-τ)[(I,0)ω1]⊤[(0,I)ω1]-τ(1-τ)[(I,0)ω2]⊤[(0,I)ω2]+τ(1-τ)[(I,0)ω1]⊤[(0,I)ω2]+τ(1-τ)[(I,0)ω2]⊤[(0,I)ω1]=-τ(1-τ)([(I,0)ω1]-[(I,0)ω2])⊤×((0,I)ω1-(0,I)ω2)≤0,
where the first inequality uses Assumption 3(A1). The desired result follows.Based on (20), combining (23) with Lemma 8, we can obtain the following conclusion.Lemma 9.
A pointω*=(μ*,ν*)∈R2m is a solution of (20) if and only if ω* is a global optimal solution with the objective vanishing of (24).In the following, we give the error bound for a polyhedral cone from [13] and error bound for a convex optimization from [14] to reach our aims.Lemma 10.
For polyhedral coneP={x∈Rn∣D1x=d1,B1x≤b1} with D1∈Rl×n, B1∈Rm×n, d1∈Rl, and b1∈Rm, there exists a constant c2>0 such that
(26)dist(x,P)≤c2[∥D1x-d1∥+∥(B1x-b1)+∥],≤c2[∥D1x-d1∥+∥(B1x-b15)+∥.]∀x∈Rn.Lemma 11.
LetP be a convex polyhedron in Rn, and let θ be a convex quadratic function defined on Rn. Let S be the nonempty set of globally optimal solutions of the programming:
(27)minθ(x)s.t.x∈P
with θopt being the optimal value of θ on S. There exists a scalar c3>0 such that
(28)dist(x,S)≤c3max{|[θ(x)-θopt]+|1/2dist(x,P),|[θ(x)-θopt]+|,hhhhhhhhhhhhhhhh|[θ(x)-θopt]+|1/2},hhhhhhhhhhhhhhh55.5hhh∀x∈Rn.Before proceeding, we present the following definition introduced in [15].Definition 12.
The mappingG:Rn→Rm is said to be strongly nonexpanding with a constant α>0 if ∥G(x)-G(y)∥≥α∥x-y∥.By Lemma8, f(ω) is a convex function and the feasible set Ω is a polyhedral. Combining this with Lemmas 10 and 11, we immediately obtain the following conclusion.Theorem 13.
Suppose thatF is γ-strongly G-monotone with positive constants c1, γ, respectively, and G is strongly nonexpanding with constant α>0. Then, there exists constant ρ1>0 such that
(29)dist(x,X*)≤ρ1{|[F(x)⊤G(x)]+|1/2∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥+|[F(x)⊤G(x)]+|+|[F(x)⊤G(x)]+|1/2}2/(1+γ),∀x∈Rn.Proof.
For anyx∈Rn, let ω=(μ,ν)=(F(x),G(x))∈R2m. Then, there exists ω*=(μ*,ν*)=(F(x*),G(x*))∈Ω* such that dist(ω,Ω*)=∥ω-ω*∥. A direct computation yields that
(30)dist1+γ(x,X*)≤∥x-x*∥1+γ≤1α1+γ∥G(x)-G(x*)∥1+γ≤1c1α1+γ[(F(x)-F(x*))⊤(G(x)-G(x*))]≤1c1α1+γ∥F(x)-F(x*)∥∥G(x)-G(x*)∥≤12c1α1+γ{∥F(x)-F(x*)∥2+∥G(x)-G(x*)∥2}=12c1α1+γ∥ω-ω*∥2=12c1α1+γdist2(ω,Ω*)≤12c1α1+γc32×max{dist(ω,Ω),|[f(ω)]+|,|[f(ω)]+|1/2}2≤12c1α1+γc32×max{|[μ⊤ν]+|1/2c2{∥[A(I,0)ω]-∥+∥B(I,0)ω∥+∥[U(0,I)ω]-∥+∥V(0,I)ω∥},|[f(ω)]+|,|[f(ω)]+|1/2|[μ⊤ν]+|1/2}2≤12c1α1+γc32×max{c2,1}2{|[μ⊤ν]+|1/2∥[Aμ]-∥+∥Bμ∥+∥[Uν]-∥+∥Vν∥+|[μ⊤ν]+|+|[μ⊤ν]+|1/2}2,
where the second inequality follows from Definition 12 with constant α>0, the third inequality follows from Definition 1(ii) with constants c1>0, γ>0, the fourth inequality follows from the Cauchy-Schwarz inequality, the fifth inequality follows from the fact that (1/2)(a2+b2)≥ab, for all a,b∈R, the sixth inequality follows from Lemma 11 with constant c3>0 and Lemma 9, and the seventh inequality follows from Lemma 10 with constant c2>0. By (30) and letting ρ1={(1/2c1α1+γ)c32max{c2,1}2}1/(1+γ), then the desired result follows.Remark 14.
It is clear that ifF is γ-strongly G-monotone and G is strongly nonexpanding, then
(31)〈F(x)-F(y),G(x)-G(y)〉≥c1∥G(x)-G(y)∥1+γ≥c1α1+γ∥x-y∥1+γ,∀x,y∈Rn.
Moreover, the conditions which both F and G are Hölder continuous (or both F and G are Lipschitz continuous) in Theorem 13 are removed. Thus, Theorem 13 is stronger than Theorem 2.5 in [5]. Furthermore, by Theorem 2.1 in [5], the GNCP can be reformulated as general variational inequalities problem, and the conditions in Theorem 13 are also weaker than those in Theorem 3.1 in [15], Theorem 3.1 in [11], Theorem 3.1 in [10], and Theorem 2 in [9], respectively.On the other hand, the condition thatF is γ-strongly G-monotone and G is strongly nonexpanding in Theorem 13 is extended compared with the condition that F is strongly monotone with respect to G (i.e., γ=1) in Theorems 3.4 and 3.6 in [15], and it is also extended than compared with the condition F is strongly monotone with respect to G (i.e., γ=1) in Theorem 3.1 in [11], and compared with the condition that F(x)=x, G(x) is strongly monotone (i.e., γ=1) in Theorem 3.1 in [10].Using the following Definition15 developed from the complementarity conditions in (22), we can further detect the error bound of the GNCP.Definition 15.
A solutionx0 of the GNCP is said to be nondegenerate if it satisfies
(32)AF(x0)+UG(x0)>0.Lemma 16.
Suppose that Assumptions3(A1) and 3(A2) hold, and the GNCP has a nondegenerate solution, say x0. Then,
(33)Ω*={ω∈Ω∣[(I,0)ω]⊤[(0,I)ω0]+[(0,I)ω]⊤[(I,0)ω0]=0},
where ω0=(μ0,ν0)=(F(x0),G(x0)).Proof.
Since(34)[(I,0)ω0]⊤[(0,I)ω0]=0,
by Assumption 3(A1), for any ω∈Ω, we have
(35)0≤(μ-μ0)⊤(ν-ν0)=[(I,0)ω-(I,0)ω0]⊤[(0,I)ω-(0,I)ω0]=[(I,0)ω]⊤[(0,I)ω]-[(I,0)ω]⊤[(0,I)ω0]-[(0,I)ω]⊤[(I,0)ω0];
that is,
(36)[(I,0)ω]⊤[(0,I)ω0]+[(0,I)ω]⊤[(I,0)ω0]≤[(I,0)ω]⊤[(0,I)ω].
To prove the assertion, we only need to show that the solution set Ω* is equal to the set
(37)W∶={ω∈Ω∣[(I,0)ω]⊤[(0,I)ω0]+[(0,I)ω]⊤[(I,0)ω0]=0}.
For anyω~∈Ω*, combining Lemma 9 with (20) yields that
(38)[(I,0)ω~]⊤[(0,I)ω~]=0.
Letting ω=ω~ in (36) yields that
(39)[(I,0)ω~]⊤[(0,I)ω0]+[(0,I)ω~]⊤[(I,0)ω0]≤0.
Since ω~,ω0∈Ω, using the similar technique to that of (21), we can obtain
(40)[(I,0)ω~]⊤[(0,I)ω0]+[(0,I)ω~]⊤[(I,0)ω0]=μ~⊤ν0+ν~⊤μ0=(Aμ~)⊤(Uν0)+(Uν~)⊤(Aμ0)≥0,
where ω~=(μ~,ν~). Combining (39) with (40), we have Ω*⊆W.
On the other hand, for anyω∈W, one has
(41)[(I,0)ω]⊤[(0,I)ω0]+[(0,I)ω]⊤[(I,0)ω0]=0.
Since ω,ω0∈Ω, using the similar arguments to that of (21), one has
(42)[(I,0)ω]⊤[(0,I)ω0]=[Aμ]⊤[Uν0],[(0,I)ω]⊤[(I,0)ω0]=[Uν]⊤[Aμ0].
Combining this with (41) yields that
(43)[Aμ]⊤[Uν0]+[Uν]⊤[Aμ0]=0.
From (32), we deduce that
(44)[Aμ]⊤[Uν]=0.
Thus, using (21), one has
(45)μ⊤ν=0.
Hence, ω∈Ω*.Based on Lemma16, we obtain the following conclusion.Corollary 17.
Suppose that the hypotheses of Lemma16 hold. Then,
(46)Ω*={ω∈Ω∣[(I,0)ω]⊤[(0,I)ω0]+[(0,I)ω]⊤[(I,0)ω0]≤0}.Theorem 18.
Suppose that the hypotheses of Theorem13 hold, and the GNCP has a nondegenerate solution. Then, there exists constant ρ2>0 such that
(47)dist(x,X*)≤ρ2{|[F(x)⊤G(x)]+|∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥+|[F(x)⊤G(x)]+|}2/(1+γ),∀x∈Rn.Proof.
For anyx∈Rn, let ω=(μ,ν)=(F(x),G(x))∈R2m. Then, there exists ω*=(μ*,ν*)=(F(x*),G(x*))∈Ω* such that dist(ω,Ω*)=∥ω-ω*∥. Letting x0 be a nondegenerate solution of GNCP and letting ω0=(F(x0), G(x0))∈Ω*, then
(48)dist1+γ(x,X*)≤∥x-x*∥1+γ≤12c1α1+γdist2(ω,Ω*)≤12c1α1+γc42×{∥{μ⊤ν}+∥∥[A(I,0)ω]-∥+∥[U(0,I)ω]-∥+∥B(I,0)ω∥+∥V(0,I)ω∥+∥{[(I,0)ω]⊤[(0,I)ω0]+[(0,I)ω]⊤[(I,0)ω0]}+∥}2≤12c1α1+γc42×{∥{μ⊤ν}+∥∥[A(I,0)ω]-∥+∥[U(0,I)ω]-∥+∥B(I,0)ω∥+∥V(0,I)ω∥+∥{[(I,0)ω]⊤[(0,I)ω]}+∥}2=12c1α1+γc42×{∥{μ⊤ν}+∥∥[Aμ]-∥+∥[Uν]-∥+∥Bμ∥+∥Vν∥+∥{μ⊤ν}+∥}2,
where the second equality uses the similar technique to that of (30), the third inequality follows from Corollary 17 and Lemma 10 with constant c4>0, and the last inequality is based on (36). By (48) and letting ρ2={(1/2c1α1+γ)c42}1/(1+γ), the desired result follows.In the following, we give an error bound of the Hölderian type [14].Lemma 19.
Fori=1,2,…,m, let gi(x) be a convex quadratic function. If the set S:={x∈Rn∣g1(x)≤0,g2(x)≤0,…,gm(x)≤0} is nonempty, then there exist a positive integer d≤n+1 (called the degree of singularity of the inequality system) and a positive scalar c5 such that
(49)dist(x,S)≤c5max{∥[g(x)]+∥,∥[g(x)]+∥1/2d},∀x∈Rn,
where [g(x)]+=([g1(x)]+,[g2(x)]+,…,[gm(x)]+). Furthermore, if S contains an interior point, then d=0.Based on (18) and (21), the GNCP can also be written as
(50)AF(x)≥0,BF(x)=0,(F(x))⊤G(x)≤0,UG(x)≥0,VG(x)=0.From Lemma19, we can establish the following global error bound for GNCP.Theorem 20.
Suppose that the hypotheses of Theorem13 hold, and there exists point x^∈Rn such that
(51)F(x^)⊤G(x^)<0.
Then, there exists constant ρ3>0 such that
(52)dist(x,X*)≤ρ3{|[F(x)⊤G(x)]+|∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥+|[F(x)⊤G(x)]+|}2/(1+γ),∀x∈Rn.Proof.
LetS1:={ω∈R2m∣f(ω)≤0}, where f(ω)=[(I,0)ω]⊤[(0,I)ω]. By Lemma 8, we have f(ω) is a convex quadratic function. Combining this with (51), using Lemma 19 with d=0, this yields the following result
(53)dist(ω,S1)≤c6∥[f(ω)]+∥,∀ω∈R2m,
where c6 is a positive constant.
Obviously,S1 is a closed convex set. Thus, for any ω∈R2m, there exists a vector ω-∈S1 such that
(54)∥ω-ω-∥=dist(ω,S1).
For convenience, we also let(55)Ψ(ω)=(-A(I,0)ω,-B(I,0)ω,-U(0,I)ω,-V(0,I)ω,B(I,0)ω,V(0,I)ω)+.
From (50), we have Ω*=Ω⋂‍S1, where Ω is defined in (24), so for any ω∈S1, combining Lemma 10, one has
(56)dist(ω,Ω*)≤c7[∥(-A(I,0)ω)+∥+∥(-U(0,I)ω)+∥hh+∥B(I,0)ω∥+∥V(0,I)ω∥∥(-A(I,0)ω)+∥]=c7[∥(-A(I,0)ω)+∥+∥(-U(0,I)ω)+∥hh+∥(B(I,0)ω)+∥+∥(-B(I,0)ω)+∥hh+∥(V(0,I)ω)+∥+∥(-V(0,I)ω)+∥]≤c7{∥(-A(I,0)ω)+∥1+∥(-U(0,I)ω)+∥1hh+∥(B(I,0)ω)+∥1+∥(-B(I,0)ω)+∥1hh+∥(V(0,I)ω)+∥1+∥-(V(0,I)ω)+∥1}=c7∥Ψ(ω)∥1≤c72s+2t+2m∥Ψ(ω)∥,
where c7 is a positive constant, and the second and third inequalities follow from the fact that ∥x∥≤∥x∥1≤n∥x∥, for all x∈Rn.
Furthermore,(57)∥Ψ(ω)-Ψ(ω-)∥=∥(-A(I,0)ω,-B(I,0)ω,-U(0,I)ω,-V(0,I)ω,B(I,0)ω,V(0,I)ω)+-(-A(I,0)ω-,-B(I,0)ω-,-U(0,I)ω-,-V(0,I)ω-,B(I,0)ω-,V(0,I)ω-)+∥=∥PR+2s+2t+2m{(-A(I,0)ω,-B(I,0)ω,=∥PR+2s+2t+2m5-U(0,I)ω,-V(0,I)ω,=∥PR+2s+2t+2m5B(I,0)ω,V(0,I)ω)}-PR+2s+2t+2m{(-A(I,0)ω-,-B(I,0)ω-,-PR+2s+2t+2m5-U(0,I)ω-,-V(0,I)ω-,-PR+2s+2t+2m5B(I,0)ω-,V(0,I)ω-)}PR+2s+2t+2m∥≤∥{(-A(I,0)ω,-B(I,0)ω,-U(0,I)ω,-V(0,I)ω,B(I,0)ω,V(0,I)ω)}-{(-A(I,0)ω-,-B(I,0)ω-,-U(0,I)ω-,-V(0,I)ω-,B(I,0)ω-,V(0,I)ω-}∥≤∥A(I,0)ω-A(I,0)ω-∥+2∥B(I,0)ω-B(I,0)ω-∥+∥U(0,I)ω-U(0,I)ω-∥+2∥V(0,I)ω-V(0,I)ω-∥≤(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥+2∥V(0,I)∥)×∥ω-ω-∥=(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥+2∥V(0,I)∥)×dist(ω,S1),
where the second equality follows from the fact that
(58)min{a,b}=a-PR+(a-b),∀a,b∈R,
and the first inequality is by nonexpanding property of projection operator. Thus,
(59)∥Ψ(ω-)∥≤∥Ψ(ω)∥+(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥+2∥V(0,I)∥)dist(ω,S1).
Combining (56) with (59), for any ω∈R2m, we have
(60)dist(ω,Ω*)≤dist(ω,S1)+dist(ω-,Ω*)≤dist(ω,S1)+σ∥Ψ(ω-)∥≤dist(ω,S1)+σ(dist(ω,S1)∥Ψ(ω)∥+(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥+2∥V(0,I)∥)dist(ω,S1))≤σ∥Ψ(ω)∥+[σ(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥+2∥V(0,I)∥)+1]×dist(ω,S1)≤σ∥Ψ(ω)∥+[σ(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥+2∥V(0,I)∥)+1]c6×∥[f(ω)]+∥≤η(∥Ψ(ω)∥+∥[f(ω)]+∥)≤η(∥Ψ(ω)∥1+∥[f(ω)]+∥)≤η(∥(-A(I,0)ω)+∥1+∥(-U(0,I)ω)+∥1+∥B(I,0)ω∥1+∥V(0,I)ω∥1+∥[f(ω)]+∥)≤η(s∥(-A(I,0)ω)+∥+s∥(-U(0,I)ω)+∥+t∥B(I,0)ω∥+m∥V(0,I)ω∥+∥[f(ω)]+∥s)≤c8(∥(-A(I,0)ω)+∥+∥(-U(0,I)ω)+∥+∥B(I,0)ω∥+∥V(0,I)ω∥+∥[f(ω)]+∥),
where the second inequality follows from (56) with constant σ=c72s+2t+2m, the third inequality uses (59), the fifth inequality follows from (53), the sixth inequality follows from the fact that
(61)η=max{σ,[σ(∥A(I,0)∥+2∥B(I,0)∥+∥U(0,I)∥hhhhhhhh+2∥V(0,I)∥)+1]c6},
the seventh and ninth inequalities follow from the fact that
(62)∥x∥≤∥x∥1≤n∥x∥,∀x∈Rn,
and the last inequality follows by letting c8=ηmax{s,t,m,1}.
For anyx∈Rn, letting ω:=(μ,ν)=(F(x),G(x))∈R2m, then there exists ω*=(μ*,ν*)=(F(x*),G(x*))∈Ω* such that dist(ω,Ω*)=∥ω-ω*∥, and a direct computation yields that
(63)dist1+γ(x,X*)≤∥x-x*∥1+γ≤12c1α1+γdist2(ω,Ω*)≤12c1α1+γc82×{∥{μ⊤ν}+∥∥[A(I,0)ω]-∥+∥[U(0,I)ω]-∥+∥B(I,0)ω∥+∥V(0,I)ω∥+∥{[(I,0)ω]⊤[(0,I)ω]}+∥}2=12c1α1+γc82{+∥Vν∥+∥{μ⊤ν}+∥{μ⊤ν}+∥[Aμ]-∥+∥[Uν]-∥+∥Bμ∥hhhhhhh.h+∥Vν∥+∥{μ⊤ν}+∥}2,
where the deduction of the second equality uses the similar technique to that of (30), and the third inequality is by (60). By (63) and letting ρ3={(1/2c1α1+γ)c82}1/(1+γ), then the desired result follows.Remark 21.
WhenF is strongly monotone with respect to G, that is, γ=1, without the requirement of nondegenerate solution, the square root term in the error bound estimation is removed as stated in Theorem 20. Hence, the error estimation becomes more practical than that in Theorem 4.1 in [4].


## 3. Global Error Bound for the GLCP

In this section, we consider the linear case of the GCP such that mappingsF and G are both linear; that is, F(x)=Mx+p, G(x)=Nx+q with M,N∈Rm×n, p,q∈Rm:
(64)minH(x)=(Mx+p)⊤(Nx+q)s.t.x∈X,
where
(65)X={x∈Rn∣A(Mx+p)≥0,U(Nx+q)≥0,B(Mx+p)=0,V(Nx+q)=0}.For problem (64), combining (18) with (23) and using a similar discussion in Lemmas 8 and 9, we also have the following conclusion.Lemma 22.
Under Assumption3(A1), H(x) is a convex function.Lemma 23.
x
*
∈
R
n is a solution of the GLCP if and only if x* is global optimal solution with the objective vanishing of (64).Based on (64), using the argument similar to that of Theorem 13, we can obtain the following conclusion.Theorem 24.
Under Assumptions3(A1) and 3(A2), and that mappings F and G are both linear, there exists constant ρ4>0 such that
(66)dist(x,X*)≤ρ4{|[F(x)⊤G(x)]+|1/2+|[F(x)⊤G(x)]+|1/2∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥+|[F(x)⊤G(x)]+|+|[F(x)⊤G(x)]+|1/2},∀x∈Rn.Proof.
For anyx∈Rn, a direct computation yields that
(67)dist(x,X*)≤c9max{dist(x,X),|[H(x)]+|,|[H(x)]+|1/2}≤c9max{|[H(x)]+|1/2c10{∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥},|[H(x)]+|,|[H(x)]+|1/2}≤c9max{c10,1}{|[(F(x))⊤G(x)]+|1/2+|[(F(x))⊤G(x)]+|1/2∥[AF(x)]-∥+∥BF(x)∥hhhhhhhhhhhhhhhhh+∥[UG(x)]-∥hhhhhhhhhhhhhhhhh+∥VG(x)∥+|[(F(x))⊤G(x)]+|hhhhhhhhhhhhhhhhh+|[(F(x))⊤G(x)]+|1/2},
where the first inequality follows from Lemma 11 with constant c9>0 and Lemma 23, and the second inequality uses Lemma 10 with constant c10>0. By (67) and letting ρ4=c9max{c10,1}, the desired result follows.Remark 25.
Obviously, Assumption3(A2) in Theorem 24 is weaker than Assumption (A2) in Theorem 4.1 in [4], Assumption 3(A1) coincides with Assumption (A1) in [4]. In addition, Theorem 24 is sharper than Theorem 4.1 in [4].
The following result further estimates the error bound for the GLCP.Theorem 26.
Suppose that the hypotheses of Theorem24 hold, and the GLCP has a nondegenerate solution. Then, there exists constant ρ5>0 such that
(68)dist(x,X*)≤ρ5{∥VG(x)∥+|[F(x)⊤G(x)]+|∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥+|[F(x)⊤G(x)]+|},∀x∈Rn.Proof.
From Corollary17, we have
(69)X*={x∈X∣(Mx+p)⊤(Nx0+q)hhhhh+(Nx+q)⊤(Mx0+p)≤0},
where x0 is a nondegenerate solution of GLCP, and X is defined in (64). For any x∈Rn, a direct computation yields that
(70)dist(x,X*)≤c11{(Nx+q)⊤(Mx0+p)]+∥[A(Mx+p)]-∥+∥[U(Nx+q)]-∥+∥B(Mx+p)∥+∥V(Nx+q)∥+∥[(Mx+p)⊤(Nx0+q)+(Nx+q)⊤(Mx0+p)]+∥}≤c11{∥[(Mx+p)⊤(Nx+q)]+∥∥[A(Mx+p)]-∥+∥[U(Nx+q)]-∥+∥B(Mx+p)∥+∥V(Nx+q)∥+∥[(Mx+p)⊤(Nx+q)]+∥},
where the first inequality follows from Lemma 10 with constant c11>0, and the second inequality uses (36). Letting ρ5=c11, the desired result follows.Remark 27.
The condition in Theorem26 is weaker than that in Theorem 4.2 in [4].Theorem 28.
Suppose that the hypotheses of Theorem24 hold, and there exists point x^∈Rn such that (51) holds. Then there exists constant ρ6>0 such that
(71)dist(x,X*)≤ρ6{|[F(x)⊤G(x)]+|∥[AF(x)]-∥+∥BF(x)∥+∥[UG(x)]-∥+∥VG(x)∥+|[F(x)⊤G(x)]+|},∀x∈Rn.Proof.
LetS2:={x∈Rn∣H(x)≤0}, where H(x)=(Mx+p)⊤(Nx+q). By Lemma 22, H(x) is a convex quadratic function, and S2 is a closed convex set. For any x∈Rn, there exists a vector x-∈S2 such that
(72)∥x-x-∥=dist(x,S2).
Combining (51) and applying Lemma 19 yield the following result:
(73)dist(x,S2)≤c12∥[H(x)]+∥,∀x∈Rn,
where c12 is a positive constant. For convenience, we let
(74)φ(x)=(-AF(x),-BF(x),-UG(x)-VG(x),BF(x),VG(x)-AF(x),-BF(x),-UG(x))+.
From (50), we have X*=X⋂‍S2, where X is defined in (64). So for any x∈S2, combining Lemma 10 and using the similar technique to that of (56), one has
(75)dist(x,X*)≤c13[∥(-AF(x))+∥+∥(-UG(x))+∥+∥BF(x)∥+∥VG(x)∥∥(-AF(x))+∥]≤c132s+2t+2m∥φ(x)∥,
where c13 is a positive constant.
Using the fact that(76)min{a,b}=a-PR+(a-b),∀a,b∈R,
and using the similar technique to that of (57), one has
(77)∥φ(x)-φ(x-)∥=∥-VG(x-),BF(x-),VG(x-))+(-AF(x),-BF(x),-UG(x),-VG(x),hhhhhhhBF(x),VG(x))+-(-AF(x-),-BF(x-),-UG(x-),hhhhhhhhh-VG(x-),BF(x-),VG(x-))+∥≤∥AF(x)-AF(x-)∥+2∥BF(x)-BF(x-)∥+∥UG(x)-UG(x-)∥+2∥VG(x)-VG(x-)∥≤(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)∥x-x-∥=(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)dist(x,S2),
where the second inequality is by nonexpanding property of projection operator. Thus,
(78)∥φ(x-)∥≤∥φ(x)∥+(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)dist(x,S2).
Combining (75) with (78), we know that for any x∈Rn, it holds that
(79)dist(x,X*)≤dist(x,S2)+dist(x-,X*)≤dist(x,S2)+σ1∥φ(x-)∥≤dist(x,S2)+σ1(∥φ(x)∥+(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)dist(x,S2))≤σ1∥φ(x)∥+[σ1(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)+1]dist(x,S2)≤σ1∥φ(x)∥+[σ1(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)+1]c12∥[H(x)]+∥≤η1(∥φ(x)∥+∥[H(x)]+∥)≤η1(∥φ(x)∥1+∥[H(x)]+∥)≤η1(∥(-AF(x))+∥1+∥(-UG(x))+∥1hhhhhhhh+∥BF(x)∥1+∥VG(x)∥1+∥[H(x)]+∥∥(-AF(x))+∥1)≤η1(+t∥BF(x)∥+m∥VG(x)∥+∥[H(x)]+∥s∥(-AF(x))+∥+s∥(-UG(x))+∥hhhhhhhh+t∥BF(x)∥+m∥VG(x)∥+∥[H(x)]+∥s∥(-AF(x))+∥+s∥(-UG(x))+∥)≤ρ6(∥(-AF(x))+∥+∥(-UG(x))+∥+∥BF(x)∥hhhhh+∥VG(x)∥+∥[H(x)]+∥∥(-UG(x))+∥),
where the second inequalities follows from (75) with constant σ1=c132s+2t+2m, the third inequality follows from (78), the fifth inequality follows from (73), the sixth inequality follows by letting η1=max{σ1,[σ1(∥AM∥+2∥BM∥+∥UN∥+2∥VN∥)+1]c12}, and the seventh and ninth inequality follow from the fact that
(80)∥x∥≤∥x∥1≤n∥x∥,∀x∈Rn.
By (79) and letting ρ6=η1max{s,t,m,1}, the desired result follows.Remark 29.
In Theorem28, without the requirement of nondegenerate solution, the square root term in the error bound estimation is removed. Hence, the error estimation becomes more practical than that in Theorem 4.1 in [4].


## 4. Comparison with Existing Error Bound

In the end of this paper, we will present an example to compare Theorem13 and Theorem 2.5 in [5]. Furthermore, we will present two examples to show the conclusion in Theorem 13 can provide a global error bound for the GNCP, while the conclusion in Theorem 2.5 in [5] cannot do.Example 30.
When𝒦=R+m, (2) reduces to the generalized nonlinear complementarity problem of finding vector x*∈Rn such that
(81)F(x*)≥0,G(x*)≥0,F(x*)⊤G(x*)=0.For (81), using Theorem 13 with γ=1, we have
(82)dist(x,X*)≤ρ~φ(x),∀x∈Rn,
where φ(x)=:∥[F(x)]-∥+∥[G(x)]-∥+|[F(x)⊤G(x)]+|+|[F(x)⊤G(x)]+|1/2.Using Theorem 2.5 in [5] with γ=1, v1=v2=1, and β=1, we have that there exists constant ρ->0 such that
(83)dist(x,X*)≤ρ-r(x),
where r(x)=:∥min{F(x),G(x)}∥. In addition,
(84)φ(x)≤{2m+∥max{F(x),G(x)}∥}{r(x)+r(x)1/2}.
In particular, when ∥x∥≤c14 with constant c14>0, then there exists positive constant c15 such that
(85)φ(x)≤c15{r(x)+r(x)1/2}.In fact, we have(86)φ(x)≤∥(F(x))-∥1+∥(G(x))-∥1+[(F(x))⊤G(x)]++[(F(x))⊤G(x)]+1/2≤2m∥min{F(x),G(x)}∥+[(F(x))⊤G(x)]++[(F(x))⊤G(x)]+1/2≤2m∥min{F(x),G(x)}∥+∑i=1m‍[(F(x))i(G(x))i]++{∑i=1m‍[(F(x))i(G(x))i]+}1/2≤2m∥min{F(x),G(x)}∥+∑i=1m‍|min{F(x),G(x)}i|·|max{F(x),G(x)}i|+{∑i=1m‍|min{F(x),G(x)}i|·|max{F(x),G(x)}i|∑i=1m‍|min{F(x),G(x)}i|}1/2≤2m∥min{F(x),G(x)}∥+∥min{F(x),G(x)}∥·∥max{F(x),G(x)}∥+{∥min{F(x),G(x)}∥·∥max{F(x),G(x)}∥}1/2={2m+∥max{F(x),G(x)}∥}r(x)+∥max{F(x),G(x)}∥1/2r(x)1/2≤{2m+∥max{F(x),G(x)}∥}{r(x)+r(x)1/2},
where the first inequality follows from the fact that ∥x∥≤∥x∥1, for all x∈Rm, the second inequality follows from the fact that a-≤|min{a,b}|, for all a,b∈R, the third inequality follows from the fact that (a+b)+≤a++b+, for all a,b∈R, the fourth inequality follows from the fact that (ab)+≤|min{a,b}|·|max{a,b}|, for all a,b∈R, and the fifth inequality follows from the Cauchy-Schwarz inequality.Example 31.
For mappingsF,G:R+→R involved in problem (81), we set
(87)F(x)=(x+1)2,G(x)=x.It is easy to see that the solution setX*={0}, and one has
(88)〈F(x)-F(y),G(x)-G(y)〉=x+y+2x+y(x-y)2≥(x-y)2,
where the first inequality follows from the fact that x+y+2≥x+y.In fact, we consider the following four cases.Case 1 (x≥1 and y≥1).
Then,x≥x and y≥y, and the desired result follows.Case 2 (0≤x≤1 and 0≤y≤1).
Then,x≤1 and y≤1, and the desired result follows.Case 3 (0≤x≤1 and y≥1).
Then,x≤1 and y≤y, and the desired result follows.Case 4 (x≥1 and 0≤y≤1).
Then,x≤x and y≤1, and the desired result follows.For anyx(ϵ):=ϵ,ϵ≥0. By Theorem 13 with γ=1, we can obtain
(89)∥x(ϵ)-0∥φ(x(ϵ))=ϵ(ϵ+1)2ϵ+(ϵ+1)2ϵ⟶0
as ϵ→+∞. Thus, Theorem 13 provides a global error bound for the GNCP. Using Theorem 2.5 in [5], for x(ϵ), we have
(90)∥x(ϵ)-0∥r(x(ϵ))=ϵ∥min{(ϵ+1)2,ϵ}∥=ϵϵ=ϵ⟶+∞
as ϵ→+∞. Thus, Theorem 2.5 in [5] fails in providing an error bound for this GNCP.Example 32.
For mappingsF,G:R→R involved in problem (81), we set
(91)F(x)=13x3+x,G(x)=x.It is easy to see that the solution setX*={0}. Without loss of generality, we let x>y, and one has
(92)F(x)-F(y)≥(x-y)2,
where the inequality follows from the fact that
(93)(13x3+x)-(13y3+y)-(x-y)2=(x-y)[13x2+13y2+13xy+1+(x-y)]≥0.
In fact, we consider the following four cases.Case 1 (x>y≥0).
Then,(1/3)x2+(1/3)y2+(1/3)xy+1+(x-y)≥0, and the desired result follows.Case 2 (0≥x>y).
Then,(1/3)x2+(1/3)y2+(1/3)xy+1+(x-y)≥0, and the desired result follows.Case 3 (x≥0,y<0 and x+y≥0).
Then,(94)13x2+13y2+13xy+1+(x-y)=13x(x+y)+13y2+1+(x-y)≥0,
and the desired result follows.Case 4 (x≥0,y<0, and x+y≤0).
Then,(95)13x2+13y2+13xy+1+(x-y)=13x2+13y(x+y)+1+(x-y)≥0,
and the desired result follows.Thus, we obtain(96)〈F(x)-F(y),G(x)-G(y)〉≥(x-y)3.For anyx(ϵ):=ϵ, ϵ≥0. By Theorem 13 with γ=2, we can obtain
(97)∥x(ϵ)-0∥φ(x(ϵ))=ϵ[((1/3)ϵ3+ϵ)ϵ+((1/3)ϵ3+ϵ)ϵ]2/3⟶0
as ϵ→+∞. Thus, Theorem 13 provides a global error bound for the GNCP.On the other hand, using Theorem 2.5 in [5], for x(ϵ), we have
(98)∥x(ϵ)-0∥r(x(ϵ))δ=ϵ∥min{(1/3)ϵ3+ϵ,ϵ}∥δ=ϵϵδ⟶+∞
as ϵ→+∞, where δ is a constant with 1/3<δ≤1/2. Thus, Theorem 2.5 in [5] fails in providing an error bound for this GNCP.


## 5. Conclusion

In this paper, we established some global error bounds on the generalized nonlinear complementarity problems over a polyhedral cone, which improves the result obtained for variational inequalities and the GNCP [4, 5, 9–11] by weakening the assumptions. Surely, under milder conditions, we may establish global error bounds for GNCP and use the error bounds estimation to establish quick convergence rate of the methods for the GNCP. This is a topic for future research.



---

*Source: 209340-2013-11-18.xml*