中 国 科 学(A 辑)
第30卷 第10期
SCIE NCE IN C HINA (Series A)
2000年10月
变分不等式问题的解的存在性
张立平 韩继业 徐大川
¹
¹
º
*
(中国科学院数学与系统科学研究院¹应用数学研究所; º计算数学与科学工程计算研究所, 北京100080)
摘要 对一般凸集约束下的变分不等式问题提出了一个新的例外簇概念. 基于此概念, 给出了变分不等式问题解存在的一个充分条件, 此条件弱于许多已知的关于变分不等式问题的解的存在性条件. 对于伪单调变分不等式问题, 它是解存在的充要条件. 对于P 0非线性互补问题, 利用例外簇的概念, 给出了其解存在的充分条件.
关键词 例外簇 变分不等式 互补问题 P 0-函数
令K 是R 中一非空闭凸集, F :R y R 为一连续函数. 变分不等式问题(VI(K , F ) ) 即是:求一点x I K , 满足
(x -x ) F (x ) \0, P x I K .
当K =R +时, VI(K , F ) 转化为如下的非线性互补问题(NCP(F ) ) :求一点x , 满足
x \0, F (x ) \0, x F (x ) =0.
[1]
T
n
*
*
T
*
*
n n n
(1) (2)
变分不等式问题在经济平衡理论、控制论、对策论、交通、社会和经济模型等许多方面都有着广泛的应用, 其理论和算法的研究在近几十年里得到了长足的进展. (1) 与(2) 式的基本问题之一是解的存在性问题:在何种条件下, VI(K , F ) 或NCP(F ) 有解. 文献[1]举出了多个存在性定理和文献, 如文献[2~7]等等. 另外Smith
[8]
和Isac 等
[9]
分别引入了/例外序列0和
[10,11]
/例外簇0的概念来研究NCP(F ) 的解的存在性问题. 最近赵和韩等的结果, 对一类VI(K , F ) 提出了例外簇的概念, 这里K 定义如下:
n
n
n
推广了文献[8, 9, 12]
(3)
K ={x I R :g i (x ) [0(i =1, , , m ) ; h j (x ) =0(j =1, , , l ) },
其中g i :R y R 为连续可微凸函数, h j :R y R 为仿射函数, 且K 满足Slater 条件. 赵和韩等的例外簇概念提供了形如(3) 式的VI(K , F ) 的解存在的一个充分条件, 且对伪单调变分不等式而言, 它也是解存在的必要条件. 应用例外簇的概念, 文献[11]给出了P *非线性互补问题解存在的一个充分条件.
本文对于带一般闭凸集约束的变分不等式问题定义了例外簇, 它是赵和韩例外簇概念的推广. 通过此概念, 我们给出了关于VI(K , F ) 解存在的一个基本定理:若VI(K , F ) 不存在例外簇, 则它必定有解. 且对伪单调VI(K , F ) 而言, 此条件也是必要的. 最后, 我们给出了P 0非线性互补问题解存在的充分条件.
2000-01-30收稿
*国家自然科学基金资助项目
894
中 国 科 学 (A 辑) 第30卷
1 例外簇和VI(K , F ) 的解的存在性定理
首先给出一些记号:+#+表示Euclid 模, R +表示R 中非负象限, P K (#) 表示到闭集K 上的投影算子. 令D
D y R 的连续函数组成的线性空间, 令deg (f , D , y ) 表示f , D 和y 之间的拓扑度, 这里
n
f I C (D ) , y I R 且y |f (5D ) (见文献[13, 14]) . 下面列出一些引理, 以备后用.
引理111引理112
n
[1][13]
n
n
n
x 是VI(k , F ) 的解, 当且仅当x =P K (x -F (x ) ) . 设D
n
****
H (x , t ) =tG (x ) +(1-t ) F (x ) , 0[t [1. 设y 是R 中的任意一点, 若
y |{H (x , t ) :x I 5D , t I [0, 1]}, 则
引理113
[14]
deg(G , D , y ) =deg(F , D , y ) .
设D 和F 由引理1. 2定义, 若y |F (5D ) 且deg(F , D , y ) X 0, 则F (x ) =y
在D 中有解.
[1]n
引理114 设F :K y R 为一连续函数. 若K 是非空紧凸集, 则VI(K , F ) 必定有解. 由于引理1. 4, 为研究VI(K , F ) 解的存在性, 本文以下假设K 是无界闭凸集. 我们给出VI(K , F ) 的例外簇的定义.
定义111 令x ^I K , 称序列{x }r y ]
-[F (x +t r (x ^-x ) ) +t r (x -x ^) ]I N K (x ) ,
其中N K (x ) 表示K 在x 的法锥. 法锥N K (#) 的定义如下:
N K (x ) =
{z I R :z (y -x ) [0, P y I K }, 若x I K ,
ª, 其他.
n
T
r
r
r
r
r
r
r
r
(4)
(5)
注111 定义1. 1是文献[11]中例外簇概念的推广. 事实上, 设K 是由(3) 式定义的非空闭凸集且满足Slater 条件. 令x I K , 则对任意的y I K , K I [0, 1], 有x +K (y -x ) I K . 令I ={1, 2, , , m }, J ={1, 2, , , l }, I (x ) ={i I I :g i (x ) =0}, 则有
0\lim K |00=lim K |0
g i (x +K (y -x ) ) -g i (x )
K
h j (x +K (y -x ) ) -h j (x )
=$g i (x ) (y -x ) , P i I I (x ) , =$h j (x ) (y -x ) , P j I J .
T T
(6a)
(6b)
K n
对于任意z I N K (x ) , 任意y I R , 如果存在 K >0, 使得x +K (y -x ) I K , P K , 0[K
T
(5) 和(6) 式, z (y -x ) [0; 如果有x +K (y -x ) |K , P K , 0[K
T T
$g i (x ) (y -x ) >0, 或存在j I J , 使得$h j (x ) (y -x ) X 0, 故集合
S =y -x :y I R ; z (y -x ) >0; $g i (x ) (y -x ) [0, P i I I (x ) ;
$h j (x ) (y -x ) =T
n T T
第10期张立平等:变分不等式问题的解的存在性
895
是空集. 由Farkas 引理知, 存在K i \0(i I I (x ) ) , L j I R(j I J ) , 使得
z =
r
r
i I I (x )
E
K i $g i (x ) +
r
j I J
E L $h (x ).
j
j
r l
r
(7) (8)
r
T
设{x }是VI(K , F ) 关于x ^的一例外簇, 由(4) 式知,
-2[F (x +t r (x ^-x ) ) +t r (x -x ^) ]I N K (x ).
再由(7) 和(8) 式知, v (K r ) i \0(i I I (x ) ) , 和L r I R , 使得
-2[F (x +t r (x ^-x ) ) +t r (x -x ^) ]=
取(K r ) i =0(i I I \I (x ) ) , 则有
F (x +t r (x ^-x ) ) =-t r (x -x ^) -(K r ) g (x ) =0.
令y =x +t r (x ^-x ) , 则x =
r
r
r
r
r T
r
r
r
r
r
r
r
r
i I I (x )
r
E
(K r ) i $g i (x ) +$h (x ) L r .
r
r
(9)
1r T r T
$g (x ) K r +$h (x ) L r , 2
(10) (11)
t r r r r r
-, 且y I K . 令A r =, 则有x =A r y +(1-1-t r 1-t r 1-t r
r
r
A ^I K . 因01, A r y +(1-A ^I K , 并且(10) 和(11) 式可化为r ) x
F (y ) =-(A r -1) (y -x ^) -r
T
r
r
r T
$g (A r y +(1-A r ) x ^) K r 2
(12) (13)
$h (A r y +(1-A r ) x ^) L r ,
(K ^) =0. r ) g (A r y +(1-A r ) x
r
T
r
这表明{y }r y ]
设K ={x I R :-x [0}=R +, 取x ^=0, 则(12) 和(13) 式化为
-(A r -1) y i , 若y i >0,
(14) r (K r ) i \0, 若y i =0. 2
r
这意味着{y }既是文献[8]中定义的NCP(F ) 的例外序列, 也是文献[9]中讨论的反半径序列.
n n n
定理111 设K 是R 中一个非空闭凸集, F :R y R 为一连续函数, 则VI(K , F ) 或有解, 或对任意x ^I K , 有关于x ^的一个例外簇.
F i (y ) =
证 令
由引理1. 1知, x 是VI(K , F ) 的解当且仅当
H (x , t ) =t (x -x ^) +(1-t )
D r ={x I R :+x +0.
若VI(K , F ) 无解, 则对每个r >+x ^+, 存在z I 5D r , t r I [0, 1], 使得0=H (z , t r ) . 若不然, 则存在r 0>+x ^+, 使得
0|{H (x , ) :x I 5D r 0, I [0, 1]}.
r
r
n
r
r
r
n
n
896
中 国 科 学 (A 辑) 第30卷
由引理1. 2知,
deg(
因|deg(x -x ^, D r 0, 0) |=1, 故由引理1. 3知,
0=H (z , t r ) =t r (z -x ^) +(1-t r ) [z -P K (z -F (z ) ) ]=z -t r x ^-(1-t r ) P K (z -F (z ) ).
r
r
r
r
r
r
r
r
r
r
r
r
r
r
(15)
若t r =0, 则由(15) 式知z =P K (z -F (z ) ) , 即z 是(1) 式的解, 矛盾. 若t r =1, 则由(15) 式知, z =x ^, 这与+z +=r >+x ^+相矛盾. 故t r I (0, 1). 由(15) 式知, 对所有的r >+x ^+, t r I (0, 1) ,
t r r r r
-=P K (z -F (z ) ) I K . 1-t r 1-t r
即x >
r
(16)
t r r
-是下面问题的惟一解:
1-t r 1-t r
r r 2
+x -(z -F (z ) ) +:x I K .
2
于是有
-[x -(z -F (z ) ) ]I N K (x ).
即
-[F (x +t r (x ^-x ) ) +t r (x -x ^) ]I N K (x ).
VI(K , F ) 关于x ^的一个例外簇.
定理112 若对某一x ^I K , VI(K , F ) 无关于x ^的例外簇, 则VI(K , F ) 有解.
r
r
r
r
r
r
r
r
(17) (18)
r r r r
由(16) 式及+z +=r 可知, x I K 且+x +y ](r y +]). 根据定义1. 1, {x }r y ]
2 VI(K , F ) 无例外簇的条件
定理1. 1和1. 2给出了VI(K , F ) 有解的一个充分条件. 我们将证明这个条件弱于文献中一些已知的解的存在性条件. 对伪单调变分不等式而言, 它也是必要的.
n n n
定理211 设F :R y R 是一连续函数, K
r r r r
对每个序列{x }+x ^+, 使得
r T r (x -x ^) F (x ) \0, (19) 则VI(K , F ) 无关于x ^的例外簇, 因此VI(K , F ) 有解.
证 用反证法. 假若VI(K , F ) 有关于x ^的例外簇{x }r
数列{t r }, 满足0
[F (x +t r (x ^-x ) ) +t r (x -x ^) ](x -x ) \0, P x I K .
在(20) 式中, 令y =x +t r (x ^-x ) 及x =x ^, 得
t r r
(y -x ^) F (y ) +
1-t r
r
T
r
r
r
r
r
r
T
r r
y +]
(20)
r
-1-t (y -x ^)
r t r r 2
+y -x ^+. -t r
\0.
因0
F (y ) (y -x ^) [-r T
r
第10期张立平等:变分不等式问题的解的存在性
897
于是,
(y -x ^) F (y ) +x ^+.
r
r
r
r
r
r
T
r
r
r
(21)
但y =x +t r (x ^-x ) I K , 且由+x +y ], 0
推论211 设F :R y R 是一连续函数, K
K (x ^) ={x I K :(x -x ^) F (x )
T
(22)
有界(或为空) , 则VI(K , F ) 无例外簇.
注211 Harker 和Pang 提出了条件(22) (见文献[1]中定理2. 3) , 它是本文条件的推论.
文献[11]提出了/p -阶强制性0的概念:
定义211 称函数F :R y R 关于凸集K 是p -阶强制的, 若存在p I (-], 1) , x ^I K , 使得
lim =+]. (23) x I K , +x +y ]+x +
当p =1, (23) 式就是通常的强制性条件(见文献[7]) . 显然, 强制性函数必是p -阶强制的. 反之不然(见文献[11]) . 强制性条件在研究VI(K , F ) 解存在方面起着重要的作用(见文献[7~9, 15]). Hartman 和Sta mpacchia 个结果可推广到p -阶强制性函数.
[16]
T
n
n
, Mor 证明了:若F 是强制的, 则VI(K , F ) 有解. 这
[7]
n n n
推论212 设F :R y R 是一连续函数, K
使得F 是p -阶强制的, 则VI(K , F ) 无例外簇.
[1]n n
定义212 称函数F :R y R 在凸集K 中满足Karamardian 条件, 若存在非空有界集D
(x -y ) F (x ) \0.
n n
定义213 称函数F :R y R 为
n
(a) 在K
T T
(y -x ) F (x ) \0](y -x ) F (y ) \0;
n
(b) 在K
T T
(y -x ) F (x ) >0](y -x ) F (y ) \0.
[10]
显然, 在单调的概念中, 拟单调是最弱的. 伪单调函数必是拟单调的, 反之不然.
T
(24) (25)
r
定义214
[11]
(D1) 称F :R y R 在K 中是弱正常的, 若存在x ^I K , 使得对每个序列{x }
(26) (27)
n n
r T r (x -x ^) F (x ^) \0, +x +>+x ^+. (D2) 称F :R y R 在K 中是严格弱正常的, 若(26) 式换为(x -x ^) F (x ^) >0, +x +>+x ^+.
类似于文献[10, 11], 也可证明以下的一些结果:Karamardian 条件, 则VI(K , F ) 无例外簇.
r
T
r
n
n
n n n
定理212 设F :R y R 是一连续函数, K
n n n
:,
898
中 国 科 学 (A 辑) 第30卷
调的, 则下列条件等价:
( ) VI(K , F ) 无例外簇;
( ) F 在K 中是弱正常的; ( ) VI(K , F ) 有解.
n n n
定理214 设F :R y R 是一连续函数, K
定理2. 2~2. 4说明本文定理1. 2给出的VI(K , F ) 的解存在条件弱于许多已知的解存在条件, 而且成为伪单调VI(K , F ) 解存在的充分必要条件.
3 P 0非线性互补问题的解的存在性
我们研究一类重要的非线性互补问题NCP(F ) 的解的存在性, 这里F 是P 0-函数. 常见的单调函数、一致P -函数、P -函数、P *-函数均是P 0-函数的特例. 文献[10, 11, 15]中对于单调函数、一致P -函数、P -函数、P *-函数等构成的NCP(F ) 已研究了解的存在性.
n n n
定义311 称F :R y R 为K
1[i [n
max [F i (x ) -F i (y ) ](x i -y i ) \0, P x , y I K , x X y .
下面给出NCP(F ) 的解存在的两个充分条件, 这里F 是P 0-函数. 记e i 为第i 个分量是1, 其余分量是0的n 维向量.
n n
定理311 设F :R y R 是一连续P 0-函数, 若存在n 个数A , n ) , 使得i \0(i =1, 2, , F (A i e i ) I R +(i =1, 2, , , n ) , 则NCP(F ) 在R +中无关于点0的例外簇, 因而NCP(F ) 有解.
证 设NCP(F ) 在R +中有关于点0的例外簇{x }r y +
存在数列{G r }, G r >0, 有
F i (x ) =-G r x i , 如果x i >0, F i (x ) \0, 如果x i =0.
令
I
r
r
+
r
r
r
r
r
n
r
]
n r
n
n
(28) (29)
={i :x i >0}, I
r
r
r
={i :x i =0}.
r
(30) (31)
由于+x +y ](r y +]) , 故存在i 0, 使得
lim sup x i 0=+]. r y +]
于是存在r , 使得x i 0>A , y =A i \0. 令x =x i e i , 则有000
x i =y i , P i I I
r
*
*
*
*r r
; x i 0=x
r i
*0
>A i =y i ; x i >0=y i , P i I I 00
r
*
r
+
*
, i X i 0. (32)
由(28) ~(30) 和(32) 式及定理假设知,
*x F i (x ) =-G r i , P i I I
r
+
*
,
F i (y ) \0, P i =1, 2, , , n ,
故P i I I
r +
*
, 有x i X y i , 且
F (x ) i () i i x r *i -F i ) r
*
r
*
第10期张立平等:变分不等式问题的解的存在性
899
=-G r (x i ) -x F i (y )
*
r
*
2
r i
*
(33)
[F i 0(x ) -F i 0(y ) ](x i 0-y i 0)
*
=(x i 0-A i ) (-G r x i 0-F i 0(y ) )
r
*
r
*
(34)
于是(32) ~(34) 式和F 是P -0函数相矛盾, 故NCP(F ) 无例外簇, 因此(2) 式有解.
定理312 设F :R y R 是一连续P 0-函数, 若存在n 个数B i [0(i =1, 2, , , n ) , 使得F (B i e i ) I R +(i =1, 2, , , n ) , 则NCP(F ) 在R +中无关于点0的例外簇, 因而NC P(F ) 有解.
证明类似于定理3. 1, 故略.
n
n
n
n
4 结论
本文给出了VI(K , F ) (K 是一般闭凸集) 的例外簇的概念, 证明了VI(K , F ) 无例外簇是解存在的一个充分条件, 并且证明了这个新的充分条件弱于一些已知的解存在条件. 此条件对于伪单调变分不等式问题的解的存在性是充分必要条件, 最后, 给出了P 0非线性互补问题解存在的充分条件.
参 考 文 献
1 Harker P T, Pang J S. Fini te -di mensional variati onal inequality and nonlinear complementari ty problems:A survey of theory, algo -rithm, and applicati ons. Mathematical Programming, 1990, 48(2):161~220
2 Eaves B C. The linear complementarity problem. M anagement Science, 1971, 17(3) :612~634
3 Eaves B C. On the basic theorem of complementarity problem. Math Programming, 1971, 1(1):68~754 Karamardian S. Generaliz ed complementarity problem. J Optim Theory Appl, 1971, 8(1) :161~167
5 Kojima M. A uni fication of the existence theorems of the nonlinear complementari ty problem. Math Progra mming, 1975, 9(2) :257~2776 Mor J J. Class es of functions and feasi bility condi tions in nonli near comple mentari ty problems. Math Programming, 1974, 6(2) :327~3387 Mor J J. Coercivity condi tions in nonlinear complementarity problems. SIA M Rev, 1974, 16(1):1~16
8 Smith T E. A s oluti on condition for complementarity problems, with an application to s patial price equili brium. Appl Math Co mputa -tion, 1984, 15(1) :61~69
9 Isac G, Bulavas ki V, Kalas hnikov V. Exceptional families, topological degree and complementarity proble ms. J Global Opti m, 1997, 10(2) :207~225
10 Zhao Y B, Han J Y, Qi H D. Exceptional families and e xis tence theorems for vari ational i nequality proble ms. J Opti m Theory Appl,
1999, 101(2) :475~495
11 Zhao Y B, Han J Y. Exceptional family of ele ments for a variati onal i nequali ty problem and i ts applications. J Global Optim, 1999,
14(2) :313~330
12 Zhao Y B. Exceptional families and fi nite dimensional variati onal inequalities over pol yhedral convex sets. Appl Math Computation,
1997, 87(1) :111~126
13 Ll oyd N Q. Degree Theory. Cambridge:Cambri dge Universi ty Press, 1978. 6~54
14 Ortega J M , R hei nholdt W C. Iterative Solution of Nonli near Equations i n Several Vari ables. Ne w York:Academic Press, 1970. 30~
45
15 Isac G, Obuchows ka W T. Functions w i thout exceptional family of ele ments and complementarity problems. J Opti m Theory Appl,
1998, 99(1) :147~163
16 Hartman P, Stampacchia G. On s ome nonlinear elliptic differentiable functional equati on. Acta Math, 1966, 115(2) :271~310
中 国 科 学(A 辑)
第30卷 第10期
SCIE NCE IN C HINA (Series A)
2000年10月
变分不等式问题的解的存在性
张立平 韩继业 徐大川
¹
¹
º
*
(中国科学院数学与系统科学研究院¹应用数学研究所; º计算数学与科学工程计算研究所, 北京100080)
摘要 对一般凸集约束下的变分不等式问题提出了一个新的例外簇概念. 基于此概念, 给出了变分不等式问题解存在的一个充分条件, 此条件弱于许多已知的关于变分不等式问题的解的存在性条件. 对于伪单调变分不等式问题, 它是解存在的充要条件. 对于P 0非线性互补问题, 利用例外簇的概念, 给出了其解存在的充分条件.
关键词 例外簇 变分不等式 互补问题 P 0-函数
令K 是R 中一非空闭凸集, F :R y R 为一连续函数. 变分不等式问题(VI(K , F ) ) 即是:求一点x I K , 满足
(x -x ) F (x ) \0, P x I K .
当K =R +时, VI(K , F ) 转化为如下的非线性互补问题(NCP(F ) ) :求一点x , 满足
x \0, F (x ) \0, x F (x ) =0.
[1]
T
n
*
*
T
*
*
n n n
(1) (2)
变分不等式问题在经济平衡理论、控制论、对策论、交通、社会和经济模型等许多方面都有着广泛的应用, 其理论和算法的研究在近几十年里得到了长足的进展. (1) 与(2) 式的基本问题之一是解的存在性问题:在何种条件下, VI(K , F ) 或NCP(F ) 有解. 文献[1]举出了多个存在性定理和文献, 如文献[2~7]等等. 另外Smith
[8]
和Isac 等
[9]
分别引入了/例外序列0和
[10,11]
/例外簇0的概念来研究NCP(F ) 的解的存在性问题. 最近赵和韩等的结果, 对一类VI(K , F ) 提出了例外簇的概念, 这里K 定义如下:
n
n
n
推广了文献[8, 9, 12]
(3)
K ={x I R :g i (x ) [0(i =1, , , m ) ; h j (x ) =0(j =1, , , l ) },
其中g i :R y R 为连续可微凸函数, h j :R y R 为仿射函数, 且K 满足Slater 条件. 赵和韩等的例外簇概念提供了形如(3) 式的VI(K , F ) 的解存在的一个充分条件, 且对伪单调变分不等式而言, 它也是解存在的必要条件. 应用例外簇的概念, 文献[11]给出了P *非线性互补问题解存在的一个充分条件.
本文对于带一般闭凸集约束的变分不等式问题定义了例外簇, 它是赵和韩例外簇概念的推广. 通过此概念, 我们给出了关于VI(K , F ) 解存在的一个基本定理:若VI(K , F ) 不存在例外簇, 则它必定有解. 且对伪单调VI(K , F ) 而言, 此条件也是必要的. 最后, 我们给出了P 0非线性互补问题解存在的充分条件.
2000-01-30收稿
*国家自然科学基金资助项目
894
中 国 科 学 (A 辑) 第30卷
1 例外簇和VI(K , F ) 的解的存在性定理
首先给出一些记号:+#+表示Euclid 模, R +表示R 中非负象限, P K (#) 表示到闭集K 上的投影算子. 令D
D y R 的连续函数组成的线性空间, 令deg (f , D , y ) 表示f , D 和y 之间的拓扑度, 这里
n
f I C (D ) , y I R 且y |f (5D ) (见文献[13, 14]) . 下面列出一些引理, 以备后用.
引理111引理112
n
[1][13]
n
n
n
x 是VI(k , F ) 的解, 当且仅当x =P K (x -F (x ) ) . 设D
n
****
H (x , t ) =tG (x ) +(1-t ) F (x ) , 0[t [1. 设y 是R 中的任意一点, 若
y |{H (x , t ) :x I 5D , t I [0, 1]}, 则
引理113
[14]
deg(G , D , y ) =deg(F , D , y ) .
设D 和F 由引理1. 2定义, 若y |F (5D ) 且deg(F , D , y ) X 0, 则F (x ) =y
在D 中有解.
[1]n
引理114 设F :K y R 为一连续函数. 若K 是非空紧凸集, 则VI(K , F ) 必定有解. 由于引理1. 4, 为研究VI(K , F ) 解的存在性, 本文以下假设K 是无界闭凸集. 我们给出VI(K , F ) 的例外簇的定义.
定义111 令x ^I K , 称序列{x }r y ]
-[F (x +t r (x ^-x ) ) +t r (x -x ^) ]I N K (x ) ,
其中N K (x ) 表示K 在x 的法锥. 法锥N K (#) 的定义如下:
N K (x ) =
{z I R :z (y -x ) [0, P y I K }, 若x I K ,
ª, 其他.
n
T
r
r
r
r
r
r
r
r
(4)
(5)
注111 定义1. 1是文献[11]中例外簇概念的推广. 事实上, 设K 是由(3) 式定义的非空闭凸集且满足Slater 条件. 令x I K , 则对任意的y I K , K I [0, 1], 有x +K (y -x ) I K . 令I ={1, 2, , , m }, J ={1, 2, , , l }, I (x ) ={i I I :g i (x ) =0}, 则有
0\lim K |00=lim K |0
g i (x +K (y -x ) ) -g i (x )
K
h j (x +K (y -x ) ) -h j (x )
=$g i (x ) (y -x ) , P i I I (x ) , =$h j (x ) (y -x ) , P j I J .
T T
(6a)
(6b)
K n
对于任意z I N K (x ) , 任意y I R , 如果存在 K >0, 使得x +K (y -x ) I K , P K , 0[K
T
(5) 和(6) 式, z (y -x ) [0; 如果有x +K (y -x ) |K , P K , 0[K
T T
$g i (x ) (y -x ) >0, 或存在j I J , 使得$h j (x ) (y -x ) X 0, 故集合
S =y -x :y I R ; z (y -x ) >0; $g i (x ) (y -x ) [0, P i I I (x ) ;
$h j (x ) (y -x ) =T
n T T
第10期张立平等:变分不等式问题的解的存在性
895
是空集. 由Farkas 引理知, 存在K i \0(i I I (x ) ) , L j I R(j I J ) , 使得
z =
r
r
i I I (x )
E
K i $g i (x ) +
r
j I J
E L $h (x ).
j
j
r l
r
(7) (8)
r
T
设{x }是VI(K , F ) 关于x ^的一例外簇, 由(4) 式知,
-2[F (x +t r (x ^-x ) ) +t r (x -x ^) ]I N K (x ).
再由(7) 和(8) 式知, v (K r ) i \0(i I I (x ) ) , 和L r I R , 使得
-2[F (x +t r (x ^-x ) ) +t r (x -x ^) ]=
取(K r ) i =0(i I I \I (x ) ) , 则有
F (x +t r (x ^-x ) ) =-t r (x -x ^) -(K r ) g (x ) =0.
令y =x +t r (x ^-x ) , 则x =
r
r
r
r
r T
r
r
r
r
r
r
r
r
i I I (x )
r
E
(K r ) i $g i (x ) +$h (x ) L r .
r
r
(9)
1r T r T
$g (x ) K r +$h (x ) L r , 2
(10) (11)
t r r r r r
-, 且y I K . 令A r =, 则有x =A r y +(1-1-t r 1-t r 1-t r
r
r
A ^I K . 因01, A r y +(1-A ^I K , 并且(10) 和(11) 式可化为r ) x
F (y ) =-(A r -1) (y -x ^) -r
T
r
r
r T
$g (A r y +(1-A r ) x ^) K r 2
(12) (13)
$h (A r y +(1-A r ) x ^) L r ,
(K ^) =0. r ) g (A r y +(1-A r ) x
r
T
r
这表明{y }r y ]
设K ={x I R :-x [0}=R +, 取x ^=0, 则(12) 和(13) 式化为
-(A r -1) y i , 若y i >0,
(14) r (K r ) i \0, 若y i =0. 2
r
这意味着{y }既是文献[8]中定义的NCP(F ) 的例外序列, 也是文献[9]中讨论的反半径序列.
n n n
定理111 设K 是R 中一个非空闭凸集, F :R y R 为一连续函数, 则VI(K , F ) 或有解, 或对任意x ^I K , 有关于x ^的一个例外簇.
F i (y ) =
证 令
由引理1. 1知, x 是VI(K , F ) 的解当且仅当
H (x , t ) =t (x -x ^) +(1-t )
D r ={x I R :+x +0.
若VI(K , F ) 无解, 则对每个r >+x ^+, 存在z I 5D r , t r I [0, 1], 使得0=H (z , t r ) . 若不然, 则存在r 0>+x ^+, 使得
0|{H (x , ) :x I 5D r 0, I [0, 1]}.
r
r
n
r
r
r
n
n
896
中 国 科 学 (A 辑) 第30卷
由引理1. 2知,
deg(
因|deg(x -x ^, D r 0, 0) |=1, 故由引理1. 3知,
0=H (z , t r ) =t r (z -x ^) +(1-t r ) [z -P K (z -F (z ) ) ]=z -t r x ^-(1-t r ) P K (z -F (z ) ).
r
r
r
r
r
r
r
r
r
r
r
r
r
r
(15)
若t r =0, 则由(15) 式知z =P K (z -F (z ) ) , 即z 是(1) 式的解, 矛盾. 若t r =1, 则由(15) 式知, z =x ^, 这与+z +=r >+x ^+相矛盾. 故t r I (0, 1). 由(15) 式知, 对所有的r >+x ^+, t r I (0, 1) ,
t r r r r
-=P K (z -F (z ) ) I K . 1-t r 1-t r
即x >
r
(16)
t r r
-是下面问题的惟一解:
1-t r 1-t r
r r 2
+x -(z -F (z ) ) +:x I K .
2
于是有
-[x -(z -F (z ) ) ]I N K (x ).
即
-[F (x +t r (x ^-x ) ) +t r (x -x ^) ]I N K (x ).
VI(K , F ) 关于x ^的一个例外簇.
定理112 若对某一x ^I K , VI(K , F ) 无关于x ^的例外簇, 则VI(K , F ) 有解.
r
r
r
r
r
r
r
r
(17) (18)
r r r r
由(16) 式及+z +=r 可知, x I K 且+x +y ](r y +]). 根据定义1. 1, {x }r y ]
2 VI(K , F ) 无例外簇的条件
定理1. 1和1. 2给出了VI(K , F ) 有解的一个充分条件. 我们将证明这个条件弱于文献中一些已知的解的存在性条件. 对伪单调变分不等式而言, 它也是必要的.
n n n
定理211 设F :R y R 是一连续函数, K
r r r r
对每个序列{x }+x ^+, 使得
r T r (x -x ^) F (x ) \0, (19) 则VI(K , F ) 无关于x ^的例外簇, 因此VI(K , F ) 有解.
证 用反证法. 假若VI(K , F ) 有关于x ^的例外簇{x }r
数列{t r }, 满足0
[F (x +t r (x ^-x ) ) +t r (x -x ^) ](x -x ) \0, P x I K .
在(20) 式中, 令y =x +t r (x ^-x ) 及x =x ^, 得
t r r
(y -x ^) F (y ) +
1-t r
r
T
r
r
r
r
r
r
T
r r
y +]
(20)
r
-1-t (y -x ^)
r t r r 2
+y -x ^+. -t r
\0.
因0
F (y ) (y -x ^) [-r T
r
第10期张立平等:变分不等式问题的解的存在性
897
于是,
(y -x ^) F (y ) +x ^+.
r
r
r
r
r
r
T
r
r
r
(21)
但y =x +t r (x ^-x ) I K , 且由+x +y ], 0
推论211 设F :R y R 是一连续函数, K
K (x ^) ={x I K :(x -x ^) F (x )
T
(22)
有界(或为空) , 则VI(K , F ) 无例外簇.
注211 Harker 和Pang 提出了条件(22) (见文献[1]中定理2. 3) , 它是本文条件的推论.
文献[11]提出了/p -阶强制性0的概念:
定义211 称函数F :R y R 关于凸集K 是p -阶强制的, 若存在p I (-], 1) , x ^I K , 使得
lim =+]. (23) x I K , +x +y ]+x +
当p =1, (23) 式就是通常的强制性条件(见文献[7]) . 显然, 强制性函数必是p -阶强制的. 反之不然(见文献[11]) . 强制性条件在研究VI(K , F ) 解存在方面起着重要的作用(见文献[7~9, 15]). Hartman 和Sta mpacchia 个结果可推广到p -阶强制性函数.
[16]
T
n
n
, Mor 证明了:若F 是强制的, 则VI(K , F ) 有解. 这
[7]
n n n
推论212 设F :R y R 是一连续函数, K
使得F 是p -阶强制的, 则VI(K , F ) 无例外簇.
[1]n n
定义212 称函数F :R y R 在凸集K 中满足Karamardian 条件, 若存在非空有界集D
(x -y ) F (x ) \0.
n n
定义213 称函数F :R y R 为
n
(a) 在K
T T
(y -x ) F (x ) \0](y -x ) F (y ) \0;
n
(b) 在K
T T
(y -x ) F (x ) >0](y -x ) F (y ) \0.
[10]
显然, 在单调的概念中, 拟单调是最弱的. 伪单调函数必是拟单调的, 反之不然.
T
(24) (25)
r
定义214
[11]
(D1) 称F :R y R 在K 中是弱正常的, 若存在x ^I K , 使得对每个序列{x }
(26) (27)
n n
r T r (x -x ^) F (x ^) \0, +x +>+x ^+. (D2) 称F :R y R 在K 中是严格弱正常的, 若(26) 式换为(x -x ^) F (x ^) >0, +x +>+x ^+.
类似于文献[10, 11], 也可证明以下的一些结果:Karamardian 条件, 则VI(K , F ) 无例外簇.
r
T
r
n
n
n n n
定理212 设F :R y R 是一连续函数, K
n n n
:,
898
中 国 科 学 (A 辑) 第30卷
调的, 则下列条件等价:
( ) VI(K , F ) 无例外簇;
( ) F 在K 中是弱正常的; ( ) VI(K , F ) 有解.
n n n
定理214 设F :R y R 是一连续函数, K
定理2. 2~2. 4说明本文定理1. 2给出的VI(K , F ) 的解存在条件弱于许多已知的解存在条件, 而且成为伪单调VI(K , F ) 解存在的充分必要条件.
3 P 0非线性互补问题的解的存在性
我们研究一类重要的非线性互补问题NCP(F ) 的解的存在性, 这里F 是P 0-函数. 常见的单调函数、一致P -函数、P -函数、P *-函数均是P 0-函数的特例. 文献[10, 11, 15]中对于单调函数、一致P -函数、P -函数、P *-函数等构成的NCP(F ) 已研究了解的存在性.
n n n
定义311 称F :R y R 为K
1[i [n
max [F i (x ) -F i (y ) ](x i -y i ) \0, P x , y I K , x X y .
下面给出NCP(F ) 的解存在的两个充分条件, 这里F 是P 0-函数. 记e i 为第i 个分量是1, 其余分量是0的n 维向量.
n n
定理311 设F :R y R 是一连续P 0-函数, 若存在n 个数A , n ) , 使得i \0(i =1, 2, , F (A i e i ) I R +(i =1, 2, , , n ) , 则NCP(F ) 在R +中无关于点0的例外簇, 因而NCP(F ) 有解.
证 设NCP(F ) 在R +中有关于点0的例外簇{x }r y +
存在数列{G r }, G r >0, 有
F i (x ) =-G r x i , 如果x i >0, F i (x ) \0, 如果x i =0.
令
I
r
r
+
r
r
r
r
r
n
r
]
n r
n
n
(28) (29)
={i :x i >0}, I
r
r
r
={i :x i =0}.
r
(30) (31)
由于+x +y ](r y +]) , 故存在i 0, 使得
lim sup x i 0=+]. r y +]
于是存在r , 使得x i 0>A , y =A i \0. 令x =x i e i , 则有000
x i =y i , P i I I
r
*
*
*
*r r
; x i 0=x
r i
*0
>A i =y i ; x i >0=y i , P i I I 00
r
*
r
+
*
, i X i 0. (32)
由(28) ~(30) 和(32) 式及定理假设知,
*x F i (x ) =-G r i , P i I I
r
+
*
,
F i (y ) \0, P i =1, 2, , , n ,
故P i I I
r +
*
, 有x i X y i , 且
F (x ) i () i i x r *i -F i ) r
*
r
*
第10期张立平等:变分不等式问题的解的存在性
899
=-G r (x i ) -x F i (y )
*
r
*
2
r i
*
(33)
[F i 0(x ) -F i 0(y ) ](x i 0-y i 0)
*
=(x i 0-A i ) (-G r x i 0-F i 0(y ) )
r
*
r
*
(34)
于是(32) ~(34) 式和F 是P -0函数相矛盾, 故NCP(F ) 无例外簇, 因此(2) 式有解.
定理312 设F :R y R 是一连续P 0-函数, 若存在n 个数B i [0(i =1, 2, , , n ) , 使得F (B i e i ) I R +(i =1, 2, , , n ) , 则NCP(F ) 在R +中无关于点0的例外簇, 因而NC P(F ) 有解.
证明类似于定理3. 1, 故略.
n
n
n
n
4 结论
本文给出了VI(K , F ) (K 是一般闭凸集) 的例外簇的概念, 证明了VI(K , F ) 无例外簇是解存在的一个充分条件, 并且证明了这个新的充分条件弱于一些已知的解存在条件. 此条件对于伪单调变分不等式问题的解的存在性是充分必要条件, 最后, 给出了P 0非线性互补问题解存在的充分条件.
参 考 文 献
1 Harker P T, Pang J S. Fini te -di mensional variati onal inequality and nonlinear complementari ty problems:A survey of theory, algo -rithm, and applicati ons. Mathematical Programming, 1990, 48(2):161~220
2 Eaves B C. The linear complementarity problem. M anagement Science, 1971, 17(3) :612~634
3 Eaves B C. On the basic theorem of complementarity problem. Math Programming, 1971, 1(1):68~754 Karamardian S. Generaliz ed complementarity problem. J Optim Theory Appl, 1971, 8(1) :161~167
5 Kojima M. A uni fication of the existence theorems of the nonlinear complementari ty problem. Math Progra mming, 1975, 9(2) :257~2776 Mor J J. Class es of functions and feasi bility condi tions in nonli near comple mentari ty problems. Math Programming, 1974, 6(2) :327~3387 Mor J J. Coercivity condi tions in nonlinear complementarity problems. SIA M Rev, 1974, 16(1):1~16
8 Smith T E. A s oluti on condition for complementarity problems, with an application to s patial price equili brium. Appl Math Co mputa -tion, 1984, 15(1) :61~69
9 Isac G, Bulavas ki V, Kalas hnikov V. Exceptional families, topological degree and complementarity proble ms. J Global Opti m, 1997, 10(2) :207~225
10 Zhao Y B, Han J Y, Qi H D. Exceptional families and e xis tence theorems for vari ational i nequality proble ms. J Opti m Theory Appl,
1999, 101(2) :475~495
11 Zhao Y B, Han J Y. Exceptional family of ele ments for a variati onal i nequali ty problem and i ts applications. J Global Optim, 1999,
14(2) :313~330
12 Zhao Y B. Exceptional families and fi nite dimensional variati onal inequalities over pol yhedral convex sets. Appl Math Computation,
1997, 87(1) :111~126
13 Ll oyd N Q. Degree Theory. Cambridge:Cambri dge Universi ty Press, 1978. 6~54
14 Ortega J M , R hei nholdt W C. Iterative Solution of Nonli near Equations i n Several Vari ables. Ne w York:Academic Press, 1970. 30~
45
15 Isac G, Obuchows ka W T. Functions w i thout exceptional family of ele ments and complementarity problems. J Opti m Theory Appl,
1998, 99(1) :147~163
16 Hartman P, Stampacchia G. On s ome nonlinear elliptic differentiable functional equati on. Acta Math, 1966, 115(2) :271~310