求解线性代数方程组的一种鲁棒分布式算法

于梦晓

摘 要：针对分布式环境应用背景下的线性代数方程组，本文提出了一种基于多智能体系统求解线性代数方程组的分布式算法。该算法是鲁棒的，因为它不需要预先假设线性代数方程组有解。算法或者收敛到线性代数方程组的某个解，或者通过判断准则有效终止，而不会陷入死循环。数值仿真验证了算法的有效性。仿真结果表明，对于有解的线性代数方程组，本文的算法比之前的分布式算法需要更少的迭代次数；对于无解的线性代数方程组，可通过判断准则终止算法。

关键词：多智能体系统 线性代数方程组 分布式算法 鲁棒

中图分类号：G64 文献标识码：A 文章编号：1674-098X（2019）03（c）-0146-03

在诸如传感器网络和过滤应用程序中，各个处理器是彼此分离的。每个传感器只掌握局部信息，但没有传感器可获得网络拓扑的全局信息。此时对应的线性代数方程组问题：每个传感器对应矩阵Ai和向量bi，在不透漏自己信息的情况下，寻找多个方程组的公共解：

许多学者通过多智能体系统建立分布式算法来求解问题（2）[2-5]。每个自主体掌握信息且控制变量xi。多个变量同时更新趋于一致得到方程组的解。2015年，Mou等[4]提出算法DALE。若方程组有解，DALE可找到其解。但每個方程组均有解，方程组未必有解。若其无解，DALE将陷入死循环。基于上述考虑，我们提出一种改进的分布式算法。新算法具有更简洁的迭代格式，同时对无解的线性代数方程组，给出判断准则避免算法陷入死循环。最后，通过数值仿真验证了算法的有效性。

1 一些基本结论

引理1：给定方程组（1）（2），若存在某个方程组无解，则方程组无解；

证明.若方程组无解，但方程组存在解，则对所有的i满足，与方程组无解矛盾。故方程组必定无解。同时，无解等价于， 故若存在某个方程组满足， 则方程组无解。

为叙述引理2， 引入方程组，且，

引理2：给定方程组与， 则：

（1）方程组有解的充要条件是方程组存在t≠0的解；

（2）方程组无解的充要条件是方程组的所有解中均有t=0。

证明：（1）设方程组存在解x0。则即为方程组的解；反之，若方程组存在解，则满足方程组， 即方程组有解。

（2）若方程组无解， 方程组存在解，则满足方程组，与假设矛盾， 故方程组的所有解中均有t=0。反之， 逆否命题必成立.

2 基于多智能体系统的鲁棒分布式算法

通过上述转化， 我们得到比DALE更简洁的迭代格式.若方程组无解， 根据引理1，2的证明过程可得其判断准则： 对所有的i，或。由该判断准则， 我们可以避免新算法在方程组无解时陷入死循环。下面给出算法1的具体步骤：

3 数值仿真

本节我们通过数值仿真说明算法1的有效性，测试软件为Matlab-R2014a，运行环境为宏基笔记本Win 8系统（Intel（R） Core（TM） i5-3337U CPU 1.80 GHZ， 3.80 GB）.

例1[6]： 考虑由3个自主体的多智能体系统生成的线性代数方程组：

用DALE求解此方程组时， 由于始终不满足停止准则， 算法将会陷入死循环。而用本文算法求解时，通过判断，可知方程组无解。从而终止算法。仿真结果见图2。

4 结语

本文针对分布式计算环境下的线性代数方程组提出了一种鲁棒分布式算法。通过将非齐次线性代数方程组转换为齐次线性代数方程组求解， 新算法具有更简洁的迭代格式， 当方程组有解时， 比DALE更快地收敛到方程组的解； 对无解的方程组， 通过判断准则可以有效终止算法。 最后， 数值仿真说明了算法的有效性.

参考文献

[1] 洪奕光， 张艳琼. 分布式优化： 算法设计和收敛性分析[J].控制理论与应用， 2014， 31（7）： 850-857.

[2] Nedic A， Ozdaglar A E. Distributed Subgradient Methods for Multi-Agent Optimization[J]. IEEE Transactions on Automatic Control， 2009， 54（1）： 48-61.

[3] Anderson B D O， Mou S， Morse A S， et al. Decentralized gradient algorithm for solution of a linear equation[J]. Numerical Algebra Control & Optimization， 2015， 6：（3）： 319-328.

[4] Mou S， Liu J， Morse A S. A distributed algorithm for solving a linear algebraic equation[J]. IEEE Transactions on Automatic Control， 2015， 60（11）： 2863-2878.

[5] 龙昱屾， 刘帅， 谢立华. 带集合约束的分布式随机凸优化[J]. 中国科学：数学， 2016， 46（10）： 1487-1498.

[6] Wang X， Mou S， Sun D. Improvement of a distributed algorithm for solving linear equations[J]. IEEE Transactions on Industrial Electronics， 2017， 64（4）： 3113-3117.