设$D\subseteq {\Bbb R}^{n}$是一个非空闭凸集, $F:{\Bbb R}^{n}\rightarrow {\Bbb R}^{n}$是连续映射.我们考虑经典的变分不等式问题:寻找$x^{*}\in D$,使得

其中, $\langle{\cdot}, {\cdot}\rangle$是欧几里得内积.为了便于表述,我们将问题(1.1)记为$VI(F, D)$,将其解集记为$D^{*}$.变分不等式问题在数学规划,偏微分方程,优化控制等领域有广泛应用.为了解决问题(1.1),众多学者已经提出了一系列的数值计算方法.投影算法因为其简洁而有效得到了广泛的发展(参见文献[1]).最早的投影算法由Goldstein^[2]和Levitin-Polyak^[3]提出

虽然该投影算法的每步迭代仅计算一次投影,但需要$VI(F, D)$中的映射$F$满足Lipschitz连续和强单等非常限制的条件.为了使投影算法能够有更广的适用范围,学者不断改进一步投影算法.通过多计算一次投影,投影算法能够适用于具有更弱单调性的变分不等式,如Korpelevich^[4]提出的适用于伪单调变分不等式的外梯度算法

但是,文献[5-6]的双投影算法通过引入的Armijo线性搜索去掉对映射的Lipschtz连续假设条件.在双投影算法中,第一次投影和线性搜索是为了寻找合适的搜索方向,第二次投影将当前迭代投影到由搜索方向确定的超平面,产生下一步迭代.因为不同的搜索方向产生的超平面不相同,一些学者尝试研究新的搜索方向,如文献[7].本文提出一种新的双投影算法,利用了不同于已有文献的搜索方向,证明算法所产生的序列全局收敛.

本文的内容安排如下:在第2节给出一些定义和基本的事实;在第3节呈现具体的双投影算法;在第4节讨论算法的收敛性并作出收敛率分析;在第5节给出数值实验说明算法的有效性.

设$X\subset {\Bbb R}^n$是一个非空闭凸集.$(z, X) = \inf_\limits{x\in X}\|{z-x}\|$表示向量$z$到$X$的距离, $P_X(z)$表示向量$z$在$X$上的投影,即$P_X(x)$满足$\|{x-P_X(x)}\| = (x, X)$.

引理2.1^[8]  令$X$是${\Bbb R}^{n}$上的一个非空闭凸集.对任意$x\in {\Bbb R}^{n}, z\in X,$有下列不等式成立

引理2.2^[8]  令$X$是${\Bbb R}^{n}$上的一个非空闭凸集, $\bar{x} = P_X(x), \; x^{*}\in X$则有

命题2.1^[8]  给定参数$\mu>0$,记$r_{\mu}(x) = x-P_{D}(x-\mu F(x))$,则$x^{*}\in D^{*}$当且仅当$r_{\mu}(x^*) = 0$.

命题2.2^[7]  对任意$x\in D$,都有如下不等式成立

定义2.1  映射$F:K\subseteq R^n\rightarrow R^n$,任意$x, y\in K$,若

(1) $\langle{F(y)-F(x)}, {y-x}\rangle\geq \eta \|{y-x}\|^2$,则称$F$在$K$上是强单调的, $\eta>0$是$F$在$K$上的强单调系数;

(2) $\langle{F(y)-F(x)}, {y-x}\rangle\geq 0$,则称$F$在$K$上是单调的;

(3) $\langle{F(x)}, {y-x}\rangle\geq 0\Rightarrow \langle{F(y)}, {y-x}\rangle\geq 0$,则称$F$在$K$上是伪单调的;

(4) $\|{F(x)-F(y)}\|\leq L\|{x-y}\|$,则称$F$在$K$上是Lipschitz连续的, $L>0$是$F$在$K$上的Lipschitz系数.

本文假设

$(C_{1})$$D^{*}\neq\emptyset$;

$(C_{2})$对$\forall x^{*}\in D^{*}$都有$\langle{F(x)}, {x-x^{*}}\rangle\geq 0, \forall x\in D$.

具体算法内容如下.

算法3.1  选取初始点$x^{0}\in D$, $\sigma>0, \mu\in(0, \sigma^{-1}), \gamma\in(0, 1)$.令$k = 0$.计算$z^{k} = P_{D}(x^{k}-\mu F(x^{k}))$.

步骤1  计算$r_{\mu}(x^k) = x^{k}-z^{k}$.如果$r_{\mu}(x^k) = 0$,停止;否则,转到步骤2.

步骤2  计算$y^{k} = x^{k}-\eta_{k}r_{\mu}(x^{k})$,其中$\eta_{k} = \gamma^{m_{k}}$, $m_{k}$是使得(3.1)式成立的最小非负整数

步骤3  计算$x^{k+1} = P_{D\bigcap H_{k}}(x^{k})$,其中

令$k: = k+1$,转到步骤1.

为了对算法$3.1$有更好的理解,我们呈现下面的分析.

首先,我们总是假设$x^{k}\notin D^{*}$,那么$\{x^{k}\}$是由算法$3.1$所产生的无穷序列.于是, $r_{\mu}(x^{k})\neq0$.对$\forall k\in N$,都存在非负整数$m$满足(3.1)式.事实上,倘若这样的$m$不存在,则$\exists k_{0}\in N$,使得对所有的非负整数$m$都有

因为$F$是连续的, $\gamma\in(0, 1)$,所以

因此,由(3.2)式可得$0>\sigma\|{r_{\mu}(x^{k_0})}\|^2$.显然这与$r_{\mu}(x^{k_0})\neq0$矛盾.也即是算法$3.1$中的$\eta_{k}$有定义.

其次,我们给出下面的引理,便于我们在第4节讨论算法的收敛性.

引理3.1  令$\{x^{k}\}$是由算法$3.1$所产生的无穷序列, $x^{*}\in D^{*}$是任意的.则对任意固定的$k\in N$都有$x^{*}\in H_{k}, \; x^{k}\notin H_{k}$.

证  定义$h_{k}(x) = \langle{x-x^{k}}, {F(x^{k})+F(y^{k})}\rangle+\eta_{k}\langle{F(y^{k})}, {r_{\mu}(x^k)}\rangle$.由命题$2.2$和(3.1)式可得

因此, $x^{k}\notin H_{k}$.由$C_{2}$可得

又因为

于是我们有

由(3.5)式可得

因此, $x^{*}\in H_{k}$.又因为$x^{*}\in D$,所以$D\bigcap H_{k}\neq\emptyset$.由于$D\bigcap H_{k}$是非空闭凸集,于是$x^{k+1} = P_{D\bigcap H_{k}}(x^{k})$是有定义的,也进一步说明算法$3.1$是可行的.证毕.

引理3.2  令$D\subseteq R^{n}$是一个非空闭凸集, $h:R^{n}\rightarrow {\Bbb R}$是实值函数, $K = \{x\in D|h(x)\leq0\}$.若$K$是非空的, $h(x)$在$D$上是Lipschitz连续的, $L>0$是其Lipschitz系数,则

证  显然,对任意$x\in K$都有(3.7)式成立.因此,我们只需证明对任意$x\in D\setminus K$也有(3.7)式成立.令$x\in D$,但是$x\notin K$.因为$K$是闭的,所以存在$y_{x}\in K$使得${{\rm{dist}}}(x, K) = \|{x-y_{x}}\|$.根据$h(x)$的Lipschitz连续性有

因为$x\notin K, y_{x}\in K$,所以$h(x)>0, h(y_{x})<0$.因此,我们有

于是,结论成立.证毕.

下面的定理将分别呈现算法的收敛结果以及收敛率分析.

定理4.1  假设$(C_{1}), (C_{2})$成立,且$\{x^{k}\}$是由算法$3.1$所产生的无穷序列,则$\{x^{k}\}$收敛于$VI(F, D)$的一个解.

证  因为$x^{k+1} = P_{D\bigcap H_{k}}(x^{k})$,由引理2.2可得

由(4.1)式可知序列$\{\|{x^{k}-x^{*}}\|^{2}\}$是收敛序列.因此$\{x^{k}\}$有界,同时有

根据$F$的连续性可知, $\{F(x^{k})\}, \{F(y^{k})\}$都为有界序列,则存在一个常数$M>0$,使得$\|{F(x^{k})+F(y^{k})}\|\leq M, \forall k\in N$.显然,引理$3.1$的证明过程中定义的$h_{k}(x)$在$D$上是Lipschitz连续的, $M$为其Lipschitz系数.由引理$3.2$以及$x^{k}\notin D\bigcap H_{k}$有

(4.3)式以及引理3.1表明

于是有$\lim_{k\rightarrow\infty}\eta_{k}\|{r_{\mu}(x^{k})}\|^{2} = 0$.

(ⅰ)如果$\limsup_{k\rightarrow\infty}\eta_{k}>0$,则必有$\liminf_{k\rightarrow\infty}\|{r_{\mu}(x^{k})}\|^{2} = 0$.由$r_{\mu}(x)$的连续性以及序列$\{x^{k}\}$的有界性可知必存在$\{x^{k}\}$的聚点$\bar{x}$使得$r_{\mu}(\bar{x}) = 0$,由命题$2.1$可知$\bar{x}$是$VI(F, D)$的解.用$\bar{x}$代替先前的$x^{*}$可得序列$\{\|{x^{k}-\bar{x}}\|^{2}\}$收敛.因为$\bar{x}$是$\{x^{k}\}$的聚点,则存在$\{\|{x^{k}-\bar{x}}\|^{2}\}$的子列$\{\|{x^{k_{j}}-\bar{x}}\|^{2}\}$收敛于$0$.因此整个序列$\{\|{x^{k}-\bar{x}}\|^{2}\}$收敛于$0$,也即是$\lim_{k\rightarrow\infty}x^{k} = \bar{x}$.

(ⅱ)如果$\limsup_{k\rightarrow\infty}\eta_{k} = 0$.令$\bar{x}$是$\{x^{k}\}$的聚点,则存在子列$\{x^{k_{j}}\}$收敛于$\bar{x}$.$\eta_{k}$的选取表明

因为$\{r_{\mu}(x^{k})\}$是有界的, $F$是连续的.令$j\rightarrow\infty$,则$r_{\mu}(\bar{x}) = 0$.运用$(i)$中相同的论述可得$\lim_{k\rightarrow\infty}x^{k} = \bar{x}$.证毕.

定理4.2  在定理$4.1$中进一步假设$F$是$L$-Lipschitz连续的,且存在常数$\lambda, \delta>0$以及任意的$x$,使得当$\|{r_{\mu}(x)}\|\leq\delta$时,有

则存在常数$\omega>0$使得对充分大的$k$,有${{\rm{dist}}}(x^{k}, D^{*})\leq \omega/(k+1)^{\frac{1}{2}}$,其中${{\rm{dist}}}(x, D^{*})$是$x$到$D^{*}$的距离.

证  对任意的$k\geq1$,若$m_{k}\neq1$,由$F$的Lipschitz连续性和(3.1)式可得

于是有$\eta_{k}>\frac{\sigma\gamma}{L}>0$,故$\eta_{k}$是有下界的.因此,存在$T>0$使得$\eta_{k}>T$.根据(4.1)和(4.2)式有

又因为$\|{r_{\mu}(x^{k})}\|$收敛于$0$,故存在$N>0$,使得当$k\geq N$时有$\|{r_{\mu}(x^{k})}\|\leq\delta$.假设$x^{*}$为解集$D^{*}$中最接近$x^{k}$的点,则有

由此可得序列$\{{{\rm{dist}}}(x^{k}, D^{*})\}$满足文献[9]第二章引理$6$的条件,故存在常数$\omega>0$使得对充分大的$k$,有

证毕.

本节给出数值实验,我们在Windows 7,处理器为Intel(R) Core(TM) 2 Quad CPU Q9500 $@$2.83GHz的系统环境下,使用版本为R2014a的MATLAB进行数值实验.在计算过程中,我们允许误差为$\varepsilon = 10^{-4}$,即当$\|{r(x)}\|^2\leq 10^{-4}$程序终止.我们令算法$3.1$中参数取为:$\gamma = 0.8$, $\sigma = 6$, $\mu = 0.15$,令$x^{0}$代表初始点, nf表示计算$F$的次数, iter表示程序迭代的次数, time代表程序运行所需的时间.

例5.1  令$D = [0, 1]^{n}, F(x) = Mx+d$,其中

我们分别选取原点$x^{0} = (0, \cdots 0, 0)$和$x^{0} = (1, \cdots 1, 1)$为初始点,对算法$3.1$和文献[6]的算法$2.2$进行测试,并将两者的数值结果进行比较.其中,文献[6]的算法$2.2$参数取为:$\gamma = 0.5, \sigma = 0.3$.得到数值结果分别如表 1和表 2所示.

例5.2  Kojima-Shindo型的非线性相补问题(取$n = 4$)被文献考虑,其中函数$F(x)$的定义如下

我们分别选取不同的初始点,然后对算法$3.1$和文献[10]的算法$3.1$进行测试,并将两者的数值结果进行比较.其中,文献[10]的算法$3.1$参数取为:$\gamma = 0.9, \sigma = 3, \mu = 0.3, \beta = 0.4, \alpha = 3$.得到数值结果如表 3所示.

观察表 1-表 3的数值实验结果,我们可以得到:在适当参数的选取下,算法$3.1$收敛到解的速度较其它两种算法更快.在例1,例2的问题中,算法$3.1$的迭代次数和运行时间都比文献[6]中的算法$2.2$和文献[10]中的算法$3.1$少.这表明我们的算法$3.1$在一定程度上的有效性.但是,能否改进搜索方向使得我们的算法$3.1$收敛速度更快以及能否进一步削弱假设条件使得我们的算法$3.1$适用于拟调单调变不等式是我们进一步需要探究的工作.