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

于夢(mèng)曉

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

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

中圖分類號(hào)：G64 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2019）03（c）-0146-03

在諸如傳感器網(wǎng)絡(luò)和過(guò)濾應(yīng)用程序中，各個(gè)處理器是彼此分離的。每個(gè)傳感器只掌握局部信息，但沒(méi)有傳感器可獲得網(wǎng)絡(luò)拓?fù)涞娜中畔ⅰ４藭r(shí)對(duì)應(yīng)的線性代數(shù)方程組問(wèn)題：每個(gè)傳感器對(duì)應(yīng)矩陣Ai和向量bi，在不透漏自己信息的情況下，尋找多個(gè)方程組的公共解：

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

1 一些基本結(jié)論

引理1：給定方程組（1）（2），若存在某個(gè)方程組無(wú)解，則方程組無(wú)解；

證明.若方程組無(wú)解，但方程組存在解，則對(duì)所有的i滿足，與方程組無(wú)解矛盾。故方程組必定無(wú)解。同時(shí)，無(wú)解等價(jià)于， 故若存在某個(gè)方程組滿足， 則方程組無(wú)解。

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

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

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

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

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

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

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

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

3 數(shù)值仿真

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

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

[1] 洪奕光， 張艷瓊. 分布式優(yōu)化： 算法設(shè)計(jì)和收斂性分析[J].控制理論與應(yīng)用， 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ī)凸優(yōu)化[J]. 中國(guó)科學(xué)：數(shù)學(xué)， 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.