求解線性代數方程組的一種魯棒分布式算法

于夢曉

摘 要：針對分布式環境應用背景下的線性代數方程組，本文提出了一種基于多智能體系統求解線性代數方程組的分布式算法。該算法是魯棒的，因為它不需要預先假設線性代數方程組有解。算法或者收斂到線性代數方程組的某個解，或者通過判斷準則有效終止，而不會陷入死循環。數值仿真驗證了算法的有效性。仿真結果表明，對于有解的線性代數方程組，本文的算法比之前的分布式算法需要更少的迭代次數；對于無解的線性代數方程組，可通過判斷準則終止算法。

關鍵詞：多智能體系統 線性代數方程組 分布式算法 魯棒

中圖分類號：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.