许多来自科学计算和工程应用的实际问题都可转化为求解一个互补问题, 如博弈论中的纳什均衡问题、弹性接触问题、经济运输问题、流体动力学的自由边界问题等^{[1, 2]}. 互补问题是数学规划、经济学、博弈论和力学等领域的研究热点之一, 它在工程和经济学中有着广泛的应用.

本文考虑以下非线性互补问题(NCP)^{[3, 4]}: 求向量$z\in {{{\Bbb R}} ^n}$使得

其中$A=(a_{ij})\in {{{\Bbb R}} ^{n \times n}}$是给定的大型稀疏矩阵, $q\in {{\Bbb R}} ^n$是给定的向量, $\phi(z): {{\Bbb R}} ^n\rightarrow {{\Bbb R}} ^n$是给定的对角可微函数, 即$\phi(z)$的第$i$个分量函数只是$z_{i}$的单变量函数

显然, 当$\phi(z)=0$时, 问题(1.1) 即退化为线性互补问题(LCP). 1981年, van Bokhoven提出了一种模数方法^[5], 将LCP转化为等价的隐式不动点方程来求解. Chen和Ye提出了一种求解$P$ -矩阵线性互补问题的Big-Gamma平滑方法^[6]. 最近, Bai建立了一种线性互补问题的基于模的矩阵分裂方法^[7], 该方法引入了矩阵分裂技术, 使其在实际计算中比现有的模方法更有效、更经济. 在文献[8] 中, Zhang提出了求解线性互补问题的基于模的两步矩阵分裂迭代法, 该方法包括一个前向和一个后向扫描. Li在文献[9] 中将基于模的矩阵分裂迭代方法推广到更一般的$H$ -矩阵线性互补问题中. 对于线性互补问题, 已经提出了各种加速的基于模的矩阵分裂迭代方法^[8-10]. 更多关于基于模的迭代方法的论著见文献[11-24], 在系统矩阵为正定矩阵或$H_{+}$ - 矩阵时, 给出了这些方法的全局收敛条件.

由于对角可微函数$\phi(z)$一般是非线性的, 因此问题(1.1) 属于非线性互补问题^[25-26]. 在线性互补问题求解方法的启发下, 可将基于模的矩阵分裂迭代法^[27]和基于模的两步矩阵分裂迭代法^[28]推广应用于求解此类非线性互补问题. 文献[29]提出了系统矩阵为$H_{+}$ -矩阵时改进的基于模的矩阵分裂算法. 文献[30] 针对一类非线性互补问题, 提出并分析了基于加速技巧的模系矩阵分裂迭代法, 给出了$H$ -矩阵NCP的分裂条件和一个较大的收敛域, 改进了基于模的矩阵分裂迭代法的收敛理论. 当$A$是$H_{+}$ -矩阵时, 文献[31]和^[32] 在分裂为$H$ -分裂或$H$ -相容分裂的假设下给出了收敛性分析.此外, 文献[32] 给出了基于模的两步加速矩阵分裂迭代方法, 该方法可以获得更高的计算效率.

本文通过给出一个较弱的条件, 证明了$H$ -矩阵非线性互补问题基于模的矩阵分裂迭代法和相应的加速方法的收敛性定理.

本文的其余部分组织如下. 第2节给出了一些有用的记号、定义和引理. 第3节, 我们对基于模的矩阵分裂迭代法进行了新的收敛性分析. 第4节给出了一些算例. 第5节是小结.

本节先简要回顾几个必要的符号和引理.

对于两个矩阵$A=(a_{ij}) \in {{\Bbb R}} ^{m\times n}$和$B=(b_{ij}) \in {{\Bbb R}} ^{m\times n}$, 称$A\geq B$ ($A>B$) 当且仅当$a_{ij}\geq b_{ij}$ ($a_{ij}>b_{ij}$) 对所有的$1\leq i\leq m$, $1\leq j\leq n$成立. $|A|=(|a_{ij}|)\geq0$表示矩阵$A\in {{\Bbb R}} ^{m\times n}$的绝对值矩阵. $|v|=(|v_{i}|)\geq0$表示向量$v\in {{\Bbb R}} ^n$的绝对值向量. $\rho(A)$表示矩阵$A=(a_{ij})\in {{{\Bbb R}} ^{n\times n}}$谱半径. 设$A=D_{A}-B_{A}$, 其中$D_{A}$和$-B_{A}$分别表示矩阵$A$的对角部分和非对角部分. 对于$v=(v_{1}, v_{2}, \cdots, v_{n})^{\rm T}\in {{{\Bbb R}} ^n}$, ${\rm diag}(v)={\rm diag}(v_{1}, v_{2}, \cdots, v_{n})$表示由分量$v_{i}$ ($i=1, 2, \cdots, n$) 构成的对角矩阵.

对于$A=(a_{ij})\in {{{\Bbb R}} ^{n\times n}}$, 其比较矩阵定义为$\langle A\rangle=(\langle a_{ij}\rangle)$, 其中

方阵$A=(a_{ij})\in {{{\Bbb R}} ^{n\times n}}$称为$Z$ -矩阵, 是指其所有非对角元都是非正的^[33]. 矩阵$A$称为$M$ -矩阵, 是指其为非奇异的$Z$ -矩阵且$A^{-1}\geq0$. 矩阵$A$称为$H$ -矩阵是指其比较阵$\langle A\rangle$是$M$ -矩阵. 若$A$是具有正对角元的$H$ -矩阵, 则称其为$H_{+}$矩阵. 若$A, B\in {{{\Bbb R}} ^{n\times n}}$都是$M$ -矩阵, 且$C\in {{{\Bbb R}} ^{n\times n}}$满足$A\leq C \leq B$, 则$C$也是$M$ - 矩阵.

对于非奇异矩阵$A\in {{{\Bbb R}} ^{n \times n}}$, 矩阵$M, N\in{{{\Bbb R}} ^{n \times n}}$满足$A=M-N$, 若$M$是非奇异的, 则称$A=M-N$为矩阵$A$的一个分裂. 称其是收敛的当且仅当$\rho(M^{-1}N)<1$. 称$A=M-N$是$M$ -分裂, 若$M$是$M$ -矩阵且$N$是非负矩阵. 称其是$H$ -分裂, 若$\langle M \rangle-|N|$是单调的(即$(\langle M \rangle-|N|)^{-1}\geq0$). 称其是$H$ -相容分裂, 若$\langle A\rangle=\langle M \rangle-|N|$成立. 显然, 若$A=M-N$是一个$M$ -分裂, 则$\rho(M^{-1}N)<1$当且仅当$A$是$M$ -矩阵^[33].

下面的引理给出了$H$ -矩阵的一个基本性质.

引理2.1^[29]   设$A\in {{\Bbb R}} ^{n\times n}$是$H$ -矩阵. 则$A$非奇异且$|A^{-1}|\leq \langle A\rangle^{-1}$.

在本节中, 我们将给出新的收敛性分析, 以改进NCP (1.1) 中当$A$为$H_{+}$ -矩阵时基于模的矩阵分裂迭代法.

为了进行下面的讨论, 我们假设$\phi(z)=(\phi_{1}(z_{1}), \phi_{2}(z_{2}), \cdots, \phi_{n}(z_{n}))^{\rm T}$连续可微且满足$0\leq \frac{{\rm d}\phi_{i}(z_{i})}{{\rm d}z_{i}} \leq \psi_{i}$, 其中$\psi_{i}\in {{\Bbb R}} , i=1, 2, \cdots, n$. 由中值定理可知, 存在$\zeta_{i}^{(k)}\in {{\Bbb R}}$, 使得

令

和$\Psi={\rm diag}(\psi_{1}, \psi_{2}, \cdots, \psi_{n})$. 则有

取$z=\frac{1}{h}(|x|+x)$, $f(z)=\frac{1}{h}\Omega(|x|-x)$及$A=M-N$, NCP (1.1) 能等价地转换成下列不动点方程

其中$\Omega$是正对角矩阵, $h$是正常数. 基于(3.2) 式, Huang和Ma提出了基于模的矩阵分裂迭代法^[29]如下.

算法3.1  设$A=M-N$是$A$的一个分裂. 给定初始向量$x^{(0)}\in{{{\Bbb R}} ^n}$, 对$k=1, 2, \cdots$进行迭代直到序列$\{z^{(k)}\}_{k=1}^{+\infty}\subset{{{\Bbb R}} ^n}$收敛, 通过解下列方程组得到$x^{(k)}\in{{{\Bbb R}} ^n}$:

这里$\Omega$是$n\times n$正对角矩阵, $h$是正常数.令

在文献[31] 中, Zheng针对$A=M-N$是$H$ -分裂的$H$ -矩阵非线性互补问题, 提出了基于模的矩阵迭代方法的一个新的收敛定理. 然而, 通过验证, 我们发现收敛条件可以减弱到$\langle M \rangle-|N|+\Omega$是$M$ -矩阵, 其中${\rm diag}(M)>0$. 这个条件也保证了算法3.1生成的迭代序列$\{z^{(k)}\}^{+\infty}_{k=1}$对任何初始向量$x^{(0)}\in {{\Bbb R}} ^n$都收敛于问题(1.1) 的唯一解$z^{*}$. 新的收敛定理如下:

定理3.1   设$A$是$H_{+}$ -矩阵, $A=M-N$是$A$的一个分裂且${\rm diag}(M)>0$及(3.1) 式对任意的$\Psi^{(k)}$成立. 假定$\Omega\geq D_{M}+\Psi$和$\langle M \rangle-|N|+\Omega$是$M$ -矩阵. 那么由算法3.1生成的迭代序列$\{z^{(k)}\}^{+\infty}_{k=1}$对任意的初始向量$x^{(0)}\in {{\Bbb R}} ^n$均收敛到问题(1.1) 的唯一解$z^{*}$.

证  设$z^{*}$是问题(1.1) 的一个解, 则有$x^{*}=\frac{h}{2}(z^{*}-\Omega^{-1}f(z^{*}))$, 因而有

要证$\lim \limits _{k\rightarrow +\infty}z^{(k)}=z^{*}$, 只需证明$\lim \limits _{k\rightarrow +\infty}x^{(k)}=x^{*}$. 注意到$\langle M \rangle-|N|+\Omega$是$M$ -矩阵, 可推得$\langle M \rangle+\Omega$也是$M$ -矩阵. 据此及$m_{ii}>0$$(i=1, 2, \cdots, n)$可知$\Omega+M$是$H_{+}$ -矩阵. 因此, 有

利用(3.5) 式和$||x^{(k)}|-|x_{*}||\leq|x^{(k)}-x_{*}|$, 由(3.4) 式可得

令$\Gamma_{1}=\tilde{M}-\tilde{N}$, $\tilde{M}=\Omega+ \langle M\rangle$, $\tilde{N}_{1}=|N-\Psi^{(k)}|+|\Omega-M-\Psi^{(k)}|+|N|$. 若$\Omega\geq D_{M}+\Psi$, 则有

不难发现, $\tilde{M}$是$M$ -矩阵且$\tilde{M}-\tilde{N}$是$Z$ -矩阵. 根据$M$ -矩阵的性质, 可知$\tilde{M}-\tilde{N}$也是$M$ -矩阵. 注意到$\tilde{M}$是$M$ -矩阵及$\tilde{N}\geq0$, 可得$\Gamma_{1}=\tilde{M}-\tilde{N}$是一个$M$ -分裂. 故有$\rho(\tilde{M}^{-1}\tilde{N})<1$, 即$\lim \limits _{k\rightarrow +\infty}x^{(k)}=x^{*}$.

注3.1  注意到$A=M-N$是一个$H$ -分裂, 这意味着$\langle M \rangle-|N|+\Omega$是一个$M$ -矩阵. 但反之不然. 例如: 设

由$M$矩阵的定义, 易知$\langle M\rangle-|N|+\Omega$是$M$ -矩阵, 但

不是$M$ -矩阵. 因此, 假设条件"$A=M-N$是一个分裂且${\rm diag}(M)>0$及$\langle M\rangle-|N|+\Omega$是$M$ -矩阵"要比文献[31, 定理3.1] 的条件弱.

在算法3.1中, 每次迭代都需要求解线性方程组(3.3). 在实际执行过程中要得到精确解几乎是不现实的, 特别是对于大型稀疏线性方程组. 因此, 用加速迭代法近似求解(3.3) 是比较理想的选择. 注意到, 若$A=M_{1}-N_{1}=M_{2}-N_{2}$是$A$的两个分裂, 我们可以将问题(1.1) 重新表述为以下隐式不动点方程

其中$z=\frac{1}{h}(|x|+x)$, $\phi(z)=\frac{1}{h}\Omega(|x|-x)$. 这种策略得到了NCP的加速迭代法. 关于加速迭代法的更多细节可参见文献[32].

算法3.2   设$A=M_{1}-N_{1}=M_{2}-N_{2}$是矩阵$A\in {{\Bbb R}} ^{n \times n}$的两个分裂, $\Omega$是一个$nn$阶正对角矩阵, $h$是正常数. 给定处世向量$x^{0}\in {{\Bbb R}} ^n$, 计算$z^{(0)}=\frac{1}{h}(|x^{(0)}|+x^{(0)})$. 对于$k=0, 1, 2, \cdots,$进行迭代直到序列$\{z^{(k)}\}_{k=0}^{\infty}$收敛, 通过解下列方程组得到$x^{(k+1)}\in {{\Bbb R}} ^n$:

并设

在下文中, 我们给出了当系统矩阵$A$是$H_{+}$ -矩阵时算法3.2的收敛性分析.

定理3.2   设$A\in {{\Bbb R}} ^{n\times n}$是$H_{+}$ -矩阵, $A=M_{1}-N_{1}=M_{2}-N_{2}$矩阵$A$的两个分裂, 其中$M_{1}=(m_{ij}^{(1)}), M_{2}=(m_{ij}^{(2)}) \in {{\Bbb R}} ^{n\times n}$. 设$A=D-B$是$A$的一个分裂, 其中$D$, $-B$分别是它的对角部分和非对角部分. 假定$\Omega$是一个正对角矩阵, $h$是一个正常数. 那么, 由算法3.2生成的迭代序列$\{z^{(k)}\}_{k=0}^{\infty}\subseteq {{\Bbb R}} _{+}^{n}$对任何初始向量$x^{(0)}\in {{\Bbb R}} ^n$均收敛到问题(1.1) 的唯一解$z^{*}\in {{\Bbb R}} _{+}^{n}$, 只要下列条件之一被满足:

(a) 当$\Omega\geq {\rm diag} (M_{2})+\Psi$, $A=M_{1}-N_{1}=M_{2}-N_{2}$是$A$的两个$H$ -分裂, $\langle M_{1}\rangle+\Omega-|N_{2}|$是一个$M$ -矩阵.

(b) 当$\Omega\geq {\rm diag (M_{2})}$, $M_{1}$的对角元是正的, $\langle A\rangle-\Psi$和$\langle M_{1}\rangle+\Omega-|N_{2}|$是$M$ -矩阵.

证   (a) 首先证明$M_{1}+\Omega$是$H_{+}$ -矩阵. 事实上, 因$A=M-N$是$H$ -分裂, 即$\langle M_{1}\rangle-|N_{1}|$是单调的, 于是有$|m_{ii}^{(1)}|-|n_{ii}^{(1)}|>0$. 再注意到$A$是$H_{+}$ -矩阵, 可得$a_{ii}=m_{ii}^{(1)}-n_{ii}^{(1)}>0$. 因此有$m_{ii}^{(1)}>0, i=1, 2, \cdots, n$. 由于$\langle M_{1}\rangle-|N_{1}|$是$M$ -矩阵且$\Omega$是正对角矩阵, 我们有

根据$M$ -矩阵的性质, $M_{1}$和$M_{1}+\Omega$都是$H_{+}$ -矩阵且由引理2.1有

结合(3.8) 和(3.9) 式可得

由于$z=\frac{1}{h}(|x|+x)$, 可得

将(3.11) 式代入(3.10) 式, 我们有

经过简单的计算, (3.12) 式是可重写为

因为$\langle M_{1}\rangle+\Omega-|N_{2}|$是$M$ -矩阵, $\langle M_{1}\rangle+\Omega$也是$M$ -矩阵, 因此分裂$\langle M_{1}\rangle+\Omega-|N_{2}|$是一个$M$ -分裂且$\rho((\langle M_{1}\rangle+\Omega)^{-1}|N_{2}|)<1$. 于是, 若$I-(\langle M_{1}\rangle+\Omega)^{-1}|N_{2}|$是$M$ -矩阵且它的逆是非负的, 则

令$\Gamma_{2}=\hat{M}-\hat{N}$, $\hat{M}=\langle M_{1} \rangle+\Omega-|N_{2}|$, $\hat{N}=|N_{1}-\Psi^{(k)}|+|\Omega-M_{2}-\Psi^{(k)}|$, 经过简单的计算, 立即可得

因$\langle M_{1} \rangle-|N_{1}|$和$\langle M_{2} \rangle-|N_{2}|$都是$M$ -矩阵, 分裂$\Gamma_{2}=\hat{M}-\hat{N}$是$M$ -分裂, 因此$\rho(\hat{M}^{-1}\hat{N})<1$, 即$\lim \limits _{k\rightarrow +\infty}x^{(k)}=x^{*}$.

(b) 类似地, 我们证明$M_{1}+\Omega$是一个$H_{+}$ -矩阵. 因$M_{1}$的对角元是正的且$\langle M_{1}\rangle+\Omega-|N_{2}|$是$M$ - 矩阵, 可知$\langle M_{1}\rangle+\Omega$是$M$ -矩阵且$M_{1}+\Omega$是$H_{+}$ -矩阵. 故(3.10) 式成立.

由于$h>0$, 我们有

结合(3.15) 和(3.10)式, 我们有

注意到(3.16) 式可以重写为

由前面的分析, 立即可得

令$\Gamma_{3}=\bar{M}-\bar{N}$, $\bar{M}=\langle M_{1} \rangle+\Omega-|N_{2}|$, $\bar{N}=|N_{1}|+|\Omega-M_{2}|+2\Psi$, 经过简单的计算, 立得

因此, 若$\Omega \geq {\rm diag}(M_{2})$且$\langle A \rangle-\Psi$是$M$ -矩阵, 则分裂$\Gamma_{3}=\bar{M}-\bar{N}$是一个$M$ -分裂, 故$\rho(\bar{M}^{-1}\bar{N})<1$, 从而$\lim \limits _{k\rightarrow +\infty}x^{(k)}=x^{*}$. 证毕.

注3.2  虽然在条件${\rm (a)}$中, 矩阵$A=M_{1}-N_{1}=M_{2}-N_{2}$的分裂必须是$H$ -分裂, 但是${\rm NCP}$的系统矩阵$A$可以是任何$H_{+}$ -矩阵. 但在条件${\rm (b)}$下, 矩阵$A$应满足$\langle A \rangle -\Psi$是$M$ -矩阵, 即算法$3.2$的收敛结果与条件${\rm (b)}$下函数$\phi(z)$的选取有关.

注3.3  对于文献[32] 中基于模的矩阵分裂加速迭代法, 当矩阵$A$为$H_{+}$ -矩阵时, 要求$A=M_{1}-N_{1}=M_{2}-N_{2}$为$H$ -相容分裂, 且$\langle A \rangle +\Psi$和$\Omega+M_{1}-|N_{2}|$$M$ -矩阵. 因此, 算法3.2的分裂$A=M-N$被减弱. 这意味着对于分裂$A=M-N$有更多的选择使得基于模的矩阵分裂迭代方法收敛.

本节将提供一些数值例子来验证新定理的理论分析. 实验结果中, "Iter"表示迭代步数, "CPU"表示所耗费的计算时间, "Res"表示残差向量的模, 即

其中min算子是按分量取极小. 在所有的算例中, 随机选取初始向量$x^{(0)}$, 取$h=2$. 实验环境是Windows 10操作系统, CPU 3.19GHz (Intel(R) Core(TM) i5-6500), 8 GB内存. 软件平台是MATLAB 7.0. 终止准则是: Res$(z^{(k)})<10^{-5}$或迭代次数$k$达到1000.

例4.1   求向量$z\in {{{\Bbb R}} ^n}$使得

其中

非线性函数$\phi(z)$取如下不同的表达式$:$

$(1)$$\phi_1(z)=|z|=(|z_{1}|, |z_{2}|, \cdots, |z_{n}|)^{T};$

$(2)$$\phi_2(z)=z^{*}$, 其中$z^{*}_{i}=\left\{ \begin{array}{cc} z_{i}, & 0\leq z_{i}\leq\frac{1}{2} , \\ 1-z_{i}, & \frac{1}{2}<z_{i}\leq1 \\ 1+z_{i}, & z_{i}>1, \\ \end{array} \right., i=1, 2, \cdots, n;$

$(3)$$\phi_3(z)=(z_{1}-\sin z_{1}, z_{2}-\sin z_{2}, \cdots, z_{n}-\sin z_{n})^{T};$

$(4)$$\phi_4(z)=(\arctan z_{1}, \arctan z_{2}, \cdots, \arctan z_{n})^{T};$

$(5)$$\phi_5(z)=(\frac{z_{1}}{1+z_{1}}, \frac{z_{2}}{1+z_{2}}, \cdots, \frac{z_{n}}{1+z_{n}})^{T}$.

取$n=200, \Omega=20I$, $A=M-N$, 其中

实验结果见表 1.

例4.2  求$z\in {{{\Bbb R}} ^{2}}$使得

其中

令

利用算法3.2, 迭代17次即可获得原问题满足终止准则的近似解. 此外, 不难发现, $A=M_1-N_1=M_2-N_2$是$H$ -相容分裂, $\langle M_1\rangle-|N_2|+\Omega$是$M$ -矩阵. 例4.2的结果说明了定理3.2的优越性.

例4.3   问题的矩阵$A$与例$4.1$相同. 非线性函数$\phi(z)$取为

考虑$A=M_1-N_1=M_2-N_2$, 其中

不难发现, 这两个分裂都是$H$ -相容分裂. 选取$\Psi$为单位矩阵. 情形1: 取$\Omega=D_{M_2}+\Psi$, 则$\langle M_1\rangle+\Omega-|N_2|$是$M$ -矩阵. 情形2: 取$\Omega=D_{M_2}$, 则$\langle A\rangle-\Psi$和$\langle M_1\rangle+\Omega-|N_2|$是$M$ -矩阵. 实验结果见表 2. 实验结果表明, 定理3.2的假设条件是合适的.

定理3.1给出了在较弱条件下求解非线性互补问题的基于模的矩阵分裂迭代方法的收敛理论. 由于$\langle M \rangle-|N|+\Omega$是一个$M$ -矩阵, 它不一定是$A$的$H$ -分裂, 所以当我们使用基于模的矩阵分割迭代法求解NCP时, 存在一种分裂, 它不必是$H$ -分裂, 使迭代法收敛.

同样, 定理3.2也改进了基于加速模的矩阵分裂迭代法在新条件下的收敛性理论. 这表明对分裂$A=M-N$有更多的选择使得基于模的矩阵分裂迭代方法收敛. 因此, 本文的收敛理论扩展了基于模的矩阵分裂迭代方法的应用范围.