Generalized linear complementarity problems

GENERALIZED LINEAR COMPLEMENTARITY PROBLEMS M. Seetharama Gowda and Thomas I. Seidman1 University of Maryland Baltimore County, Baltimore, Maryland 21228, U.S.A. It has been shown by Lemke that if a matrix is copositive plus on IRn, then feasibility of the corresponding Linear Complementarity Problem implies solvability. In this article we show, under suitable conditions, that feasibility of a Generalized Linear Complementarity Problem (i.e., de ned over a more general closed convex cone in a real Hilbert Space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a nite dimensional real Hilbert Space, polyhedral cones are the only ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for Generalized Linear Complementarity Problems.

Key Words: Linear Complementarity Problems, polyhedral cones, copositive plus, thin cone.

Abbreviation Title: Complementarity Problem.

1 This research has been partially supported by the Air Force Oce of Scienti c Research under grants #AFOSR{82{0271 and #AFOSR{87{0350.

1

1 Introduction There are many existence results concerning Complementarity Problems in both nite dimensional and in nite dimensional settings. See, e.g., Habetler and Price [10], Karamardian [12{15], More [22,23], Parida and Roy [25], Saigal [26], Allen [1], Borwein [3,4], Isac [11]. By a Generalized Linear Complementarity Problem (GLCP) on a real Hilbert Space H we mean: Find an x 2 K such that hTx + q; ki  0 (8 k 2 K) and hTx + q; xi = 0 where we are given a closed convex cone K in H, a continuous linear operator T on H, and a q in H. We denote this problem by GLCP (T; K; q). The phrase `generalized linear complementarity problem' was introduced (in the nite dimensional setting) by Habetler and Price [10]. The generalization there is to the use of a cone other than the non-negative orthant K = (IR+)n  IRn | the setting for the (classical) Linear Complementarity Problem which has been extensively studied. Here, we include the generalization to in nite dimensional Hilbert spaces (although we must note that only our main existence result, Theorem 4.1, deals with a general Hilbert space; the rest is set in IRn) and also a further generalization to consider linear operators T which are copositive plus but which need not be strictly copositive. In this article, we prove existence and perturbation results for Generalized Linear Complementarity Problems. Our main result, which says that under suitable conditions the solution set of a Generalized Linear Complementarity Problem is nonempty and weakly compact, extends several results of Borwein [3]. Our proof of the main result is based on approximating the given cone by polyhedral cones and applying the (classical) result of Lemke (that for copositive plus matrices, feasibility implies solvability) to each of the polyhedral cones. This result can also be proved by using Ky Fan's min-max inequality (Allen [1], Isac [11]); such a proof (for a nonlinear mapping on a locally compact cone in a locally convex space) will appear elsewhere. This paper is organized as follows. In Sec. 3, we state an existence result of Lemke type for polyhedral cones. The main existence result appears in Sec. 4. A perturbation result of Mangasarian-Doverspike type is given in Sec. 6. Sec. 7 deals with a characterization of polyhedral cones in nite dimensional spaces. Finally we state some open problems and indicate a generalization to re exive Banach spaces. 2

2 Preliminaries

Let T be a bounded linear operator on a real Hilbert space H. The adjoint T of T is the (unique) bounded linear operator on H de ned by hTx; yi = hx; Tyi(x; y 2 H); when H=IRn, T is just the transpose of T. If T = T, we say that T is self-adjoint. For a closed convex cone K  H (i.e., one has (x + y) 2 K for x; y 2 K and ;  0) we de ne the polar of K by K := fx 2 H : hx; ki  0 for all k 2 Kg: Given such T, K and an element q 2 H, we say that GLCP (T; K; q), as de ned in the previous section, is feasible provided there exists some x in K such that (Tx + q) is in K. In this case we also call such an x feasible for GLCP (T; K; q). We say that GLCP (T; K; q) is solvable if there is an x which is feasible for GLCP (T; K; q) and for which hTx + q; xi = 0. We say that T is copositive plus on K if (a) k 2 K implies hTk; ki  0, (b) k 2 K and hTk; ki = 0 imply (T + T)k = 0. We say that T is monotone on K if hTx ? Ty; x ? yi  0 for x; y 2 K. A set E in H is separable if E contains a countable subset which is dense in E . The weak topology on H is the weakest topology on H making the functional: x 7! hx; yi continuous for each y 2 H and the weak-closure of a set E in H is the closure of E in the weak topology of H. A cone K is said to be thin if K is separable and 0 is not in the weakclosure of fk 2 K : kkk = 1g. (Note that: Every cone in a nite dimensional subspace of H is thin. For any  > 0 and a xed non-zero element e in a separable Hilbert space H, the cone fx 2 H : hx; ei  kxkkekg is thin. It can easily be shown, using the re exivity of H, that a thin cone is weakly locally compact). A cone K is said to be polyhedral if there exists a nite set fa1; a2; : : : ; ang  K such that

K = fx 2 H : x =

Xn  a ;   0g: m m m

m=1

We note that polyhedral cones are always thin. 3

For q1; q2 2 H, q2 q1 denotes the linear operator on H de ned by (q2 q1)(x) = hq1; xiq2 A real valued function '(x) is lower semi-continuous (lsc for short) on K, with respect to the weak topology, if lim inf'(y)  '(x) whenever y ! x weakly in K. For E  H, we write: Span E for the smallest linear subspace of H containing E , int E for the interior of E in H, @ E for its boundary, and E ? for the set fx 2 H : hx; ei = 0 for all e 2 Eg. For an operator T, we write: Ran T = fTx : x 2 Hg for the range and Ker T = fx 2 H : Tx = 0g for the kernel.

3 An Existence Result for Polyhedral Cones

Theorem 3.1 Let K be polyhedral and let T be copositive plus on K. If GLCP (T; K; q) is feasible then it is solvable. If dim H < 1, then, by using an inner product preserving transformation, we can assume that H = IRn for some n; using the usual inner product on IRn . Since K is polyhedral, there is a positive integer m and an n  m matrix B : IRm ! IRn such that B(IRm+ ) = K. It follows easily that T^ := BTB is copositive plus on IRm+ . Since GLCP (T; K; q) is feasible, there is some x0 2 K such that hTx0 + q; ki  0 for k 2 K. For any element in x^0 2 IRm+ such that Bx^0 = x0 one then has hT^ x^0 + Bq; xi = hB(Tx0 + q); xi = hTx0 + q; Bxi  0 for each x 2 IRm+ . Thus, GLCP (T^ ; IRm+ ; Bq) is feasible. By Lemke's Theorem [16], there exists an x^ 2 IRm+ such that hT^ x^ + Bq; xi  0 (x 2 IRm+ ) and hT^ x^ + Bq; x^i = 0: (1) Proof:

Simpli cation of (3.1) leads to

hT(Bx^) + q; Bxi  0(x 2 IRm+ ) and hT(Bx^) + q; Bx^i = 0 and we observe that Bx^ solves GLCP (T; K; q). 4

For the general case, let X be a nite dimensional subspace of H containing K. Let P be the (orthogonal) projection from H into X and set S := PT. Then S : X ! X is copositive plus on K, and hSx0 +Pq; ki = hTx0 +q; ki  0 for each k 2 K; thus GLCP (S; K; Pq) is feasible in X . By the previous case, there exists x 2 K such that

hSx + Pq; ki  0(k 2 K); and hSx + Pq; xi = 0: (2) Since hSx + Pq; ki = hTx + q; ki for each k 2 K, (3.2) shows that this x is a solution of GLCP (T; K; q).

4 Existence Results for a General Cone

Theorem 4.1 Suppose that (i) T is copositive plus on K, (ii) the map x 7! hTx; xi is weak-lsc on K, (iii) K is thin, (iv) fk 2 K : Tk 2 K, hTk; ki = 0, and hq; ki = 0g = f0g. If GLCP (T; K; q) is feasible, then the solution set of GLCP (T; K; q) is nonempty and weakly compact.

We rst show existence of a solution. Let x0 be feasible for GLCP (T; K; q). We can assume that x0 6= 0 and K 6= f0g; else 0 is the desired solution. Then the set fx 2 K : kxk = 1g is non-empty and separable by (iii). Let f0; 1; : : :g be a dense subset of fx 2 K : kxk = 1g with 0 := x0=kx0k and let Kn be the closed convex cone generated by f0; 1; : : : ; ng; each Kn is polyhedral and contains x0. Since Kn  K, T is copositive plus on Kn for each n = 1; 2; : : : by (i). Now x an n. Since x0 is feasible for GLCP (T; Kn ; q), Theorem 3.1 gives an xn 2 Kn such that Proof:

hTxn + q; ki  0 (k 2 Kn ); and hTxn + q; xni = 0: 5

(3)

We claim that the sequence fxng is bounded as n ! 1. If not, then we would have (for a subsequence) kxnk ! 1 so, from (4.1), hTun + qn; uni = 0 (n = 1; 2; : : :) (4) with un := xn=kxnk and qn := q=kxnk ! 0. Since fu 2 K : kuk  1g is closed, convex, and bounded in the Hilbert Space H, fung (or a subsequence) converges weakly to some element d 2 K. By (ii), and (4.2), we get hTd; di  0 which implies, by (i), Td = ?Td: (5) Now (4.1) implies that hq; xni = ?hTxn; xni  0 (by (i)). This gives hq; di  0: (6) Since any k 2 K can be written as limn!1 kn with kn 2 Kn, we have from (4.1) that hTd; ki  0 for every k 2 K, that is, Td 2 K: (7) Now the feasibility of GLCP (T; K; q) implies that hTx0 + q; di  0 whence, using (4.3)and (4.5), hq; di  ?hTx0; di = ?hx0; Tdi = hx0; Tdi  0: From (4.4), we get hq; di = 0. Thus, d is in fx 2 K : Tx 2 K; hTx; xi = 0; hq; xi = 0g. By (iv) this implies d = 0 so 0 2 [weak-closure fx 2 K : kxk = 1g] which contradicts (iii). It follows that fxng (or a subsequence) is bounded. We may then assume that fxng converges weakly to some element x0 2 K. Now (4.1) gives, by (ii), that hTx0 + q; x0i  0. Further, on writing k = lim kn with kn 2 Kn, (4.1) shows that, hTx0 + q; ki  0 for any k 2 K . Therefore, x0 solves GLCP (T; K; q). Finally, a similar argument shows the solution set of GLCP (T; K; q) cannot be unbounded: otherwise, as before, one could construct an element d 2 K satisfying (4.3), (4.4), (4.5) leading to a contradiction (by (iii)). The weak compactness follows, since the solution set of GLCP (T; K; q) is weakly closed in K.

Remarks on the Hypotheses of Theorem 4.1 6

(1) Conditions (i) and (ii) hold, for example, when T is monotone on H. (2) Feasibility of GLCP (T; K; q) is equivalent to q 2 [K ? T(K)]. In the presence of (i), q 2 int [K ? T(K)] implies that condition (iv) holds

(see [3], Prop. 2.3). (3) If int(K) is nonempty, then q is in int(K ?T(K)) if and only if (Tx+q) is in int K for some x 2 K (cf. [3], p.349). (4) If K is locally norm compact then condition (iii) holds. In view of Remarks 1 and 2, Theorem 4.1 generalizes the following result of Borwein [3]: If T is monotone on H; K is locally norm compact, and K ? T(K) = H, then the solution set for GLCP (T; K; q) is non-empty and bounded for any q (cf. [3], Theorem 3.1, Remark (v), p.353, and Corollary 2.1). (5) Without conditions (iii) and (iv) the above result may fail: see Section 5. (6) When T is self-adjoint, condition (iv) (in the presence of (i)) becomes K\ Ker T \ fqg? = f0g. (7) When dim H < 1, conditions (ii) and (iii) are always true. Theorem 4.2 Let dim H < 1 and suppose that T, K, q are such that (i) T is self-adjoint, (ii) T is copositive plus on K, (iii) (T + q q)(K) is closed. If GLCP (T; K; q) is feasible then it is solvable. > Proof: Let M :=Ker T \ fq g . If M = f0g, then the result follows immediately from Theorem 4.1 (see Remarks 6 and 7) so assume that M 6= f0g. Let P denote the orthogonal projection from H onto M? =Ran T + Spanfqg). Since hTx + q; ki = hTPx + q; Pki (x; k 2 K), we see that the solvability of GLCP (T; K; q) is equivalent to the solvability of GLCP (T; P(K); q). By (iii), the set 7

K + Ker (T + q q) = K + Ker T \ fqg? = K + Ker P is closed; hence, P(K) is closed. It follows easily from (ii) that T is copositive plus on P(K) and, nally, we have P(K)\ Ker T \ fqg?  Ran P\ Ker P = f0g. Thus, all the conditions of Theorem 4.1 are met for GLCP (T; P(K); q) so it is solvable. This implies that GLCP (T; K; q) is also solvable.

5 Examples

Example 1. This example shows that if condition (iii) is omitted in Theorem 4.1 then GLCP (T; K; q) need not be solvable. Let P 1 2 H = `2 = fx = (x1; x2; : : :) : xn 2 IRP; 1 xn < 1g with inner product given by hx; yi = 11 xnyn. Let `+2 be the positive cone in `2 (i.e., each xn  0 for x = (x1; x2; : : :) 2 `+2  `2). Set v = (1; 14 ; 19 ; : : :) and u = ( ; 12 ; 31 ; : : :) where ; ; are chosen so that ; > 0; kuk = kvk = 1, and hu; vi = 0. We de ne a projection operator P : `2 ! `2 by P : x 7! hx; uiu + hx; vi+v. Being a projection, P is monotone on `2 and hence copositive plus on `2 . Once again, monotonicity of P implies the weak lower semi-continuity of x 7! hPx; xi. If 0 6= x 2 Ker P, then hx; vi = 0 so some component of x must be negative. This shows that `+2 \ Ker P = f0g. Although `+2 is separable, we do have 0 2 weak-closure fx 2 `+2 : kxk = 1g. Let en denote the element in `+2 with 1 as the nth entry and zero elsewhere. Put q = ?u. Then, for n > 1, P( n en ) = h n en; uiu + h n en; viv = u +  n1 v: (8) Since v 2 (`+2 ) (= `+2 ), we have [P( n en) + q] 2 (`+2 ). Thus GLCP (P; `+2 ; q) is feasible and we have veri ed all the conditions of Theorem 4.1 except part of the thinness of `+2 . Suppose, there were an a 2 `+2 with hPa + q; xi  0 for all x 2 `+2 , and hPa + q; ai = 0. The inequality hPa + q; n eni  0 (n = 1; 2; : : :) gives ha; ui +  n1 ha; vi ? 1  0 for n = 2; 3; : : : so ha; ui  1. Now hPa + q; ai = 0 reduces to jha; uij2 + jha; vij2 ?ha; ui = 0 and, since ha; ui  1, this implies ha; vi = 0. Since a 2 `+2 and all entries of v are strictly positive, one must then have a = 0 whence h?u; xi = hq; xi = hPa + q; xi  0 for 8

x 2 `+2 . But h?u; e2i = ? =2 < 0 and we have a contradiction. Thus, GLCP (P; `+2 ; q) is not solvable.

Remark: (8) Letting n ! 1 in (5.1) we see that u 2 cl[P(`+2 )]. However, u is not in P(`+2 ): if one were to have Px = hx; uiu + hx; viv = u for some x 2 `+2 , then hx; vi = 0 which implies that x = 0 and hence u = Px = 0. Thus, the image of `+2 under P is not closed. Example 2. This example shows that if condition (iv) were to be omitted in Theorem 4.1 then the result need not be true; the same example shows that condition (iii) in Theorem 4.2 cannot be omitted. Let H = IR3, T(x; y; z) = (x; y; 0), K = f(x; y; z) : x; z  0; 2xz  y2g. Put q = (1; 1; 0) and x0 = (1; ?1; 1). Then K is a closed convex cone with K = K and x0 2 K. Since Tx0 + q = (2; 0; 0) 2 K, GLCP (T; K; q) is feasible. Being a projection, T is monotone on IR3 and hence copositive plus on K. Now suppose k = (x; y; z) were any solution of GLCP (T; K; q). Then Tk + q = (x + 1; y + 1; 0) 2 K (= K) whence y = ?1. Since 2xz  y2 = 1, one has x > 0 so hTk + q; ki = x(x + 1) + y(y + 1) = x(x + 1) > 0. Thus GLCP (T; K; q) is not solvable. We observe that K\ Ker T \ fqg? = f(0; 0; z) : z 2 IRg 6= f0g, (T + q q)K = f(2x + y; x + 2y; 0) : x = y = 0 or x > 0g. This set is not closed, since (1; 2; 0) is a limit point of (T + q q)K which is not in (T + q q)K. Thus, neither condition (iv) in Theorem 4.1 nor condition (iii) in Theorem 4.2 is satis ed.

6 A Perturbation Result

Theorem 6.1 Let dim H < 1 and suppose that T is copositive plus on K.

Then the following are equivalent: (a) The solution set of GLCP (T; K; q) is nonempty and compact. (b) fx 2 K : Tx 2 K; hTx; xi = 0 and hq; xi  0g = f0g. (c) q 2 int(K ? T(K)), i.e., GLCP (T; K; q 0) is feasible for all q 0 near q.

9

(d) GLCP (T; K; q) is feasible and fx 2 K : Tx 2 K; hTx; xi = 0, and hq; xi = 0g = f0g. Proof:

(a)=)(b): Suppose that GLCP (T; K; q) has nonempty compact solution set. Following Mangasarian [7, p.159], we show that (b) holds. Suppose there were some x^ 2 K such that Tx 2 K; hTx; xi = 0, and hq; xi  0. Let x0 be a solution of GLCP (T; K; q). Then, for any t  0, one has x0 + tx 2 K and T(x0 + tx) + q 2 K. Further,

hT(x0 + tx) + q; x0 + txi = hTx0 + q; x0i + hTx0 + q; txi + hT(tx); x0 + txi = 0 + thq; xi + thx0; Txi +thx0; Txi + t2hTx; xi  0 since hq; xi  0, Tx + Tx = 0, and hTx; xi = 0. Since T(x0 + tx) + q 2 K, we must have hT(x0 + tx)+ q; x0 + txi  0. Thus hT(x0 + tx)+ q; x0 + txi = 0 whence x0 + tx solves GLCP (T; K; q) for all t  0. By the boundedness of

the solution set, we must then have x = 0, proving (b). (b)=)(c): Suppose that (b) holds but (c) does not. Then either q 62 (K ? T(K)) or q 2 @ (K ? T(K)). In either case, there exists a sequence fqng such that qn 62 (K ? T(K)), and qn ! q (as n ! 1). Fixing n, a separation theorem [18, p.49] shows that there exists n with kn k = 1 and  2 IR such that hqn ; ni    hn ; ki ? hn ; Tki (k 2 K; k 2 K): Since K ? T(K) is a cone, we can take  = 0. Then

hqn; n i  0  hn ; ki ? hn ; Tki (k 2 K; k 2 K): (9) Putting k = 0, we get hn ; ki  0 (k 2 K), which shows that n 2 K. Next putting k = 0, we get 0  ?hn ; Tki and hence hTn ; n i  0 so hTn ; n i = 0, and hqn; n i  0. Since, kn k = 1 (n = 1; 2; : : :), we may assume that fn g (or a subsequence) converges to some element . Then kk = 1,  2 K, T 2 K, hT; i = 0, and hq; i  0. This would contradict (b) so one has (b)=)(c). 10

(c)=)(d): Suppose (c) holds. Clearly GLCP (T; K; q) is then feasible. Suppose that there is some  6= 0 such that  2 K; T 2 K; hT; i = 0, and hq; i = 0. Take any z 2 K ? T(K) so z = k ? Tk where k 2 K and k 2 K. Then,

h; zi = h; k i ? h; Tki = h; k i + h?T; ki  0 + 0 (since  2 K and ? T = T 2 K  0 = hq; i: This shows that the hyperplane fx 2 H : hx; i = 0g separates q from K ? T(K). On the other hand, this is impossible since q 2 int [K ? T(K)]. Hence  = 0 and (d) holds. (Note that (c)=)(d) also follows from [3]: Prop. 2.3 on p. 349 and (32) on p. 351.) (d)=)(a): Follows from Theorem 4.1.

Remarks on Theorem 6.1 (9) When H = IRn and K = IRn+, the equivalence of (a) and (c) recaptures

a result of Mangasarian [19,Theorem 2.] (see also [6]). (10) Suppose that K has nonempty interior and T is copositive plus on K. Assume that there is an x 2 K with (Tx + q) 2int(K). Borwein [3, Theorem 4.1] has shown that GLCP (T; K; q) has a compact solution set, possibly empty. Since (Tx + q) 2int K implies q 2int [K ? T(K)], Theorem 6.1 actually shows that GLCP (T; K; q) must have a nonempty solution set. (11) For the nite dimensional case, compactness of the solution set is equivalent to boundedness since the solution set of GLCP (T; K; q) is always closed. (12) In [20], McLinden proves perturbation results for monotone operators de ned on re exive Banach spaces.

11

7 A Characterization of Polyhedral Cones in Finite Dimensional Spaces The examples given in section 5 lead one to conjecture that if the image of the cone under the operator were not closed then the corresponding GLCP need not be solvable. This turns out to be correct if the space is nite dimensional. (It seems likely that the same result extends to in nite dimensional spaces but we have not shown this.) The following result shows that among all closed convex cones in H (dim H < 1), polyhedral cones are the only ones with the property that every copositive plus, feasible GLCP is solvable.

Theorem 7.1 For dim H < 1 the following are equivalent: (a) There is an operator S : H ! H such that S(K) is not closed. (b) There is an (orthogonal) projection P : H ! H such that P(K) is not

closed. (c) There is an operator P : H ! H which is copositive plus on K, and a q 2 H such that GLCP (T; K; q) is feasible but not solvable.

(d) K is not polyhedral. (e) There is a projection operator P : H ! H with dim(Ran P) = 2 for which P(K) is not closed.

(a)=)(b): Suppose (a) holds. Since H=Ker S is isomorphic to Ran S (recall that dim H < 1) and  : H ! H=Ker S is a quotient map, the set K+Ker S is not closed in H. Let P be the orthogonal projection from H onto (Ker S)? . Since Ker P = Ker S, it follows that [K+Ker P] is not closed; therefore P(K) is not closed in H. This gives (b). (b)=) (c): Let P be a projection on H such P(K) is not closed in H. Let u be a limit point of P(K) which is not in P(K). Put q = ?u and let I denote the identity operator. We show that P(K) ? P(K) = H. Let L denote any convex cone (not necessarily P(K)). Suppose, to get a contradiction, that L ? L 6= H. Let x 2 H with x 62 (L ? L). Then by a separation theorem (see [18], p.49), there exists  6= 0 in H and  2 IR such that h; xi    h; wi ? h; vi (v 2 L; w 2 L): (10) Proof:

12

Since [L ? L] is a cone, we can take  = 0. Putting w = 0 in (7.1), we then get 0  ?h; vi (v 2 L) so ? 2 L. By putting w = ?, v = 0, and recalling that we took  = 0, we get from (7.1) that 0  h; ?i so  = 0, contradicting the assertion  6= 0. Therefore [P(K) ? P(K)] = H whence GLCP (I; P(K); q) is feasible. Suppose GLCP (I; P(K); q) were solvable. Then there would exist an a 2 P(K) such that ha + q; vi  0 for v 2 P(K) and ha + q; ai = 0. Writing q = ?u, we have, for any v 2 P(K), that kv ? uk2 = kv ? ak2 + ka ? uk2 + 2hv ? a; a ? ui  ka ? uk2 since hv ? a; a ? ui = hv; a ? ui ? ha; a ? ui  0. As u 2 cl[P(K)]nP(K), this cannot happen; thus GLCP (I; P(K); q) cannot have a solution. Since q 2 Ran P and P is a projection, the feasibility (solvability) of GLCP (I; P(K); q) is equivalent to the feasibility (solvability) of GLCP (P; K; q). Thus we see that GLCP (P; K; q) is feasible but not solvable. Finally, P is copositive plus on K since projections are always monotone. (c)=)(d): Follows from Theorem 3.1 (d)=)(e): Follows from a result of Mirkil [21]. (e)=)(a): Obvious.

8 Concluding Remarks and Open Problems

(13) Let dim H < 1 and let T be copositive plus on K. Suppose that GLCP (T; K; q) is feasible, i.e., q 2 [K ? T(K)]. Then our results show that (i) If q 2 int[K ? T(K)] then the solution set of GLCP (T; K; q) is nonempty and compact, (ii) If q 2 @ (K ? T(K)); (T + q q)K is closed, and T is selfadjoint then the solution set of GLCP (T; K; q) is nonempty and unbounded. We thus ask: Problem 1: Can self-adjointness of T be dropped in (ii), i.e., in Theorem 4.2? 13

(14) Theorem 4.2 can also be proved by minimizing a quadratic functional. This approach is described in [9]. (15) Theorem 6.1 shows that when dim H < 1 and T is copositive plus, the solution set of GLCP (T; K; q) being nonempty and compact is equivalent to the existence of an " > 0 such that GLCP (T; K; q0) has nonempty (compact) solution set for kq0 ? qk < ".

Problem 2: Assume that dim H < 1 and T is copositive plus. If GLCP (T; K; q) is nonempty and compact then can one nd an " > 0 such that GLCP (T0; K; q0) has a nonempty solution set for all T0 and q0 with maxfkT0 ? Tk; kq0 ? qkg < "? We note that when H = IRn and K = IRn+, an armative answer to Problem 3 is known ([19],[6]). Problem 3: Is Theorem 7.1 true when H is in nite dimensional? (16) Here is a generalization of Theorem 4.1 to re exive Banach spaces: Let X be a re exive Banach space with dual X . For f 2 X  and x 2 X , let hf; xi denote f (x). Let K be a closed convex cone in X and let q 2 X . Let T : X ! X  be linear (and continuous) such that hTx; xi  0 for all x 2 K, and, x 2 K; hTx; xi = 0 imply hTx; ki + hTk; xi = 0 for all k 2 K. Assume further that the map: x 7! hTx; xi is weak-lsc on K, that K is thin, that fx 2 K : Tx 2 K; hTx; xi = 0, hq; xi = 0g = f0g. Then GLCP (T; K; q) has a nonempty compact solution set whenever it is feasible. The proof of this is obtained by modifying the proofs of Theorems 3.1 and 4.1 and hence we omit it. (While proving Theorem 3.1 for this case, one may want to look at GLCP (JT; K; Jq) where J is the inclusion map from [K ? K] into X ).

Acknowledgments

We wish to thank Thomas Armstrong of University of Maryland Baltimore County for helpful suggestions, in particular for reference [21]. We are also grateful to the referees for a number of valuable comments and suggestions. The research by T. I. Seidman has been partially supported by the Air Force Oce of Scienti c Research under grants #AFOSR{82{0271 and #AFOSR{ 87{0350. 14

References [1] G. Allen, "Variational inequalities, complementarity problems, and duality theorems", Journal of Mathematical Analysis and Applications 58 (1977) 1{10. [2] M.S. Bazaraa, J.J. Goode, and M.Z. Nashed, "A nonlinear complementarity problem in mathematical programming in Banach space", Proceedings of the American Mathematical Society 35 (1973) 165{170. [3] J.M. Borwein, "Alternative theorems for general complementarity problems", In Proceedings of the Cambridge Symposium on In nite Programming (Springer-Verlag Lecture Notes in Economics and Mathematical systems,No.259,1984) pp.194-203. [4] J.M. Borwein, "Generalized linear complementarity problems treated without the xed point theory", Journal of Optimization Theory and Applications 43(2) (1984) 343{356. [5] A.T. Dash and S. Nanda, "A complementarity problem in mathematical programming in Banach space", Journal of Mathematical Analysis and Applications 98(1984) 318-331. [6] R. Doverspike, "Some perturbation results for the linear complementarity problem", Mathematical Programming 23 (1982) 181-192. [7] I. Ekeland and R. Temam, Convex Analysis and Variational Problems (North-Holland American Elsevier, New York, 1976). [8] K. Fan, "A minimax inequality and applications", In: O. Shisha, editor, Inequalities, III (Academic Press, New York, 1972) pp.103-113. [9] M.S. Gowda, "Minimizing quadratic functionals over closed convex cones", Research Report, Department of Mathematics and Statistics, University of Maryland Baltimore County (Baltimore, MD, 1985). [10] G.J. Habetler and A.L. Price, "Existence theory for generalized nonlinear complementarity problems", Journal of Optimization Theory and Applications 7(4) (1971) 223-239. 15

[11] G. Isac, "Nonlinear complementarity problem and Galerkin method", Journal of Mathematical Analysis and Applications 108 (1985) 563-574. [12] S. Karamardian, "The complementarity problem", Mathematical Programming 2(1972) 107-129. [13] S. Karamardian, "Complementarity problems over cones with monotone and pseudomonotone mapppings", Journal of Optimization Theory and Applications 18(4) (1976) 445{454. [14] S. Karamardian, "An existence theorem for the complementarity problem", Journal of Optimization Theory and Applications 19(2) (1976) 227{232. [15] S. Karamardian, "Generalized complementarity problem", Journal of Optimization Theory and Applications 8(3) (1971) 161{168. [16] C.E. Lemke, "On complementary pivot theory", In G.B.Danzig & A.F. Veinott,Jr., editors, Mathematics of the Decision Sciences, Part I (American Mathematical Society, Providence, Rhode Island, 1968). [17] G. Luna, "A remark on the nonlinear complementarity problem", Proceedings of the American Mathematical Society 48 (1975) 132-134. [18] O.L. Mangasarian, "Characterizations of bounded solutions of linear complementarity problems", Mathematical Programming Study 19 (1982) 153-166. [19] O.L. Mangasarian, Nonlinear Programming (McGraw Hill, New York, 1969). [20] L. McLinden, "Stable Monotone Variational Inequalities", Technical Report #2734, Mathematics Research Center, University of Wisconsin, Madison, 1974. [21] H. Mirkil, "New characterizations of polyhedral cones", Canadian Journal of Mathematics IX(1) (1957) 1-4. [22] J.J. More, "Classes of functions and feasibility conditions in nonlinear complementarity problems", Mathematical Programming 6 (1974) 327{ 338. 16

[23] J.J. More, "Coercivity conditions in nonlinear complementarity problems", SIAM Review 16(1) (1974) 1-16. [24] J. Parida and K.L. Roy, "An existence theorem for the nonlinear complementarity problem", Indian Journal of Pure and Applied Mathematics 13(6) (1982June) 615{619. [25] S. Nanda and S. Nanda, "A nonlinear complementarity problem in Banach space", Bulletin of the Australian Mathematical Society 21 (1980) 351{356. [26] R. Saigal, "Extension of the generalized complementarity problem", Mathematics of Operations Research 1(3) (1976) 260{266.

17