线性互补问题的数值分析

黎　稳，郑　华

（1.华南师范大学数学科学学院，广州510631；2.韶关学院数学与统计学院，韶关512005）

线性互补问题的数值分析

黎稳1*，郑华1，2

（1.华南师范大学数学科学学院，广州510631；2.韶关学院数学与统计学院，韶关512005）

综述了线性互补问题理论的最新发展和已有成果，包括线性互补问题的数值解法，特别是模基矩阵分析算法、误差分析以及扰动分析.给出了线性互补问题的数学问题形式、数学模型以及相关概念；介绍了求解线性互补问题的各种数值解法，其中重点关注迭代法特别是近年来比较热门的模基矩阵分裂迭代法，基于模方程通过运用非光滑Newton法的思想，给出了模基非光滑Newton法，新算法比已有的模基矩阵分裂迭代法收敛更快；给出了线性互补问题解的误差分析，介绍了已有的几个误差界结果，包括运用预处理技术得到的更好的新误差界.同时介绍了线性互补问题解扰动分析的结果及目前最新的扰动界.

线性互补问题；模基方法；误差分析；扰动分析

在这里，对于任意的m×n矩阵B=（bij）和C=（cij），B≥C的定义为:对任意的i，j，bij≥cij.

线性互补问题简记为LCP（q，A）.可见，向量r，z满足rizi=0（i=1，2，…，n）.这表明了两组变量ri和zi满足互补关系.

线性互补问题在实际中有着广泛的应用.早期的线性互补问题主要来源于线性规划、二次规划和双矩阵对策的研究，这3类问题都是线性互补问题的特例.例如，考虑二次规划:

定义:

显然，式（3）即转化为式（1）.

线性互补问题还与最优化、变分不等式、平衡问题、对策论和不动点理论等数学分支紧密联系，使线性互补问题成为数学规划的一个十分热门的研究课题.随着对线性互补问题理论和算法研究的不断发展和日益完善，其应用逐渐扩展到力学、交通、经济、金融和控制等领域，其中包括了最优停止问题、期权定价问题、市场均衡问题、自由边界问题和弹性接触问题等，详见文献［1］-［3］以及其中的参考文献.

对线性互补问题的研究分为基本理论和数值算法两部分.在基本理论部分，主要研究解的存在性、唯一性、稳定性和灵敏度分析，以及线性互补问题与其他数学问题的联系.关于线性互补问题解的存在唯一性问题，已经有了明确的结论.近年来，基本理论方面的研究热点是对解的误差分析以及扰动分析.对于数值解法，则主要建立有效的求解方法以及相应的算法理论分析.线性互补问题的数值解法主要有直接法和迭代法两大类.直接法一般用于求解中小型的线性互补问题，具有求解速度快以及解的精度高等优点.迭代法适用于工程应用中出现的大型稀疏线性互补问题，其在计算过程中能保持矩阵的稀疏结构，使用较小的存储空间，求解速度快，和直接法相比具有稳定性和可行性.

以下是一些基本概念和已知结论.如果A满足对i≠j，有aij≤0，则称A为Z-矩阵；如果A满足对x≠0，有xi（Ax）i＞0（1≤i≤n），则称A为P-矩阵；如果A是Z-矩阵，并且满足A-1≥0，则称A为M-矩阵；矩阵A的比较矩阵〈A〉=（a'ij）的定义为如果〈A〉是M-矩阵，则称A为H-矩阵［4］.对任意的qn，式（1）存在唯一解的充要条件是A为P-矩阵.H+-矩阵一定是P-矩阵.M-矩阵一定是H-矩阵［1］.具有正对角元的 H矩阵称为 H+矩阵［5］.如果M非奇异，则称A=M-N是矩阵A的一个分裂.如果M是M-矩阵且N≥0，则称A=MN是矩阵A的一个M-分裂［4］.如果〈M〉-|N|是M-矩阵，则称A=M-N是矩阵A的一个H-分裂［6］.如果〈A〉=〈M〉-|N|，则称A=M-N是矩阵A的一个H-相容分裂.M-分裂必是H-相容分裂.H-相容分裂必是H-分裂，反之不成立［7］.设ci=max｛0，aij|∀i≠j｝（i=1，2，…，n），e表示分量全为1的n维列向量，C=diag（c）eeT，如果B=A-C是M-矩阵，则称A为MB-矩阵.MB-矩阵必是P-矩阵，但不一定是H-矩阵［8］.

本文总结了一些常用的求解线性互补问题的数值解法，特别关注近几年出现的模基矩阵分裂迭代方法及其推广；归纳了线性互补问题解的误差分析结果，特别是我们得到的最新误差界；总结了线性互补问题解的扰动分析结果；给出了结论和对未来研究工作的展望.

1　数值解法

线性互补问题从诞生之日起，其数值解法一直受到众多学者的重视.尤其是20世纪80年代中后期前，Lemke的转轴法和Cottle、Dantzig的主元转轴法等是非常著名的直接法，对于这一时期关于线性互补问题的研究成果，文献［1］给出了详尽的介绍.因为工程应用中大型稀疏问题的求解需要，20世纪80年代末期起，线性互补问题的数值解法进入了一个新的高潮，出现了很多迭代方法.早期的迭代方法包括:投影法、内点法、非光滑Newton法以及光滑化Newton法.这些方法都是伴随着对非线性互补问题的研究得到的，它们的详细研究成果可参看文献［3］及其参考文献.近年来出现了一类基于模方程［9］的迭代法，尤其是Bai［10］提出的模基矩阵分裂迭代法及其推广变形，经过不断改进发展，在实际应用中非常有效.本节主要介绍各种迭代法.

1.1投影法

投影法源于Goldstein［11］、Levitin和Polyak［12］求解凸约束优化问题的投影梯度法，包括著名的外梯度法、逐点逼近法和矩阵分裂法等，这里简单介绍其中的矩阵分裂法.

首先引入投影的概念.

定义1给定n中一个非空闭凸子集X，定义一点yn到X上的投影为

考虑矩阵A的分裂A=M-N，利用投影构造出一系列的线性互补问题，进而得到收敛于原线性互补问题真实解的向量序列，这种方法称为矩阵分裂法:

算法1 设A=M-N是A的一个分裂，任给初始向量z（0），对于k=1，2，…，计算q（k）=Nz（k）+ q，并且计算序列z（k）直到其收敛，其中

在算法1中，选取A不同的分裂会导出不同的迭代格式，常用的分裂为经典的Jacobi、Gauss-seidel、SOR等.关于投影法的详尽介绍可以参看文献［1］、［3］以及其中的参考文献.

1.2内点法

内点法的基本思想是把线性互补问题转化为一个与之等价的非负约束方程组，然后用Newton类方法求解.

式（4）是一个带有非负约束且具有特殊结构的2n阶非线性方程组，正是因为这种特殊性，才导致了内点法能获得极大成功.运用Newton类方法求解式（4），根据每次迭代搜索方向和步长的选取不同，常见的内点法有路径跟踪法、势缩减法、预测校正法和不可行内点法等［3，13］.

1.3Newton类方法

求解线性互补问题的Newton类方法分为非光滑Newton法和光滑化Newton法.两者都是引进势函数把线性互补问题转化为一个与之等价的非光滑方程组，对于这个等价的方程组，非光滑Newton法的思想是直接用非光滑Newton法求解，而光滑化Newton法的思想是寻找一个光滑的函数列来逼近原来的非光滑函数，然后通过用光滑Newton法求近似问题的解来逼近原问题的解.

首先给出势函数的定义:

定义2设函数φ:2→，如果它具有性质:

则称φ为一个势函数.

由此，式（1）可以转化为以下方程组:

常用的势函数有φ（a，b）=min（a，b）以及φ（a，b）=等.

注意到式（5）中的Φ（z）并不是可微函数，不能用传统的光滑Newton法直接求解.引入Clarke意义下的广义Jacobian矩阵［14］，Qi和Sun［15］给出了非光滑Newton法，因此其中一个求解思路是运用非光滑Newton法求解式（5）.另一个求解思路是寻找一个光滑的函数列Φk（z），满足，然后用光滑的Newton法求解Φk（z）=0得到解的序列，当k充分大时取zk为近似解.关于这2类方法的详细讨论可以参看文献［3］以及其中的参考文献.

1.4模基迭代方法

模基迭代方法在1981年由Van Bokhoven［9］提出，其思想是把线性互补问题等价地转化成一个模方程，然后针对模方程设计迭代方法.经过近30年的研究，特别是Bai［10］引入矩阵分裂思想后，这类方法得到了快速的发展，现已成为求解线性互补问题的一种简单高效实用的求解方法，本节的内容主要来源于文献［16］及其参考文献和我们得到的结果.

1.4.1模迭代方法及其改进Van Bokhoven［9］利用式（1）中z和r各分量之间的互补性质，令z=|x|+ x，r=|x|-x，将式（1）等价地转化为一个不动点方程组

容易得到，如果x是式（6）的解，那么z=|x|+x，r=|x|-x是式（1）的解；反之，如果z，r是式（1）的解，那么x=（z-r）/2是式（6）的解.由式（6）马上可以构造求解式（1）的模迭代方法:

关于算法2有以下的收敛定理［2，17，9］:

为了加快模迭代方法的收敛速度，Dong和Jiang［18］引入移位因子α＞0，把式（7）的迭代格式推广为:

由此得到了改进的模迭代方法.他们对参数α的选取方式做了理论分析.其他的加速方法可参考Hadjidimos和Tzoumas［19］提出的非定常外推模迭代方法.

1.4.2模基矩阵分裂迭代方法及其推广在式（1）中，引进正对角矩阵Ω1、Ω2、Γ，为了更高效求解式（8），把A分裂为A=M-N.由此得到如下引理:

引理1［10］设A=M-N是矩阵A的一个分裂，Ω1、Ω2和Γ为正对角矩阵，记Ω=Ω1+Ω2，下列结论成立:

（i）如果z和r是式（1）的解，那么x=（Γ-1z-Ω-1r）/2是下列方程的解:

（ii）如果x是式（8）的解，那么z=Γ（|x|+x）和r=Ω（|x|-x）是式（1）的解.

基于引理1，Bai［10］取Ω=Ω2，Ω1=0，Γ=I/γ，其中γ是正常数，提出了:

算法3［10］（模基矩阵分裂迭代方法）选取初始向量x（0）n，对于k=1，2，…，计算序列z（k）=（|x（k）|+x（k））/γ直到其收敛，其中x（k）是以下方程组的解:

算法3不但包含了模迭代方法［9］、改进的模迭代方法［18］以及非定常外推模迭代方法［19］，而且在每一步迭代的时候可以选取适当的分裂A=M-N，使得式（9）易于求解，从而提高求解效率.例如，记D、-L和-U分别是A的对角部分、严格下三角部分和严格上三角部分，令

便得到了模基AOR（MAOR）迭代方法，若参数（α，β）分别取为（α，α）、（1，1）和（1，0），就分别得到模基SOR迭代方法（MSOR）、模基Gauss-Seidel迭代方法（MGS）和模基Jacobi迭代方法（MJ）.

对于算法3，有如下收敛性定理［10］:

注1Zhang和Ren［7］把定理2中“H-相容分裂”的条件减弱为“H-分裂”，其他条件不变，也得到了和定理2相同的结论.

同样基于引理1，我们考虑了比式（9）更一般的迭代格式，提出如下算法:

算法4［20］（广义模基矩阵分裂迭代方法）给定正对角矩阵Ω1、Ω2n×n，设AΩ1=MΩ1-NΩ1是矩阵AΩ的一个分裂，选取初始向量x（0）n1，对于k=1，2，…，计算序列z（k）=Ω1（|x（k）|+x（k））直到其收敛，其中x（k）是以下方程组的解:

易见，在式（10）中令Ω1=I/γ，Ω2=Ω/γ，MΩ1=M/γ，NΩ1=N/γ，算法4转化为算法3.关于算法4，有如下收敛性定理:

定理3［20］设An×n为 H+矩阵，DA=diag（A），AΩ1=MΩ1-NΩ1是H-分裂，则对于任意的初始向量x（0）n，算法4产生的迭代序列均收敛到式（1）的唯一解z*的充分条件是:

这里D是使得（〈MΩ1〉-|NΩ1|）D严格对角占优的正对角矩阵.

注2从式（11）可见，算法4中对于正对角矩阵的收敛域比文献［11］给出的更大.

1.4.3模基多分裂迭代方法把模基矩阵分裂迭代法和高性能并行技术相结合，就得到模基多分裂迭代方法.其思想是利用矩阵的多分裂技巧，将式（1）等价转化为适用于并行计算的一组不动点方程组，这样在每次迭代中让一个处理器求解一个小规模的不动点方程组，从而提高求解问题的规模和节省运算时间.

矩阵多分裂的定义是:

定义3［21-22］设An×n，l（l≤n）是正整数，如果A=Ms-Ns（s=1，2，…，l）是A的分裂，Ek，则称（Ms， Ns，Es）（s=1，2，…，l）为矩阵A的一个多分裂，其n×n是非负对角矩阵且满足中Es称为权重矩阵.

设（Ms，Ns，Es）（s=1，2，…，l）为矩阵A的一个多分裂，对于给定的正对角矩阵Ω以及正常数γ，由引理1可以得到，如果x满足

是式（1）的解.由此Bai和Zhang［23］提出了:

注3当l=1时，算法5即为算法3.

算法5具有很好的并行计算性质，能够在多处理器系统上实现，具体可以通过合理地选择分裂矩阵Ms（s=1，2，…，l）和权重矩阵Es（s=1，2，…，l），使得多处理器系统中每一个处理器承载的任务比较均衡，从而使得算法能达到较高的并行计算效率.

关于算法5，有如下的收敛性结果［23］:

跟模基矩阵分裂迭代方法类似，如果选取每个分裂为Jacobi分裂、Gauss-Seidel分裂、SOR分裂以及AOR分裂，就可以得到相应版本的模基同步多分裂迭代方法［23］.

为了提高并行计算的求解效率，算法5可以做进一步的改进，相关的方法简介如下:

（1）因为算法5的每一步需要精确求解一组线性子系统，这可能会非常耗时和占用大量存储空间，为此考虑引入内迭代来近似求解这些子问题，可以提高求解效率.基于这种想法，Bai和Zhang［24］考虑在内外迭代都使用模基分裂技术，提出了模基同步二级多分裂迭代方法.

（2）使用二级多分裂方法，内迭代选择为模基分裂技术，外迭代则采用矩阵多分裂技巧，将式（1）的求解转化为求解一系列的线性互补子问题［5，25-26］.基于这种想法，Zhang［27］提出了同步二级多分裂迭代方法.

（3）为了在每一次迭代中充分利用前一次迭代和信息交换的结果，减少各进程间信息传递的次数，Zhang［28-29］提出了两步模基分裂和多分裂迭代方法，其优势在于每一步迭代都包含了前推和回代过程，从而提高计算效率.

1.4.4模基非光滑Newton法基于模方程（6），我们考虑直接用非光滑的Newton法求解，得到了:

算法6［30］（模基非光滑Newton法）记F（x）（A+I）x+（A-I）|x|+q.给定初始向量x（0），通过以下迭代得到序列直到收敛:

其中Vk是F（x）在x（k）处的广义Jacobian矩阵［14］:

关于算法6的可行性，我们证明了如果A为P-矩阵，那么广义Jacobian矩阵Vk非奇异［30］.

Qi和Sun［15］证明了非光滑Newton法的局部平方收敛性质，算法6的实现还需要确定初始向量以及广义Jacobian矩阵（即β的选择）.关于这2个问题，我们给出了相关结果［30］:

（1）初始向量选取要保证与式（6）真实解向量的各分量符号一致，这可以通过引入算法3迭代若干步后得到.

（2）一旦得到我们想要的初始向量，可以证明特殊选取的广义Jacobian矩阵能让算法6达到1步收敛.

2　误差分析

对线性互补问题解的误差分析，是指研究任意的近似向量（比如迭代向量）与线性互补问题真实解之间的接近程度，也就是得到相应的误差界.

容易得到，z*是式（1）的解当且仅当z*是下列方程的解:

其中“min”是针对向量的对应位置分量取最小.结合上述定义的残量函数r（z），当A为P矩阵或者H矩阵时，20世纪90年代开始，许多学者利用不同的方法陆续给出了关于式（1）的误差界［1，31-39］，其中包含了针对特殊的DB-矩阵［8］、SB-矩阵［8］和MB-矩阵的误差界结果［37-39］.

Chen和Xiang［34］考虑最小值函数的等价变形，得到了如下误差界:

可以证明式（12）比之前文献出现的误差界要小.误差界（12）的缺点是最小化问题很难求解.在A为特殊矩阵时，Chen和Xiang［34］给出了相应可计算的各种误差界.例如，当A为M-矩阵时有:

Garcia-Esnaola和Pena［35］引进一个正对角矩阵Ω=diag（w1，w2，…，wn），使得AΩ为严格对角占优，进而得到如下可计算的误差界:

在文献［36］中，我们利用等价的LCP给出原来LCP的误差分析，从而改进已有的Chen和Xiang［34］的结果.设Ω和～Ω是n阶正对角矩阵，考虑如下线性互补问题:

注意到z是式（1）的解当且仅当Ω-1z是式（15）的解.由此，可以得到新的误差界:

注4当Ω=～Ω=I时，式（16）简化为误差界（12）.这表明，通过适当选择参数矩阵Ω和～Ω，我们可以得到更好的误差界（16）.

另一方面，误差界（16）存在难以计算的问题，为了得到可计算的误差界，在A为特殊矩阵的情况下，通过适当选取Ω和～Ω，可以减小界（16）的计算复杂度.

考虑A为M-矩阵的情形，我们得到:

（3）当Ω=diag（A-1e），Ω～=I时，

注5通过进一步的讨论，我们得到的以上各种误差界在数值实现上计算复杂性不大，数值例子表明我们得到的误差界比文献［34］以及文献［35］的误差界要更小［36］.

进一步考虑A为MB-矩阵的情形.该类矩阵是P-矩阵，但不一定是H-矩阵，是比SB-矩阵更广的一类矩阵，具体可参考文献［39］.

由式（15）可以推出如下误差界结果:

定理5［39］设A=B+C为MB-矩阵，则存在正对角矩阵H=diag｛h1，h2，…，hn｝，使得:

其中Ω=diag｛w1，w2，…，wn｝和～Ω=diag｛～1，～2，…，～wn｝是正对角矩阵，

我们给出了矩阵 H的选取方式［39］，基于式（18），通过选取不同的参数矩阵Ω和～Ω，可以得到不同形式的误差界.以下列举其中几个结果:

（1）当Ω=～Ω=I时，

数值例子表明，以上几个误差界比文献［37］和文献［38］中得到的误差界更小［39］.

3　扰动分析

对线性互补问题的扰动分析，是指当矩阵A和向量q的数据有扰动时，研究线性互补问题解的变化情况，通常给出解的扰动界.

Mathias和Pang［31］引进了P-矩阵的一个度量函数

使用上述函数c（A），Cottle等［1］给出了式（1）的扰动结果:

定理6对于线性互补问题以及带线性互补约束的数学规划问题的研究起着重要的作用，但是缺点在于度量函数c（A）难以计算，并且参数c0的大小并不明确，因此难以用来对式（1）做扰动分析.

考虑在文献［34］中所用到过的一个结论:

引理2对于任给的x，x*，y，y*n，有

Chen和Xiang［40］结合引理2，给出了新的扰动界结果:

Chen和 Xiang［40］证明了当A为 P-矩阵时，βp（A）≤1/c（A），并且明显可以看出式（20）与式（19）相比形式上更明确，这表明定理7的扰动界比定理6的扰动界要更好.

更进一步，得到了相对扰动界结果:

定理8［40］设An×n为P-矩阵，则对任意的BM以及bn满足‖q-b‖p≤ε‖（-q）+‖p，有

以定理7为基础，当A取为特殊矩阵时，可以得到相应形式更简洁的结果［40］:

（1）当A为H+-矩阵时，βp（A）≤‖〈A〉-1‖p.

（2）当A为M-矩阵时，βp（A）=‖A-1‖p.

（3）当A为对称正定矩阵时，β2（A）=‖A-1‖2.

注6新的扰动界结果可以用来对求解式（1）的Newton型方法进行扰动分析［40］.

4　展望

本文主要从数值解法、误差分析以及扰动分析三方面归纳总结了近年来线性互补问题的一些新的结果和研究进展.在数值解法方面，迭代方法尤其是由模基矩阵分裂迭代方法及其推广衍生出来的各类算法能十分有效地进行求解，但是这些算法中使用的正对角矩阵都是事先给定，怎样选取合适的正对角矩阵使得算法得到加速还有待进一步研究.在误差分析方面，通过引进参数矩阵Ω和～Ω，把式（1）转化为等价问题（15）的想法对于得到更好的误差界起了关键作用，该思想可以用于LCP其他问题的研究.对于扰动分析方面，特别是稳定性分析与条件数的研究方面，目前相关的文章较少，有待于进一步探索.

结合相对成熟的矩阵理论，线性互补问题的相关理论正在不断地发展.随着Qi［41］和Lim［42］在2005年提出张量特征值的概念，近十年来，有关张量各项研究工作正在不断展开，使张量理论与应用研究成为应用数学领域一个热门分支.作为矩阵概念的推广，张量以及张量和向量的运算法则定义如下:

定义4一个实的m阶n维张量T包含了nm个元素.

当m=2时，张量就是常见的n阶矩阵.

最近，Song和Qi［43］中提出了张量互补问题:

可以展望，以张量理论为基础建立的张量互补问题在未来会成为一个新的研究领域.

［1］Cottle R W，Pang J S，Stone R E.The linear complementarity problem［M］.SanDiego:Academic，1992.

［2］Murty K G.Linear complementarity，linear and nonlinear programming［M］.Berlin:Heldermann Verlag，1988.

［3］韩继业，修乃华，戚厚铎.非线性互补理论与算法［M］.上海:上海科学技术出版社，2006.

［4］Berman A，Plemmons R J.Nonnegative matrix in the mathematical sciences［M］.Philadelphia:SIAM Publisher，1994.

［5］Bai Z Z.On the convergence of the multisplitting methods for the linear complementarity problem［J］.SIAM Journal on Matrix Analysis and Applications，1999，21（1）:67 -78.

［6］Frommer A，Szyld D B.H-splittings and two-stage iterative methods［J］.Numerische Mathematik，1992，63（1）:345-356.

［7］Zhang L L，Ren Z R.Improved convergence theorems of modulus-based matrix splitting iteration methods for linear complementarity problems［J］.Applied Mathematicics Letters，2013，26:638-642.

［8］Li H B，Huang T Z，Li H.On some subclasses of P-matrices［J］.Numerical Linear Algebra with Applications，2007，14（5）:391-405.

［9］Van Bokhoven W M G.Piecewise-linear modelling and analysis［M］.Eindhoven:Proefschrift，1981.

［10］Bai Z Z.Modulus-based matrix splitting iteration methods for linear complementarity problems［J］.Numerical Linear Algebra with Applications，2010，17:917-933.

［11］Goldstein A A.Convex programming in Hilbert space［J］.Bulletin of the American Mathematical Society，1964，70:709-710.

［12］Levitin E S，Polyak B T.Constrained minimization methods［J］.USSR Computational Mathematics and Mathematical Physics，1966，6（5）:787-823.

［13］Yoshise A.Complementarity problems［M］.Dordrecht: Kluwer Acamemic Publishers，1996.

［14］Clarke F H.Optimization and nonsmooth analysis［M］. New York:Wiley，1983.

［15］Qi L Q，Sun J.A nonsmooth version of Newton＇s method［J］.Mathematical Programming，1993，58:353-367.

［16］张丽丽.关于线性互补问题的模系矩阵分裂迭代方法［J］.计算数学，2012，34（4）:373-386.

［17］Schäfer U.On the modulus algorithm for the linear complementarity problem［J］.Operations Research Letters，2004，32（4）:350-354.

［18］Dong J L，Jiang M Q.A modified modulus method for symmetric positive-definite linear complementarity problems［J］.Numerical Linear Algebra with Applications，2009，16:129-143.

［19］ Hadjidimos A，Tzoumas M.Nonstationary extrapolated modulus algorithms for the solution of the linear complementarity problem［J］.Linear Algebra and its Applications，2009，431:197-210.

［20］Li W.A general modulus-based matrix splitting method for linear complementarity problems of H-matrices［J］. Applied Mathematics Letters，2013，26:1159-1164.

［21］Bai Z Z，Sun J C，Wang D R.A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations［J］. Computers&Mathematics with Applications，1996，32（12）:51-76.

［22］O＇Leary D P，White R E.Multi-splittings of matrices and parallel solution of linear systems［J］.SIAM Journal on Algebraic and Discrete Methods，1985，6:630-640.

［23］Bai Z Z，Zhang L L.Modulus-based synchronous multisplitting iteration methods for linear complementarity problems［J］.Numerical Linear Algebra with Applications，2013，20:425-439.

［24］ Bai Z Z，Zhang L L.Modulus-based synchronous twostage multisplitting iteration methods for linear complementarity problems［J］.Numerical Algorithms，2013，62（1）:59-77.

［25］Bai Z Z，Evans D J.Matrix multisplitting methods with applications to linear complementarity problems:Parallel synchronous andchaoticmethods［J］.Réseauxet Systèmes Répartis:Calculateurs Parallelès，2001，13:125 -154.

［26］ Machida N，Fukushima M，Ibaraki T.A multisplitting method for symmetric linear complementarity problems［J］.Journal of Computational and Applied Mathematics，1995，62（2）:217-227.

［27］Zhang L L.Two-stage multisplitting iteration methods using modulus-based matrix splitting as inner iteration for linear complementarity problems［J］.Journal of Optimization Theory and Applications，2014，160（1）:189-203.

［28］Zhang L L.Two-step modulus based matrix splitting iteration for linear complementarity problems［J］.Numerical Algorithms，2011，57:83-99.

［29］Zhang L L.Two-step modulus-based synchronous multisplitting iteration methods for linear complementarity problems［J］.Journal of Computational Mathematics，2015，33（1）:100-112.

［30］Zheng H，Li W.The modulus-based nonsmooth Newton＇s method for solving linear complementarity problems［J］. Journal of Computational and Applied Mathematics，doi: 10.1016/j.cam.2015.04.006.

［31］Mathias R，Pang J S.Error bounds for the linear complementarity problem with a P-matrix［J］.Linear Algebra and its Applications，1990，132:123-136.

［32］Mangasarian O L，Ren J.New improved error bounds for the linear complementarity problem［J］.Mathematical Programming，1994，66:241-257.

［33］ Pang J S.Error bounds in mathematical programming［J］.Mathematical Programming，1997，79:299-332.

［34］Chen X J，Xiang S H.Computation of error bounds for P-matrix linear complementarity problems［J］.Mathematical Programming:Series A，2006，106:513-525.

［35］ Garcia-Esnaola M，Pena J M.A comparison of error bounds for linear complementarity problems of H-matrices［J］.Linear Algebra and its Applications，2010，433: 956-964.

［36］Li W，Zheng H.Some new error bounds for linear complementarity problems of H-matrices［J］.Numerical Algorithm，2014，67:257-269.

［37］Dai P F.Error bounds for linear complementarity problems of DB-matrices［J］.Linear Algebra and its Applications，2011，434:830-840.

［38］Dai P F，Li Y T，Lu C J.New error bounds for linear complementarity problem with an SB-matrices［J］.Numerical Algorithms，2013，64:741-757.

［39］Chen T T，Li W，Wu X P，et al.Error bounds for linear complementarity problems of MB-matrices［J］.Numerical Algorithms，2014，doi:10.1007/s11075-014-9950-9.

［40］Chen X J，Xiang S H.Perturbation bounds for P-matrix linear complementarity problems［J］.SIAM Journal on Optimization，2007，18（4）:1250-1265.

［41］Qi L Q.Eigenvalues of a real supersymmetric tensor［J］. Journal of Symbolic Computation，2005，40（6）:1302-1324.

［42］Lim L H.Singular values and eigenvalues of tensors:A variational approach［J］.Proceedings of the IEEE International Workshop on Computational Advances in Multisensor Adaptive Processing，2005，1:129-132.

［43］Song Y S，Qi L Q.Properties of tensor complementarity problem and some classes of structured tensors［J/OL］.（2015-02-08）［2015-02-12］.http://arxiv.org/ abs/1412.0113v2.

【中文责编：庄晓琼英文责编：肖菁】

Numerical Analysis on Linear Complementarity Problems

Li Wen1*，Zheng Hua1，2
（1.School of Mathematical Sciences，South China Normal University，Guangzhou 510631，China；2.School of Mathematics and Statistics，Shaoguan University，Shaoguan 512005，China）

The latest progress in the study on LCPs are summarized.In particularly，some new numerical algorithms for solving LCPs such as the modules-based matrix splitting methods are introduced.Some new results in the error analysis and perturbation analysis are summarized.At first，the linear complementarity problem is presented with its mathematical models and some notations.Secondly，the numerical algorithms for solving the linear complementarity problem are given.The iteration methods especially the module-based matrix splitting iteration methods proposed these years are summarized.Based on module equations，by introducing the idea of nonsmooth Newton＇s method，the modules-based nonsmooth Newton＇s method is established，which converges faster than the existing module-based matrix splitting iteration methods.Then the error analysis of the solution of the linear complementarity problem is given with the new error bounds based on preconditioned technique，which is better than the error bounds given before.The results of the perturbation analysis of the solution of the linear complementarity problem are shown with the latest perturbation bounds.

linear complementarity problem；modules-based method；error analysis；perturbation analysis

O241.6

A

1000-5463（2015）03-0001-09

2015-02-14《华南师范大学学报（自然科学版）》网址:http://journal.scnu.edu.cn/n

国家自然科学基金项目（11271144）；广东省高校创新基金项目（2013KJCX0053）

黎稳，教授，Email:liwen@scnu.edu.cn.