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

(1.1) $ \begin{equation} \langle F(x^{*}), x-x^{*}\rangle \geq 0, \forall x\in D. \end{equation} $

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

(1.2) $ \begin{equation} x^{k+1} = P_{D}(x^{k}-\beta_{k} F(x^{k})). \end{equation} $

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

(1.3) $ \begin{equation} \bar{x}^{k} = P_{D}(x^{k}- \beta_{k}F(x^{k})), \qquad x^{k+1} = P_{D}(x^{k}- \beta_{k}F(\bar{x}^{k})). \end{equation} $

但是,文献[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.1) $ \begin{equation} \langle{x-P_X(x)}, {z-P_X(x)}\rangle\leq 0. \end{equation} $

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

(2.2) $ \begin{equation} \|{\bar{x}-x^{*}}\|^{2} \leq\|{x-x^{*}}\|^{2}-\|{x-\bar{x}}\|^{2}. \end{equation} $

命题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 $,都有如下不等式成立

$ \langle{F(x)}, {r_{\mu}(x)}\rangle\geq \mu^{-1}\|{r_{\mu}(x)}\|^{2}. $

定义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.1) $ \begin{equation} \langle{F(x^{k})-F(x^{k}-\gamma^{m} r_{\mu}(x^{k}))}, {r_{\mu}(x^{k})}\rangle \leq \sigma \|{r_{\mu}(x^k)}\|^{2}. \end{equation} $

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

$ H_{k} = \{x\in R^n|\langle{x-x^{k}}, {F(x^{k})+F(y^{k})}\rangle+\eta_{k}\langle{F(y^{k})}, {r_{\mu}(x^k)}\rangle\leq0\}. $

令$ 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 $都有

(3.2) $ \begin{equation} \langle{F(x^{k_0})-F(x^{k_0}-\gamma^{m} r_{\mu}(x^{k_0}))}, {r_{\mu}(x^{k_0})}\rangle>\sigma\|{r_{\mu}(x^{k_0})}\|^2, \end{equation} $

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

$ \langle{F(x^{k_0})-F(x^{k_0}-\gamma^{m} r_{\mu}(x^{k_0}))}, {r_{\mu}(x^{k_0})}\rangle\rightarrow0(m\rightarrow \infty). $

因此,由(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)式可得

(3.3) $ \begin{equation} h_{k}(x^{k}) = \eta_{k}\langle{F(y^{k})}, {r_{\mu}(x^k)}\rangle\geq\eta_{k}(\mu^{-1}-\sigma)\|{r_{\mu}(x^{k})}\|^{2}>0. \end{equation} $

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

$ \langle{ F(x^{k})}, {x^{k}-x^{*}}\rangle\geq0. $

又因为

(3.4) $ \begin{eqnarray} \langle{ F(y^{k})}, {x^{k}-x^{*}}\rangle& = &\langle{ F(y^{k})}, {x^{k}-y^{k}+y^{k}-x^{*}}\rangle\\ &\geq & \langle{F(y^{k})}, {x^{k}-y^{k}}\rangle\\ & = &\eta_{k}\langle{ F(y^{k})}, {r_{\mu}(x^{k})}\rangle. \end{eqnarray} $

于是我们有

(3.5) $ \begin{eqnarray} \langle{ F(x^{k})+F(y^{k})}, {x^{k}-x^{*}}\rangle& = &\langle{F(x^{k})}, {x^{k}-x^{*}}\rangle+\langle{ F(y^{k})}, {x^{k}-x^{*}}\rangle\\ &\geq& \langle{F(y^{k})}, {x^{k}-y^{k}}\rangle\\ & = &\eta_{k}\langle{ F(y^{k})}, {r_{\mu}(x^{k})}\rangle. \end{eqnarray} $

由(3.5)式可得

(3.6) $ \begin{eqnarray} 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\\ &\leq&-\eta_{k}\langle{ F(y^{k})}, {r_{\mu}(x^{k})}\rangle+\eta_{k}\langle{F(y^{k})}, {r_{\mu}(x^k)}\rangle \\ & = &0. \end{eqnarray} $

因此, $ 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系数,则

(3.7) $ \begin{equation} {{\rm{dist}}}(x, K)\geq L^{-1}\max\{h(x), 0\}, \forall x\in D. \end{equation} $

证  显然,对任意$ 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连续性有

$ |h(x)-h(y_{x})|\leq L\|{x-y_{x}}\| = L{{\rm{dist}}}(x, K). $

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

$ h(x)\leq h(x)-h(y_{x}) = | h(x)-h(y_{x})|\leq L{{\rm{dist}}}(x, K). $

于是,结论成立.证毕.

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

定理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) $ \begin{equation} \|{x^{k+1}-x^{*}}\|^{2}\leq\|{x^{k}-x^{*}}\|^{2}- \|{x^{k+1}-x^{k}}\|^{2} = \|{x^{k}-x^{*}}\|^{2}-{{\rm{dist}}}^{2}(x^{k}, D\bigcap H_{k}). \end{equation} $

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

(4.2) $ \begin{equation} \lim\limits_{k\rightarrow\infty}{{\rm{dist}}}(x^{k}, D\bigcap H_{k}) = 0. \end{equation} $

根据$ 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) $ \begin{equation} {{\rm{dist}}}(x^{k}, D\bigcap H_{k})\geq M^{-1}h_{k}(x^{k}), \; \; \forall k\in N. \end{equation} $

(4.3)式以及引理3.1表明

(4.4) $ \begin{equation} {{\rm{dist}}}(x^{k}, D\bigcap H_{k})\geq M^{-1}h_{k}(x^{k})\geq M^{-1}\eta_{k}(\mu^{-1}-\sigma)\|{r_{\mu}(x^{k})}\|^{2}. \end{equation} $

于是有$ \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} $的选取表明

(4.5) $ \begin{eqnarray} \sigma \|{r_{\mu}(x^{k_{j}})}\|^{2}&<&\langle{F(x^{k_{j}})-F(x^{k_{j}}-\gamma^{k_{j}-1}r_{\mu}(x^{k_{j}}))}, {r_{\mu}(x^{k_{j}})}\rangle\\ & = &\langle{F(x^{k_{j}})-F(x^{k_{j}}-\gamma^{k_{j}-1}\eta_{k_{j}}r_{\mu}(x^{k_{j}}))}, {r_{\mu}(x^{k_{j}})}\rangle\\ &\leq&\|{F(x^{k_{j}})-F(x^{k_{j}}-\gamma^{k_{j}-1}r_{\mu}(x^{k_{j}}))}\|\|{r_{\mu}(x^{k_{j}})}\|, \forall j. \end{eqnarray} $

因为$ \{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 $时,有

(4.6) $ \begin{equation} {{\rm{dist}}}(x, D^{*})\leq \lambda\; \|{r_{\mu}(x)}\|, \end{equation} $

则存在常数$ \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)式可得

$ \frac{L}{\gamma}\eta_{k}\|{r_{\mu}(x)}\|^{2}\geq \langle{F(x^{k})-F(x^{k}-\gamma^{-1}\eta_{k}r_{\mu}(x^{k}))}, {r_{\mu}(x^{k})}\rangle>\sigma \|{r_{\mu}(x)}\|^{2}\nonumber. $

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

(4.7) $ \begin{eqnarray} \|{x^{k+1}-x^{*}}\|^{2}&\leq&\|{x^{k}-x^{*}}\|^{2}-{{\rm{dist}}}^{2}(x^{k}, D\bigcap H_{k})\\ &\leq&\|{x^{k}-x^{*}}\|^{2}-M^{-2}(\mu^{-1}-\sigma)^{2}\eta_{k}^{2}\|{r_{\mu}(x^{k})}\|^{4}\\ &\leq&\|{x^{k}-x^{*}}\|^{2}-M^{-2}(\mu^{-1}-\sigma)^{2}T^{2}\|{r_{\mu}(x^{k})}\|^{4}. \end{eqnarray} $

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

$ \begin{eqnarray} {{\rm{dist}}}(x^{k+1}, D^{*})&\leq & \|{x^{k+1}-x^{*}}\|^{2}\\ &\leq & \|{x^{k}-x^{*}}\|^{2}-M^{-2}(\mu^{-1}-\sigma)^{2}T^{2}\lambda^{-4}{{\rm{dist}}}^{4}(x^{k}, D^{*})\\ & = &{{\rm{dist}}}^{2}(x^{k}, D^{*})-M^{-2}(\mu^{-1}-\sigma)^{2}T^{2}\lambda^{-4}{{\rm{dist}}}^{4}(x^{k}, D^{*}). \end{eqnarray} $

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

$ {{\rm{dist}}}(x^{k}, D^{*})\leq \omega/(k+1)^{\frac{1}{2}}\nonumber. $

证毕.

本节给出数值实验,我们在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 $,其中

(5.1) $\begin{equation} \nonumber M = \left( \begin{array}{cccccc} 4&\; -2\; &&&&\\ 1&4&-2&&&\\ &1&4&\; -2\; &&\\ &&\cdot &\cdot &\cdot &\\ &&&&1&\; 4\\ \end{array} \right) , \qquad d = \left( \begin{array}{c} -1\\-1\\\cdots \\-1\\ \end{array} \right) . \end{equation}$

我们分别选取原点$ 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) $的定义如下

(5.2) $\begin{equation} \nonumber F(x) = \left( \begin{array}{c} 3x_{1}^{2}+2x_{1}x_{2}+2x_{2}^{2}+x_{3}+3x_{4}-6\\ 2x_{1}^{2}+x_{1}+x_{2}^{2}+10x_{3}+2x_{4}-2\\ 3x_{1}^{2}+x_{1}x_{2}+2x_{2}^{2}+2x_{3}+9x_{4}-9\\ x_{1}^{2}+3x_{2}^{2}+2x_{3}+3x_{4}-3\\ \end{array} \right) . \end{equation}$

我们分别选取不同的初始点,然后对算法$ 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 $适用于拟调单调变不等式是我们进一步需要探究的工作.