定义1.1^[1]  设 $K\subseteq\mathbb{R}^n$, $F:K\rightarrow\mathbb{R}^n$, 所谓变分不等式问题( ${\rm VI}(K, F)$)是指:求 $x\in K$, 使得不等式

$ {(y - x)^T}F(x) \ge 0, \;\;\;\;\forall y \in K $

成立.满足上述不等式的 $x$称为 ${\rm VI}(K, F)$的解, 解的全体记为 ${\rm SOL}(K, F)$.

当 $K=\mathbb{R}^n_+$时, ${\rm VI}(K, F)$等价于如下的非线性互补问题:求 $x\in\mathbb{R}^n$, 满足

$ x \ge 0, \quad F(x) \ge 0, \quad {x^T}F(x) = 0 $

变分不等式与互补问题在经济理论、控制论、对策论、交通、社会及网络平衡等学科中有着广泛而重要的应用^[1].求解一般变分不等式问题的算法有很多, 主要包括

(1) 基于变分不等式的等价非光滑方程形式的Josephy -牛顿算法;

(2) 基于变分不等式的间隙函数的优化算法;

(3) 基于KKT条件将变分不等式转化为互补问题, 利用互补问题的算法, 包括内点算法、半光滑牛顿算法以及光滑化牛顿法等^[10].对于满足特殊条件的变分不等式又有一些特殊的有效算法.关于变分不等式的各种具体算法可参见文献[1], 而互补问题的各种有效算法则可参见文献[11].

本文主要研究的幂罚函数法最早是由文献[3]提出的, 用于求解无限维线性互补问题; 文献[2]又将幂罚函数法用于求解无限维非线性互补问题.而文献[4-6]又对幂罚函数法做了进一步的推广, 将其分别应用于求解有限维线性互补问题、非线性互补问题和混合互补问题等.文献[7, 10]则对文献[5, 6]中的一些结果做了改进, 并将幂罚函数法推广至求解约束域为 $K=\{x\in \mathbb{R}^n \mid Ax=b, x\geq0\}$的 ${\rm VI}(K, F)$, 具体做法是利用 ${\rm VI}(K, F)$的KKT条件将 ${\rm VI}(K, F)$转化为等价的互补问题, 进而设计幂罚函数法求解, 且将这一结果应用于求解非对称交通均衡问题.最近, 文献[8]又将幂罚函数法应用于求解有限维障碍问题.

本文主要研究利用幂罚函数法求解约束域为

$ K=\{x\in {{\mathbb{R}}^{n}}\mid Ax=b, Cx\le d\} $

(1.1)

的 ${\rm VI}(K, F)$, 其中 $A, C$分别是 $l \times n, m \times n$的实矩阵.下文出现的 ${\rm VI}(K, F)$中的 $K$均是形如(1.1) 式所定义.首先, 利用KKT条件和互补问题与变分不等式的等价性给出了与 ${\rm VI}(K, F)$等价的两个问题, 并在一定条件下分析了这些问题的解的存在性和唯一性; 然后, 根据等价的混合互补问题提出对应的幂罚方程组, 并利用度理论的有关结论证明了幂罚方程组的解的存在性以及唯一性; 最后, 证明了幂罚函数法的收敛性, 即幂罚方程组的解是收敛于 ${\rm VI}(K, F)$的解的.

变分不等式问题 ${\rm VI}(K, F)$的KKT条件是如下的混合互补问题.

问题2.1  求 $(x^T, u^T, v^T)^T\in\mathbb{R}^n\times\mathbb{R}^l\times\mathbb{R}^m$, 使得

$ F(x)-{{A}^{T}}u-{{C}^{T}}v=0, \quad Ax=b, \quad 0\ge v\bot Cx-d\le 0. $

(2.1)

定理2.1   $x^*\in \mathbb{R}^n$是 ${\rm VI}(K, F)$的解当且仅当存在 $u^*\in \mathbb{R}^l, 0\geq v^*\in \mathbb{R}^m$, 使得 $({x^*}^T, {u^*}^T, {v^*}^T)^T$是问题2.1的解.

证  若 $x^*\in {\rm SOL}(K, F)$, 则 $x^*$是如下线性规划问题的解

$ \begin{align} & \rm{min}\;\;\;\;{{\mathit{x}}^{\mathit{T}}}\mathit{F}({{\mathit{x}}^{*}}), \\ & \rm{s}\rm{.t}\rm{.}\;\;\;\mathit{Ax}=\mathit{b},\;\;\;\mathit{Cx}\le \mathit{d}. \\ \end{align} $

从而存在 $u^*\in \mathbb{R}^l, 0\geq v^*\in \mathbb{R}^m$是其KKT条件(2.1) 的解.

反之, 设 $({x^*}^T, {u^*}^T, {v^*}^T)^T$是(2.1) 式的解, 则有 $Ax=Ax^*=b, {v^*}^T(Cx^*-d)=0$, 从而 $\forall x\in K$, 有

$ \begin{align} &{{(x-{{x}^{*}})}^{T}}F({{x}^{*}})={{(x-{{x}^{*}})}^{T}}({{A}^{T}}{{u}^{*}}+{{C}^{T}}{{v}^{*}}) \\ &\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; ={{[Ax-A{{x}^{*}}]}^{T}}{{u}^{*}}-{{[Cx-C{{x}^{*}}]}^{T}}{{v}^{*}}={{[Cx-d]}^{T}}{{v}^{*}}\ge 0. \\ \end{align} $

最后的不等式成立, 是因为 $Cx\leq d, v^*\leq 0$, 从而证得 $x^*$是 ${\rm VI}(K, F)$的解.

由此可知 ${\rm VI}(K, F)$与其KKT条件(问题2.1) 等价, 即求解 ${\rm VI}(K, F)$等价于求解问题2.1.

令 $K_1=\{(x^T, u^T, v^T)^T|(x^T, u^T, v^T)^T\in\mathbb{R}^n\times\mathbb{R}^l\times\mathbb{R}^m, v\leq 0\}$, 容易验证 $K_1$是 $\mathbb{R}^n\times\mathbb{R}^l\times\mathbb{R}^m$中的凸锥, 利用 $K_1$定义如下变分不等式问题.

问题2.2  求 $z=(x^T, u^T, v^T)^T\in K_1$, 使得 $\forall \omega\in K_1$都有

$ \begin{equation}\label{1} (\omega-z)^TG(z)\geq 0, \end{equation} $

(2.2)

其中

$ G(z)=G(x, u, v)=\left( \begin{array}{c} F(x)-A^Tu-C^Tv\\ Ax-b\\ Cx-d \end{array} \right). $

关于问题2.1和问题2.2, 我们有如下结论.

定理2.2  设 $z=(x^T, u^T, v^T)^T\in\mathbb{R}^n\times\mathbb{R}^l\times\mathbb{R}^m$, 则 $z$是问题2.1的解, 当且仅当 $z$是问题2.2的解.

该定理的证明可以参看文献[6].由此可知 ${\rm VI}(K, F)$、问题2.1和问题2.2三者等价.

在下文中, 我们将用 $\parallel\cdot\parallel_p$表示 $\mathbb{R}^n$空间中向量的 $l_p$范数.特别地, $\parallel\cdot\parallel_2$表示欧几里得范数.对于 ${\rm VI}(K, F)$, 做如下的假设.

$\mathcal{A}1$设 $F(x)$在 $\mathbb{R}^n$上连续, 且 $\xi$-单调, 即存在 $\xi\in(1, 2]$和 $\alpha>0$, 使得

$ (x-y)^T(F(x)-F(y))\geq \alpha {\parallel x-y\parallel}^\xi_2, \quad \forall x, y\in \mathbb{R}^n. $

$\mathcal{A}2$设线性独立约束规格(LICQ)成立, 即矩阵 $B=\left(\begin{array}{c}A\\C\end{array} \right)$是行满秩的, 从而 $A, C$均是行满秩矩阵, 且有 ${\rm Rank}(B)={\rm Rank}(A)+{\rm Rank}(C)=l+m\leq n$.

在假设条件 $\mathcal{A}1$下, 由文献[1]中定理2.3.3可知 ${\rm VI}(K, F)$有唯一解, 记为 $x$.

在假设条件 $\mathcal{A}2$下, 容易证明线性方程组 $Ax=b, Cx=d$有公共解.本文接下来的讨论都是假设条件 $\mathcal{A}1$和 $\mathcal{A}2$是成立的.

引理2.1  对于任意 $z_i=(x_i^T, u_i^T, v_i^T)^T\in\mathbb{R}^n\times\mathbb{R}^l\times\mathbb{R}^m, i=1, 2$, 问题2.2中定义的函数 $G(z)$满足

$ (z_1-z_2)^T(G(z_1)-G(z_2))\geq\alpha {\parallel x_1-x_2\parallel}^\xi_2, $

其中 $\xi\in(1, 2]$, $\alpha>0$.

证  由函数 $G(z)$的定义容易得

$ (z_1-z_2)^T(G(z_1)-G(z_2))=(x_1-x_2)^T(F(x_1)-F(x_2)), $

由于 $\mathcal{A}1$成立, 故存在 $\xi\in(1, 2]$, $\alpha>0$使得

$ (x_1-x_2)^T(F(x_1)-F(x_2))\geq \alpha {\parallel x_1-x_2\parallel}^\xi_2, $

从而有

$ (z_1-z_2)^T(G(z_1)-G(z_2))\geq \alpha {\parallel x_1-x_2\parallel}^\xi_2. $

定理2.3  问题2.2有唯一解.

证  由定理2.1知问题2.1有解, 设为 $z=(x^T, u^T, v^T)^T$, 由定理2.2知 $z$也是问题2.2的解, 即问题2.2有解.即有

$ F(x)-A^Tu-C^Tv=F(x)-(A^T, C^T)\left( \begin{array}{c}u\\v\end{array} \right)=0. $

两边左乘 $B=\left( \begin{array}{c}A\\C\end{array} \right)$, 得

$ BF(x)-BB^T\left( \begin{array}{c}u\\v\end{array} \right)=0. $

由 ${\rm Rank}(B)={\rm Rank}(A)+{\rm Rank}(C)=l+m\leq n$知 $BB^T$可逆, 从而有

$ \begin{equation}\label{10}\left( \begin{array}{c}u\\v\end{array} \right)=(BB^T)^{-1}BF(x).\end{equation} $

(2.3)

故由 $x$的唯一性, 可得 $u, v$也都是唯一的, 即问题2.2有唯一解.

考虑如下的非线性、非光滑的方程组:

问题3.1  求 $z_\lambda=(x_\lambda^T, u_\lambda^T, v_\lambda^T)^T\in\mathbb{R}^n\times\mathbb{R}^l\times\mathbb{R}^m$, 使得

$ \begin{equation}\label{2}G(z_\lambda)+\lambda\Phi(z_\lambda)=0, \end{equation} $

(3.1)

其中 $\Phi(z_\lambda)=\Phi(x_\lambda, u_\lambda, v_\lambda)=\left(\begin{array}{c}0\\0\\{[v_\lambda]_+^{1/k}}\end{array} \right)$, $\lambda\geq1$是罚参数, $k\geq0$是幂参数, ${[u]}_+=\max{\{u, 0\}}$, 对于 $y=(y_1, y_2, \cdots, y_n)^T\in\mathbb{R}^n, a>0$, 规定 $y^a=(y_1^a, y_2^a, \cdots, y_n^a)^T$.

方程组(3.1) 式称为问题2.1的幂罚方程组.本节将主要应用度理论证明(3.1) 式解的存在性, 并证明其唯一性.为此, 先将需要用到的度理论的有关结论(详见文献[9]叙述如下.

在以下结论中, 设 $E\subset\mathbb{R}^n$为有界开集, $\overline{E}$和 $\partial E$分别表示 $E$的闭包和边界.

引理3.1^[9]  设 $I:\mathbb{R}^n\rightarrow\mathbb{R}^n$是恒等映射, 若 $y\in E$, 则 $\deg(I, E, y)=1$.

引理3.2^[9]  (同伦不变性)设 $H:\overline{E}\times[0,1]\subset\mathbb{R}^{n+1}\rightarrow\mathbb{R}^n$是一连续函数, 若 $y\in\mathbb{R}^n$满足

$ y\notin\{H(x, t)\mid (x, t)\in \partial E\times[0,1]\}, $

则 $\deg(H(x, t), E, y)$是与 $t\in [0,1]$无关的一个常数.

引理3.3^[9]  设 $f:\overline{E}\rightarrow\mathbb{R}^n$是连续函数, 若 $y\notin f(\partial E)$, 且 $\deg(f, E, y)\neq 0$, 则方程组 $f(x)=y$在 $E$中有解.

为了利用以上结论证明幂罚方程组(3.1) 的解的存在性, 先构造如下的同伦函数

$ H(z, t)=t\Psi(z)+(1-t)z, \quad t\in[0,1], $

其中

$ z=(x^T, u^T, v^T)^T, \quad \Psi(z)=G(z)+\lambda\Phi(z), $

则 $H(z, t)$在 $\overline{E}\times[0,1]$上是连续的.如果 $H(z, t)=0$有解, 则其解有如下性质:

引理3.4  对于任意的 $\lambda\geq1, t\in[0,1]$, 若 $H(z, t)=0$有解 $z_{\lambda t} =(x_{\lambda t}^T, u_{\lambda t}^T, v_{\lambda t}^T)^T$, 则存在不依赖于 $\lambda, t$和 $z_{\lambda t}$的正数 $M$, 使得

$ \parallel x_{\lambda t}\parallel_2\leq M. $

证   (a)当 $t=0$时, $H(z, 0)=z$, 即 $H(z, 0)$为恒等映射, $H(z, 0)=0$有唯一解 $z=0$.(b)当 $t\in(0, 1]$时, 在等式

$ H(z_{\lambda t}, t)=t\Psi(z_{\lambda t})+(1-t)z_{\lambda t}=0 $

两边左乘 $z_{\lambda t}^T$, 得

$ tz_{\lambda t}^T\Psi(z_{\lambda t})=(t-1)z_{\lambda t}^Tz_{\lambda t}, $

即

$ z_{\lambda t}^T[G(z_{\lambda t})+\lambda\Phi(z_{\lambda t})]=-\frac{1-t}{t}z_{\lambda t}^Tz_{\lambda t}. $

设 $x_0$是方程组 $Ax=b, Cx=d$的一个公共解, 记 $z_0=(x_0^T, 0^T, 0^T)^T$, 由函数 $G(z)$和 $\Phi(z)$的定义可得

$ z_{\lambda t}^T[G(z_{\lambda t})-G(z_0)]=-\lambda v_{\lambda t}^T[v_{\lambda t}]_+^{1/k}-x_{\lambda t}^TF(x_0)-\frac{1-t}{t}z_{\lambda t}^Tz_{\lambda t}, $

从而

$ (z_{\lambda t}-z_0)^T[G(z_{\lambda t})-G(z_0)]=-\lambda v_{\lambda t}^T[v_{\lambda t}]_+^{1/k}-x_{\lambda t}^TF(x_0)-\frac{1-t}{t}z_{\lambda t}^Tz_{\lambda t}+x_0^TF(x_0). $

再由引理2.1, 可以得到

$ \begin{align} & \alpha \parallel {{x}_{\lambda t}}-{{x}_{0}}\parallel _{2}^{\xi }\le {{({{z}_{\lambda t}}-{{z}_{0}})}^{T}}[G({{z}_{\lambda t}})-G({{z}_{0}})] \\ & \;\;\;\;\;\;\;\;\;=-\lambda v_{\lambda t}^{T}[{{v}_{\lambda t}}]_{+}^{1/k}-x_{\lambda t}^{T}F({{x}_{0}})-\frac{1-t}{t}z_{\lambda t}^{T}{{z}_{\lambda t}}+x_{0}^{T}F({{x}_{0}}). \\ \end{align} $

又 $v_{\lambda t}=[v_{\lambda t}]_+-[v_{\lambda t}]_-$, 其中 $[v]_-=\max\{-v, 0\}$, 则有 $[v_{\lambda t}]^T_+[v_{\lambda t}]_-=0$, 因此有

$ -v_{\lambda t}^T[v_{\lambda t}]_+^{1/k}=-([v_{\lambda t}]_+-[v_{\lambda t}]_-)^T[v_{\lambda t}]_+^{1/k}=-[v_{\lambda t}]^T_+[v_{\lambda t}]_+^{1/k}\leq0, $

且 $t\in(0, 1]$时有

$ -\frac{1-t}{t}z_{\lambda t}^Tz_{\lambda t}\leq0. $

结合上面两式及Cauchy-Schwarz不等式有

$ \alpha {\parallel x_{\lambda t}-x_0\parallel}^\xi_2\leq-x_{\lambda t}^TF(x_0)+x_0^TF(x_0)\leq{\parallel x_{\lambda t}-x_0\parallel}_2{\parallel F(x_0) \parallel}_2. $

从而有

$ {\parallel x_{\lambda t}-x_0\parallel}_2\leq({\alpha^{-1}\parallel F(x_0)\parallel}_2)^{1/(\xi-1)}. $

进一步有

$ {\parallel x_{\lambda t} \parallel}_2\leq({\alpha^{-1}\parallel F(x_0) \parallel}_2)^{1/(\xi-1)}+{\parallel x_0 \parallel}_2=M. $

结合(a)、(b)两种情况即证明了引理.

推论3.1  对于任意的 $\lambda\geq1$, 若 $\Psi(z)=0$(即问题3.1) 有解 $z_\lambda=(x_\lambda^T, u_\lambda^T, v_\lambda^T)^T$, 则存在不依赖于 $\lambda$和 $z_\lambda$的正数 $M'$, 使得

$ \parallel x_\lambda\parallel_2\leq M', \quad \parallel y_\lambda\parallel_2\leq M', $

其中 $y_\lambda=(u_\lambda^T, v_\lambda^T)^T$.

证  在引理3.4中取 $t=1$即可得第一个不等式.

由(2.3) 式可知

$ y_\lambda=\left( \begin{array}{c}u_\lambda\\v_\lambda \end{array} \right)=(BB^T)^{-1}BF(x_\lambda), $

其中 $B=(A^T, C^T)^T$, 从而有

$ \parallel y_\lambda\parallel_2\leq \parallel (BB^T)^{-1}\parallel_2\cdot \parallel B \parallel_2\cdot\parallel F(x_\lambda)\parallel_2. $

由条件 $\mathcal{A}1$的假设, $F(x)$是连续的, 又由上面的证明知, 对于任意的 $\lambda\geq1$, $\parallel x_\lambda\parallel_2$都是有界的, 从而 $\parallel F(x_\lambda)\parallel_2$是有界的, 也就证明了第二个式子.

下面证明问题3.1的解存在且唯一.

定理3.1  对于任意的 $\lambda\geq1$, 问题3.1有唯一解.

证  设 $M$是引理3.4中所定义的正数, 取 $r>M$, 令

$ D=\{z=(x^T, u^T, v^T)^T\mid \parallel x\parallel_2<r, \parallel (u^T, v^T)^T\parallel_2<r\}, $

则 $D$是 $\mathbb{R}^{n+m+l}$中的有界开集.由同伦函数

$ H(z, t)=t\Psi(z)+(1-t)z, \quad t\in[0,1] $

的定义可知, $H(z, t)$在 $\overline{D}\times[0,1]$上连续.

由引理3.4, 对于任意的 $\lambda\geq1, t\in[0,1]$, 若 $H(z, t)=0$有解 $z_{\lambda t} =(x_{\lambda t}^T, u_{\lambda t}^T, v_{\lambda t}^T)^T$, 则有

$ \parallel x_{\lambda t}\parallel_2\leq M<r. $

从而有 $z_{\lambda t}\notin \partial D$, 即方程 $H(z, t)=0$在 $\partial D\times[0,1]$上没有解, 由引理3.2有

$ \deg(H(z, 1), D, 0)=\deg(H(z, 0), D, 0), $

而 $H(z, 0)=z=I(z)$为恒等映射, 且 $0\in D$, 由引理3.1知 $\deg(I, D, 0)=1$.又 $H(z, 1)=\Psi(z)$, 从而有

$ \deg(\Psi(z), D, 0)=\deg(H(z, 1), D, 0)=\deg(H(z, 0), D, 0)=\deg(I, D, 0)=1. $

再由引理3.3可得方程 $\Psi(z)=0$在 $D$中有解, 即问题3.1的解存在.

下证问题3.1的解是唯一的.设 $z_i=(x_i^T, u_i^T, v_i^T)^T$(其中 $i=1, 2$)是问题3.1的两个解.容易证明 $\Phi(z)$是单调的(可参考文献[10], 故有

$ (z_1-z_2)^T(\Phi(z_1)-\Phi(z_2))=(v_1-v_2)^T([v_1]_+^{1/k}-[v_2]_+^{1/k})\geq0. $

从而

$ \begin{split} 0&=(z_1-z_2)^T(\Psi(z_1)-\Psi(z_2)) =(z_1-z_2)^T(G(z_1)-G(z_2))+(z_1-z_2)^T(\Phi(z_1)-\Phi(z_2))\\ & \geq(z_1-z_2)^T(G(z_1)-G(z_2)).\\ \end{split} $

由引理2.1立即可得 $x_1=x_2$.而由(2.3) 式可知

$ \left( \begin{array}{c} u_1\\v_1 \end{array} \right)=(BB^T)^{-1}BF(x_1), \quad \left( \begin{array}{c} u_2\\v_2 \end{array} \right)=(BB^T)^{-1}BF(x_2), $

可得 $\left( \begin{array}{c}u_1\\v_1\end{array} \right)=\left( \begin{array}{c}u_2\\v_2\end{array} \right)$.从而 $z_1=z_2$, 唯一性得证.

下面主要证明问题3.1的解收敛于问题2.2的解.

由定理3.1和推论3.1可知, 若 $z_\lambda=(x_\lambda^T, u_\lambda^T, v_\lambda^T)^T$是问题3.1的解, 则存在有界集 $S\subset\mathbb{R}^n$, 使得 $\forall\lambda\geq1$, 都有 $x_\lambda\in S$, 利用这个性质, 接下来证明 $\parallel [v_\lambda]_+\parallel_2\rightarrow 0(\lambda\rightarrow\infty)$.

引理4.1  对于任意的 $\lambda\geq1$, 设 $z_\lambda=(x_\lambda^T, u_\lambda^T, v_\lambda^T)^T$是(3.1) 的解, 则存在不依赖于 $\lambda$和 $z_\lambda$的正数 $M_0$, 使得

$ \parallel [v_\lambda]_+\parallel_2\leq M_0\lambda^{-k}. $

证  在(3.1) 式两边左乘 $(0^T, [v_\lambda]_+^T)$, 得

$ [v_\lambda]_+^T(Cx_\lambda-d)+\lambda[v_\lambda]_+^T[v_\lambda]_+^{1/k}=0. $

设 $p=1+1/k, q=1+k$, 由Hölder不等式有

$ \lambda[v_\lambda]_+^T[v_\lambda]_+^{1/k}=\lambda\|[v_\lambda]_+\|_p^p=-[v_\lambda]_+^T(Cx_\lambda-d)\leq\|[v_\lambda]_+\|_p\cdot\|Cx_\lambda-d\|_q, $

即

$ \|[v_\lambda]_+\|_p^{p-1}\leq \|Cx_\lambda-d\|_q\cdot\lambda^{-1}. $

两边开 $p-1$次方得

$ \begin{equation}\label{11} \|[v_\lambda]_+\|_p\leq \|Cx_\lambda-d\|_q^{1/(p-1)}\cdot\lambda^{-1/(p-1)}\leq M_S\lambda^{-k}, \end{equation} $

(4.1)

其中 $M_S=\sup\limits_{\omega\in S}\parallel C\omega-d\parallel_q^k, S$是如上所定义的有界集.

由欧几里得空间中范数的等价性可知存在正数 $\delta$,使得

$ \|[v_\lambda]_+\|_2\leq \delta\|[v_\lambda]_+\|_p. $

结合(4.1) 式可得

$ \|[v_\lambda]_+\|_2\leq \delta M_S\lambda^{-k}=M_0\lambda^{-k}, $

其中 $M_0=\delta M_S$.

下面介绍主要的收敛定理.

定理4.1  对于任意的 $\lambda\geq1$, 设

$ z=(x^T, u^T, v^T)^T, z_\lambda=(x_\lambda^T, u_\lambda^T, v_\lambda^T)^T $

分别是问题2.1和问题3.1的解.则存在不依赖于 $\lambda$和 $z_\lambda$的正数 $L$, 使得

$ \parallel x-x_\lambda\parallel_2\leq L\lambda^{-k/(\xi-1)}. $

进一步, 若令$y=(u^T, v^T)^T, y_\lambda=(u_\lambda^T, v_\lambda^T)^T$, 则有$\lim\limits_{\lambda\rightarrow+\infty}y_\lambda=y $.

证  将 $z-z_\lambda$分解如下

$ z-z_\lambda=z-\left( \begin{array}{c} 0\\ 0\\ {[v_\lambda]_+}\end{array} \right)+\left( \begin{array}{c} -x_\lambda\\ -u_\lambda\\ {[v_\lambda]_-}\end{array} \right)=r_\lambda-\left( \begin{array}{c} 0\\ 0\\ {[v_\lambda]_+}\end{array} \right), $

其中 $r_\lambda=z+(-x_\lambda^T, -u_\lambda^T, [v_\lambda]_-^T)^T$, 注意到 $z-r_\lambda=(x_\lambda^T, u_\lambda^T, -[v_\lambda]_-^T)^T\in K_1$, 用 $z-r_\lambda$替换(2.2) 式中的 $\omega$可得

$ \begin{equation}\label{3} -r_\lambda^TG(z)\geq 0, \end{equation} $

(4.2)

在(3.1) 式两边左乘 $r_\lambda^T$得

$ \begin{equation}\label{4} r_\lambda^TG(z_\lambda)+\lambda r_\lambda^T\Phi(z_\lambda)=0. \end{equation} $

(4.3)

将(4.2) 和(4.3) 式相加可得

$ \begin{equation}\label{5} r_\lambda^T[G(z_\lambda)-G(z)]+\lambda r_\lambda^T\Phi(z_\lambda)\geq0. \end{equation} $

(4.4)

由 $[v_\lambda]_-^T[v_\lambda]_+^{1/k}=0, v\leq0, [v_\lambda]_+^{1/k}\geq0$可得

$ r_\lambda^T\Phi(z_\lambda)=(v+[v_\lambda]_-)^T[v_\lambda]_+^{1/k}=v^T[v_\lambda]_+^{1/k}\leq0. $

结合(4.4) 式可得

$ r_\lambda^T[G(z)-G(z_\lambda)]\leq0. $

又 $[v_\lambda]_-=-v_\lambda+[v_\lambda]_+$, 有 $r_\lambda=z-z_\lambda+(0^T, 0^T, [v_\lambda]_+^T)^T$, 则上面的不等式变为

$ (z-z_\lambda)^T[G(z)-G(z_\lambda)]\leq-[v_\lambda]_+^TC(x-x_\lambda). $

再由引理2.1和引理4.1, 以及上述不等式, 并利用Cauchy-Schwarz不等式, 有

$ \alpha {\parallel x-x_\lambda \parallel}^\xi_2\leq\parallel[v_\lambda]_+\parallel_2\cdot \parallel C\parallel_2\cdot\parallel x-x_\lambda\parallel_2\leq M_0\lambda^{-k}\parallel C\parallel_2\cdot\parallel x-x_\lambda\parallel_2. $

即

$ \parallel x-x_\lambda \parallel_2\leq (\alpha^{-1}M_0\parallel C\parallel_2)^{1/(\xi-1)}\lambda^{-k/(\xi-1)}=L\lambda^{-k/(\xi-1)}, $

其中 $L=(\alpha^{-1}M_0\parallel C\parallel_2)^{1/(\xi-1)}$, $M_0$是引理4.1中所定义的正数.

注意到 $z, z_\lambda$分别是问题2.1和问题3.1的解, 即分别满足

$ 0=F(x)-A^Tu-C^Tv=F(x)-B^Ty, \quad 0=F(x_\lambda)-A^Tu_\lambda-C^Tv_\lambda=F(x_\lambda)-B^Ty_\lambda, $

其中 $B=(A^T, C^T)^T$.两式相减便有

$ F(x)-F(x_\lambda)=B^T(y-y_\lambda). $

又因 $B$是行满秩矩阵, 故有

$ \begin{equation}\label{6} y-y_\lambda=(BB^T)^{-1}B[F(x)-F(x_\lambda)]. \end{equation} $

(4.5)

再由定理的前部分结果以及函数 $F(x)$的连续性, 容易得到 $\lim\limits_{\lambda\rightarrow+\infty}(y-y_\lambda)=0$, 即

$ \lim\limits_{\lambda\rightarrow+\infty}y_\lambda=y $

这就完成了定理的证明.

所谓 $F(x)$是Hölder连续的, 是指存在常数 $\beta>0, \gamma\in(0, 1]$, 使得

$ \label{7}\parallel F(x_1)-F(x_2)\parallel_2\leq\beta\parallel x_1-x_2\parallel_2^\gamma, \quad \forall x_1, x_2\in\mathbb{R}^n. $

(4.6)

从定义中可知, 当 $\gamma=1$时, Hölder连续就是Lipschitz连续.对于Hölder连续和Lipschitz连续, 我们有下面的推论.

推论4.1  对于任意的 $\lambda\geq1$, 设 $z=(x^T, u^T, v^T)^T, z_\lambda=(x_\lambda^T, u_\lambda^T, v_\lambda^T)^T$分别是问题2.1和问题3.1的解.令 $y=(u^T, v^T)^T, y_\lambda=(u_\lambda^T, v_\lambda^T)^T$.

(1) 若 $F(x)$是Hölder连续的, 则存在不依赖于 $\lambda$和 $z_\lambda$的正数 $M_1$, 使得

$ \parallel y-y_\lambda\parallel_2\leq M_1\lambda^{-k\gamma/(\xi-1)}. $

(2) 若 $F(x)$是强单调且Lipschitz连续的, 则存在不依赖于 $\lambda$和 $z_\lambda$的正数 $M_2$, 使得

$ \parallel y-y_\lambda\parallel_2\leq M_2\lambda^{-k}. $

证  (1) 由(4.5) 式和Hölder连续的定义(4.6), 有

$ \parallel y-y_\lambda\parallel_2=\parallel(BB^T)^{-1}B\parallel_2\parallel F(x)-F(x_\lambda)\parallel_2\leq\parallel(BB^T)^{-1}B\parallel_2\beta\parallel x-x_\lambda\parallel_2^\gamma. $

再由定理4.1可得结论.

(2) 强单调即 $\xi=2$, Lipschitz连续即 $\gamma=1$, 结合定理4.1及(1) 的结果可得(2).