于夢曉

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

關鍵詞：多智能體系統(tǒng) 線性代數(shù)方程組 分布式算法 魯棒

中圖分類號：G64 文獻標識碼：A 文章編號：1674-098X（2019）03（c）-0146-03

在諸如傳感器網絡和過濾應用程序中，各個處理器是彼此分離的。每個傳感器只掌握局部信息，但沒有傳感器可獲得網絡拓撲的全局信息。此時對應的線性代數(shù)方程組問題：每個傳感器對應矩陣Ai和向量bi，在不透漏自己信息的情況下，尋找多個方程組的公共解：

許多學者通過多智能體系統(tǒng)建立分布式算法來求解問題（2）[2-5]。每個自主體掌握信息且控制變量xi。多個變量同時更新趨于一致得到方程組的解。2015年，Mou等[4]提出算法DALE。若方程組有解，DALE可找到其解。但每個方程組均有解，方程組未必有解。若其無解，DALE將陷入死循環(huán)?；谏鲜隹紤]，我們提出一種改進的分布式算法。新算法具有更簡潔的迭代格式，同時對無解的線性代數(shù)方程組，給出判斷準則避免算法陷入死循環(huán)。最后，通過數(shù)值仿真驗證了算法的有效性。

1 一些基本結論

引理1：給定方程組（1）（2），若存在某個方程組無解，則方程組無解；

證明.若方程組無解，但方程組存在解，則對所有的i滿足，與方程組無解矛盾。故方程組必定無解。同時，無解等價于， 故若存在某個方程組滿足， 則方程組無解。

為敘述引理2， 引入方程組，且，

引理2：給定方程組與， 則：

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

（2）方程組無解的充要條件是方程組的所有解中均有t=0。

證明：（1）設方程組存在解x0。則即為方程組的解；反之，若方程組存在解，則滿足方程組， 即方程組有解。

（2）若方程組無解， 方程組存在解，則滿足方程組，與假設矛盾， 故方程組的所有解中均有t=0。反之， 逆否命題必成立.

2 基于多智能體系統(tǒng)的魯棒分布式算法

通過上述轉化， 我們得到比DALE更簡潔的迭代格式.若方程組無解， 根據引理1，2的證明過程可得其判斷準則： 對所有的i，或。由該判斷準則， 我們可以避免新算法在方程組無解時陷入死循環(huán)。下面給出算法1的具體步驟：

3 數(shù)值仿真

本節(jié)我們通過數(shù)值仿真說明算法1的有效性，測試軟件為Matlab-R2014a，運行環(huán)境為宏基筆記本Win 8系統(tǒng)（Intel（R） Core（TM） i5-3337U CPU 1.80 GHZ， 3.80 GB）.

例1[6]： 考慮由3個自主體的多智能體系統(tǒng)生成的線性代數(shù)方程組：

用DALE求解此方程組時， 由于始終不滿足停止準則， 算法將會陷入死循環(huán)。而用本文算法求解時，通過判斷，可知方程組無解。從而終止算法。仿真結果見圖2。

4 結語

本文針對分布式計算環(huán)境下的線性代數(shù)方程組提出了一種魯棒分布式算法。通過將非齊次線性代數(shù)方程組轉換為齊次線性代數(shù)方程組求解， 新算法具有更簡潔的迭代格式， 當方程組有解時， 比DALE更快地收斂到方程組的解； 對無解的方程組， 通過判斷準則可以有效終止算法。 最后， 數(shù)值仿真說明了算法的有效性.

參考文獻

[1] 洪奕光， 張艷瓊. 分布式優(yōu)化： 算法設計和收斂性分析[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] 龍昱屾， 劉帥， 謝立華. 帶集合約束的分布式隨機凸優(yōu)化[J]. 中國科學：數(shù)學， 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.