变分不等式问题$ (VIP) $是寻找$ x^*\in X $, 使得

(1.1) $ \begin{equation} \left<F(x^*), y-x^*\right>\geq0, \qquad\forall y \in X, \end{equation} $

其中$ {{\Bbb R}} ^n $是欧几里得空间, $ X $是$ {{\Bbb R}} ^n $中的一个非空闭凸子集, $ F $是$ {{\Bbb R}} ^n $到$ {{\Bbb R}} ^n $的一个连续映射.在$ {{\Bbb R}} ^n $上的内积和范数, 分别记为$ \left<\cdot, \cdot\right> $和$ \parallel\cdot\parallel $.本文中, 我们假设(1.1)式的解集$ S $非空.若映射$ F $是单调或者在Karamardia^[1]意义下是伪单调的, 则(1.1)式的解满足如下性质

(1.2) $ \begin{equation} \left<F(y), y-x^*\right>\geq0, \qquad\forall y \in X, x^* \in S. \end{equation} $

变分不等式作为非线性分析中的重要分支, 它在工程、交通、网络规划等领域广泛应用^[2-3].投影算法是解变分不等式的有效办法, 已被广泛研究, 见文献[4-9]. $ 1976 $年, Korpelevich^[2-10]首次提出外梯度投影算法. $ 1999 $年, 文献[11]提出二次投影算法.它们的共同特点是每步迭代计算两次投影, 外梯度算法的两次投影都是到集合$ X $上, 而二次投影算法的其中一次投影是到超平面与可行集合的交上.该超平面严格分离当前迭代点和变分不等式的解集.在$ 2006 $年, He在文献[12]中构造了与文献[11]不同的超平面, 并证明了该算法的有效性.在文献[13]中, 对文献[12]的算法进行了修正, 构造了这类二次投影算法的一种框架结构.

本文提出一类关于二次投影算法新的框架结构, 文献[13]中超平面方向为三个方向的非负组合, 本文算法中的超平面方向允许其中一个方向的系数为负数, 进而改进和推广了文献[13], 使得超平面的选取更加广泛.文献[13]中投影算法的收敛分析的证明方法并不能处理本文算法的收敛分析, 是一个全新的结果.

本文的内容安排如下.在第$ 2 $节中我们将给出本文证明所需用到的定义与基本结论, 在第$ 3 $节给出新的双投影算法, 在第$ 4 $节中将讨论算法的收敛性及收敛率, 第$ 5 $节给出数值实验及运算结果.

对任意$ z\in {{\Bbb R}} ^{n} $, 记$ \rm{dist} $$ { }(z, X): = \inf\limits_{x\in X}{\|{z-x}\|} $表示向量$ z $到$ X $的距离, $ z $在$ X $上的投影可以表示为$ P_X(z): = \arg\min{\left\{\|{y-z}\| | y\in X\right\}} $.任意$ {\mu >0} $, 记$ r_{\mu}(x) = x-P_{X}(x-\mu F(x)) $, 称$ r_{\mu}(x) $为自然残差函数.

下面是一些后面要用到的结论, 以引理的形式给出.其中引理2.1–2.3见文献[12], 引理2.4–2.5见文献[14].

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

$ \rm(1) \ \ $$ \left<F(y)-F(x), {y-x}\right> \geq 0 $, 则称$ F $在$ X $上是单调的;

$ \rm(2)\ \ $$ \left<{F(x)}, {y-x}\right>\geq 0\Rightarrow \left<{F(y)}, {y-x}\right> \geq 0 $, 则称$ F $在$ X $上是伪单调的.

注2.1  由单调和伪单调的定义可得, 单调必定是伪单调, 但伪单调不一定是单调.

定义2.2  映射$ F:X\subseteq {{\Bbb R}} ^n\rightarrow {{\Bbb R}} ^n $, 任意$ x, y\in X $, 若$ \|{F(x)-F(y)}\| \leq L\|{x-y}\| $, 则称$ F $在$ X $上是$ \rm{Lipschitz} $连续的, $ L>0 $是$ F $在$ X $上的$ \rm{Lipschitz} $系数.

引理2.1  对任意$ x\in X $, $ {\mu >0} $, 都有如下不等式成立

(2.1) $ \begin{equation} \left<F(x), r_{\mu}(x) \right>\geq\mu^{-1}\| {r_{\mu}(x)}\|^{2}. \end{equation} $

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

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

引理2.3  令$ X $是$ {{\Bbb R}} ^n $上的一个非空闭凸集, $ h(x) $是$ X $上的$ \rm{Lipschitz} $连续实函数, 其中设$ C = \left\{ {x\in X} \mid {h(x)} \leq 0 \right\} $.若$ h(x) $的$ \rm{Lipschitz} $系数$ \theta>0 $, 则对任意的$ {x\in X} $, 有$ \rm{dist} $$ (x, C)\geq{\theta^{-1}\max\{h(x), 0}\} $.

引理2.4  令$ X $是$ {{\Bbb R}} ^n $上的一个非空闭凸集, 若$ \bar{x} = P_X(x) $, 则对任意$ x\in {{\Bbb R}} ^n $, $ z\in X $有下列不等式成立

(2.3) $ \begin{equation} \left< {\bar{x}-x, z-\bar{x}} \right> \geq 0. \end{equation} $

引理2.5  $ x^* $$ \in $S当且仅当对任意的$ \mu > 0 $有$ r_{\mu}(x^*) = 0 $.

算法的具体内容如下.

算法3.1  选取初始点$ x_{0}\in X $, $ \sigma>0 $, $ {\mu}\in(0, \sigma^{-1}) $, $ \gamma \in (0, 1) $, $ a\geq {\frac{\mu^{2}}{1-\sigma \mu}} $, 令$ k = 0 $.

步骤1  计算$ r_{\mu}(x_k) = x_{k}-P_{X}(x_{k}-\mu F(x_{k})) $.如果$ r_{\mu}(x_{k}) = 0 $, 停止; 否则, 转到步骤2.

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

(3.1) $ \begin{equation} \left<{F(x_{k})-F(x_{k}-\gamma^{m} r_{\mu}(x_{k}))}, {r_{\mu}(x_{k})} \right> \leq \sigma \|{r_{\mu}(x_k)}\|^{2}. \end{equation} $

步骤3  计算$ x_{k+1} = P_{D_k}(x_{k}) $, 其中$ D_{k}: = { X\bigcap H_{k}} $, $ H_{k}: = \{\upsilon: h_{k}(v)\leq 0\} $以及函数

(3.2) $ \begin{equation} h_{k}(\upsilon): = \left<{aF(z_{k})+c_{k}r_{\mu}(x_{k})-{\mu}b_{k}F(x_{k})}, {\upsilon-x_{k}} \right> + \mu \eta_{k}\|{r_{\mu}(x_{k})}\|^{2}. \end{equation} $

其中$ 0\leq b_{k}\leq c_{k}\leq {\frac{a}{\mu}}\eta_{k} $.令$ k: = k+1 $, 返回步骤1.

现在说明步骤$ 2 $中(3.1)式的线性搜索是存在的.

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

$ \left<{F(x_{k})-F(x_{k}-\gamma^{m} r_{\mu}(x_{k}))}, {r_{\mu}(x_{k})}\right> \rightarrow0(m\rightarrow \infty). $

另一方面, $ r_{\mu}(x_{k}) $必定满足$ r_{\mu}(x_{k})>0 $, 否则在步骤$ 1 $中程序终止.因此, 对任意$ k\in N $, 都存在最小非负整数$ m $满足(3.1)式.

为了证明算法$ 3.1 $产生的序列$ \left\{x_k \right\} $收敛性, 先证明下面两个引理.

引理3.1  映射$ F $满足在$ {{\Bbb R}} ^n $上连续且满足条件(1.2), $ \left\{x_k \right\} $是算法$ 3.1 $中产生的序列, $ x^{*}\in S $, $ \mu >0 $, 则下列两个不等式成立

(i)   $ \left<{-\mu F(x_{k})}, {x^{*}-x_{k}}\right> \leq -\|{r_{\mu}(x_{k})}\|^{2}+\left<{r_{\mu}(x_{k})}, {x_{k}-x^{*}} \right>+\mu\left<{r_{\mu}(x_{k})}, {F(x_{k})} \right>; $

(ii)   $ \left<{r_{\mu}(x_{k})}, {x^{*}-x_{k}}\right> \leq \left<{r_{\mu}(x_{k})}, {\mu F(x_{k})-r_{\mu}(x_{k})} \right>. $

证  由于

$ r_{\mu}(x_k) = x_{k}-P_{X}(x_{k}-\mu F(x_{k})). $

因此

$ x_{k}-r_{\mu}(x_k) = P_{X}(x_{k}-\mu F(x_{k}). $

由引理$ 2.4 $可知, 对于任意的$ y\in X $成立

$ \left< {r_{\mu}(x_{k})-\mu F(x_{k})}, {y-x_{k}+r_{\mu}(x_{k})} \right> \leq 0. $

用$ x^{*} $代替上式中的$ y $, 我们可以得到

(3.3) $ \begin{equation} \left< {r_{\mu}(x_{k})-\mu F(x_{k})}, {x^{*}-x_{k}+r_{\mu}(x_{k})} \right> \leq 0. \end{equation} $

通过移项, 可得不等式(i).

由(3.3)式移项可得

$ \left< {r_{\mu}(x_{k})}, {x^{*}-x_{k}+r_{\mu}(x_{k})} \right> -\mu \left<{F(x_{k})}, {r_{\mu}(x_{k})}\right>\leq \mu \left<{F(x_{k})}, {x^*-x_{k}}\right>. $

又因为$ x_{k}\in X $和$ F $满足条件(1.2), 有

$ \mu \left<{F(x_{k})}, {x^*-x_{k}}\right>\leq 0. $

因此

$ \left< {r_{\mu}(x_{k})}, {x^{*}-x_{k}+r_{\mu}(x_{k})} \right> -\mu \left<{F(x_{k})}, {r_{\mu}(x_{k})}\right>\leq 0. $

通过移项, 不等式(ii)得证.证毕.

引理3.2  映射$ F $满足在$ {{\Bbb R}} ^n $上连续且满足条件(1.2), $ \left\{x_k \right\} $是算法$ 3.1 $中产生的无穷序列, $ x^{*}\in S $, 则有$ h_{k}(x^{*})\leq 0 $, $ h_{k}(x_{k}) = \mu \eta_{k}\|{r_{\mu}(x_{k})}\|^{2} $.

证  由(3.2)式可知$ h_{k}(x_{k}) = \mu \eta_{k}\|{r_{\mu}(x_{k})}\|^{2} $, 尤其当$ r_{\mu}(x_{k}) \neq 0 $时, 有$ h_{k}(x_{k})> 0. $

因为

(3.4) $ \begin{equation} \left< F(z_{k}), {x^{*}-x_{k}} \right> = \left< F(z_{k}), {x^{*}-z_{k}} \right>+\left< F(z_{k}), {z_{k}-x_{k}} \right>. \end{equation} $

又因为$ z_{k}\in X $和$ F $满足条件(1.2), 有

$ \left< F(z_{k}), {x^{*}-z_{k}} \right>\leq 0, $

所以(3.4)式化为

(3.5) $ \begin{equation} \left< F(z_{k}), {x^{*}-x_{k}} \right> \leq \left< F(z_{k}), {z_{k}-x_{k}} \right>. \end{equation} $

$ \begin{eqnarray*} h_{k}(x^{*})& = &\left<{aF(z_{k})+c_{k}r_{\mu}(x_{k})-{\mu}b_{k}F(x_{k})}, {x^{*}-x_{k}} \right> + \mu \eta_{k}\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber & = &a \left< F(z_{k}), {x^{*}-x_{k}} \right>+c_{k}\left<r_{\mu}(x_{k}), {x^{*}-x_{k}} \right>- \mu b_{k} \left<{F(x_{k})}, {x^{*}-x_{k}} \right>+\mu \eta_{k}\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber &\leq& a\left<{ F(z_{k}), z_{k}-x_{k}} \right> +c_{k}\left<r_{\mu}(x_{k}), {x^{*}-x_{k}} \right>- b_{k}\|{r_{\mu}(x_{k})}\|^{2}+b_{k}\left<r_{\mu}(x_{k}), {x_{k}-x^{*}} \right>\\\nonumber && + \mu b_{k}\left<r_{\mu}(x_{k}), F(x_{k}) \right>+\mu \eta_{k}\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber & = &-a\eta_{k}\left<{ F(z_{k}), r_{\mu}(x_{k})} \right>+(c_{k}-b_{k})\left<r_{\mu}(x_{k}), {x^{*}-x_{k}} \right>+\mu b_{k} \left<r_{\mu}(x_{k}), {F(x_{k})} \right>\\\nonumber &\quad& +(\mu \eta_{k}-b_{k})\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber &\leq &a \sigma \eta_{k}\|{r_{\mu}(x_{k})}\|^{2}-a\eta_{k}\left<F(x_{k}, r_{\mu}(x_{k})) \right>+(c_{k}-b_{k})\left<r_{\mu}(x_{k}), {x^{*}-x_{k}} \right>\\ &\quad &+\mu b_{k} \left<r_{\mu}(x_{k}), F(x_{k}) \right>+(\mu \eta_{k}-b_{k})\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber & = &(-a\eta_{k}+\mu b_{k})\left<r_{\mu}(x_{k}), F(x_{k}) \right>+(c_{k}-b_{k})\left<r_{\mu}(x_{k}), {x^{*}-x_{k}} \right>\\\nonumber &\quad& +(\mu \eta_{k}-b_{k}+a\eta_{k}\sigma)\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber &\leq &(-a\eta_{k}+\mu b_{k})\left<r_{\mu}(x_{k}), F(x_{k}) \right>+(c_{k}-b_{k})\left<r_{\mu}(x_{k}), {\mu F(x_{k})-r_{\mu}(x_{k})} \right>\\\nonumber &\quad &+(\mu \eta_{k}-b_{k}+a\eta_{k}\sigma)\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber & = &(-a\eta_{k}+\mu c_{k})\left<r_{\mu}(x_{k}), F(x_{k}) \right>+(\mu \eta_{k}-c_{k}+a\eta_{k}\sigma)\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber &\leq&(-a\eta_{k}+\mu c_{k}){\mu^{-1}}\|{r_{\mu}(x_{k})}\|^{2}+(\mu \eta_{k}-c_{k}+a\eta_{k}\sigma)\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber & = &(\frac{a(\sigma \mu-1)+{\mu}^{2}}{\mu})\eta_{k}\|{r_{\mu}(x_{k})}\|^{2}\\\nonumber &\leq&0, \end{eqnarray*} $

其中第一个不等式由(3.5)式和引理$ 3.1 $的(i)可得, 第三个等式由$ z_{k} = x_{k}-\eta_{k}r_{\mu}(x_{k}) $可得, 第二个不等式由(3.1)式可得, 第三个不等式由引理$ 3.1 $的(ii)可得, 第四个不等式由引理$ 2.1 $可得, 最后一个不等式由算法$ 3.1 $中$ a $的取值范围可得.证毕.

下面对算法$ 3.1 $产生的序列$ \left\{x_k \right\} $进行收敛性分析以及收敛率分析.

定理4.1  假设映射$ F $满足在$ {{\Bbb R}} ^n $上连续且满足条件(1.2), $ \{x_{k}\} $是由算法$ 3.1 $产生的无穷序列, 变分不等式的解集$ S $非空, 则$ \{x_{k}\} $收敛于$ VI(F, X) $的一个解.

证  设$ x^{*}\in S $是变分不等式的一个解.由引理$ 3.2 $知, $ x^{*}\in D_{k} $.又因为$ x_{k+1} = P_{D_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_{k}). \end{equation} $

由(4.1)式可知序列$ \{\|{x_{k}-x^{*}}\|^{2}\} $是递减序列, 因此$ \{\|{x_{k}-x^{*}}\|^{2}\} $为收敛序列, 并且$ \{x_{k}\} $有界.根据(4.1)式, 有

(4.2) $ \begin{equation} \lim\limits_{k\rightarrow\infty}{\rm dist}(x_{k}, D_{k}) = 0. \end{equation} $

因为$ F $的连续性, 所以$ r_{\mu}(x) $关于$ x $是连续的.由$ \{x_{k}\} $的有界性可知, $ \{r_{\mu}(x_{k})\} $, $ \{z_{k}\} $, $ \{F(x_{k})\} $, $ \{F(z_{k})\} $是有界序列.又因为$ \{b_{k}\} $, $ \{c_{k}\} $为有界数列, 则存在一个常数$ M>0 $, 使得

(4.3) $ \begin{equation} \|{aF(z_{k})+c_{k}r(x_{k})-{\mu}b_{k}F(x_{k})}\| \leq M, \forall k\in N. \end{equation} $

由此可得, 算法$ 3.1 $中定义的$ h_{k}(\upsilon) $在$ X $上是Lipschitz连续且$ M $为Lipschitz系数.由引理$ 2.3 $以及$ x_{k}\notin D_{k} $, 我们有

(4.4) $ \begin{equation} {\rm dist}(x_{k}, D_{k})\geq M^{-1}h_{k}(x_{k}), \forall k\in N.\\ \end{equation} $

由引理$ 3.2 $和上式表明

(4.5) $ \begin{equation} {\rm dist}(x_{k}, D_{k})\geq M^{-1}h_{k}(x_{k}) = \mu M^{-1}\eta_{k} \|{r_{\mu}(x_{k})}\|^{2}, \\ \end{equation} $

即

(4.6) $ \begin{equation} {\rm dist}^{2}(x_{k}, D_{k})\geq {\mu}^{2} M^{-2}{\eta_{k}}^{2} \|{r_{\mu}(x_{k})}\|^{4}.\\ \end{equation} $

由(4.2)和(4.6)式表明

(4.7) $ \begin{equation} \lim\limits_{k\rightarrow\infty}\eta_{k}\|{r_{\mu}(x_{k})}\|^{2} = 0. \end{equation} $

(Ⅰ)如果$ \mathop {\lim {\kern 1pt} \sup}\limits_{k \to \infty } \eta k > 0 $, 则必有$ \mathop {\lim {\kern 1pt} \inf}\limits_{k \to \infty }\|{r_{\mu}(x_{k})}\|^{2} = 0 $.由序列$ \{x_{k}\} $的有界性和$ r_{\mu}(x) $的连续性可知必存在$ \{x_{k}\} $的聚点$ \bar{x} $使得$ r_{\mu}(\bar{x}) = 0 $, 由引理$ 2.5 $可知$ \bar{x} $是$ VI(F, X) $的解.用$ \bar{x} $代替先前的$ x^{*} $可得序列$ \{\|{x_{k}-\bar{x}}\|^{2}\} $收敛.又因为$ \bar{x} $是$ \{x_{k}\} $的聚点, 因此整个序列$ \{\|{x_{k}-\bar{x}}\|^{2}\} $收敛于$ 0 $, 即$ \mathop {\lim }\limits_{k \to \infty } x_{k} = \bar{x} $.

(Ⅱ)如果$ \mathop {\lim {\kern 1pt} \sup}\limits_{k \to \infty }\eta_{k} = 0 $.令$ \bar{x} $是$ \{x_{k}\} $的聚点, 则存在子列$ \{x_{k_{j}}\} $收敛于$ \bar{x} $.由$ \eta_{k} $的选取可得

(4.8) $ \begin{eqnarray} \sigma\|{r_{\mu}(x_{k_{j}})}\|^{2}&<&\left<{F(x_{k_{j}})-F(x_{k_{j}}-\gamma^{k_{j}-1}r_{\mu}(x_{k_{j}}))}, {r_{\mu}(x_{k_{j}})}\right>{}\\ & = &\left<{F(x_{k_{j}})-F(x_{k_{j}}-{\gamma}^{-1}{\eta_{k_{j}}}r_{\mu}(x_{k_{j}}))}, {r_{\mu}(x_{k_{j}})}\right>{}\\ &\leq&\|{F(x_{k_{j}})-F(x_{k_{j}}-{\gamma}^{-1}{\eta_{k_{j}}}r_{\mu}(x_{k_{j}}))}\| \|{r_{\mu}(x_{k_{j}})}\|, \forall j\in N. \end{eqnarray} $

因为$ \{r_{\mu}(x_{k})\} $是有界, $ F $是连续的.令$ j\rightarrow\infty $, 则$ r_{\mu}(\bar{x}) = 0 $.运用$ (I) $中相同的证明可得$ \mathop {\lim }\limits_{k \to \infty } x_{k} = \bar{x} $.证毕.

定理4.2  在定理$ 4.1 $的条件下, 进一步假设$ F $是$ L $-Lipschitz连续的, $ L>0 $, 且存在常数$ c $, $ \delta>0 $, 使得当满足$ \|{r_{\mu}(x)}\| \leq\delta $时, 有

(4.9) $ \begin{equation} {\rm dist}(x, S)\leq c \|{r_{\mu}(x)}\|, \\ \end{equation} $

则存在常数$ \alpha >0 $, 使得对充分大的$ k $, 有

(4.10) $ \begin{equation} {\rm dist}(x_{k}, S)\leq {\frac{1}{\sqrt{\alpha k+{\rm dist}^{-2}(x_{0}, S)}}}. \end{equation} $

证  令$ \eta : = \min\left\{\frac{1}{2}, L^{-1}\gamma \sigma \right\} $.我们第一步证明$ \eta_{k}>\eta $对于所有的$ k $成立.根据$ \eta_{k} $的构造, 有$ \eta_{k} \in(0 , 1] $.如果$ \eta_{k} = 1 $, 那么明显有$ \eta_{k}>\frac{1}{2}\geq \eta $.现在我们假设$ \eta_{k}<1 $, 那么非负整数$ m_{k}\geq1 $.根据$ \eta_{k} $的构造, 我们有

(4.11) $ \begin{equation} \left<{F(x_{k})-F(x_{k}-\gamma^{-1}{\eta_{k}} r_{\mu}(x_{k}))}, {r_{\mu}(x_{k})} \right> > \sigma \|{r_{\mu}(x_k)}\|^{2}. \end{equation} $

由$ F $的Lipschitz连续性, 我们得到

$ \begin{eqnarray*} {\sigma}\|{r_{\mu}(x_k)}\|^{2}&< &\left<{F(x_{k})-F(x_{k}-\gamma^{-1}{\eta_{k}} r_{\mu}(x_{k}))}, {r_{\mu}(x_{k})} \right> \\\nonumber &\leq&\|{F(x_{k})-F(x_{k}-\gamma^{-1}{\eta_{k}} r_{\mu}(x_{k}))}\| \|{r_{\mu}(x_k)}\|\\\nonumber &\leq& L{\gamma}^{-1}{\eta_{k}}\|{r_{\mu}(x_k)}\|^{2}. \end{eqnarray*} $

因此$ {\eta_{k}}> L^{-1}\gamma \sigma\geq\eta $.

令$ x^{*}\in P_{S}(x_{k}) $.根据(4.1), (4.6)和(4.9)式可知, 对于充分大的$ k $, 有

$ \begin{eqnarray*} {\rm dist}^{2}(x_{k+1}, S)&\leq&\|{x_{k+1}-x^{*}}\|^{2}\\\nonumber &\leq&\|{x_{k}-x^{*}}\|^{2}-{\rm dist}^{2}(x_{k}, D_{k})\\\nonumber &\leq&\|{x_{k}-x^{*}}\|^{2}-{\mu^{2}} M^{-2}{\eta_{k}^{2}}\|{r_{\mu}(x_k)}\|^{4}\\\nonumber &\leq&\|{x_{k}-x^{*}}\|^{2}-{\mu^{2}} M^{-2}{\eta^{2}}\|{r_{\mu}(x_k)}\|^{4}\\\nonumber &\leq &{\rm dist}^{2}(x_{k}, S)-{\mu^{2}} M^{-2}{\eta^{2}}{c^{-4}}{\rm dist}^{4}(x_{k}, S).\nonumber \end{eqnarray*} $

记$ \alpha = {\mu^{2}} M^{-2}{\eta^{2}}{c^{-4}} $, 应用文献[15]中第二章节的引理$ 6 $, 可以得到

$ {\rm dist}(x_{k}, S)\leq {\rm dist}(x_{0}, S)/\sqrt{\alpha k {{\rm dist}^{2}(x_{0}}, S)+1} = 1/\sqrt{\alpha k+{{\rm dist}^{-2}(x_{0}, S)}}. $

定理4.2证毕.

这一部分给出算法的数值实验结果.我们在Windows 7, 处理器为Intel(R) Core(TM) 2 Quad CPU Q9500 @2.83GHz的系统环境下, 使用版本为R2014a的MATLAB进行数值实验.在计算过程中, 收敛标准是$ \|{r(x)}\|\leq 10^{-4} $.我们令算法$ 3.1 $中参数取为: $ \gamma = 0.8 $, $ \sigma = 2 $, $ \mu = 0.4 $, $ a = 1 $.我们令$ b_{k} = 0 $, $ c_{k} = \frac{1}{2}a\mu{\eta_{k}} $记为算法$ 3.1.1 $.令$ b_{k} = \frac{1}{4}a\mu{\eta_{k}} $, $ c_{k} = \frac{1}{2}a\mu{\eta_{k}} $记为算法$ 3.1.2 $.并将其与文献[11]的算法$ 2.2 $比较.文献[11]的算法$ 2.2 $参数取为: $ \gamma = 0.45 $, $ \sigma = 0.5 $.令$ x^{0} $代表初始点, nf表示计算$ F $的次数, iter表示程序迭代的次数, time代表程序运行所需的时间, $ x $表示最后一个迭代点.

例  本例子首先被文献[16]测试, 定义$ D = [0, 1]^{n} $, $ F(x) = Mx+d $, 有

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

我们选取原点$ x_{0} = (0, \cdots 0, 0) $和$ x_{0} = (1, \cdots 1, 1) $为初始点, 然后对算法$ 2.1 $和^[11]的算法$ 2.2 $进行测试, 得到数值结果分别如表 1和表 2所示.