线性互补问题的二级多重分裂并行算法

1、线性互补问题的二级多重分裂并行算法段班祥 李郴良 徐安农（桂林电子工业学院 计算科学与应用物理系 广西桂林 541004）摘要：运用二级迭代方法与矩阵多重分裂理论，同时考虑并行计算，提出了求解线性互补问题的二级多重分裂并行算法。在一定条件下证明了算法的收敛性，分析了算法的收敛速度。数值结果表明，该算法是十分有效的。关键词：线性互补问题；二极多重分裂；并行计算；解的稳定性中图分类号：O241.6 AMS(1991)主题分类: 90C33 文献标识码： A1 引言线性互补问题是一类重要的优化问题，在线性规划、凸二次规划、双矩阵对策及经济与交通平衡等科学与工程中有着广泛的应用。其标准形式为：求使得

2、， ， . （1）其中，简写为.由于应用的广泛性，因而研究求解问题（1）的高效数值算法是非常必要的。文献1-5提出了许多迭代算法，但没有充分利用并行计算，因而对大规模稀疏矩阵，效果并不理想。文6提出了二级多重分裂法求解线性方程组，这类方法将系数矩阵连续进行二级分裂，把大规模问题转化为规模比较小的子问题，以达到减小计算量的目的。文7提出了求解线性互补问题的多分裂方法，这种方法充分运用并行计算以提高计算效率。本文基于二级分裂与多重分裂两种思想，并且考虑并行计算，提出了线性互补问题的二级多重分裂迭代算法，数值实例说明了算法的有效性。 2 预备知识我们首先回顾一般的分裂算法求解. 设，称为的一个分裂，

3、记为.若对 总有解，则称为Q-矩阵；一个分裂称为Q-分裂，是指为Q-矩阵。如果为半正定矩阵，则称分裂为弱正则分裂；为正定矩阵，则称分裂为正则分裂。这一节我们假定为正则分裂。算法2.1 （基本分裂法）（1） 初始化，设为任意的非负向量，置；（2） 一般迭代，给定，解子问题，其中，设为它的一个解；（3）终止检测，若满足预先给定的终止准则，停止迭代，否则，转（2）.我们知道，如果为对称矩阵，则等价于如下二次规划问题： 基于上述假设，文献给出如下引理：引理2.1 设是由算法2.1产生的序列，为弱正则Q-分裂，则有：.进而，如果为正则Q-分裂，当且仅当时，.引理2.2 设为对称矩阵，为正则Q-分裂，如果

4、下述两条件成立： （1）二次函数对任意的有下界； （2）若成立，则有.则由算法2.1产生的序列有界，且至少有一个聚点；并且每个聚点为的一个解。3 算法的建立在给出算法之前，先给出矩阵的二级多重分裂定义：定义3.1 设，为非负对角阵，若满足下列条件：（1）。（2）.（3）（单位阵），则称集簇为矩阵的二级多重分裂。注3.1：为满足线性互补问题有解，对上述定义，我们假设、（）分别为的Q-分裂，即为Q-矩阵。算法3.1 （二级多重分裂并行算法）（1）设为任意的非负向量，置；（2）给定，对的每个二级多重分裂，并行求解 产生序列，若，返回第（2）步，否则，令，转下一步；（3）令；（4），转第（2）步，直至

5、收敛。注3.2 在上面的算法中，为方便起见，每个初始向量可选为，当然也可选为其它向量。注3.3 将:划分为一些子集的和：，其中各子集可以是重叠的，也可以是非重叠的。定义如下：，.因此，在计算中，只须计算对应于的分量，这样以来，计算量就减小了许多，又由于本算法适于并行计算，计算效率自然就提高了。4 收敛性分析在这一节，我们给出算法3.1的收敛性。引理4.1 设为对称半正定矩阵，则.证明：因为为对称半正定矩阵，则二次函数为凸函数，于是 利用了为非负矩阵且.引理4.2 设为满足的指标集，分别为的弱正则分裂，则由算法3.1产生的序列满足下面的不等式：.证明：由引理4.1知，而利用了，为半正定矩阵。引理

6、4.3 设、（）分别为的正则Q-分裂，则由算法3.1产生的序列的每个聚点为的解。证明：设为的任意聚点，不妨设为收敛于的子序列，则.又由引理4.2知非增，则有下界，因此整个序列收敛。、分别为的正则Q-分裂，由引理4.2知.，而为的解，即当时，由上式可知为的解。现在我们来建立二级多重分裂并行算法的收敛性定理。定理4.4 设为对称半正定矩阵，、（）分别为的正则Q-分裂，如果下面两条件成立：（1）二次函数对任意的有下界，（2）.则由算法3.1产生的序列有界，且的每个聚点为的解。证明：先证有界，用反证法。假设无界，则存在子序列使得，由条件（1）知序列有下界，由引理4.2知序列非增，因此收敛。又、（）分别

7、为的正则Q-分裂，.所以序列，即.考虑单位化序列，它有界，因此有一个聚点使得，不失一般性，设，而为的解，即：对上述第一、二式左右两边除以，第三式左右两边除以，则当时，.由条件（1）知对任意的（见1性质3.7.14），而，对上式两边同时除以取极限，考虑，得.与条件（2）矛盾，所以算法3.1产生的序列有界。再由引理4.3可得的每个聚点为的解。证毕。5 收敛速度分析为了给出算法的收敛速度，先给出解的稳定性定义。定义5.1设，为的解，如果存在的邻域及的邻域，使得下述两条件成立：（1）对所有的，集非空；（2）当时，则称为的稳定解，特别，若为单元素集，则称为的强稳定解。从上面的定义可知，强稳定性蕴涵稳定性

8、。引理5.1设为的稳定解，则存在常数和的邻域及的邻域，使得下述两条件成立：（1） 对所有的，集非空；（2） . 引理5.2设，、（）分别为的Q-分裂，由算法3.1产生的序列，为的稳定解，则存在常数和整数，使得对任意的，有. 证明：为的稳定解，从的定义知，又由引理5.1易得出存在常数和整数，使得对任意的，有.定理5.3 设是由算法3.1产生的迭代误差，且满足引理5.2的条件，则存在常数和整数，使得对任意的，有. 证明：由引理5.2可知，对每个，存在常数和整数，使得对任意的，有.取，则当时，上述个不等式均成立，即，则 ， 而，.易知结论成立。1 数值试验本节我们给出数值试验，以验证算法的有效性。考

9、虑如下线性互补问题： ，.其中.该问题的精确解为，在试验中，取初始值为.我们首先对进行两种二级分裂：，.， .分别用(投影雅可比)，（投影逐次超松弛），（二级多重分裂并行算法）进行计算，数值结果如下表：维数次数方法PJacobiPSOR() TSMSP 内迭代 外迭代分裂1分裂2n=616 20 3 2 5n=13 63 20 3 2 2 n=50 不收敛 28 3 2 3算例很好的说明了算法的有效性。参考文献1 Cottle R E, Pang J S and Stone R E. The Linear Complementarity ProblemM. Academic Press, Sa

10、n Diego,1992.2 Iusem A N. On the convergence of iterative methods for symmetric linear complementarity problemsJ. Math. Programming, 59(1993)33-48.3 Bai Z Z and Evans D J. Chaotic iterative methods for the linear complementarity problemsJ. J. Comput. Appl. Math. 96(1998)127-138.4 Yuan D J and Song Y

11、 Z. Modified AOR methods for linear complementarity problemJ. Appl. Math. And Comput. 140(2003)53-67.5 Bai Z Z. On the convergence of the multi-splitting methods for the linear complementarity problemJ. SIAM J. Matrix Anal. Appl. 21(1999)67-78.6 Bai Z Z. Convergence analysis of the two-stage multisp

12、litting methodJ. Calcolo 36(1999)63-74.7 Machid N, Fukushima M and Ibaraki T. A multisplitting method for symmetric linear complementarity problemsJ. J. Comput. and Appl. Maht. 62(1995)217-227.8 蒋美群. 二级多重分裂迭代法J. 苏州大学学报（自然科学版），17（1）（2001）5-8.9 谷同祥，王能超. 并行求解线性方程组的非定常二级多分裂迭代算法J. 工程数学学报，14（4）（1997）25-32

13、.10 Frield A, Martinez J M and Stantos S A. A new strategy for solving variational inequalities in bounded polytopesJ. Numer. Funct and Optimiz. 16(5-6)(1995)653-668.Two-Stage Multi-splitting Parallel Algorithm for the Linear Complementarity ProblemsDUAN Ban-xiang ,Li Chen-liang XU An-nong(Dept. of

14、Computing Science and Applied Physics, Guilin 541004, China)Abstract: In this paper, we extend the two-stage iterative methods, multisplitting iterative methods and parallel computation. And then, we propose the two-stage multisplitting parallel algorithm for linear complementarity problems. In particular, we establish the convergence theory of th