# Further Application ofH-Differentiability to Generalized Complementarity Problems Based on Generalized Fisher-Burmeister Functions

Authors: Wei-Zhe Gu; Mohamed A. Tawhid
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We study nonsmooth generalized complementarity problems based on the generalized Fisher-Burmeister function and its generalizations, denoted by GCP(f,g) where f and g are H-differentiable. We describe H-differentials of some GCP functions based on the generalized Fisher-Burmeister function and its generalizations, and their merit functions. Under appropriate conditions on the H-differentials of f and g, we show that a local/global minimum of a merit function (or a “stationary point” of a merit function) is coincident with the solution of the given generalized complementarity problem. When specializing GCP(f,g) to the nonlinear complementarity problems, our results not only give new results but also extend/unify various similar results proved for C1, semismooth, and locally Lipschitzian.


---

## Body

## 1. Introduction

Gowda et al. in [1] introduced the concepts of the H-differentiability and H-differential for a function f:Rn→Rn. They showed that the Fréchet derivative of a Fréchet differentiable function, the Clarke generalized Jacobian of a locally Lipschitzian function [2], the Bouligand subdifferential of a semismooth function [3–5], and the C-differential of a C-differentiable function [6] are instances of H-differentials. In their paper, they noted that H-differentials enjoy simple sum, product, and chain rules, H-differentiability implies continuity, and any superset of an H-differential is an H-differential. It is noted in [7] that the H-differentiable function needs not be locally Lipschitzian nor directionally differentiable.There have been many applications of these concepts to optimization, complementarity problems, and variational inequalities, characterizations ofP(P0) and E(E0) properties when the underlying functions are not necessarily locally Lipschitzian or semismooth (see, e.g., [7–15]).In this paper, we study a further application ofH-differentiability to nonsmooth generalized complementarity problems based on the generalized Fisher-Burmeister function and its generalizations, denoted by GCP(f,g) where f and g are H-differentiable.We consider a generalized complementarity problem corresponding toH-differentiable functions f and g, denoted by GCP(f,g), which is to find a vector x*∈Rn such that
(1)fx*≥0,gx*≥0,fx*,gx*=0,
where f:Rn→Rn and g:Rn→Rn.In the last decades, many researchers have given a lot of attention to this problems in terms of its applications, numerical methods, and formulation; see [16, 17] and the references cited therein. If g(x)=x-T(x) with some T:Rn→Rn, then GCP(f,g) is known as the quasi/implicit complementarity problem; see, for example, [17–19]. Also, if g(x)=x, then GCP(f,g) reduces to the nonlinear complementarity problem NCP(f). By taking in NCP(f)  f(x)=Mx+q with M∈Rn×n and a vector q∈Rn, then NCP(f) is called a linear complementarity problem LCP(M,q).Our approach is to reformulate GCP(f,g) as an unconstrained optimization problem through some merit function. We construct a merit function via a GCP function ϕ:R2→R:
(2)ϕa,b=0⟺ab=0,a≥0,b≥0.
For the problem GCP(f,g), we define
(3)Φx=ϕf1x,g1x,…,ϕfix,gix,…,ϕfnx,gnxT
and we call Φ(x) a GCP function for GCP(f,g). A function Ψ:Rn→[0,∞) is said to be a merit function for GCP(f,g) provided that the global minima of Ψ are coincident with the solutions of the original GCP(f,g). We consider a GCP function Φ:Rn→Rn associated with GCP(f,g) and its merit function
(4)Ψ(x):=12Φx2,
so that
(5)x¯solvesGCPf,g⟺Φx¯=0⟺Ψ(x¯)=0.The organization of the paper is as follows. We state some basic definitions and preliminary results. We describeH-differentials of some GCP functions based on the generalized Fisher-Burmeister function and its generalizations and their merit functions. We show that under appropriate show P0(P) conditions and column P property conditions, local/global minimum of a merit function (or a “stationary point” or “semi-stationary point” of a merit function) based on the generalized Fisher-Burmeister function and its generalizations coincides with the solution of the given generalized complementarity problem. Note that considering GCP functions on the basis of the generalized Fisher-Burmeister function and its generalizations seems to be new.Moreover, when specializing GCP(f,g) to the nonlinear complementarity problems, our results not only give new results but also extend/unify various similar results proved for C1, semismooth, and locally Lipschitzian.


## 2. Preliminaries

Throughout this paper, all vectors inRn are column vectors. xTy or 〈x,y〉 denotes the inner product between two vectors x and y in Rn. Vector inequalities are interpreted componentwise. All the operations are performed componentwise. For a set E⊆Rn, co⁡E denotes the convex hull of E and co⁡¯E denotes the closure of co⁡E. For a differentiable function f:Rn→Rm, ∇f(x¯) denotes the Jacobian matrix of f at x¯. For a matrix A, Ai denotes the ith row of A. xp denotes the p-norm of x and x denotes the Euclidean norm of x. In addition, unless otherwise stated, assume p in the sequel is any fixed real number in (1,∞).In this section, we first recall some background concepts.We first recall the definition ofH-differentiability and examples from [1].Definition 1.
Given a functionF:Ω⊆Rn→Rm, where Ω is an open set in Rn and x*∈Ω, we say that a nonempty subset T(x*), also denoted by TF(x*), of Rm×n is an H-differential of F at x* if for every sequence xk∈Ω converging to x*, there exist a subsequence xkj and a matrix A∈T(x*) such that
(6)Fxkj-Fx*-Axkj-x*=oxkj-x*.
We say that F is H-differentiable at x* if F has an H-differential at x*.A useful equivalent definition of anH-differential TF(x*) is as follows: for any sequence xk:=x*+tkdk with tk↓0 and dk=1 for all k, there exist convergent subsequences tkj↓0 and dkj→d, and A∈TF(x*) such that
(7)lim⁡j→∞Fx*+tkjdkj-Fx*tkj=Ad.
Here are some well-known facts about H-differentiability; see, for example, [8–10, 15].Remark 2.
(i) Any superset of anH-differential is an H-differential.
(ii)H-differentiability implies continuity, and H-differentials enjoy simple sum, product, and chain rules.
(iii) While the Fréchet derivative of a differentiable function, the Clarke generalized Jacobian of a locally Lipschitzian function [2], the Bouligand differential of a semismooth function [4], and the C-differential of a C-differentiable function [6] are particular instances of H-differential, it is shown in [10] by example that an H-differentiable function need not be locally Lipschitzian nor directionally differentiable.
(iv) If a functionF:Ω⊆Rn→Rm is H-differentiable at a point x¯, then there exist a constant L>0 and a neighborhood B(x¯,δ) of x¯ with
(8)F(x)-F(x¯)≤x-x¯∀x∈B(x¯,δ).
Conversely, if condition (8) holds, then T(x¯):=Rm×n can be taken as an H-differential of F at x¯.In [10], the following definition is introduced to generalize the concepts of monotonicity, P0-property, and their variants for function in [20].Definition 3.
For functionsf,g:Rn→Rn, we say that f and g are as follows:(a)
relatively monotone if(9)fx-fy,gx-gy≥0∀x,y∈Rn,(b)
relatively strictly monotone if(10)fx-fy,gx-gy>0∀x,y∈Rn,(c)
relatively strongly monotone if there exists a constantμ>0 such that
(11)fx-fy,gx-gy≥μx-y2∀x,y∈Rn,(d)
relativelyP0(P)-functions if for any x≠y in Rn,
(12)max⁡i:xi≠yifx-fyigx-gyi≥(>)0,(e)
relatively uniform (P)-functions if there exists a constant η>0 such that for any x,y∈Rn,
(13)max⁡1≤i≤nfx-fyigx-gyi≥ηx-y2.


## 3.H-Differentials of Some GCP Functions When the Underlying Functions Are H-Differentiable

In this section, we compute theH-differentials of some GCP functions and their merit functions.Example 4.
Suppose thatf and g are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯). Consider the following GCP function which is the basis of
(14)ϕpa,b:=a+b-a,bp,
where p is any fixed real number in the interval (1,+∞) and a,bp denotes the p-norm of (a,b); that is, a,bp=|a|p+|b|pp. The function ϕp was noted by Tseng [21]. For further study on this family of NCP functions, see [22]. The ith component of this kind of GCP function Φp(x) in (3) is defined as
(15)Φpxi=ϕpfix,gix:=fix+gix-fix,gixp.
Now we describe theH-differentials of Φp. Let
(16)J(x¯):=i:fix¯=0=gix¯.
The H-differential of Φp at x¯ is given by
(17)TΦp(x¯)={VA+WB:(A,B,V,W,d)∈Γ},
where Γ is the set of all quadruples (A,B,V,W,d) with A∈Tf(x¯), B∈Tg(x¯), d=1, V=diag⁡(vi), and W=diag⁡(wi) being diagonal matrices satisfying the conditions:
(18)1-vip/(p-1)+1-wip/(p-1)=1,∀i=1,2,…,n,(19)vi=1-fix¯p-1sgn⁡fixfix¯p+gix¯pp-1/p,i∉J(x¯),1-Aidp-1sgn⁡AidAidp+Bidpp-1/p,i∈Jx¯,Aidp+Bidp>0,arbitrary,i∈Jx¯,Aidp+Bidp=0,wi=1-gix¯p-1sgn⁡gix¯fix¯p+gix¯pp-1/p,i∉J(x¯),1-Bidp-1sgn⁡BidAidp+Bidp(p-1)/p,i∈Jx¯,Aidp+Bidp>0,arbitrary,i∈Jx¯,Aidp+Bidp=0.Proof.
To see this claim, letx¯+tkdk→x¯ with tk↓0 and dk=1. By the H-differentiability of f, there exists a sequence tkj of tk, dkj→d, and A∈Tf(x¯), such that
(20)fx¯+tkjdkj-fx¯-Atkjdkj=otkj.
Let ykj:=x¯+tkjdkj. With A, B, d, V, and W satisfying (19), let C:=VA+WB. We claim that Φp(ykj)-Φp(x¯)-C(tkjdkj)=o(tkj). To see this, we fix an index i and show that (Φp(ykj))i-(Φp(x¯))i-[C(tkjdkj)]i=o(tkj). Without loss of generality, let i=1. We denote the 1st row of A, B, and C by A1, B1, and C1.
We consider two cases.
Case
1 (
1
∉
J
x
¯
). In this case, we have
(21)C1=1-fix¯p-1sgn⁡fixfix¯p+gix¯p(p-1)/pA1+1-g1x¯p-1sgn⁡g1x¯f1x¯p+g1x¯pp-1/pB1,Φpykj1-Φpx¯1-C1tkjdkj=A1tkjdkj+B1tkjdkj+otkj-f1x¯+A1tkjdkj+otkj,g1x¯+B1tkjdkj+otkjp+f1x¯,g1x¯p-1-f1x¯p-1sgn⁡f1xf1x¯p+g1x¯p(p-1)/pA1tkjdkj-1-g1x¯p-1sgn⁡g1x¯f1x¯p+g1x¯p(p-1)/pB1tkjdkj=otkj.
Case
2  (1∈Jx¯)
Subcase
(1) (
|
A
1
d
|
p
+
|
B
1
d
|
p
>
0
). In this case,
(22)C1=1-A1dp-1sgn⁡A1dA1dp+B1dp(p-1)/pA1+1-Bidp-1sgn⁡BidAidp+Bidpp-1/pB1,Φpykj1-Φpx¯1-C1tkjdkj=A1tkjdkj+B1tkjdkj+otkj-A1tkjdkj+otkj,B1tkjdkj+otkjp-1-A1dp-1sgn⁡A1dA1dp+B1dp(p-1)/pA1tkjdkj-1-Bidp-1sgn⁡BidAidp+Bidp(p-1)/pB1tkjdkj=A1dkj+otkjtkj,B1dkj+otkjtkjpA1dp-1sgn⁡A1dA1dp+B1dp(p-1)/pA1dkj+Bidp-1sgn⁡BidAidp+Bidp(p-1)/pB1dkj-A1dkj+otkjtkj,B1dkj+otkjtkjptkj+o(tkj)=o(tkj).
Subcase
(2) (
|
A
1
d
|
p
+
|
B
1
d
|
p
=
0
). In this case, A1d=0=B1d. Then
(23)Φpykj1-Φpx¯1=A1tkjdkj+B1tkjdkj+o(tkj)-A1tkjdkj+otkj,B1tkjdkj+otkjp=A1dkj+otkjtkj,B1dkj+otkjtkjpA1dkj+B1dkj-A1dkj+otkjtkj,B1dkj+otkjtkjp×tkj+o(tkj)=o(tkj).Example 5.
Consider the following GCP function which is based on proposed family of NCP functions [22] relying on ϕp in (14) and some introduced NCP functions in [23]:
(24)ϕ1(a,b):=ϕp(a,b)+αa+b+,α>0,
where a+=max⁡{0,a} and GCP function Φ(x) in (3) is defined as
(25)Φ1(x):=ϕpfx,gx+αfx+gx+,α>0,
where all the operations are performed componentwise.
Let(26)Jx¯:=i:fix¯=0=gix¯,K(x¯):=i:fix¯>0,gix¯>0.
Then the H-differential of Φ1 at x¯ is given by
(27)TΦ1(x¯)=VA+WB:A,V,W,d∈Γ,
where Γ is the set of all quadruples (A,B,V,W,d) with A∈Tf(x¯), B∈Tg(x¯), d=1, V=diag⁡(vi), and W=diag⁡(wi) being diagonal matrices with
(28)vi=1-fix¯p-1fix¯p+gix¯pp-1/p+αgix¯,i∈K(x¯),1-Aidp-1sgn⁡AidAidp+Bidpp-1/p,i∈Jx¯,Aidp+Bidp>0,1-fix¯p-1sgn⁡fix¯fix¯p+gix¯pp-1/p,i∉J(x¯)∪K(x¯),arbitrary,i∈Jx¯,Aidp+Bidp=0,wi=1-gix¯p-1fix¯p+gix¯pp-1/p+αfix¯,i∈K(x¯),1-Bidp-1sgn⁡BidAidp+Bidpp-1/p,i∈Jx¯,Aidp+Bidp>0,1-gix¯p-1sgn⁡gix¯fix¯p+gix¯pp-1/p,i∉J(x¯)∪K(x¯),arbitrary,i∈Jx¯,Aidp+Bidp=0.
The above calculation relies on the observation that the following is an H-differential of the one variable function Δ:t↦t+ at any t¯:
(29)Δ(t¯)={1}ift¯>0,{0,1}ift¯=0,{0}ift¯<0.Example 6.
The following GCP function is based on NCP function in [22]:
(30)ϕ2(a,b):=ϕp(a,b)+αab+,α>0.
We define the GCP function Φ(x) in (3) as
(31)Φ2(x):=ϕpfx,gx+αfxgx+,α>0,
where all the operations in (31) are performed componentwise.
Let(32)Jx¯:=i:fix¯=0=gix¯,L(x¯):=i:fix¯gix¯>0.
Then the H-differential of Φ2 at x¯ is given by
(33)TΦ2(x¯)={VA+WB:(A,V,W,d)∈Γ},
where Γ is the set of all quadruples (A,B,V,W,d) with A∈Tf(x¯), B∈Tg(x¯), d=1, V=diag⁡(vi), and W=diag⁡(wi) being diagonal matrices with
(34)vi=1-fix¯p-1sgn⁡fix¯fix¯p+gix¯pp-1/p+αgix¯,i∈L(x¯),1-Aidp-1sgn⁡AidAidp+Bidpp-1/p,i∈Jx¯,Aidp+Bidp>0,1-fix¯p-1sgn⁡fix¯fix¯p+gix¯pp-1/p,i∉J(x¯)∪Lx¯,arbitrary,i∈Jx¯,Aidp+Bidp=0,wi=1-gix¯p-1sgn⁡gix¯fix¯p+gix¯pp-1/p+αfix¯,i∈L(x¯),1-Bidp-1sgn⁡BidAidp+Bidpp-1/p,i∈Jx¯,Aidp+Bidp>0,1-gix¯p-1sgn⁡gix¯fix¯p+gix¯pp-1/p,i∉J(x¯)∪L(x¯),arbitrary,i∈Jx¯,Aidp+Bidp=0.Example 7.
The following GCP function is based on NCP function in [23]:
(35)ϕ3(a,b):=ϕpa,b2+αa+b+2,α>0.
We define the GCP functionΦ(x) in (3) as
(36)Φ3(x):=ϕpfx,gx2+αfx+gx+2,α>0,
where all the operations in (36) are performed componentwise.
Let(37)Jx¯:=i:fix¯=0=gix¯,K(x¯):=i:fix¯>0,gix¯>0.
When i∉K(x¯), (Φ3(x¯))i=|(Φp(x¯))i|=-(Φp(x¯))i.
Then theH-differential of Φ3 at x¯ is given by
(38)TΦ3(x¯)=VA+WB:A,V,W,d∈Γ,
where Γ is the set of all quadruples (A,B,V,W,d) with A∈Tf(x¯), B∈Tg(x¯), d=1, V=diag⁡(vi), and W=diag⁡(wi) being diagonal matrices with(39)vi=ϕpfix¯,gix¯1-fix¯p-1/fix¯p+gix¯pp-1/p+αfi(x¯)gi2(x¯)ϕp2fix¯,gix¯+αfix¯,gix¯2,i∈K(x¯),Aidp-1sgn⁡(Aid)Aidp+Bidp(p-1)/p-1,i∈Jx¯,Aidp+Bidp>0,fix¯p-1sgn⁡fix¯fix¯p+gix¯p(p-1)/p-1,i∉J(x¯)∪K(x¯),arbitrary,i∈Jx¯,Aidp+Bidp=0,wi=ϕpfix¯,gix¯1-gix¯p-1/fix¯p+gix¯pp-1/p+αfi2(x¯)gi(x¯)ϕp2fix¯,gix¯+αfix¯,gix¯2,i∈K(x¯),Bidp-1sgn⁡BidAidp+Bidp(p-1)/p-1,i∈Jx¯,Aidp+Bidp>0,gix¯p-1sgn⁡gix¯fix¯p+gix¯p(p-1)/p-1,i∉J(x¯)∪K(x¯),arbitrary,i∈Jx¯,Aidp+Bidp=0.


## 4. Minimizing the Merit Function

In this section, we consider an NCP functionΦ corresponding to GCP and let Ψ:=(1/2)Φ2, when the underlying functions f and g are H-differentiable.It should be recalled that(40)Ψx¯=0⟺Φx¯=0⟺x¯solvesGCP(f,g).LetΦ be an GCP function with an H-differential TΦ(x¯) given by
(41)TΦx¯=VA+WB:A∈Tfx¯,B∈Tg(x¯),V=diag⁡vi,W=diag⁡(wi)VA+WB:A∈Tf(x¯),B∈Tg(x¯).The following theorem from [15] describes H-differential, TΨ(x¯) at x¯, for the merit function Ψ:=1/2Φ2.Theorem 8.
SupposeΦ is H-differentiable at x¯ with S(x¯) as an H-differential. Then Ψ:=(1/2)Φ2 is H-differentiable at x¯ with an H-differential given by
(42)TΨ(x¯)=Φx¯TB:B∈Sx¯.We need the following Lemma [10] in our subsequent analysis.Lemma 9.
Suppose thatf,g:Rn→Rn and g is one-to-one and onto. Define h:Rn→Rn where h:=f∘g-1. The following hold.(a)
f and g are relatively (strictly) monotone if and only if h is (strictly) monotone.(b)
Ifg is Lipschitz-continuous and f and g are relatively strongly monotone then h is strongly monotone.(c)
f and g are relatively P0(P)-functions if and only if h is P0(P)-function.(d)
Ifg is Lipschitz-continuous and f and g are relatively uniform P-functions, then h is uniform P-function.The following result is from [20, 24].Theorem 10.
Under each of the following conditions,f:Rn→Rn is a P0(P)-function. (a)
f is Fréchet differentiable on Rn and, for every x∈Rn, the Jacobian matrix ∇f(x) is a P0(P)-matrix.(b)
f is locally Lipschitzian on Rn and, for every x∈Rn, the generalized Jacobian ∂f(x) consists of P0(P)-matrices.(c)
f is semismooth on Rn (in particular, piecewise affine or piecewise smooth) and, for every x∈Rn, the Bouligand subdifferential ∂Bf(x) consists of P0(P)-matrices.(d)
f is H-differentiable on Rn and, for every x∈Rn, an H-differential Tf(x) consists of P0(P)-matrices.Remarks. Based on some results in [20, 24], we note the following.(i)
ForP-conditions, the the converse statements in the above theorem are usually false.(ii)
ForP0-conditions in Theorem 10, the converse statements of Item (a) and Item (c) are true, while the converse statements of Item (b) and Item (d) may not hold in general ([20, 24]).It is easy to see the following Lemma.Lemma 11.
Suppose thatf,g:Rn→Rn and g is one-to-one and onto. Define h:Rn→Rn where h:=f∘g-1. Suppose that f and g are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯) with Tg(x¯) consisting of nonsingular matrices. Denote y¯:=x¯. Then h is H-differentiable at y¯ with Th(y¯), where
(43)Th(y¯)=AB-1:A∈Tfx¯,B∈Tgx¯.The following two Lemmas give favorable properties which will be needed in our results.Lemma 12.
We can easily see thatΦ, V, and W in Examples 4–6 satisfy the following properties. (i)
x¯ solves GCP (f,g)⇔Φ(x¯)=0.(ii)
vi>0, wi>0, when Φi(x¯)≠0.(iii)
vi+wi≠0, when Φi(x¯)≠0.(iv)
Φ(x¯)Tv≠0, when Φ(x¯)≠0.(v)
Φi(x¯)>0, when fi(x¯)>0, gi(x¯)>0.Proof.
The proof can be easily verified.Lemma 13.
We can easily see thatΦ, V, and W in Example 7 satisfy the following properties: (i)
x¯ solves GCP (f,g)⇔Φ(x¯)=0.(ii)
viwi>0, when Φi(x¯)≠0.(iii)
vi+wi≠0, when Φi(x¯)≠0.(iv)
Φ(x¯)Tv≠0, when Φ(x¯)≠0.(v)
Φi(x¯)>0, when fi(x¯)>0, gi(x¯)>0.Proof.
The proof can be easily verified.Starting withH-differentiable functions f and g, we show that, under appropriate conditions, a vector x¯ is a solution of the GCP(f,g) if and only if zero belongs to TΨ(x¯).In the following theorems we will minimize the merit function underP0(P)-conditions.Theorem 14.
Supposef:Rn→Rn and g:Rn→Rn are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯). Suppose Φ is a GCP function of f and g. Assume that Ψ:=1/2Φ2 is H-differentiable at x¯ with an H-differential given by
(44)TΨx¯=Φx¯T[VA+WB]:A∈Tf(x¯),B∈Tg(x¯),V=diag⁡vi,W=diag⁡wiwithviwi>0wheneverΦi(x¯)≠0x¯T.
Further suppose that Tg(x¯) consists of nonsingular matrices and S(x¯) consists of P0-matrices where S(x¯):={AB-1:A∈Tf(x¯),B∈Tg(x¯)}. Then
(45)0∈TΨ(x¯)⟺Φ(x¯)=0.Proof.
The proof is similar to Theorem 6 in [15].Remark 15.
Theorem14 is applicable to GCP functions of Examples 4–7 by the property (ii) in Lemma 12 and the property (ii) in Lemma 13.A slight modification of the above theorem leads to the following result.Theorem 16.
Supposef:Rn→Rn and g:Rn→Rn are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯). Suppose Φ is a GCP function of f and g. Assume that Ψ:=1/2Φ2 is H-differentiable at x¯ with an H-differential given by
(46)TΨx¯=Φx¯T[VA+WB]:A∈Tf(x¯),B∈Tg(x¯),V=diag⁡vi,W=diag⁡(wi)withviwi>0wheneverΦi(x¯)≠0x¯T.
Further suppose that Tg(x¯) consists of nonsingular matrices and S(x¯) consists of positive semidefinite matrices where S(x¯):={AB-1:A∈Tf(x¯),B∈Tg(x¯)}. Then
(47)0∈TΨ(x¯)⟺Φ(x¯)=0.Proof.
Since every positive semidefinite matrix is also aP0-matrix, the proof follows from Theorem 14.Iff is a monotone (strongly monotone) C1, ∇f(x¯) is positive semidefinite (positive definite) matrix. From Lemma 9, Example 4, and the above theorems, we have the following.Corollary 17.
Supposef:Rn→Rn and g:Rn→Rn are differentiable at x¯. Assume g is continuous and strongly monotone. Moreover, f and g are relatively monotone (relatively strongly monotone) functions. Suppose Φ is a GCP function of f and g, which is based on the generalized Fischer-Burmeister function and Ψ:=1/2Φ2.
Thenx¯ is a local minimizer to Ψ if and only if x¯ solves GCP (f,g).In view of Example5 and the above results, we have the following.Corollary 18.
Supposef:Rn→Rn and g:Rn→Rn are semismooth (piecewise smooth or piecewise affine) at x¯ with Bouligand subdifferentials, respectively, by ∂Bf(x¯) and ∂Bg(x¯). Assume g is continuous, one-to-one, onto and ∂Bg(x¯) consists of nonsingular matrices. Moreover, f and g are relatively monotone (relatively strongly monotone) functions. Suppose Φ is a GCP function of f and g, which is based on the generalized Fischer-Burmeister function and Ψ:=1/2Φ2.
Thenx¯ is a local minimizer to Ψ if and only if x¯ solves GCP(f,g).We state the result for GCP function which is based on the generalized Fischer-Burmeister function. However, as in Theorem14, it is possible to state a very general result for any GCP function Φ satisfying the properties in Lemmas 12 and 13. For simplicity, we avoid dealing in such a generality.Corollary 19.
Supposef:Rn→Rn and g:Rn→Rn are differentiable at x¯. Suppose Φ is a GCP function of f and g, which is the basis of the generalized Fischer-Burmeister function in Example 4 and Ψ:=1/2Φ2. If ∇g(x¯) is nonsingular and the product ∇f(x¯)∇g(x¯)-1 is P0-matrix, then x¯ is a local minimizer to Ψ if and only if x¯ solves GCP (f,g).Corollary 20.
Supposef:Rn→Rn and g:Rn→Rn are differentiable at x¯. Assume g is continuous, one-to-one, onto and ∇g(x¯) is nonsingular. Moreover, assume f and g are relatively P0-functions. Suppose Φ is a GCP function of f and g, which is based on the generalized square Fischer-Burmeister function in Example 4 and Ψ:=1/2Φ2.
Thenx¯ is a local minimizer to Ψ if and only if x¯ solves GCP(f,g).Proof.
Sinceg is one-to-one and onto and f and g are relatively P0-functions, by Lemma 9, the mapping f∘g-1 is P0-function which implies ∇f(x¯)∇g(x¯)-1 is P0-matrix; see [20]. The proof follows from Corollary 19.We recall that a continuous mapping is called a homeomorphism if it is a one-to-one and onto mapping and if its inverse mapping is also continuous.It is known that a continuous, strongly monotone mappingf:Rn→Rn is a homeomorphism from Rn onto itself and the ∇f(x¯) is positive definite matrix if f is C1 (see [20]). So we have the following.Corollary 21.
Supposef:Rn→Rn and g:Rn→Rn are differentiable at x¯. Assume g is continuous and strongly monotone. Moreover, assume f and g are relatively P0-functions. Suppose Φ is a GCP function of f and g, which is based on the generalized Fischer-Burmeister function and Ψ:=1/2Φ2. Then x¯ is a local minimizer to Ψ if and only if x¯ solves GCP(f,g).Remark 22.
Wheng(x)=x in Corollary 21, we get Proposition  3.4 in [22].In a view of Example 2, Theorem 3, Corollary 3 in [24], and the above results, we get the following.Corollary 23.
Supposef:Rn→Rn and g:Rn→Rn are semismooth (piecewise smooth or piecewise affine) at x¯ with Bouligand subdifferentials, respectively, by ∂Bf(x¯) and ∂Bg(x¯). Assume g is continuous, one-to-one, onto and ∂Bg(x¯) consists of nonsingular matrices. Moreover, assume f and g are relatively P0-functions. Suppose Φ is a GCP function of f and g, which is based on the generalized Fischer-Burmeister function and Ψ:=(1/2)Φ2.
Thenx¯ is a local minimizer to Ψ if and only if x¯ solves GCP(f,g).Theorem 24.
Supposef:Rn→Rn and g:Rn→Rn are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯). Suppose Φ is a GCP function of f and g. Assume that Ψ:=1/2Φ2 is H-differentiable at x¯ with an H-differential given by
(48)TΨx¯=Φx¯TVA+WB:A∈Tf(x¯),B∈Tg(x¯),V=diag⁡vi,W=diag⁡(wi)withΦT(x¯)v≠0whenΦ(x¯)≠0,viwi≥0wheneverΦix¯≠0x¯T,
or
(49)TΨx¯=Φx¯TVA+WB:A∈Tf(x¯),B∈Tg(x¯),V=diag⁡vi,W=diag⁡(wi)withviwi≥0,vi+wi≠0wheneverΦix¯≠0x¯T.
Further suppose that Tg(x¯) consists of nonsingular matrices and S(x¯) consists of P-matrices where S(x¯):={AB-1:A∈Tf(x¯),B∈Tg(x¯)}. Then
(50)0∈TΨ(x¯)⟺Φ(x¯)=0.Proof.
The proof is similar to that of Theorem 9 in [15].Remark 25.
Theorem24 is applicable to GCP functions of Examples 4–7 by the properties (i) and (iii) (or (i) and (iv)) in Lemma 12 and (i) and (iii) (or (i) and (iv)) in Lemma 13.Since every positive definite matrix is also aP-matrix, now we minimize the merit function under positive semidefinite/definite conditions.Theorem 26.
Supposef:Rn→Rn and g:Rn→Rn are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯). Suppose Φ is a GCP function of f and g. Assume that Ψ:=1/2Φ2 is H-differentiable at x¯ with an H-differential given by
(51)TΨx¯=Φx¯TVA+WB:A∈Tfx¯,B∈Tg(x¯),V=diag⁡(vi),W=diag⁡(wi)withΦT(x¯)v≠0whenΦ(x¯)≠0,viwi≥0wheneverΦix¯≠0x¯T,
or
(52)TΨx¯=Φx¯T[VA+WB]:A∈Tf(x¯),B∈Tg(x¯),V=diag⁡(vi),W=diag⁡(wi)withviwi≥0,vi+wi≠0wheneverΦix¯≠0x¯T.
Further suppose that Tg(x¯) consists of nonsingular matrices and S(x¯) consists of positive definite matrices where S(x¯):={AB-1:A∈Tf(x¯),B∈Tg(x¯)}. Then
(53)0∈TΨ(x¯)⟺Φ(x¯)=0.Now we replace the condition0∈TΨ(x¯) by weaker conditions 0∈co⁡TΨ(x¯) or 0∈co⁡¯TΨ(x¯). In the next two successive theorems, of course, stronger/different conditions on the H-differentials of f and g will be imposed. First, we have the following definition.Remark 27.
As noted in [15], a stationary point of the problem min⁡f(x) is a point x* such that 0∈co⁡¯Tf(x*) where Tf(x*) is an H-differential of f at x*. By weakening this condition, we may call a point x* a quasi-stationary point (semistationary point) of the problem min⁡f(x) if 0∈Tf(x*) (resp., 0∈co⁡Tf(x*)). While local/global minimizers of min⁡f(x) are stationary points, it is not clear how to get or describe semi- and quasi-stationary points.We will show that under appropriate conditions whenx* is a semistationary point of min⁡Ψ with Ψ:=1/2Φ2, then x* is a solution of a generalized complementarity problem. That is, starting with H-differentiable functions f and g, we show that under appropriate conditions, a vector x* is a solution of the GCP(f,g) if and only if zero belongs to co⁡TΨ(x*).Definition 28.
Consider a nonempty setC in Rn×n. We say that a matrix A is a row representative of C if for each index i=1,2,…,n, the ith row of A is the ith row of some matrix C∈C. We say that C has the row-P0-property (row-P-property) if every row representative of C is a P0-matrix (P-matrix). We say that C has the column-P0-property (column-P-property) if CT={AT:A∈C} has the row-P0-property (row-P-property).We have the result from [9].Proposition 29.
A setC has the row-P0-property (row-P-property) if and only if for each nonzero x∈Rn, there is an index i such that xi≠0 and xi(Cx)i≥0(>0) for all C∈C.A simple consequence of this proposition is the following result in [15].Proposition 30.
The following statements hold.(i)
Suppose the set of matrices{A1,A2,…,AL} has the row-P0-property. Then for any collection {V1,V2,…,VL} of nonnegative diagonal matrices, the sum
(54)A*=∑j=1LVjAj
is a P0-matrix. In particular, any convex combination of the Ais is a P0-matrix.(ii)
Suppose the set of matrices{A1,A2,…,AL} has the row-P-property. Then for any collection {Y1,…,YL,Z*} of nonnegative diagonal matrices with Y1+⋯+YL+Z*>0,
(55)A*=∑j=1LYjAj+Z*
is a P-matrix.Theorem 31.
Supposef:Rn→Rn and g:Rn→Rn are H-differentiable at x¯ with H-differentials, respectively, by Tf(x¯) and Tg(x¯). Suppose Φ is a GCP function of f and g. Assume that Ψ:=1/2Φ2 is H-differentiable at x¯ with an H-differential given by
(56)TΨx¯=Φx¯TVA+WB:A∈Tf(x¯),B∈Tg(x¯),V=diag⁡vi,W=diag⁡(wi)withvi≥0,wi>0wheneverΦi(x¯)≠0x¯T.
Further suppose S(x¯) has the column-P-property where S(x¯):=Tf(x¯)∪Tg(x¯). Then
(57)0∈co⁡TΨ(x¯)⟺Φ(x¯)=0.Proof.
SupposeΦ(x¯)=0; then co⁡TΨ(x¯)={0}. Conversely, suppose 0∈co⁡TΨ(x¯). Then by Carathéodory’s theorem, there exist Φ(x¯)T[VjAj+WjBj]∈TΨ(x¯) and scalars λj>0, Aj∈Tf(x¯), and Bj∈Tg(x¯) for j=1,2,…,L with L≤n+1 such that
(58)∑j=1LλjΦx¯TVjAj+WjBj=0,
where ∑j=1L‍λj=1. Then (58) can be rewritten as
(59)Φx¯TY1A1+⋯+YLAL+Z1B1+⋯+ZLBL=0,
where λjVj=Yj and λjWj=Zj for all j. And (59) can reduce to
(60)C*TΦ(x¯)=0,
where C*=Y1A1+⋯+YLAL+Z1B1+⋯+ZLBL. From (60), we have
(61)C*TΦx¯i=0,fori=1,2,…,n.
Then
(62)Φi(x¯)C*TΦx¯i=0,fori=1,2,…,n.
Now, we claim that Φ(x¯)=0. Assume the contrary that Φ(x¯)≠0; then for Φ(x¯), from Proposition 29, there is an index i0 such that Φi0(x¯)≠0 and
(63)Φi0(x¯)CTΦx¯i0>0,∀C∈A1,…,AL,B1,…,BL.
Note that vi0j≥0, wi0j>0 and λj>0 for j=1,2,…,L; then we have
(64)Φi0(x¯)YjAjTΦx¯i0=λjvi0jΦi0(x¯)AjTΦx¯i0≥0,Φi0(x¯)ZjBjTΦx¯i0=λjwi0jΦi0(x¯)BjTΦx¯i0>0,
for j=1,2,…,L. Then we obtain
(65)Φi0x¯C*TΦx¯i0=∑j=1LΦi0(x¯)YjAjTΦx¯i0+∑j=1LΦi0(x¯)ZjBjTΦx¯i0>0.(65) contradicts (62). This proves that Φ(x¯)=0.Remark 32.
(i) Wheng(x)=x, the GCP reduces to NCP.
(ii) Theorem31 is applicable to GCP functions of Examples 4–7 by the properties (ii) in Lemma 12 and (ii) in Lemma 13.Concluding Remarks. We considered a generalized complementarity problem corresponding to H-differentiable functions, with an associated GCP function Φ and a merit function Ψ(x)=1/2Φ2. In this paper, we showed under certain P(P0)-conditions the global/local minimum or a stationary point of Ψ is a solution of GCP(f,g). For generalized complementarity problem based on the penalized Fischer-Burmeister function, our results give various results for generalized complementarity problem when the underlying functions are continuously differentiable (locally Lipschitzian, semismooth, and directionally differentiable) functions. For example, we have the following.(i)
Wheng(x)=x in this paper, then GCP(f,g) reduces to nonlinear complementarity problem NCP(f) and we get results for nonsmooth NCP(f) based on the generalized Fischer-Burmeister function and its generalizations which seems to be new.(ii)
Whenf and g are C1 in which case Tf(x¯)={∇f(x¯)} and Tg(x¯)={∇g(x¯)}, our results will be true when the underlying functions are C1 and get the results in [25].(iii)
Whenf is C1 and g(x)=x (in which case we can let Tf(x¯)={∇f(x¯)}), GCP(f,g) reduces to nonlinear complementarity problem NCP(f), and the results of this paper will be valid for NCP(f).(iv)
Whenf is locally Lipschitzian with Tf(x¯)=∂f(x¯) and g(x)=x, our results will be applicable to NCP(f) when the underlying data are locally Lipschitzian.(v)
Our results give various results for generalized complementarity problem whenp-norm is replaced by 2-norm (or when p is an integer greater than 2), we can state our results for GCP function based on the Fischer-Burmeister function and we get the following.
(a)
Whenf and g are C1 in which case Tf(x¯)={∇f(x¯)} and Tg(x¯)={∇g(x¯)}, Theorem 14 reduces to Theorem  3.2 in [26].(b)
Whenf is C1 and g(x)=x (in which case we can let Tf(x¯)={∇f(x¯)}), GCP(f,g) reduces to NCP(f) and the above result reduces to Prop. 3.4 in [27].(c)
Whenf is locally Lipschitzian with Tf(x¯)=∂f(x¯) and g(x)=x, the above theorem reduces to a result for nonlinear complementarity problem by Fischer [28]. Moreover, when g(x)=x, our result extends/generalizes a result obtained by Geiger and Kanzow [29] for NCP(f) under monotonicity of a C1 function and by Jiang [30] under uniform P-property of a directionally differentiable function.To the best of our knowledge, solving nonsmooth GCP(f,g) on the basis of the generalized Fischer-Burmeister function and its generalizations seems to be new.



---

*Source: 468065-2014-11-17.xml*