本文研究一类特殊的变分不等式问题:寻找一点$ {u^ * } \in \Omega $, 使得

$ {\left( {u{\rm{ - }}{u^ * }} \right)^T}F\left( {{u^ * }} \right) \ge 0, \forall u \in \Omega, $

其中$ u = {\left( {x, y} \right)^T}, F\left( u \right) = {\left( {f\left( x \right), g\left( y \right)} \right)^T}, \Omega {\rm{ = }}\left\{ {\left( {x{\rm{, }}y} \right)\left| {x \in X{\rm{, }}} \right.{\rm{ }}y \in Y{\rm{, }}Ax{\rm{ + By}} \ge {\rm{b}}} \right\}. $将此类问题记作$ SMVI\left( {\Omega , F} \right), $这里$ X \subseteq {R^n} $和$ Y \subseteq {R^m} $为非空闭凸集, $ A \in {R^{l \times n}}, B \in {R^{l \times m}} $是矩阵, $ b \in {R^l} $是向量, $ f:X \to {R^n}, \; g:Y \to {R^m} $为单调映射, 并且以上各量均已给定.因为映射$ f $只取决于变量$ x $, 映射$ g $只取决于变量$ y $, 所以被称为是可分离带线性约束的变分不等式问题.这类问题被广泛应用于研究网络分析、交通运输、图论等领域.目前对于问题$ SMVI\left( {\Omega , F} \right) $的研究, 首先要在线性约束条件$ Ax{\rm{ + }}By{\rm{ = }}b $中引入拉格朗日乘子$ \lambda \in {R^l} $, 进而得到原$ SMVI\left( {\Omega , F} \right) $的等价形式如下:求$ {w^ * } \in Z $, 满足$ {\left( {w{\rm{ - }}{w^ * }} \right)^T}Q\left( {{w^ * }} \right) \ge 0{\rm{, }}\; w \in Z, $其中$ w = {\left( {x, y, \lambda } \right)^T}, Q\left( w \right) = {\left( {f\left( x \right) - {A^T}\lambda , g\left( y \right) - {B^T}\lambda , Ax + By - b} \right)^T}, Z{\rm{ = }}X \times Y \times {R^l} $.接着再对该等价形式进行求解.

交替方向法(ADM)是用来求解原问题$ SMVI\left( {\Omega , F} \right) $最经典的算法.一直以来, 如何快速求解两个子变分不等式问题成了考查ADM有效性的关键, 为此很多学者作了大量工作, 对ADM进行了相应的改进^[1-5].虽然提出的各种改进策略在一定程度上有效提高了ADM的计算速度, 但需要注意的是, 此类改进的方法并没有完全避免求解子变分不等式问题.因为从计算角度上看, 在大部分情况下, 直接求解变分不等式并不是件容易的事情.为了能更好的提出新混合算法, 接下来我们介绍对数二次临近点法.对数二次临近点算法(LQP)^[6-11]主要用于求解如下这样一类变分不等式问题, 即找一点$ {u^ * } \in \Omega $, 满足$ {\left( {u - {u^ * }} \right)^T}F\left( {{u^ * }} \right) \ge 0, \forall u \in \Omega $, 其中$ u = {\left( {x, y} \right)^T}, F\left( u \right) = {\left( {f\left( x \right) + Ay, - {A^T} + b} \right)^T}, \Omega = R_ + ^n \times Y $这里矩阵$ A \in {R^{m \times n}} $, 向量$ b \in {R^m}, $ $ Y $为$ {R^m} $中的闭凸子集, $ f:{R^n} \to {R^n} $是连续单调映射. LQP在每次迭代时只需解决这样一个非线性方程组

$ {\beta _k}\left( {f\left( x \right) + Ay} \right) + x - \left( {1 - \mu } \right){x^k} - \mu {X^k}{x^{ - 1}} = 0. $

一般而言, 求解一个非线性方程组比一个变分不等式组更容易操作.尽管此方法是对子问题进行非精确求解, 但是相对于精确求解子问题, 非精确求解更可行、快速.因为从数值计算角度分析, 精确求解一个子问题往往不太容易实现.考虑到这个方法求解较容易的特点, LQP方法值得关注和借鉴.基于上面的考虑, 本文提出了一种新的混合算法.此算法在预测步只需求解一系列相关联的非线性方程组, 而不是去处理一系列的子变分不等式问题.同时这样做还可以在可行集中产生一个内点序列, 在一定程度上提高了算法的有效性和可行性:在修正步中, 修正值是由当前预测点和一个投影算子构成的凸组合得到的.这样保证了如果前一个迭代点是内点, 那么这样一个凸组合得到的下一个迭代点也将会是内点.另一方面需要注意的是, 当可行集为简单集时, 投影算子更容易执行.

本文结构如下:第2节主要概述了本文所需要的预备知识, 参见文献[12-15]; 第3节在映射单调和原变分不等式解集非空的条件下提出一种新的混合算法, 并给出算法的一些性质, 相关证明技巧参见文献[16-21]; 第4节和第5节分析了新算法的收缩性及全局收敛性, 参见文献[22-26]; 第6节利用数值算例验证了算法的有效性.

用$ \left\| x \right\| = \sqrt {{x^T}x} $表示2 -范数, $ {\left\| u \right\|_G} $表示向量的$ G $ -范数, 记为$ {\left\| u \right\|_G} = \sqrt {{u^T}Gu} $, 其中$ G $为给定的对称正定矩阵.

令$ {P_\Omega }( \cdot ) $为$ {R^n} $到$ \Omega $上的投影映射, 即$ {P_\Omega }\left( x \right) = \arg \min \left\{ {\left\| {y - x} \right\|\left| {y \in \Omega } \right.} \right\} $.投影映射有如下重要性质.

引理 1 ^[6] 若$ \Omega\subseteq R^n $为一非空闭凸子集, $ P_\Omega(\cdot) $为$ R^n $到$ \Omega $上的投影映射, 对于任意的$ x, y \in {R^n} $, 任意$ z \in \Omega $, 有

$ \begin{eqnarray} &&{\left( {x - {P_\Omega }\left( x \right)} \right)^T}\left( {z - {P_\Omega }\left( x \right)} \right) \le 0, \end{eqnarray} $

(2.1)

$ \begin{eqnarray} &&\left\| {{P_\Omega }\left( x \right) - {P_\Omega }\left( y \right)} \right\| \le \left\| {x - y} \right\|. \end{eqnarray} $

(2.2)

定义 1 集合$ \Omega \subseteq {R^n} $, 设$ f $是$ \Omega \to {R^n} $的映射, 如果$ f $满足$ {\left( {x - y} \right)^T}\left( {f\left( x \right) - f\left( y \right)} \right) \ge 0, $ $ \forall x, y \in \Omega, $则称$ f $在$ \Omega $上是单调的.若不等号严格成立, 则称$ f $在$ \Omega $上是严格单调的.

以下给出新的LQP-ADM ^[11-24]混合算法用于求解可分离带线性约束的变分不等式问题的步骤, 然后给出此算法的一些性质.算法的步骤如下.

步 0  令$ \varepsilon {\rm{ > }}0 $, $ {\mu _1}, {\mu _2} \in \left( {0{\rm{, }}1} \right) $, $ t \in \left( {0{\rm{, }}1} \right) $, $ k{\rm{ = }}0 $, $ {w^0}{\rm{ = }}\left( {{x^0}{\rm{, }}{y^0}{\rm{, }}{\lambda ^0}} \right) \in X \times Y \times {R^l} $, H为一给定的$ l \times l $阶对称正定矩阵, $ X \subseteq {R^n} $和$ Y \subseteq {R^m} $为非空闭凸集, $ A \in {R^{l \times n}}, B \in {R^{l \times m}} $是矩阵, $ b \in {R^l} $是向量, $ f:X \to {R^n} $, $ g:Y \to {R^n} $为单调映射.

步 1(预测步)  计算预测值$ \tilde w = \left( {\tilde x, \tilde y, \tilde \lambda } \right). $

步 1.1  通过代入点$ \left( {{x^k}{\rm{, }}{y^k}{\rm{, }}{\lambda ^k}} \right) $求解下面的非线性方程得到$ {\tilde x^k} $,

$ \begin{eqnarray} f\left( {{{\tilde x}^k}} \right) - {A^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right] + {\tilde x^k} - \left( {1 - {\mu _1}} \right){x^k} - {\mu _1}X_k^2{\left( {{{\tilde x}^k}} \right)^{ - 1}} = 0. \end{eqnarray} $

(3.1)

这里设$ ({\tilde x^k}) = ({m_1}, {m_2}, \cdots , {m_n}), {x^k} = \{ {w_1}, {w_2}, \cdots , {w_n}\}, $则

$ {({\tilde x^k})^{ - 1}} = (\frac{1}{{{m_1}}}, \frac{1}{{{m_2}}}, \cdots, \frac{1}{{{m_n}}}), X_k^2 = {\rm diag}\{ w_1^2, w_2^2, \cdots , w_n^2\}. $

下面的符号类似.

步 1.2  通过带入点$ \left( {{{\tilde x}^k}{\rm{, }}{y^k}{\rm{, }}{\lambda ^k}} \right) $求解下面的非线性方程得到$ {\tilde y^k} $.

$ \begin{eqnarray} g\left( {{{\tilde y}^k}} \right) - {B^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right] + {\tilde y^k} - \left( {1 - {\mu _2}} \right){y^k} - {\mu _2}Y_k^2{\left( {{{\tilde y}^k}} \right)^{ - 1}} = 0. \end{eqnarray} $

(3.2)

步 1.3

$ \begin{eqnarray} {\tilde \lambda ^k} = {\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right). \end{eqnarray} $

(3.3)

步 2  如果$ \max \left\{ {\left\| {{{\tilde w}^k} - {w^k}} \right\|, {\rm{ }}\left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|} \right\} < \varepsilon $, 则停止.否则转到步3.

步 3  计算步长

$ {\alpha _k} = \frac{{{{\left( {{{\tilde w}^k} - {w^k}} \right)}^T}Q\left( {{{\tilde w}^k}} \right)}}{{{{\left\| {Q\left( {{{\tilde w}^k}} \right)} \right\|}^2}}}. $

步 4(修正步)  计算下一个迭代点$ {w^{k{\rm{ + }}1}}{\rm{ = }}\left( {{x^{k{\rm{ + }}1}}{\rm{, }}\; {y^{k{\rm{ + }}1}}{\rm{, }}\; {\lambda ^{k{\rm{ + }}1}}} \right), $

$ \begin{eqnarray} {w^{k{\rm{ + }}1}}{\rm{ = }}\left( {1{\rm{ - }}t} \right){w^k}{\rm{ + }}t\left\{ {{w^k}{\rm{ - }}{\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\}. \end{eqnarray} $

(3.4)

步 5  如果$ \max \left\{ {\left\| {{w^{k + 1}} - {{\tilde w}^k}} \right\|, {\rm{ }}\left\| {A{x^{k + 1}} + B{y^{k + 1}} - b} \right\|} \right\} < \varepsilon $, 则停止.否则令$ k: = k+1 $转到步1.

观察新算法的预测步可知, 此算法的主要任务是解下面两个非线性方程的近似解:带入点$ \left( {{x^k}, {y^k}, {\lambda ^k}} \right) $求解$ x $,

$ \begin{eqnarray} f\left( x \right) - {A^T}\left[ {{\lambda ^k} - H\left( {Ax + B{y^k} - b} \right)} \right] + x - \left( {1 - {\mu _1}} \right){x^k} - {\mu _1}X_k^2{x^{ - 1}} = 0. \end{eqnarray} $

(3.5)

带入点$ \left( {{x^{k + 1}}, {y^k}, {\lambda ^k}} \right) $求解$ y $,

$ \begin{eqnarray} g\left( y \right) - {B^T}\left[ {{\lambda ^k} - H\left( {A{x^{k + 1}} + B{y^k} - b} \right)} \right] + y - \left( {1 - {\mu _2}} \right){y^k} - {\mu _2}Y_k^2{y^{ - 1}} = 0. \end{eqnarray} $

(3.6)

比较(3.5), (3.6)两式的共同点就相当于求解如下方程的近似解

$ \begin{eqnarray} q\left( u \right) + u - \left( {1 - \mu } \right){u^k} - \mu U_k^2{u^{ - 1}} = 0, \end{eqnarray} $

(3.7)

其中$ {u^k} = ({m_1}, {m_2}, \cdots , {m_n}), u = ({w_1}, {w_2}, \cdots, {w_n}) $,

$ U_k^2 = {\rm diag}\left( {m_1^2, m_2^2, \cdots , m_n^2} \right), {u^{ - 1}} = (\frac{1}{{{w_1}}}, \frac{1}{{{w_2}}}, \cdots , \frac{1}{{{w_n}}}). $

引理 2 ^[6] 如果$ q\left( u \right) $为$ {R^n} $上的单调映射, 则对于给定的$ {u^k} \in R_ + ^n $, 方程(3.7)存在唯一的$ u \in R_ + ^n $.

因为$ \left( x \right), g\left( y \right) $分别是关于$ x $和$ y $的单调映射, 所以由此性质可知非线性方程(3.5)和(3.6)都有唯一的解.

引理 3  对给定的$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in R_ + ^n \times R_ + ^m \times {R^l} $和$ q = \left( {{q_x}, {q_y}, q{}_\lambda } \right) \in {R^n} \times {R^m} \times {R^l} $, 若$ w = \left( {x, y, \lambda } \right) $是如下方程组的解:

$ \begin{eqnarray} \left\{ {\begin{array}{*{20}{c}} {{q_x} + x - \left( {1 - {\mu _1}} \right){x^k} - {\mu _1}X_k^2{x^{ - 1}} = 0}, \\ {{q_y} + y - \left( {1 - {\mu _2}} \right){y^k} - {\mu _2}Y_k^2{y^{ - 1}} = 0}, \\ {{q_\lambda } + \gamma \lambda - \gamma {\lambda ^k} = 0}, \end{array}} \right. \end{eqnarray} $

(3.8)

则对任意$ v \ge 0 $, 有下面不等式成立:

$ \begin{eqnarray} {\left( {v - w} \right)^T}q &\ge& \frac{1}{2}\left( {\left\| {w - v} \right\|_G^2 - \left\| {{w^k} - v} \right\|_G^2} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{x^k} - x} \right\|^2} \\ &&+ \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - y} \right\|^2} + \frac{\gamma }{2}{\left\| {{\lambda ^k} - \lambda } \right\|^2}, \end{eqnarray} $

(3.9)

其中

$ G = \left( {\begin{array}{*{20}{c}} {\left( {1 + {\mu _1}} \right){I_n}}&{}&{}\\ {}&{\left( {1 + {\mu _2}} \right){I_m}}&{}\\ {}&{}&{\gamma {I_l}} \end{array}} \right). $

证  令$ v = \left( {{v_x}, {v_y}, {v_\lambda }} \right) $, 则(3.8)式证明包括下面三个不等式的证明:

$ \begin{eqnarray} &&{\left( {{v_x} - x} \right)^T}{q_x} \ge \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {x - {v_x}} \right\|}^2} - {{\left\| {{x^k} - {v_x}} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{x^k} - x} \right\|^2}, \end{eqnarray} $

(3.10)

$ \begin{eqnarray} &&{\left( {{v_y} - y} \right)^T}{q_y} \ge \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {y - {v_y}} \right\|}^2} - {{\left\| {{y^k} - {v_y}} \right\|}^2}} \right) + \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - y} \right\|^2}, \end{eqnarray} $

(3.11)

$ \begin{eqnarray} &&{\left( {{v_\lambda } - \lambda } \right)^T}{q_\lambda } = \frac{\gamma }{2}\left( {{{\left\| {\lambda - {v_\lambda }} \right\|}^2} - {{\left\| {{\lambda ^k} - {v_\lambda }} \right\|}^2}} \right) + \frac{\gamma }{2}\left\| {{\lambda ^k} - \lambda } \right\|. \end{eqnarray} $

(3.12)

不失一般性, 可以将不等式(3.10)中的$ x, {x^k}, {q_x}, {v_x} $简化为实数.因为$ x > 0, {\rm{ }}{x^k} > 0, {\rm{ }}{v_x} > 0 $, 故有$ {v_x}{\left( {{x^k}} \right)^2}/x \ge {v_x}\left( {2{x^k} - x} \right). $结合方程组(3.8)有

$ \begin{eqnarray*} \left( {{v_x} - x} \right){q_x} & = & \left( {x - {v_x}} \right)\left( {x - \left( {1 - {\mu _1}} \right){x^k} - {\mu _1}{{{{\left( {{x^k}} \right)}^2}}/x}} \right)\\{\rm{ }} &\ge& {\left( x \right)^2} - \left( {1 - {\mu _1}} \right)x{x^k} - {\mu _1}{\left( {{x^k}} \right)^2} - x{v_x} + \left( {1 - {\mu _1}} \right){x^k}{v_x} + {\mu _1}{v_x}\left( {2{x^k} - x} \right)\\ & = &{\left( x \right)^2} - \left( {1 - {\mu _1}} \right)x{x^k} - {\mu _1}{\left( {{x^k}} \right)^2} - \left( {1 + {\mu _1}} \right)x{v_x} + \left( {1 + {\mu _1}} \right){x^k}{v_x}\\ &{\rm{ }} = & \frac{{1 + {\mu _1}}}{2}\left( {{{\left( {x - {v_x}} \right)}^2} - {{\left( {{x^k} - {v_x}} \right)}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left( {{x^k} - x} \right)^2}, \end{eqnarray*} $

则(3.10)式得证.同理可证得(3.11)式也是成立的.下面来证明(3.12)式, 由方程组(3.8)可得

$ \begin{eqnarray*} {\left( {{v_\lambda } - \lambda } \right)^T}{q_\lambda } & = & \gamma {\left( {{v_\lambda } - \lambda } \right)^T}\left( {{\lambda ^k} - \lambda } \right)\\ &{\rm{ = }}&\gamma \left( {v_\lambda ^T{\lambda ^k} - v_\lambda ^T\lambda - {\lambda ^T}\lambda + {{\left\| \lambda \right\|}^2}} \right)\\ &{\rm{ = }}&\frac{\gamma }{2}\left( {{{\left\| {\lambda - {v_\lambda }} \right\|}^2} - {{\left\| {{\lambda ^k} - {v_\lambda }} \right\|}^2}} \right) + \frac{\gamma }{2}{\left\| {{\lambda ^k} - \lambda } \right\|^2}, \end{eqnarray*} $

则(3.12)式得证.综上所述, 要证的不等式成立.证毕.

下面给出一个引理来解释算法中的停机准则.

引理 4  如果$ A{\tilde x^k} + B{y^k} - b = 0 $, $ {\tilde x^k} = {x^k} $, $ {\tilde y^k} = {y^k} $, 则$ \left( {{x^k}, {y^k}, {\lambda ^k}} \right) $是$ SMVI\left( {\Omega , F} \right) $的解.

证  由$ A{\tilde x^k} + B{y^k} - b = 0 $与$ {\tilde y^k} = {y^k} $可得$ A{\tilde x^k} + B{\tilde y^k} - b = 0. $由式(3.3)得$ {\tilde \lambda ^k} = {\lambda ^k}. $由(3.5)式, $ A{\tilde x^k} + B{y^k} - b = 0 $以及$ {\tilde x^k} = {x^k} $可知$ f\left( {{{\tilde x}^k}} \right) - {A^T}{\lambda ^k} = 0. $由此可得

$ {\left( {x' - {{\tilde x}^k}} \right)^T}\left( {f\left( {{{\tilde x}^k}} \right) - {A^T}{\lambda ^k}} \right) = 0, \forall x' \in X, $

同理可得

$ {\left( {y' - {{\tilde y}^k}} \right)^T}\left( {g\left( {{{\tilde y}^k}} \right) - {B^T}{\lambda ^k}} \right) = 0, \forall {y^\prime } \in Y. $

所以$ \left( {{x^k}, {y^k}, {\lambda ^k}} \right) $满足问题$ SMVI\left( {\Omega , F} \right) $中所有条件.由此说明$ \left( {{x^k}, {y^k}, {\lambda ^k}} \right) $是问题$ SMVI( \Omega, $ $ F) $的一个解.

本节准备给出任取$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) \in {W^ * } $, 由上面的LQP-ADM混合算法得到的序列$ \left\{ {{w^k}} \right\} $满足

$ \begin{eqnarray*} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 &\le& \left\| {{w^k} - {w^ * }} \right\|_R^2 - t{\alpha _k}\left[ {\left( {1 - {\alpha _k}} \right)\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2 + \left( {1 - {\mu _1}} \right){{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2}} \right.\\ &&+ \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2}\left. { + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right], \end{eqnarray*} $

其中$ R, H $为固定的正定矩阵, $ {\left\| u \right\|_R} = \sqrt {{u^T}Ru} , {\left\| u \right\|_H} = \sqrt {{u^T}Hu} $并且给出相应的分析.为了证明此结论, 需分别从新算法的预测步和修正步进行分析.

我们先来探讨提出的LQP-ADM混合算法的预测步.

引理 5  给定$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in X \times Y \times {R^l} $, 将其代入算法步1中产生预测值$ \tilde w = \left( {\tilde x, \tilde y, \tilde \lambda } \right) $.若$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) $是$ SMVI\left( {\Omega , F} \right) $的解, 则有

$ \begin{eqnarray} &&{\left( {{\lambda ^k} - {\lambda ^ * }} \right)^T}\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)\\ &\ge& \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{x^k} - {{\tilde x}^k}} \right\|^2}\\ &&+ \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _2}}}{2}\left\| {{y^k} - {{\tilde y}^k}} \right\|\\ &&{\rm{ + }}\left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2 - {\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right). \end{eqnarray} $

(4.1)

证  因为$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) $是$ SMVI\left( {\Omega , F} \right) $的解, 所以

$ \begin{eqnarray*} &&{\left( {x' - {x^ * }} \right)^T}\left( {f\left( {{x^ * }} \right) - {A^T}{\lambda ^ * }} \right) \ge 0, \forall x' \in X, \\ &&{\left( {y' - {y^ * }} \right)^T}\left( {g\left( {{y^ * }} \right) - {B^T}{\lambda ^ * }} \right) \ge 0, \forall y' \in Y, \end{eqnarray*} $

以及$ A{x^ * } + B{y^ * } = b $在上面的两个不等式中, 分别令$ x' = {\tilde x^k}, y' = {\tilde y^k} $, 则

$ \begin{eqnarray} {\left( {{{\tilde x}^k} - {x^ * }} \right)^T}\left( {f\left( {{x^ * }} \right) - {A^T}{\lambda ^ * }} \right) \ge 0, \end{eqnarray} $

(4.2)

$ \begin{eqnarray} {\left( {{{\tilde y}^k} - {y^ * }} \right)^T}\left( {g\left( {{y^ * }} \right) - {B^T}{\lambda ^ * }} \right) \ge 0. \end{eqnarray} $

(4.3)

另一方面, 因为(3.5)式及下面的恒等变形

$ \begin{eqnarray*} &&{\rm{ }}f\left( {{{\tilde x}^k}} \right) - {A^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{y^k} - b} \right)} \right]\\ & = & f\left( {{{\tilde x}^k}} \right) - {A^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) + H\left( {B{{\tilde y}^k} - B{y^k}} \right)} \right], \end{eqnarray*} $

所以根据引理3可得

$ \begin{eqnarray} &&{\left( {{x^ * } - {{\tilde x}^k}} \right)^T}\left\{ {f\left( {{{\tilde x}^k}} \right) - {A^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) + H\left( {B{{\tilde y}^k} - B{y^k}} \right)} \right]} \right\}\\ &\ge& \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{{\tilde x}^k} - {x^k}} \right\|^2}. \end{eqnarray} $

(4.4)

将(4.2)式与(4.4)式相加

$ \begin{align*} &{\left( {{{\tilde x}^k} - {x^ * }} \right)^T}\left\{ {f\left( {{x^ * }} \right) - f\left( {{{\tilde x}^k}} \right) + {A^T}\left( {{\lambda ^k} - {\lambda ^ * }} \right) - {A^T}H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) + {A^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right)} \right\}\; \; \\ \ge& \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{{\tilde x}^k} - {x^k}} \right\|^2}, \end{align*} $

又因为$ f\left( x \right) $是单调映射, 则

$ \begin{eqnarray*} &&{\left( {{{\tilde x}^k} - {x^ * }} \right)^T}\left\{ {{A^T}\left( {{\lambda ^k} - {\lambda ^ * }} \right) - {A^T}H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) + {A^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right)} \right\}\\ &\ge& \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{{\tilde x}^k} - {x^k}} \right\|^2}, \end{eqnarray*} $

即

$ \begin{eqnarray} &&{\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}\left\{ {\left( {{\lambda ^k} - {\lambda ^ * }} \right) - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) + H\left( {B{{\tilde y}^k} - B{y^k}} \right)} \right\}\\ &\ge& \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{{\tilde x}^k} - {x^k}} \right\|^2}. \end{eqnarray} $

(4.5)

同样由(3.2)式及引理3可得

$ \begin{eqnarray} &&{\left( {{y^ * } - {{\tilde y}^k}} \right)^T}\left\{ {g\left( {{{\tilde y}^k}} \right) - {B^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right]} \right\}\\ &\ge& \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - {{\tilde y}^k}} \right\|^2}. \end{eqnarray} $

(4.6)

将(4.3)与(4.6)式相加有

$ \begin{eqnarray*} &&{\left( {{{\tilde y}^k} - {y^ * }} \right)^T}\left\{ {g\left( {{y^ * }} \right) - g\left( {{{\tilde y}^k}} \right) + {B^T}\left( {{\lambda ^k} - {\lambda ^ * }} \right) - {B^T}H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right\}\\ &\ge& \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - {{\tilde y}^k}} \right\|^2}. \end{eqnarray*} $

又因为$ g $是关于$ y $单调的, 则

$ \begin{eqnarray*} &&{\rm{ }}{\left( {{{\tilde y}^k} - {y^ * }} \right)^T}\left\{ {{B^T}\left( {{\lambda ^k} - {\lambda ^ * }} \right) - {B^T}H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right\}\\ & \ge& \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - {{\tilde y}^k}} \right\|^2}, \end{eqnarray*} $

则

$ \begin{eqnarray} &&{\rm{ }}{\left( {B{{\tilde y}^k} - B{y^ * }} \right)^T}\left\{ {\left( {{\lambda ^k} - {\lambda ^ * }} \right) - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right\}\\ &\ge& \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - {{\tilde y}^k}} \right\|^2}. \end{eqnarray} $

(4.7)

将(4.5)与(4.7)式相加有

$ \begin{eqnarray*} &&{\left( {{\lambda ^k} - {\lambda ^ * }} \right)^T}\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) - \left\| {A{{\tilde x}^k}{\rm{ + }}B{{\tilde y}^k} - b} \right\|_H^2 + {\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right)\\ &\ge& \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} \\ &&+\frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right)+ \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} \end{eqnarray*} $

得证.

进一步, 若将(3.3)式变形为$ A{\tilde x^k} + B{\tilde y^k} - b = {H^{ - 1}}\left( {{\lambda ^k} - {{\tilde \lambda }^k}} \right), $进而有

$ \begin{eqnarray} &&{\left( {{\lambda ^k} - {\lambda ^ * }} \right)^T}\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right) = {\left( {{\lambda ^k} - {\lambda ^ * }} \right)^T}{H^{ - 1}}\left( {{\lambda ^k} - {{\tilde \lambda }^k}} \right)\\ & = &\frac{1}{2}\left[ {\left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right] + \frac{1}{2}\left\| {{{\tilde \lambda }^k} - {\lambda ^k}} \right\|_{{H^{ - 1}}}^2\\& = &\frac{1}{2}\left[ {\left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right] + \frac{1}{2}\left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2. \end{eqnarray} $

(4.8)

于是如果考虑(4.8)式, 则可得到如下引理.

引理 6  给定$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in X \times Y \times {R^l} $, 将其代入算法步1中产生预测值$ \tilde w = \left( {\tilde x, \tilde y, \tilde \lambda } \right) $.若$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) $是$ SMVI\left( {\Omega , F} \right) $的解, 则有

$ \begin{eqnarray*} &&\left( {1 + {\mu _1}} \right)\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \left( {1 + {\mu _2}} \right)\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right)\\ &&{\rm{ }} + \left( {\left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right)\\ &\le& - \left( {1 - {\mu _1}} \right){\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2\\ &&{\rm{ }} + 2{\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right). \end{eqnarray*} $

证  将(4.8)式代入引理5中有

$ \begin{eqnarray*} &&\frac{1}{2}\left[ {\left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right] + \frac{1}{2}\left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2\\ &\ge& \frac{{1{\rm{ + }}{\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} \\ && + \frac{{1 + {\mu _2}}}{2}\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right)+ \frac{{1 - {\mu _2}}}{2}{\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} \\ &&+ \left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2 - {\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right), \end{eqnarray*} $

即

$ \begin{eqnarray*} &&\left( {1 + {\mu _1}} \right)\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \left( {1 + {\mu _2}} \right)\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right)\\ &&+ \left( {\left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right)\\ &\le & - \left( {1 - {\mu _1}} \right){\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2\\ &&+ 2{\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right). \end{eqnarray*} $

证毕.

由上面的引理可得到关于LQP-ADM混合算法预测步的定理如下.

定理 1  给定$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in X \times Y \times {R^l} $, 将其代入算法步1中产生预测值$ \tilde w = \left( {\tilde x, \tilde y, \tilde \lambda } \right) $.若$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) $是$ SMVI\left( {\Omega , F} \right) $的解, 则有

$ \begin{eqnarray*} &&\left\| {{{\tilde w}^k} - {w^ * }} \right\|_R^2\\ & \le& \left\| {{w^k} - {w^ * }} \right\|_R^2 - \left( {1 - {\mu _1}} \right){\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2, \end{eqnarray*} $

其中

$ R = \left( {\begin{array}{*{20}{c}} {\left( {1 + {\mu _1}} \right){I_m}}&{}&{}\\ {}&{\left( {1 + {\mu _2}} \right){I_n} + {B^T}HB}&{}\\ {}&{}&{{H^{ - 1}}} \end{array}} \right). $

证  由引理6可知

$ \begin{eqnarray} &&\left( {1 + {\mu _1}} \right)\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \left( {1 + {\mu _2}} \right)\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right)\\ &&{\rm{ }} + \left( {\left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right)\\ &\le& - \left( {1 - {\mu _1}} \right){\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2\\ &&+ 2{\left( {A{{\tilde x}^k} - A{x^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right), \end{eqnarray} $

(4.9)

同时有

$ \left\| {B{{\tilde y}^k} - B{y^ * }} \right\|_H^2 - \left\| {B{y^k} - B{y^ * }} \right\|_H^2 + \left\| {B{y^k} - B{{\tilde y}^k}} \right\|_H^2 = 2{\left( {B{{\tilde y}^k} - B{y^ * }} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right). $

将(4.9)式与此恒等式相加可得

$ \begin{eqnarray*} &&\left( {1 + {\mu _1}} \right)\left( {{{\left\| {{{\tilde x}^k} - {x^ * }} \right\|}^2} - {{\left\| {{x^k} - {x^ * }} \right\|}^2}} \right) + \left( {1 + {\mu _2}} \right)\left( {{{\left\| {{{\tilde y}^k} - {y^ * }} \right\|}^2} - {{\left\| {{y^k} - {y^ * }} \right\|}^2}} \right)\\ &&+ \left( {\left\| {{{\tilde \lambda }^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2 - \left\| {{\lambda ^k} - {\lambda ^ * }} \right\|_{{H^{ - 1}}}^2} \right) + \left( {\left\| {B{{\tilde y}^k} - B{y^ * }} \right\|_H^2 - \left\| {B{y^k} - B{y^ * }} \right\|_H^2} \right)\\ & \le& - \left( {1 - {\mu _1}} \right){\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right\|_H^2\\ &&+ 2{\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)^T}H\left( {B{{\tilde y}^k} - B{y^k}} \right) - \left\| {B{y^k} - B{{\tilde y}^k}} \right\|_H^2\\ & = & - \left( {1 - {\mu _1}} \right){\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{{\tilde y}^k} - b - B{{\tilde y}^k} + B{y^k}} \right\|_H^2\\ & = & - \left( {1 - {\mu _1}} \right){\left\| {{x^k} - {{\tilde x}^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{y^k} - {{\tilde y}^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2, \end{eqnarray*} $

于是

$ \begin{eqnarray*} &&\left\| {{{\tilde w}^k} - {w^ * }} \right\|_R^2 \\ &\le& \left\| {{w^k} - {w^ * }} \right\|_R^2 - \left( {1 - {\mu _1}} \right){\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2 \end{eqnarray*} $

得证.

将定理1的结论作简单变形可得到以下推论.

推论 1  若已知$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in X \times Y \times {R^l} $以及其产生的预测值$ \tilde w = \left( {\tilde x, \tilde y, \tilde \lambda } \right) $, 对于$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) \in {\Omega ^ * } $, 有

$ \begin{eqnarray} 2{\left( {{w^k} - {w^ * }} \right)^T}R\left( {{w^k} - {{\tilde w}^k}} \right) &\ge& \left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2 + \left( {1 - {\mu _1}} \right){\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} + \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2}\\ &&{\rm{ + }}\left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2. \end{eqnarray} $

(4.10)

证  由定理1可得

$ \begin{eqnarray*} &&\left\| {{w^k} - {w^ * }} \right\|_R^2 - \left\| {{{\tilde w}^k} - {w^ * }} \right\|_R^2 = \left\| {{w^k} - {w^ * }} \right\|_R^2 - \left\| {\left( {{w^k} - {w^ * }} \right) - \left( {{w^k} - {{\tilde w}^k}} \right)} \right\|_R^2\\ &\ge& \left( {1 - {\mu _1}} \right){\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} + \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2} + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2. \end{eqnarray*} $

于是

$ \begin{eqnarray*} 2{\left( {{w^k} - {w^ * }} \right)^T}R\left( {{w^k} - {{\tilde w}^k}} \right) - \left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2 &\ge& \left( {1 - {\mu _1}} \right){\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} + \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2}\\ &&{\rm{ + }}\left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2 \end{eqnarray*} $

得证.

基于以上对混合算法中预测步的讨论, 结合算法的修正步可得到算法的收缩性定理如下.

定理 2  给定$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in X \times Y \times {R^l} $, 将其代入算法中得到预测值为$ \tilde w = \left( {\tilde x, \tilde y, \tilde \lambda } \right) $以及修正值为$ {w^{k + 1}} = \left( {{x^{k + 1}}, {y^{k + 1}}, {\lambda ^{k{\rm{ + }}1}}} \right) $.若$ {w^ * } = \left( {{x^ * }, {y^ * }, {\lambda ^ * }} \right) $是$ SMVI\left( {\Omega , F} \right) $的解, 则有

$ \begin{eqnarray} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 &\le& \left\| {{w^k} - {w^ * }} \right\|_R^2 - t{\alpha _k}\left[ {\left( {1 - {\alpha _k}} \right)\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2 + \left( {1 - {\mu _1}} \right){{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2}} \right.\\&& + \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2}\left. { + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right]. \end{eqnarray} $

(4.11)

证  由式(3.4)得到

$ \begin{eqnarray*} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 & = & \left\| {\left( {1 - t} \right){w^k} + t{P_Z}\left\{ {{w^k} - {\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\} - {w^ * }} \right\|_R^2\\ & = & \left\| {\left( {1 - t} \right)\left( {{w^k} - {w^ * }} \right) + t\left[ {{P_Z}\left\{ {{w^k} - {\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\} - {w^ * }} \right]} \right\|_R^2. \end{eqnarray*} $

利用柯西-施瓦茨不等式和投影的非扩张性, 可推出

$ \begin{eqnarray*} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 &\le& {\left[ {\left( {1 - t} \right){{\left\| {{w^k} - {w^ * }} \right\|}_R} + t{{\left\| {{P_Z}\left\{ {{w^k} - {\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\} - {w^ * }} \right\|}_R}} \right]^2}\\ &\le& \left( {1 - t} \right)\left\| {{w^k} - {w^ * }} \right\|_R^2 + t\left\| {{P_Z}\left\{ {{w^k} - {\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\} - {w^ * }} \right\|_R^2\\ &\le& \left( {1 - t} \right)\left\| {{w^k} - {w^ * }} \right\|_R^2 + t\left\| {\left\{ {{w^k} - {\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\} - {w^ * }} \right\|_R^2\\ & = & \left\| {{w^k} - {w^ * }} \right\|_R^2 - 2t{\alpha _k}{\left( {{w^k} - {w^ * }} \right)^T}R\left( {{w^k} - {{\tilde w}^k}} \right) + t\alpha _k^2\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2, \end{eqnarray*} $

再结合推论1可得

$ \begin{eqnarray*} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 &\le& {\left[ {\left( {1 - t} \right){{\left\| {{w^k} - {w^ * }} \right\|}_R} + t{{\left\| {{P_Z}\left\{ {{w^k} - {\alpha _k}\left( {{w^k} - {{\tilde w}^k}} \right)} \right\} - {w^ * }} \right\|}_R}} \right]^2}\\ &&\left. { + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right] + t\alpha _k^2\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2\\ & = & \left\| {{w^k} - {w^ * }} \right\|_R^2 - t{\alpha _k}\left[ {\left( {1 - {\alpha _k}} \right)\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2 + \left( {1 - {\mu _1}} \right){{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2}} \right.\\ &&+ \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2}\left. { + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right] \end{eqnarray*} $

得证.

在证明算法的全局收敛性之前, 先给出一个重要的引理.

引理 7  给定$ {w^k} = \left( {{x^k}, {y^k}, {\lambda ^k}} \right) \in X \times Y \times {R^l} $, 由新算法产生的预测值为$ {\tilde w^k} = \left( {{{\tilde x}^k}, {{\tilde y}^k}, {{\tilde \lambda }^k}} \right) $, 则对任意的$ w = \left( {x, y, \lambda } \right) \in Z $, 有

$ \begin{eqnarray} &&{\left( {x - {{\tilde x}^k}} \right)^T}{f_k}\left( {{{\tilde x}^k}} \right) \ge {\left( {{x^k} - {{\tilde x}^k}} \right)^T}\left\{ {\left( {1 + {\mu _1}} \right)x - \left( {{\mu _1}{x^k} + {{\tilde x}^k}} \right)} \right\}, \end{eqnarray} $

(5.1)

$ \begin{eqnarray} &&{\left( {y - {{\tilde y}^k}} \right)^T}{g_k}\left( {{{\tilde y}^k}} \right) \ge {\left( {{y_k} - {{\tilde y}^k}} \right)^T}\left\{ {\left( {1 + {\mu _2}} \right)y - \left( {{\mu _2}{y^k} + {{\tilde y}^k}} \right)} \right\}, \end{eqnarray} $

(5.2)

其中

$ \begin{eqnarray} &&{f_k}\left( {{{\tilde x}^k}} \right) = f\left( {{{\tilde x}^k}} \right) - {A^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{y^k} - b} \right)} \right], \end{eqnarray} $

(5.3)

$ \begin{eqnarray} && {g_k}\left( {{{\tilde y}^k}} \right) = g\left( {{{\tilde y}^k}} \right) - {B^T}\left[ {{\lambda ^k} - H\left( {A{{\tilde x}^k} + B{{\tilde y}^k} - b} \right)} \right]. \end{eqnarray} $

(5.4)

证  在引理3中, 令$ v = x $, $ w = {\tilde x^k} $, $ q\left( w \right) = {f_k}\left( {{{\tilde x}^k}} \right) $, 则由(2.12)式可得

$ {\left( {x - {{\tilde x}^k}} \right)^T}{f_k}\left( {{{\tilde x}^k}} \right) \ge \frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - x} \right\|}^2} - {{\left\| {{x^k} - x} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{x^k} - {{\tilde x}^k}} \right\|^2}. $

将此不等式右端变形为

$ \begin{eqnarray*} &&\frac{{1 + {\mu _1}}}{2}\left( {{{\left\| {{{\tilde x}^k} - x} \right\|}^2} - {{\left\| {{x^k} - x} \right\|}^2}} \right) + \frac{{1 - {\mu _1}}}{2}{\left\| {{x^k} - {{\tilde x}^k}} \right\|^2}\\ & = & \frac{{1 + {\mu _1}}}{2}\left[ {{{\left\| {{{\tilde x}^k}} \right\|}^2} - 2{x^T}{{\tilde x}^k} + 2{x^T}{x^k} - {{\left\| {{x^k}} \right\|}^2}} \right] + \frac{{1 - {\mu _1}}}{2}\left( {{{\left\| {{x^k}} \right\|}^2} - 2{{\left( {{x^k}} \right)}^T}{{\tilde x}^k} + {{\left\| {{{\tilde x}^k}} \right\|}^2}} \right)\\ & = & {\left\| {{{\tilde x}^k}} \right\|^2} - \left( {1 + {\mu _1}} \right){x^T}{\tilde x^k} - {\mu _1}{\left\| {{x^k}} \right\|^2} + \left( {1 + {\mu _1}} \right){x^T}{x^k} - \left( {1 - {\mu _1}} \right){\left( {{x^k}} \right)^T}{\tilde x^k}\\ & = & \left( {1 + {\mu _1}} \right){x^T}\left( {{x^k} - {{\tilde x}^k}} \right) - {\left( {{x^k} - {{\tilde x}^k}} \right)^T}\left( {{\mu _1}{x^k} + {{\tilde x}^k}} \right)\\ & = & {\left( {{x^k} - {{\tilde x}^k}} \right)^T}\left\{ {\left( {1 + {\mu _1}} \right)x - \left( {{\mu _1}{x^k} + {{\tilde x}^k}} \right)} \right\}. \end{eqnarray*} $

于是(5.1)式成立.若再令$ v = y $, $ w = {\tilde y^k} $, $ q\left( w \right) = {g_k}\left( {{{\tilde y}^k}} \right) $, 同理可证(5.2)式也成立.证毕.

基于对LQP-ADM混合算法收缩性的讨论, 接下来给出此算法的全局收敛性分析.

定理 3  假设由新算法产生的无穷迭代序列为$ \left\{ {{w^k}} \right\} = \left\{ {\left( {{x^k}, {y^k}, {\lambda ^k}} \right)} \right\} $, 则此序列必定收敛于变分不等式问题$ SMVI\left( {\Omega , F} \right) $的解点$ {w^\infty } $.

证  此定理可以分两步来证:首先利用已经得到的结论证明$ {w^\infty } $是$ SMVI\left( {\Omega , F} \right) $的解, 然后再证明序列$ \left\{ {{w^k}} \right\} $收敛于$ {w^\infty } $.

步 1  由定理2可得

$ \begin{eqnarray*} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 &\le& \left\| {{w^k} - {w^ * }} \right\|_R^2 - t{\alpha _k}\left( {1 - {\alpha _k}} \right)\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2 - t{\alpha _k}\left[ {\left( {1 - {\mu _1}} \right){{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2}} \right.\\&&+ \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2}\left. { + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right]. \end{eqnarray*} $

因为$ {\mu _1} $, $ {\mu _2} $, $ t \in \left( {0, 1} \right) $, 所以

$ \begin{eqnarray} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 \le \left\| {{w^k} - {w^ * }} \right\|_R^2 - t{\alpha _k}\left( {1 - {\alpha _k}} \right)\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2. \end{eqnarray} $

(5.5)

由(5.5)式可知必定存在常数$ c > 0 $, 使得

$ \begin{eqnarray} \left\| {{w^{k + 1}} - {w^ * }} \right\|_R^2 \le \left\| {{w^k} - {w^ * }} \right\|_R^2 - c\left\| {{w^k} - {{\tilde w}^k}} \right\|_R^2, \end{eqnarray} $

(5.6)

进而由上面不等式可知序列$ \left\{ {{w^k}} \right\} $有界且$ \mathop {\lim }\limits_{k \to \infty } {\left\| {{w^k} - {{\tilde w}^k}} \right\|_R} = 0 $.从而

$ \begin{eqnarray} \mathop {\lim }\limits_{k \to \infty } \left\| {{x^k} - {{\tilde x}^k}} \right\| = 0, \mathop {\lim }\limits_{k \to \infty } \left\| {{y^k} - {{\tilde y}^k}} \right\| = 0, \mathop {\lim }\limits_{k \to \infty } \left\| {{\lambda ^k} - {{\tilde \lambda }^k}} \right\| = 0. \end{eqnarray} $

(5.7)

由上可知序列$ \left\{ {{{\tilde w}^k}} \right\} $也是有界的, 并且至少存在一个聚点.由定理1可知

$ \begin{eqnarray*} &&\left\| {{{\tilde w}^k} - {w^ * }} \right\|_R^2 \\ &\le &\left\| {{w^k} - {w^ * }} \right\|_R^2 - \left( {1 - {\mu _1}} \right){\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} - \left( {1 - {\mu _2}} \right){\left\| {{{\tilde y}^k} - {y^k}} \right\|^2} - \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2. \end{eqnarray*} $

取$ \mu = \min \left\{ {1 - {\mu _1}, 1 - {\mu _2}} \right\} $, 则

$ \left\| {{{\tilde w}^k} - {w^ * }} \right\|_R^2 \le \left\| {{w^k} - {w^ * }} \right\|_R^2 - \mu \left[ {{{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2} + {{\left\| {{{\tilde y}^k} - {y^k}} \right\|}^2} + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right], $

进而有

$ \begin{eqnarray*} &&\sum\limits_{k = 0}^\infty {\mu \left[ {{{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2} + {{\left\| {{{\tilde y}^k} - {y^k}} \right\|}^2} + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right]}\\ & \le& \sum\limits_{k = 0}^\infty {\left[ {\left\| {{w^k} - {w^ * }} \right\|_R^2 - \left\| {{{\tilde w}^k} - {w^ * }} \right\|_R^2} \right]}. \end{eqnarray*} $

由上面的证明可知序列$ \left\{ {{w^k}} \right\} $, $ \left\{ {{{\tilde w}^k}} \right\} $都是有界的.则

$ \sum\limits_{k = 0}^\infty {\mu \left[ {{{\left\| {{{\tilde x}^k} - {x^k}} \right\|}^2} + {{\left\| {{{\tilde y}^k} - {y^k}} \right\|}^2} + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2} \right]} < \infty, $

故

$ \mathop {\lim }\limits_{k \to \infty } {\left\| {{{\tilde x}^k} - {x^k}} \right\|^2} + {\left\| {{{\tilde y}^k} - {y^k}} \right\|^2} + \left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H^2 = 0. $

于是

$ \begin{eqnarray} \mathop {\lim }\limits_{k \to \infty } {\left\| {A{{\tilde x}^k} + B{y^k} - b} \right\|_H} = 0 \end{eqnarray} $

(5.8)

结合(5.3)式和(5.4)式可得

$ \begin{eqnarray*} &&{f_k}\left( {{{\tilde x}^k}} \right) = f\left( {{{\tilde x}^k}} \right) - {A^T}{\tilde \lambda ^k}, \\ &&{g_k}\left( {{{\tilde y}^k}} \right) = g\left( {{{\tilde y}^k}} \right) - {B^T}{\tilde \lambda ^k} + {B^T}HB\left( {{y^k} - {{\tilde y}^k}} \right), \end{eqnarray*} $

则

$ \begin{eqnarray*} &&{\left( {x - {{\tilde x}^k}} \right)^T}\left\{ {f\left( {{{\tilde x}^k}} \right) - {A^T}{{\tilde \lambda }^k}} \right\} = {\left( {x - {{\tilde x}^k}} \right)^T}{f_k}\left( {{{\tilde x}^k}} \right), \\ &&{\left( {y - {{\tilde y}^k}} \right)^T}\left\{ {g\left( {{{\tilde y}^k}} \right) - {B^T}{{\tilde \lambda }^k}} \right\} = {\left( {y - {{\tilde y}^k}} \right)^T}{g_k}\left( {{{\tilde y}^k}} \right) - {\left( {y - {{\tilde y}^k}} \right)^T}{B^T}HB\left( {{y^k} - {{\tilde y}^k}} \right). \end{eqnarray*} $

进而由(5.1), (5.2)及(5.7)式可得

$ \begin{eqnarray} \left\{ {\begin{array}{*{20}{c}} {\mathop {\lim }\limits_{k \to \infty } {{\left( {x - {{\tilde x}^k}} \right)}^T}\left\{ {f\left( {{{\tilde x}^k}} \right) - {A^T}{{\tilde \lambda }^k}} \right\} \ge 0, }\\ {\mathop {\lim }\limits_{k \to \infty } {{\left( {y - {{\tilde y}^k}} \right)}^T}\left\{ {g\left( {{{\tilde y}^k}} \right) - {B^T}{{\tilde \lambda }^k}} \right\} \ge 0, } \end{array}} \right.\begin{array}{*{20}{c}}\; \; {\forall x \in X, }\\ {\forall y \in Y, } \end{array} \end{eqnarray} $

(5.9)

令$ {w^\infty } $为$ \left\{ {{{\tilde w}^k}} \right\} $的一个聚点且其中一个子列$ \left\{ {{{\tilde w}^{{k_j}}}} \right\} $收敛于$ {w^\infty } $.则由(5.7)及(5.8)式可得

$ \left\{ \begin{array}{l} \mathop {\lim }\limits_{j \to \infty } {\left( {x - {{\tilde x}^{{k_j}}}} \right)^T}\left\{ {f\left( {{{\tilde x}^{{k_j}}}} \right) - {A^T}{{\tilde \lambda }^{{k_j}}}} \right\} \ge 0, \; \; {\rm{ }}\forall x \in X, \\ \mathop {\lim }\limits_{j \to \infty } {\left( {y - {{\tilde y}^{{k_j}}}} \right)^T}\left\{ {g\left( {{{\tilde y}^{{k_j}}}} \right) - {B^T}{{\tilde \lambda }^{{k_j}}}} \right\} \ge 0{\rm{, }}\; \; \forall y \in Y, \\ \mathop {\lim }\limits_{j \to \infty } \left( {A{{\tilde x}^{{k_j}}} + B{{\tilde y}^{{k_j}}} - b} \right) = 0. \end{array} \right. $

因此

$ \left\{ \begin{array}{l} {\left( {x - {x^\infty }} \right)^T}\left\{ {f\left( {{x^\infty }} \right) - {A^T}{\lambda ^\infty }} \right\} \ge 0, \; \; {\rm{ }}\forall x \in X, \\ {\left( {y - {y^\infty }} \right)^T}\left\{ {g\left( {{y^\infty }} \right) - {B^T}{\lambda ^\infty }} \right\} \ge 0, \; \; {\rm{ }}\forall {\rm{y}} \in {\rm{Y, }}\\ {\rm{A}}{x^\infty }{\rm{ + B}}{{\rm{y}}^\infty } - b = 0. \end{array} \right. $

即$ {\left( {w - {w^\infty }} \right)^T}Q\left( {{w^\infty }} \right) \ge 0, \forall w \in Z, $这说明$ {w^\infty } $是$ SMVI\left( {\Omega , F} \right) $的解.

步 2  对于$ SMVI\left( {\Omega , F} \right) $的所有解都满足不等式(5.6), 所以可推出

$ \begin{eqnarray} \left\| {{w^{k + 1}} - {w^\infty }} \right\|_R^2 \le \left\| {{w^k} - {w^\infty }} \right\|_R^2, \forall k \ge 0, \end{eqnarray} $

(5.10)

因为$ {\tilde w^{{k_j}}} \to {w^\infty }\left( {j \to \infty } \right) $和$ {w^k} - {\tilde w^k} \to 0\left( {k \to \infty } \right) $, 对任意的$ \varepsilon > 0 $, 存在整数$ l > 0 $, 使得

$ \begin{eqnarray} {\left\| {{{\tilde w}^{{k_j}}} - {w^\infty }} \right\|_R} < \frac{\varepsilon }{2}, {\left\| {{w^{{k_l}}} - {{\tilde w}^{{k_l}}}} \right\|_R} < \frac{\varepsilon }{2}, \end{eqnarray} $

(5.11)

所以$ \forall k \ge l $, 由(5.11)式可得

$ {\left\| {{w^k} - {w^\infty }} \right\|_R} \le {\left\| {{w^{{k_l}}} - {{\tilde w}^{{k_l}}}} \right\|_R} + {\left\| {{{\tilde w}^{{k_l}}} - {w^\infty }} \right\|_R} \le \varepsilon, $

这说明序列$ \left\{ {{w^k}} \right\} $收敛到$ SMVI\left( {\Omega , F} \right) $的解$ {w^\infty } $证毕.

为了考察LQP-ADM混合算法的数值表现, 用Matlab软件编程来进行数值实验, 所有程序在Windows 2007系统下进行.考虑这样一个优化问题$ \min \left\{ {{c^T}x\left| {x \in {\Omega _1} \cap {\Omega _2}} \right.} \right\}, $其中

$ \begin{eqnarray*} &&{\Omega _1}{\rm{ = }}\left\{ {x \in {R^n}\left| {\left\| x \right\| \le {r_1}} \right.} \right\}, \\ &&{\Omega _2}{\rm{ = }}\left\{ {x \in {R^{^n}}\left| {\left\| {x{\rm{ - }}b} \right\|} \right. \le {r_2}} \right\}. \end{eqnarray*} $

为了保证问题的可行性, $ \left\| b \right\| \le {r_1}{\rm{ + }}{r_2} $必须满足.比如选取$ {r_1}{\rm{ = }}0.5\left\| b \right\|, {r_2}{\rm{ = }}0.6\left\| b \right\| $.

引入辅助变量$ y $, 则上述问题转化后的形式如下:

$ \min {\rm{ }}{c^T}x\; \; {\rm s{.}t.} \quad x{\rm{ + }}y{\rm{ = }}b, x \in {B_{{r_1}}}, y \in {B_{{r_2}}}, $

其中$ {B_r} $表示圆心为原点、半径为$ r $的圆.

接着将上述凸规划问题转化为可分离带线性约束的变分不等式问题, 即找一点$ {u^ * } \in \Omega $, 满足$ {\left( {u{\rm{ - }}{u^ * }} \right)^T}F\left( {{u^ * }} \right) \ge 0{\rm{, }}\; \forall u \in \Omega, $其中

$ u = {\left( {x, y} \right)^T}, F\left( u \right) = {\left( {c, 0} \right)^T}, \Omega = \left\{ {\left( {x, y} \right)\left| {x \in {B_{{r_1}}}, y \in {B_{{r_2}}}}\right., \; x + y = b} \right\}. $

在数值实验中, 选取初始迭代点$ {w^0} = \left( {{x^0}, {y^0}, {\lambda ^0}} \right) $为$ {x^0} = {\left( {1, 1} \right)^T} $, $ {y^0} = {\left( {1, 1} \right)^T} $, $ {\lambda ^0} = {\left( {1, 1} \right)^T} $, 二维列向量$ c $的元素随机分布在$ \left( { - 20, 20} \right) $, 二维列向量$ b $的元素随机分布在$ \left( {0, 20} \right) $.给定误差界$ \varepsilon = {10^{ - 6}} $, 参数$ {\mu _1} = {\mu _2} = \frac{1}{2} $, 对称正定矩阵$ H = \left( {\begin{array}{*{20}{c}} 2&1\\ 1&2 \end{array}} \right). $

由于向量$ c $与向量$ b $的元素均是随机产生的, 所以每次运行LQP-ADM混合算法求得变分不等式的解都不相同, 但是解均是收敛的并且收敛性态是一致的.为了说明情况, 从多次运行结果中选取下面三组图——图 1、图 2与图 3来分析.从这三组图可知, $ x $与$ \lambda $的收敛趋势是一样的, 都是随着迭代次数的增加其中一个分量增大另一分量减小, 但是$ y $的收敛趋势却不同, 图 1中$ y $的两个分量随着不断迭代都是增大的, 图 2中都是减小的, 而图 3中却是一个增大另一个减小, 同时容易看出新算法的收敛速度很快, 所以LQP-ADM混合算法求解问题$ SMVI(\Omega, F) $的解是收敛的, 也是有效的.