GENERALIZED STRONGLY SET-VALUED NONLINEAR COMPLEMENTARITY PROBLEMS

(1)

GENERALIZED STRONGLY SET-VALUED NONLINEAR COMPLEMENTARITY PROBLEMS

NAN-JING HUANG and YEOL JE CHO (Received 7 October 1997)

Abstract.In this paper, we introduce a new class of generalized strongly set-valued nonlinear complementarity problems and construct new iterative algorithms. We show the existence of solutions for this kind of nonlinear complementarity problems and the convergence of iterative sequences generated by the algorithm. Our results extend some recent results in this ﬁeld.

Keywords and phrases. Complementarity problem, strongly monotone and Lipschitz continuous mappings, strongly monotone andH-Lipschitz continuous set-valued mappings, algorithm.

1991 Mathematics Subject Classiﬁcation. 90C33, 47H04.

1. Introduction. The complementarity theory, which was introduced by Lemke [11], Cottle, and Dantzig [6] in the early 1960s and later developed by others, plays an important and fundamental role in the study of a wide class of problems arising in mechanics, physics, control and optimization, economics and transportation equilibrium, contact problems in elasticity, ﬂuid ﬂow through porous media, and many other branches of mathematical and engineering sciences [1, 2, 3, 4, 5, 7, 8, 9, 10, 13, 14, 15].

In particular, the set-valued quasi-(implicit)complementarity problems, considered and studied by Chang and Huang [2, 3], are important among the generalizations of the complementarity problems. In [14], Noor introduced and studied some new classes of nonlinear complementarity problems for single-valued mappings inRⁿand, in [4], Chang and Huang introduced and studied some new nonlinear complementarity problems for compact-valued fuzzy mappings and set-valued mappings which include many kinds of complementarity problems, considered by Chang [1], Cottle et al. [7], Isac [9], and Noor [13, 14], as special cases.

In this paper, we introduce and study a new class of generalized strongly set-valued nonlinear complementarity problems and construct new iterative algorithms. We also discuss the existence of solutions for this kind of nonlinear complementarity problems and the convergence of iterative sequences generated by the algorithm. Our results improve and develop some results in [4, 13, 14].

2. Preliminaries. LetRⁿbe the Euclidean space endowed with norm·and inner product(·,·), respectively. In the sequel, we use the following notations:

2^Rⁿ= {A:A⊂RⁿandAis nonempty}, (2.1) CB(Rⁿ)= {A:A⊂RⁿandAis nonempty, bounded, and closed}, (2.2)

(2)

|x| =

|x1|,|x2|,...,|xn|

for allx∈Rⁿ. (2.3) LetF, G, Q:Rⁿ→2^Rⁿ be three set-valued mappings and f, g:Rⁿ →Rⁿ be two single-valued mappings. Now, we consider the following problem.

Findu∈Rⁿ,x∈F(u),y∈G(u), andz∈Q(y)such that u≥0, f (x)+g(z)≥0,

u,f (x)+g(x)

=0. (2.4)

This problem is called the generalized strongly set-valued nonlinear complementarity problem.

IfQis the identity mapping onRⁿ, then problem (2.4) is equivalent to the following.

Findu∈Rⁿ,x∈F(u)andy∈G(u)such that u≥0, f (x)+g

y

≥0,

u,f (x)+g y

=0. (2.5)

This problem is called the generalized set-valued nonlinear complementarity problem.

IfF is the identity mapping onRⁿ, then problem (2.5) is equivalent to the following.

Findu∈Rⁿandy∈G(u)such that u≥0, f (u)+g

y

≥0,

u,f (u)+g y

=0, (2.6)

which was considered by Chang and Huang in [4].

If F =G is the identity mapping on Rⁿ, then problem (2.5) is equivalent to the following.

Findu∈Rⁿsuch that

u≥0, f (u)+g(u)≥0,

u,f (u)+g(u)

=0, (2.7)

which was considered by Noor [14].

IfF =Gis the identity mapping onRⁿandf≡0,then problem (2.5) is equivalent to the following.

Findu∈Rⁿsuch that

u≥0, g(u)≥0,

u,g(u)

=0, (2.8)

which was considered by Karamardian [10], Fang [8], and Noor [13].

Obviously, problem (2.4) can be written as follows:

Findu∈Rⁿ,x∈F(u),y∈G(u)andz∈Q(y)such that

u≥0, v=f (x)+g(z)≥0, (u,v)=0. (2.9) We now consider the following equalities:

u=¹₂

|w|+w

, v= λρ−1

|w|−w

, (2.10)

whereλ,ρ >0 are constants. Clearly,u≥0 andv≥0. From (2.5) and (2.9), it follows that problem (2.9) is equivalent to the following.

Findw∈Rⁿ,x∈F(1/2(|w|+w)),y∈G(1/2(|w|+w)), andz∈Q(y)such that w=¹₂

|w|+w

−¹₂λρ

f (x)+g(z)

, (2.11)

whereλ, ρ >0 are constants.

(3)

3. Algorithms. Based on the formulations in Section 2, we now construct the new algorithms for the generalized strongly set-valued nonlinear complementarity problem (2.4).

LetF,G,Q:Rⁿ→CB(Rⁿ)be three set-valued mappings and letf,g:Rⁿ→Rⁿ be two single-valued mappings. For anywo∈Rⁿ, let

x0∈F₁

2

|w0|+w0

, y0∈G₁

2

|w0|+w0

, z0∈Q y0

(3.1) and

w1=¹₂(1−λ)

|w0|+w0 +¹₂λ

|w0|+w0−ρ

f (x0)+g(z0)

, (3.2)

whereλ,ρ >0 are constants.

Sincex0∈F(1/2(|w0|+w0)), y0∈G(1/2(|w0| +w0))and z0∈Q(y0), by Nadler [12], there existx1∈F(1/2(|w1|+w1)),y1∈G(1/2(|w1|+w1))andz1∈Q(y1)such that

x0−x1 ≤(1+1)H F₁

2

|w0|+w0 ,F₁

2

|w1|+w1

, (3.3)

y0−y1 ≤(1+1)H G

12

|w0|+w0 ,G

12

|w1|+w1

, (3.4)

z1−z0 ≤(1+1)H Q

y1 ,Q

y0

, (3.5)

whereH(·,·)denotes the Hausdorﬀ metric on CB(Rⁿ).

Thus, by induction, we can obtain the following algorithm:

Algorithm3.1. LetF,G,Q:Rⁿ→CB(Rⁿ)be three set-valued mappings and let f,g:Rⁿ→Rⁿ be two single-valued mappings. For any w0∈Rⁿ, we can construct sequences{wn},{xn},{yn}, and{zn}inRⁿas follows:

xn∈F

12

|wn|+wn

, yn∈G

12

|wn|+wn

, zn∈Q yn

, xn−xn+1 ≤

1+ 1

n+1

H

F₁

2

|wn|+wn ,F₁

2

|wn+1|+wn+1 , yn−yn+1 ≤

1+ 1

n+1

H

G₁

2

|wn|+wn ,G₁

2

|wn+1|+wn+1

, (3.6) zn−zn+1 ≤

1+ 1 n+1

H

Q yn

,Q yn+1

, wn+1=¹₂(1−λ)

|wn|+wn +¹₂λ

|wn|+wn−ρ

f (xn)+g(zn)

forn=0,1,2,..., whereλ,ρ >0 are constants.

From Algorithm 3.1, we can obtain the following algorithms.

Algorithm3.2. LetF,G:Rⁿ→CB(Rⁿ)be two set-valued mappings and letf,g: Rⁿ→Rⁿbe two single-valued mappings. For anyw0∈Rⁿ, we can construct sequences

(4)

{wn},{xn}, and{yn}inRⁿas follows:

xn∈F₁

2

|wn|+wn

, yn∈G₁

2

|wn|+wn , xn−xn+1 ≤

1+ 1

n+1

H

F₁

2

|wn|+wn ,F₁

2

|wn+1|+wn+1 , yn−yn+1 ≤

1+ 1

n+1

H

G₁

2

|wn|+wn ,G₁

2

|wn+1|+wn+1 , wn+1=¹₂(1−λ)

|wn|+wn +¹₂λ

|wn|+wn−ρ

f (xn)+g(zn)

(3.7)

Algorithm3.3[4]. LetG:Rⁿ→CB(Rⁿ)be a set-valued mapping and letf,g: Rⁿ→Rⁿbe two single-valued mappings. For anyw0∈Rⁿ, we can construct sequences {wn}and{yn}inRⁿas follows:

yn∈G₁

2

|wn|+wn

, (3.8)

yn−yn+1≤ 1+ 1

n+1

H G

12

|wn|+wn ,G

12

|wn+1|+wn+1

, (3.9)

wn+1=¹₂(1−λ)

|wn|+wn +¹₂λ

|wn|+wn−ρ f₁

2

|wn|+wn +g

yn (3.10) forn=0,1,2,..., whereλ,ρ >0 are constants.

Algorithm3.4. [14] Letf,g:Rⁿ→Rⁿ be two single-valued mappings. For any w0∈Rⁿ, we can construct sequences{wn}and{yn}inRⁿas follows.

yn=¹₂

|wn|+wn

, (3.11)

wn+1=¹₂(1−λ)

|wn|+wn +¹₂λ

|wn|+wn−ρ f

12

|wn|+wn +g

yn (3.12)

Algorithm3.5. [15] Letg:Rⁿ→Rⁿbe a single-valued mapping. For anyw0∈Rⁿ, we can construct sequences{wn}and{yn}inRⁿas follows.

yn=¹₂

|wn|+wn

, (3.13)

wn+1=¹₂(1−λ)

|wn|+wn +¹₂λ

|wn|+wn−ρ g

yn

(3.14) forn=0,1,2,..., whereλ,ρ >0 are constants.

4. Existence and convergence. In this section, we show the existence of solutions for the generalized strongly set-valued nonlinear complementarity problem (2.4) and the convergence of the iterative sequences constructed by Algorithm 3.1. We ﬁrst give some deﬁnitions.

Deﬁnitions4.1.

(1) A mappingf:Rⁿ→Rⁿis said to bestrongly monotoneif there exists a constant α >0 such that

f (u)−f (v),u−v

≥αu−v² (4.1)

(5)

for allu,v∈Rⁿ.

(2) A mappingf:Rⁿ→Rⁿis said to beLipschitz continuousif there exists a constant β >0 such that

f (u)−f (v)≤βu−v (4.2)

for allu,v∈Rⁿ. The numberβin(2)is calledLipschitz constant.

It is easy to see thatα≤β.

Deﬁnitions4.2.

(1) A set-valued mappingF :Rⁿ→CB(Rⁿ)is said to be strongly monotone with respect to the mappingf:Rⁿ→Rⁿif there exists a constantα >0 such that

f (x)−f y

,u−v

≥αu−v² (4.3)

for allu,v∈Rⁿ,x∈F(u)andy∈F(v).

(2) A set-valued mappingF :Rⁿ→CB(Rⁿ)is said to beH-Lipschitz continuousif there exists a constantβ >0 such that

H

F(u),F(v)

≤βu−v (4.4)

for allu,v∈Rⁿ. The numberβin(2)is called theH-Lipschitz constant.

Now, we give our main theorems in this paper.

Theorem4.1. Suppose thatf,g:Rⁿ→Rⁿare Lipschitz continuous with Lipschitz constantsδandξ, respectively, andF,G,Q:Rⁿ→CB(Rⁿ)areH-Lipschitz continuous withH-Lipschitz constantsβ,η,ν, respectively, andFis strongly monotone with respect tofwith strongly monotone constantα. If

0< ρ < 4(α−ξνη)

(δβ)²−(ξνη)², ρξνη <2, ξνη <min{α,δβ}, (4.5) then there existu,x,y,z∈Rⁿwhich solve problem (2.4). Furthermore, it follows that

12

|wn|+wn

→u, xn →x, yn →y, zn →z as n→ ∞, (4.6) where{wn},{xn},{yn}, and{zn}inRⁿare the sequences generated by Algorithm 3.1.

Proof. By Algorithm 3.1, we have wn+1−wn

=¹₂(1−λ)

|wn|+wn +¹₂λ

|wn|+wn−ρ f

xn +g

zn

−¹₂(1−λ)

|wn−1|+wn−1

−¹₂λ

|wn−1|+wn−1−ρ f

xn−1 +g

zn−1

≤(1−λ)wn−wn−1+¹₂λρg zn

−g zn−1 +λ¹₂

|wn|+wn

−¹₂

|wn−1|+wn−1

−¹₂ρ f

xn

−f

xn−1.

(4.7)

(6)

SinceF,G, andQareH-Lipschitz continuous andf andgare Lipschitz continuous, from (3.6), it follows that

f xn

−f

xn−1≤δxn−xn−1

≤δ

1+1 n

H F₁

2

|wn|+wn ,F₁

2

|wn−1|+wn−1

≤δ 1+1

n

β

|wn|+wn

2 −|wn−1|+wn−1

2

≤δ

1+1 n

βwn−wn−1

(4.8)

and g zn

−g zn−1

≤ξzn−zn−1≤ξ

1+1 n

H Q

yn ,Q

yn−1

≤ξν 1+1

n

yn−yn−1

≤ξν 1+1

n 2

H G

12

|wn|+wn ,G

12

|wn−1|+wn−1

≤ξν

1+1 n

2

ηwn−wn−1.

(4.9)

Further, from the strong monotonicity ofF with respect tof and (4.8), we have 1

2

|wn|+wn

−1 2

|wn−1|+wn−1

−1 2ρ

f xn

−f

xn−1

2

≤

1−αρ+1 4ρ²δ²

1+1

n 2

β²wn−wn−1².

(4.10)

Thus, it follows, from (4.7), (4.8), (4.9), and (4.10), that wn+1−wn

≤

1−λ+1 2λρξη

1+1

n

+λ 1−αρ+1 4ρ²δ²β²

1+1

n 2

wn−wn−1

=θnwn−wn−1,

(4.11) where

θn=1−λ+1 2λρξνη

1+1

n ₂

+λ 1−αρ+1 4ρ²δ²β²

1+1

n ₂

. (4.12)

Letting

θ=1−λ+1

2λρξνη+λ 1−αρ+1

4ρ²δ²β², (4.13) θn →θ asn→ ∞. In view of (4.5), we know that 0< θ <1 and so θn <1 for n suﬃciently large. It follows from (4.11) that{wn}is a Cauchy sequence inRⁿand so

(7)

we can suppose thatwn→wasn→ ∞. (4.8) and (4.9) imply that{xn},{yn}, and{zn} are also Cauchy sequences inRⁿ. Letxn→x,yn→y, andzn→zasn→ ∞. Letting u=¹₂(|w|+w), we get

12

|wn|+wn

→u, xn →x, yn →y, zn →z asn → ∞. (4.14) Now, we prove thatx∈F(u),y∈G(u), andz∈Q(y). In fact, we have

d(x,F(u))=inf{x−z:z∈F(u)}

≤x−xn+d

xn,F(u)

≤x−xn+H F₁

2wn+wn ,F(u)

≤x−xn+β¹₂wn+wn

−u,

(4.15)

and henced(x, F(u))=0. This implies thatx∈F(u). Similarly, we havey∈G(u) andz∈Q(y). This completes the proof.

From Theorem 4.1, we get the following theorem.

Theorem4.2. Suppose thatf,g:Rⁿ→Rⁿare Lipschitz continuous with Lipschitz constantsδandξ, respectively, andF,G:Rⁿ→CB(Rⁿ)areH-Lipschitz continuous with H-Lipschitz constantsβandη, respectively, andFis strongly monotone with respect to fwith strongly monotone constantα. If

0< ρ < 4(α−ξη)

(δβ)²−(ξη)², ρξη <2, ξη <min{α,δβ}, (4.16) then there existu,x,y∈Rⁿwhich solve problem (2.5). Furthermore, it follows that

12wn+wn

→u, xn →x, yn →y asn → ∞, (4.17) where{wn},{xn}, and{yn}inRⁿare the sequences generated by Algorithm 3.2.

Theorem4.3[4]. Letf,g, andGbe the same as in Theorem 4.2. Further, suppose thatf is strongly monotone with strongly monotone constantα. If

0< ρ < 4(α−ξη)

δ²−(ξη)², ρξη <2, ξη < α, (4.18) then there existu,y∈Rⁿwhich solve problem (2.6), and

12(|wn|+wn) →u, yn →y, asn → ∞, (4.19) where{wn}and{yn}are two sequences generated by Algorithm 3.3.

Theorem4.4[14]. Letf andgbe the same as in Theorem 4.3. If 0< ρ <4(α−ξ)

δ²−ξ² , ρξ <2, ξ < α, (4.20) then there existsu∈Rⁿwhich is a solution of problem (2.7), and ¹₂(|wn|+wn)→uas n→ ∞, where{wn}is the sequence generated by Algorithm 3.4.

(8)

Theorem4.5[15]. Suppose thatg:Rⁿ→Rⁿ is strongly monotone and Lipschitz continuous with strongly monotone constantαand Lipschitz constant δ. If 0< ρ <

4α/δ², then there existsu∈Rⁿwhich is a solution of problem (2.8), and¹₂(|wn|+wn)→ uasn→ ∞, where{wn}is the sequence generated by Algorithm 3.5.

Acknowledgement. The second author was supported by the academic research fund of Ministry of Education, Republic of Korea, 1997, Project No. BSRI-97-1405.

References

[1] S. S. Chang,Variational Inequality and Compltementarity Problem Theory with Applica- tions, Shanghai Scientiﬁc and Tech. Literature Publishing House, Shanghai, 1991.

[2] S. S. Chang and N. J. Huang,Generalized multivalued implicit complementarity prob- lems in Hilbert spaces, Math. Japon.36(1991), no. 6, 1093–1100. MR 92m:47139.

Zbl 748.49006.

[3] ,Generalized strongly nonlinear quasi-complementarity problems in Hilbert spaces, J. Math. Anal. Appl.158(1991), no. 1, 194–202. MR 92d:90104. Zbl 739.90067.

[4] ,Generalized complementarity problems for fuzzy mappings, Fuzzy Sets and Sys- tems55(1993), no. 2, 227–234. MR 94e:65067. Zbl 790.90076.

[5] R. W. Cottle,Complementarity and variational problems, Symposia Mathematica, 19 (Lon- don), Academic Press, 1976, pp. 177–208. MR 58 20486. Zbl 349.90083.

[6] R. W. Cottle and G. B. Dantzig,Complementary pivot theory of mathematical program- ming, Linear Algebra Appl.1(1968), no. 1, 103–125. MR 37#2515. Zbl 155.28403.

[7] R. W. Cottle, J. S. Pang, and R. E. Stone,The Linear Complementarity Problem, Computer Science and Scientiﬁc Computing, Academic Press, Inc., Boston, London, 1992.

MR 93f:90001. Zbl 757.90078.

[8] S. C. Fang,An iterative method for generalized complementarity problems, IEEE Trans.

Automat. Control25(1980), no. 6, 1225–1227. MR 82i:90116. Zbl 483.49027.

[9] G. Isac,Complementarity Problems, Lecture Notes in Mathematics, vol. 1528, Springer- Verlag, Berlin, 1992. MR 94h:49002. Zbl 795.90072.

[10] S. Karamardian,Generalized complementarity problem, J. Optim. Theory Appl.8(1971), 161–168. MR 47 10073. Zbl 218.90052.

[11] C. E. Lemke,Bimatrix equilibrium points and mathematical programming, Management Sci.11(1964/1965), 681–689. MR 32#7243. Zbl 139.13103.

[12] S. B. Nadler, Jr.,Multi-valued contraction mappings, Paciﬁc J. Math.30(1969), 475–488.

MR 40#8035. Zbl 187.45002.

[13] M. A. Noor,Generalized nonlinear complementarity problem, J. Natur. Sci. Math.26(1986), no. 1, 9–19. MR 87k:90265. Zbl 595.90088.

[14] ,Fixed point approach for complementarity problems, J. Math. Anal. Appl. 133 (1988), no. 2, 437–448. MR 89g:90223. Zbl 649.65037.

[15] M. A. Noor and S. Zarae,An iterative scheme for complementarity problems, Engrg. Anal.

J.3(1986), 240–243.

Huang: Department of Mathematics, Sichuan University, Chengdu, Sichuan610064, China

Cho: Department of Mathematics, Gyeongsang NationalUniversity, Chinju660-701, Korea

(9)

Special Issue on

Modeling Experimental Nonlinear Dynamics and Chaotic Scenarios

Call for Papers

Thinking about nonlinearity in engineering areas, up to the 70s, was focused on intentionally built nonlinear parts in order to improve the operational characteristics of a device or system. Keying, saturation, hysteretic phenomena, and dead zones were added to existing devices increasing their behavior diversity and precision. In this context, an intrinsic nonlinearity was treated just as a linear approximation, around equilibrium points.

Inspired on the rediscovering of the richness of nonlinear and chaotic phenomena, engineers started using analytical tools from “Qualitative Theory of Di

ﬀ

erential Equations,”

allowing more precise analysis and synthesis, in order to produce new vital products and services. Bifurcation theory, dynamical systems and chaos started to be part of the mandatory set of tools for design engineers.

This proposed special edition of the Mathematical Prob-

lems in Engineering aims to provide a picture of the impor-

tance of the bifurcation theory, relating it with nonlinear and chaotic dynamics for natural and engineered systems.

Ideas of how this dynamics can be captured through precisely tailored real and numerical experiments and understanding by the combination of specific tools that associate dynamical system theory and geometric tools in a very clever, sophis- ticated, and at the same time simple and unique analytical environment are the subject of this issue, allowing new methods to design high-precision devices and equipment.

Authors should follow the Mathematical Problems in Engineering manuscript format described at

http://www .hindawi.com/journals/mpe/. Prospective authors should

submit an electronic copy of their complete manuscript through the journal Manuscript Tracking System at

http://

mts.hindawi.com/

according to the following timetable:

Manuscript Due February 1, 2009 First Round of Reviews May 1, 2009 Publication Date August 1, 2009

Guest Editors

José Roberto Castilho Piqueira,

Telecommunication and Control Engineering Department, Polytechnic School, The University of São Paulo, 05508-970 São Paulo, Brazil;

[email protected]

Elbert E. Neher Macau,

Laboratório Associado de Matemática Aplicada e Computação (LAC), Instituto Nacional de Pesquisas Espaciais (INPE), São Josè dos Campos, 12227-010 São Paulo, Brazil ; [email protected]

Celso Grebogi,

Department of Physics, King’s College, University of Aberdeen, Aberdeen AB24 3UE, UK;

[email protected]

Hindawi Publishing Corporation http://www.hindawi.com