设$ X $是Hilbert空间$ E $中的非空子集, $ E $中的内积和范数分别记为$ \langle\cdot, \cdot\rangle $和$ \|\cdot\|, $$ T:X\to E $是一个函数,由$ T $决定的变分不等式问题是

$ \mbox{求} \ x^*\in X, \mbox{使得} \ \langle T(x^*), y-x^*\rangle\geq 0, \forall y \in X. $

如果满足条件的$ x^* $存在,则称$ x^* $是变分不等式问题$ T $的解.

关于变分不等式问题的研究一直是学者们研究的热点之一,这主要源于变分不等式在最优化理论、非线性椭圆边值问题、博弈论、数理经济学等多个领域有着广泛的应用.近年来,研究者们围绕变分不等式问题在解的存在性、解的稳定性、求解算法及其应用方面获得了丰硕的研究成果,见文献[1-9].其中,最新的研究成果[2]研究了随机变分不等式解的存在性并且提供了一个求解两阶段随机变分不等式的有效算法及应用.文献[4]从算法的角度利用变分不等式的框架研究线性约束的凸优化问题,指出凸规划的分裂收缩算法,相当于变分不等式中投影收缩算法.文献[5]从稳定性的角度研究了带有变分关系的问题的解的稳定性.文献[7]从解的存在性角度研究了单调变分不等式问题的解的通有唯一性,文献[8]利用KKM引理讨论了向量变分不等式解的存在性.还有专著[10-11]及其参考文献.新的研究结果还在持续不断地涌现.

特别引起我们关注的是关于变分不等式问题的解的算法设计问题,从以上文献中看到这些算法的设计基于具体的问题来设计分析的.这引起一些自然的疑问:这些不同的算法是否可以归为一个统一的理论?解是如何依赖目标函数、约束集和求解方法的?在此文中,我们将对这些问题作出回答.

另一方面,根据Simon^[12]的有限理性理论思想,主要有三因素影响决策者的结果:决策者不可能穷尽所有的策略,即决策方案是近似的,其次选择的目标函数是近似的,再者求解的计算方法是近似的.因此人们在决策时以达“满意解”,而不是“最优解”,即有限理性下的结果.正如俞建教授在文献[13]中所说,我们应当思考这样的问题:在博弈论与经济学模型中考虑有限理性的作用,究竟会对建立在完全理性之上的模型分析结果产生怎样的影响或冲击呢?进一步,我们可以引申更深层次的思考:针对不同的问题或模型,有限理性是如何介入的?有限理性介入后如何影响原模型的结果,具体如何刻画这种影响或冲击?有限理性的解与完全理性下的解之间的关系是如何清晰表达的?或者说从数学上根据不同的问题和模型,有限理性是如何向完全理性逼近的?在多大程度上逼近?路径如何选择?有关这方面的逼近分析在现有的文献中很少提及,见文献[13].俞建教授在文献[13]中首次给出了有限理性思想下最优化问题(包括多目标优化问题)和$ n $人非合作博弈问题(包括鞍点问题)等问题的逼近定理,充分体现了有限理性是对完全理性的逼近,部分回应了Simon的质疑^[12],这些结果是非常有理论意义的.从实际应用的角度看,反映了有限理性是以完全理性作为自己的终极目标.文献[14]证明了在有限理性思想下平衡问题的逼近定理,也说明了有限理性是对完全理性的逼近,而且为平衡问题的有关算提供了一个理论支持.本文受文献[13]的启发,构造了有限理性思想下的变分不等式问题的逼近定理,为变分不等式问题的解的有关数值算法提供一个理论支持,同时在有限理性思想下分析了不同扰动下解的收敛情况.其中, Fort引理^[15]在文中关于解的收敛性分析中起了关键的作用.

本文结构如下:第2节给出我们需要的预备知识,包括集值映射的连续性质和后续用到的必要的引理;第3节直接证明有限理性下变分不等式的逼近定理,并由此得到有关的推论;第4节分别在有限理性思想下探讨了变分不等式问题在函数扰动和函数和约束集同时扰动下解的收敛分析,我们得到在Baire分类的意义下,两种情况下单调变分不等式问题的解都具有通有收敛性质;第5节对全文进行了总结.

首先,我们先回顾几个基本概念和结论,并给出后面需要用到的若干引理.

定义2.1^[16]  设$ X, Y $是两个拓扑空间,集值映射$ F: X\to P_0(Y) $,其中$ P_0(Y) $表示$ Y $的所有子集的集合, $ x\in X $,

(1)如果对$ X $中的任意开集$ G, G\supset F(x) $ (或$ G\cap F(x)\neq {\emptyset} $),存在$ x $的开邻域$ O(x) $,使得$ \forall x'\in O(x), $有$ G\supset F(x') $(或$ G\cap F(x')\neq {\emptyset} $),则称集值映射$ F $在$ x $上是上半连续的(或下半连续的).

(2)如果$ F $在$ x $上既上半连续的又下半连续,则称集值映射$ F $在$ x $上是连续的.

(3)如果$ \forall x\in X $,集值映射$ F $在$ x $上是连续的(或上半连续的,或下半连续的),则$ F $在$ X $上是连续的(或上半连续的,或下半连续的).

(4)称$ F $在$ X $上是usco映射,如果$ F $在$ X $是上半连续的,且$ \forall x\in X $, $ F(x) $是非空紧集.

(5)称集值映射$ F $是闭的,如果$ GraphF = \{(x, y)\in X\times Y: y\in F(x)\} $是$ X\times Y $中的闭集.

(6)如果$ F $在$ X $上是usco映射,则$ F $是闭映射.

(7)如果$ F $是闭的, $ Y $为紧空间,则集值映射$ F $在$ X $上是上半连续的.

集值映射的上半连续与下半连续是两个不同的概念,一般不能从一个成立推出另一个成立,但Fort^[15]指出了它们之间的某种联系,其在通有连续性研究中具有至关重要的作用.

Fort引理^[15]  设$ X $是一个Hausdorff拓扑空间, $ Y $是一个度量空间, $ F:X\rightarrow P_{0}(Y) $是一个usco映射,则存在$ X $中的一个剩余集$ Q $,使得$ \forall x\in Q $, $ F $在$ x $是下半连续的,从而是连续的.

在此基础上, Tan、Yu和Yuan^[17]将其发展为Baire空间下的结果,可见文献[17]中的引理2.3或文献[18]中的引理2.1.

引理2.1^[19]  如果$ X $是一个Baire空间, $ Y $是一个度量空间, $ F:X\rightarrow P_{0}(Y) $是一个usco映射,则存在$ X $中的一个稠密剩余集$ Q $,使得$ \forall x\in Q $, $ F $在$ x $是下半连续的,从而是连续的.

以下引理分别是文献[13]中的引理2.1.4,引理2.1.6及定理2.1.2,这些引理在本文变分不等式问题的有限理性的逼近定理中起着非常关键的作用.

引理2.2^{[13,引理2.1.4]}  设$ (X, d) $是一个度量空间, $ G $是$ X $中的开集, $ A $是$ X $中的紧集,且$ G\supset A, $则存在$ \sigma>0 $使得$ G\supset U(\sigma, A). $

引理2.3^{[13,引理2.1.6]}  对每个$ n = 1, 2, \cdots, $设$ A_n $是$ X $中的非空有界集, $ A $是$ X $中的非空有界子集. $ G $是$ X $中的开集.如果$ G\bigcap A\neq\emptyset $且$ h(A_n, A)\to 0\ (n\to\infty), $则存在一个正整数$ N $,使得对任意的$ n\geq N, G\bigcap A_n\neq \emptyset. $

引理2.4^{[13,定理2.1.2]}  对每个$ n = 1, 2, \cdots, $$ A_n $是$ X $中的非空有界子集, $ A $是$ X $中的紧子集.如果对任意的$ n = 1, 2, \cdots, $$ x_n\in A_n $且$ h(A_n, A)\to 0 \ (n\to\infty). $则$ \{x_n\} $中存在收敛子序列$ \{x_{n_k}\} $,使得$ x_{n_k}\to x^* $且$ x^*\in A. $

注2.1  引理2.4放宽了文献[20,引理1]或文献[19,定理2.1.7]的条件,不再要求$ A_n $是紧集.

在本节中,我们首先引入变分不等式问题的$ \epsilon $近似解的概念.

定义3.1  设$ X $是Hilbert空间$ E $中的非空子集,给定函数$ T:X\to E $及一个实数$ \epsilon>0, $称$ x^* $为变分不等式问题$ T $的一个$ \epsilon $近似解,如果

$ \langle T(x^*), y-x^*\rangle\geq-\epsilon, \forall y \in X. $

接着,我们将直接给出有限理性下变分不等式问题的逼近定理.

定理3.1  设$ X $是Hilbert空间$ E $中的非空子集,假设下列条件成立

(ⅰ)对每个$ n = 1, 2, \cdots, $函数$ T^n:X\to E $满足$ \sup\limits_{x\in X}\|T^n(x)-T(x)\|\to 0\ (n\to\infty) $,其中$ T:X\to\mathbb{R} $是连续的;

(ⅱ)对每个$ n = 1, 2, \cdots, $$ A_n $是$ X $中的子集,且$ h(A_n, A)\to 0 \ (n\to\infty) $,其中$ A $是$ X $中的非空紧集;

(ⅲ)对每个$ n = 1, 2, \cdots, $$ x_n\in X, $且$ d(x_n, A_n)\to 0 $,满足

$ \langle T^n(x_n), y-x_n\rangle\geq -\epsilon_n, \forall y \in A_n, $

其中$ \epsilon_n >0 $且$ \epsilon_n\to 0 \ (n\to \infty). $

则

(1)存在$ \{x_n\} $的一个收敛子列$ \{x_{n_k}\} $,即$ x_{n_k}\to x^* (n\to\infty) $且$ x^*\in A $;

(2)对任意的$ y\in A $, $ \langle T(x^*), y-x^*\rangle\geq 0; $

(3)若变分不等式$ T $的解集是单点集,必有$ x_n\to x^*. $

证  (1)由于$ d(x_n, A_n)\to 0, $则$ \exists x'_n\in A_n $,使得$ d(x_n, x'_n)\to 0 $.再由$ h(A_n, A)\to 0\ (n\to\infty) $,根据引理2.4,结论显然成立.

(2)根据(1)的结果,我们不妨设$ x_n\to x^* $.反证.如果结论不正确,那么存在点$ y_0\in A $使得$ \langle T(x^*), y_0-x^*\rangle<0; $

由于$ T $在$ x^* $处连续,且$ \langle T(x), y-x\rangle $关于变量$ x, y $都是连续的,因此存在一个实数$ \sigma_0>0, $存在$ x^* $的一个开邻域$ O(x^*) $和$ y_0 $的一个开邻域$ O(y_0) $,使得对任意的$ x'\in O(x^*) $和任意的$ y'\in O(y_o) $,有

$ \langle T(x'), y'-x'\rangle<-\sigma_0. $

由Cauchy-Swartz不等式,有$ \langle T^n(x)-T(x), y-x\rangle\leq\|T^n(x)-T(x)\|\|y-x\| $,因此$ \sup\limits_{x\in X}\| T^n(x)-T(x)\| \to 0\ (n\to\infty) $蕴含了$ \sup\limits_{(x, y)\in X\times X}\langle T^n(x)-T(x), y-x\rangle\to 0\ (n\to\infty). $

注意到$ \epsilon_n\to 0\ (n\to \infty), $存在一个正整数$ N_1, $使得$ \forall n\geq N_1, $有

$ \sup\limits_{(x, y)\in X\times X}\langle T^n(x)-T(x), y-x\rangle<\frac{\sigma_0}{2}\ \mbox{且} \ \epsilon_n<\frac{\sigma_0}{2}. $

既然$ n\to\infty, x_n\to x^*, h(A_n, A)\to 0 $且$ y_0\in A, $由引理2.3,存在一个正整数$ N_2\geq N_1 $,使得对任意的$ n\geq N_2, $有$ x_n\in O(x^*) $且$ O(y_0)\bigcap A_n\neq\emptyset $,取$ y_n\in O(y_0)\bigcap A_n, $则

$ \langle T(x_n), y_n-x_n\rangle<-\sigma_0 $

且

$ \langle T^n(x_n), y_n-x_n\rangle<\langle T(x_n), y_n-x_n\rangle+\frac{\sigma_0}{2}<-\frac{\sigma_0}{2}<-\epsilon_n $

都成立.这与条件(ⅲ)矛盾.

(3)反证.如果结论不成立,则存在$ \sigma>0 $和$ \{x_n\} $的一个子序列$ \{x_{n_k}\}, $使$ \|x-x_{n_k}\|\geq \sigma $.序列$ \{x_{n_k}\} $又必有收敛子序列,不妨设$ x_{n_k}\to \bar{x}, $即$ \|\bar{x}-x_{n_k}\|\to 0, $$ \bar{x} $属于$ A $,且也是变分不等式$ T $的解.又由于变分不等式$ T $的解是单点集,故$ \bar{x} = x^* $,则$ \|\bar{x}-x_{n_k}\|\geq \sigma $.矛盾.

注3.1  根据定理3.1,虽然目标函数是近似的($ T^n $近似$ T $),可行解集是近似的($ A_n $近似$ A $),求解精度是近似的(精度为$ \epsilon_n $),但得到的是一个逼近序列$ \{x_n\}, $$ \{x_n\} $必有收敛子序列$ \{x_{n_k}\} $,即$ x_{n_k}\to x^*\in A, $而$ x^* $必是变分问题$ T $的解.如果把变分不等式问题$ T^n $的$ \epsilon_n $近似解$ x_n $看作是有限理性的“满意解”,变分不等式问题$ T $的解$ x^* $看作为完全理性下的“最优解”,定理3.1蕴含了有限理性对完全理性的逼近,即完全理性可以通过一系列有限理性的近似解来逼近.这从数学上也验证了Simon的有限理性理论.

注3.2  根据定理3.1,序列$ \{x_n\} $存在极限点和$ \{x_n\} $存在收敛子序列是等价的,从证明过程知道序列$ \{x_n\} $必有极限点,每一个极限点必属于紧集$ A $,且都是变分不等式$ T $的解.因此,如果变分不等式的解是单点集,必有更强的收敛性结果:$ x_n\to x $.

如果定理3.1中$ x_n\in A_n, $$ n = 1, 2, \cdots, $结论仍然成立,见下面的推论.

推论3.1  设$ X $是Hilbert空间$ E $中的非空子集,假设下列条件成立

(ⅰ)对每个$ n = 1, 2, \cdots, $函数$ T^n:X\to E $满足$ \sup\limits_{x\in X}| T^n(x)-T(x)| \to 0\ (n\to\infty) $,其中$ T:X\to\mathbb{R} $是连续的;

(ⅱ)对每个$ n = 1, 2, \cdots, $$ A_n $是$ X $中的子集,且$ h(A_n, A)\to 0 \ (n\to\infty) $,其中$ A $是$ X $中的非空紧集;

(ⅲ)对每个$ n = 1, 2, \cdots, $$ x_n\in A_n, $满足

$ \langle T^n(x_n), y-x_n\rangle\geq -\epsilon_n, \;\forall y \in A_n, $

其中$ \epsilon_n >0 $且$ \epsilon_n\to 0\ (n\to \infty). $

则

(1)存在$ \{x_n\} $的一个收敛子列$ \{x_{n_k}\} $,即$ x_{n_k}\to x^* \ (n\to\infty) $且$ x^*\in A $;

(2)对任意的$ y\in A $, $ \langle T(x^*), y-x^*\rangle\geq 0; $

(3)若变分不等式$ T $的解集是单点集,必有$ x_n\to x^*. $

如果定理3.1中对任意的$ n = 1, 2, \cdots, A_n = A, $而结果仍然成立,见以下的推论3.2.

推论3.2  设$ X $是Hilbert空间$ E $中的非空子集,假设下列条件成立

(ⅰ)对每个$ n = 1, 2, \cdots, $函数$ T^n:X\to E $满足$ \sup\limits_{x\in X}| T^n(x)-T(x)| \to 0\ (n\to\infty) $,其中$ T:X\to \mathbb{R} $是连续的;

(ⅱ) $ A $是$ X $中的非空紧集;

(ⅲ)对每个$ n = 1, 2, \cdots, $$ x_n\in A $是$ A $的$ \epsilon_n $的近似解,即满足

$ \langle T^n(x_n), y-x_n\rangle\geq -\epsilon_n, \;\; \forall y \in A, $

其中$ \epsilon_n >0 $且$ \epsilon_n\to 0\ (n\to \infty). $

则

(1)存在$ \{x_n\} $的一个收敛子列$ \{x_{n_k}\} $,即$ x_{n_k}\to x^* \ (n\to\infty) $且$ x^*\in A $;

(2)对任意的$ y\in A $, $ \langle T(x^*), y-x^*\rangle\geq 0; $

(3)若变分不等式$ T $的解集是单点集,必有$ x_n\to x^*. $

本节中, $ X $是Hilbert空间$ E $中的非空凸紧子集,函数空间$ M $定义如下

$ M = \left\{T:X\to E: T\ \mbox{在$X$上是连续单调的}\ \right\}, $

其中称$ T:X\to E $在$ X $上是单调的,即$ \langle T(y)-T(x), y-x\rangle\geq 0 , $$ \forall x, y\in X $,具体例子见文献[10].

任取$ T_1, T_2\in M $,定义距离

$ \rho_1(T_1, T_2) = \max\limits_{x\in X}\|T_1(x)-T_2(x)\|. $

显然, $ (M, \rho_1) $是一个完备度量空间.

任取$ T\in M $,记

$ F(T) = \{x\in X: \langle T(x), y-x\rangle\geq 0 , \forall y\in X\}, $

那么$ F(T) $表示变分不等式$ T $所有的解,显然$ F(T)\not =\varnothing. $于是映射$ T\to F(T) $确定了一个集值映射$ F:M\to P(X) $.

根据文献[13,引理7.4.1], $ F:M\to P_0(X) $是一个usco映射.

$ \forall T\in M $,选取函数序列$ \{T^n\} $ (对$ T^n $没有任何连续性要求),使$ \sup\limits_{x\in X}\| T^n(x)-T(x)\| \to 0, $选取$ x_n\in X, $使$ \langle T^n(x_n), y-x_n\rangle\geq -\epsilon_n $对任意的$ y\in X $都成立,其中$ \epsilon_n >0 $且$ \epsilon_n\to 0 $$ (n\to \infty). $

定理4.1  存在$ M $中的一个稠密剩余集$ Q_1, $使得$ \forall T\in Q_1, $必有$ x_n\to x, $且$ \forall y\in X, $$ \langle T(x), y-x\rangle\geq 0 $.

证  由文献[13,定理7.4.4],存在$ M $中的稠密剩余集$ Q_1 $,使得$ \forall T\in Q_1 $, $ T $的解是单点集,再由定理3.1中的结论(3),必有$ x_n\to x. $

注4.1  定理4.1表明了紧集$ X $上目标函数受扰动下,具有单调性的变分不等式问题其解集具有通有收敛性.

接下来,我们考虑在非紧集中目标函数和可行集同时扰动时解的通有收敛性问题.

设$ X $是Hilbert空间$ E $中的非空凸子集(不必紧),问题空间$ M_1 $构造如下

${{M}_{1}}=\left\{ u=(T, A):\begin{array}{*{35}{l}} T:X\to E在X上是连续单调的; \\ \begin{matrix} \sup \\ x\in X \\\end{matrix}\|f(x)\|<\infty ; \\ A是X中非空凸紧子集. \\\end{array} \right\}, $

任取$ u_1 = (T_1, A_1), u_2 = (T_2, A_2)\in Y $,定义距离

$ \rho_2(u_1, u_2) = \sup\limits_{x\in X}\|T_1(x)-T_2(x)\|+h(A_1, A_2) = \rho_1(T_1, T_2)+h(A_1, A_2), $

其中$ h $是由$ E $中的范数诱导的Hausdorff距离.

记$ K(X) $表示$ X $中所有非空凸紧子集组成的集合且装备了Hausdorff距离$ h $.由$ E $的完备性, ($ K(X), h $)也是完备度量空间,见文献[21,定理3.85].

于是我们容易得到下面的引理4.1.

引理4.1   $ (M_1, \rho_2) $是完备度量空间.

任取$ u = (T, A)\in M_1 $,记

$ S(u) = \{x\in A: \langle T(x), y-x\rangle\geq 0, \forall y\in A\}, $

则$ S(u) $表示$ T $在$ A $中的所有解.显然$ S(u)\not =\varnothing $,且映射$ u\to S(u) $定义了一个集值映射$ S:M_1\to P_0(X) $.由文献[7,引理4.3],得以下引理.

引理4.2  $ S:M_1\to P_0(X) $是一个usco映射.

再根据文献[7,定理4.1],有以下定理.

定理4.2  存在$ M_1 $中的一个稠密剩余集$ Q_2 $,使得$ Q_2 $中的每个$ u = (T, A), $$ S(u) $是单点集.

$ \forall u = (T, A)\in M_1 $,选取函数序列$ \{T^n\} $ (对$ T^n $没有任何连续性要求),使$ \sup\limits_{x\in X}\| T^n(x)-T(x)\| \to 0, $选取$ X $中的子集序列$ \{A_n\} $ (对$ A_n $没有任何紧性或闭性要求),使$ h(A_n, A)\to 0 $$ (n\to\infty); $选取$ x_n\in A_n, $使$ \langle T^n(x_n), y-x_n\rangle\geq -\epsilon_n $对任意的$ y\in A_n $都成立,其中$ \epsilon_n >0 $且$ \epsilon_n\to 0 \ (n\to \infty). $

定理4.3  存在$ M_1 $中的一个稠密剩余集$ Q_2, $使得$ \forall u = (T, A)\in Q_2, $必有$ x_n\to x, $且$ \forall y\in A, \langle T(x), y-x\rangle\geq 0 $.

证  由定理4.2,存在$ M_1 $中的稠密剩余集$ Q_2 $,使得$ \forall u = (T, A)\in Q_2 $, $ T $在$ A $上是单点集,再由定理3.1中的结论(3),必有$ x_n\to x. $

注4.2  定理4.3表明了非紧集$ X $上目标函数及可行集两则均受扰动下,具有单调性的变分不等式其解集具有通有收敛性.

本文基于Simon的有限理性思想,构造了变分不等式问题的有限理性下的逼近定理,从而为有关变分不等式问题的不同算法提供了一个统一的理论框架和算法支持,并且回应了Simon的质疑,充分体现了有限理性是对完全理性的逼近,是以完全理性为终极目标的.我们将有限理性的逼近定理应用于变分不等式问题解的收敛性分析,利用集值分析的方法和Fort引理,在Baire分类的意义下,分别得到了函数扰动及函数扰动和约束集扰动两种情况下单调变分不等式问题的解具有通有收敛性的结果.