矩陣方程的分布式求解算法研究概述

鄧 文, 李偉健, 曾憲琳, 洪奕光

(1.同濟(jì)大學(xué)電子與信息工程學(xué)院控制科學(xué)與工程系;上海自主智能無(wú)人系統(tǒng)科學(xué)中心,上海 200092;2.中國(guó)科學(xué)技術(shù)大學(xué)自動(dòng)化系,安徽合肥 230027;3.北京理工大學(xué)自動(dòng)化學(xué)院,北京 100081)

1 引言

在被網(wǎng)絡(luò)覆蓋的大數(shù)據(jù)時(shí)代,基于多智能體網(wǎng)絡(luò)的分布式計(jì)算和分布式優(yōu)化方法的研究因其在自然科學(xué)和工程技術(shù)領(lǐng)域的廣泛應(yīng)用而受到了極大的關(guān)注.多智能體網(wǎng)絡(luò)通常是對(duì)工程網(wǎng)絡(luò)系統(tǒng)的抽象表示,用拓?fù)鋱D節(jié)點(diǎn)代表網(wǎng)絡(luò)中的智能體,節(jié)點(diǎn)之間的邊代表智能體之間的信息交互關(guān)系,該網(wǎng)絡(luò)結(jié)構(gòu)既可能是固定的也可能是時(shí)變的.多智能體網(wǎng)絡(luò)系統(tǒng)中的每個(gè)智能體具有一定的自主性,具有感知、計(jì)算和通信能力,分布式優(yōu)化是通過(guò)多智能體利用自身局部信息和智能體之間的協(xié)調(diào)合作來(lái)實(shí)現(xiàn)全局優(yōu)化目標(biāo)[1-2].分布式優(yōu)化問(wèn)題中的一類主要研究方向是對(duì)全局目標(biāo)函數(shù)的優(yōu)化,而每個(gè)智能體僅已知其中一部分?jǐn)?shù)據(jù)信息,允許智能體所計(jì)算的變量信息在鄰居節(jié)點(diǎn)之間進(jìn)行交互,從而實(shí)現(xiàn)全局求解.

一直以來(lái),矩陣計(jì)算在數(shù)學(xué)理論和工程實(shí)踐中都是至關(guān)重要的.矩陣方程求解是矩陣計(jì)算的一類典型問(wèn)題,它與應(yīng)用數(shù)學(xué)、計(jì)算技術(shù)以及工程控制領(lǐng)域的很多基本問(wèn)題密切相關(guān),例如,統(tǒng)計(jì)學(xué)和機(jī)器學(xué)習(xí)中針對(duì)數(shù)據(jù)的回歸分析包括建模求解線性方程,或者在多目標(biāo)預(yù)測(cè)、數(shù)據(jù)恢復(fù)等任務(wù)中建立低秩模型求解相應(yīng)的矩陣優(yōu)化問(wèn)題;現(xiàn)實(shí)世界中大多數(shù)用于解釋物理現(xiàn)象、進(jìn)行仿真預(yù)測(cè)的建模分析會(huì)借助線性或非線性動(dòng)態(tài)系統(tǒng),而矩陣方程在線性動(dòng)力系統(tǒng)的穩(wěn)定性分析、控制器設(shè)計(jì)等問(wèn)題中起著重要的作用,涉及Lyapunov方程、Sylvester方程等典型線性矩陣方程的求解問(wèn)題;非線性矩陣方程Riccati方程在最優(yōu)控制、魯棒控制等相關(guān)理論的發(fā)展中也起到了重要的作用[3-7].矩陣方程的傳統(tǒng)集中式解法在數(shù)值代數(shù)領(lǐng)域被深入研究,例如積分形式的解表達(dá)式和交替方向隱式(ADI)迭代方法[8-9],以及一些可以用來(lái)求解大規(guī)模矩陣方程的并行算法[10-11].但是在這類集中式算法和并行算法中,一般存在一個(gè)中心節(jié)點(diǎn)來(lái)收集、分發(fā)和處理數(shù)據(jù)和任務(wù)或者計(jì)算過(guò)程中需要直接利用整個(gè)數(shù)據(jù)矩陣,所以這些方法并不適用本文所探討的基于多智能體網(wǎng)絡(luò)的分布式矩陣計(jì)算情形.不同于并行算法的是,分布式算法中的智能體是平等且具有自主性的,它們各自掌控局部目標(biāo)和相對(duì)的隱私數(shù)據(jù),只需在其鄰居智能體之間傳遞部分中間變量的信息.分布式網(wǎng)絡(luò)的結(jié)構(gòu)和去中心特征使得網(wǎng)絡(luò)的靈活性和可擴(kuò)展性增強(qiáng),當(dāng)網(wǎng)絡(luò)中單一節(jié)點(diǎn)故障時(shí),對(duì)整體系統(tǒng)造成的影響比較小.研究矩陣方程的分布式算法(不同于經(jīng)典的并行算法),目前的主要方向是利用分布式優(yōu)化方法來(lái)求解,本文將對(duì)現(xiàn)有的研究工作進(jìn)行簡(jiǎn)要介紹:包括線性代數(shù)方程的分布式求解,幾類典型矩陣方程的分布式求解,如Sylvester方程和Lyapunov方程等,以及其他類型的分布式矩陣計(jì)算問(wèn)題,包括線性或非線性矩陣不等式等.

文中涉及的記號(hào)如下:Rm×n代表m×n的實(shí)矩陣空間.對(duì)于向量x,y和矩陣X,Y,〈x,y〉=xTy和〈X,Y〉F=trace(XTY)分別代表向量?jī)?nèi)積和矩陣Frobenius內(nèi)積,‖x‖p和‖X‖F(xiàn)分別為其誘導(dǎo)的向量p范數(shù)和矩陣Frobenius范數(shù).記0m和1m分別為零向量和全1向量,角標(biāo)代表向量維數(shù),0m×n和Im分別代表零矩陣和m×m的單位矩陣.Sm+和Sm++分別代表對(duì)稱半正定和正定矩陣空間,其矩陣元素可以表示為X≥0m×m和X>0m×m.記PΩ(·)為凸集Ω上的正交投影算子.用圖G(V,E)(可簡(jiǎn)記為G)描述多智能體網(wǎng)絡(luò)的通信拓?fù)?其中節(jié)點(diǎn)集V={1,2,··· ,n}代表智能體集合,邊集E ?V×V代表智能體之間存在通信,圖的鄰接矩陣和拉普拉斯矩陣分別記作[aij]和LG.不額外說(shuō)明時(shí),文中涉及的圖默認(rèn)為無(wú)向連通圖.在矩陣數(shù)據(jù)的劃分中,角標(biāo)(上標(biāo)或者下標(biāo))vi代表按行劃分的第i個(gè)數(shù)據(jù)塊,角標(biāo)li代表按列劃分的第i個(gè)數(shù)據(jù)塊.

2 線性代數(shù)方程的分布式求解

線性代數(shù)方程作為矩陣方程的一種特例,一般表示為如下形式:

其中未知變量x是向量.關(guān)于方程式(1)的傳統(tǒng)解法,在矩陣計(jì)算和數(shù)值代數(shù)領(lǐng)域的相關(guān)理論已經(jīng)比較成熟,如Gauss消去法、Gauss-Seidel方法、Jacobi迭代法等[12].但由于網(wǎng)絡(luò)系統(tǒng)的興起,在相關(guān)應(yīng)用的大規(guī)模計(jì)算中,集中式算法往往不再是第一選擇,并且由于數(shù)據(jù)的分布式存儲(chǔ)需求,集中式方法大多將不再適用.因此,在多智能體網(wǎng)絡(luò)下探究線性方程的分布式解法有重要意義,近年來(lái)已經(jīng)取得了不少的研究成果,參考文獻(xiàn)[13-20].在多智能體網(wǎng)絡(luò)中,通常假設(shè)每個(gè)智能體只能獲取式(1)中的部分信息,可能包括但不限于矩陣A的某一行Ai和相應(yīng)向量b的某個(gè)元素bi,然后通過(guò)與其鄰居的信息交流(可以通訊狀態(tài)變量但不交換原始數(shù)據(jù))共同求解一致的未知變量x,即每個(gè)智能體對(duì)x的估計(jì)值xi最終達(dá)到一致.

方程式(1)的解有3種可能性:有唯一解、有無(wú)窮多解和無(wú)解.針對(duì)解的不同假設(shè),學(xué)者們研究了多種類型的離散時(shí)間算法和連續(xù)時(shí)間算法來(lái)實(shí)現(xiàn)分布式計(jì)算.主要求解思路包括以下3類:

1) 借助各種投影算子結(jié)合一致性協(xié)議進(jìn)行求解;

2) 轉(zhuǎn)化成帶等式約束的優(yōu)化問(wèn)題進(jìn)行求解;

3) 特殊矩陣結(jié)構(gòu)下的方程求解,如滿足稀疏性.

關(guān)于第1種求解思路,重點(diǎn)在于尋找合適的投影空間以及確定投影算子的表達(dá)式.在聯(lián)合強(qiáng)連通圖的假設(shè)下,當(dāng)方程至少存在一個(gè)精確解時(shí),文獻(xiàn)[14]提出了投影一致算法:

在連續(xù)時(shí)間算法的設(shè)計(jì)中,為了實(shí)現(xiàn)所有智能體i所求子問(wèn)題的可行解xi ∈{y|Aiy=bi}趨于一致,通常有下列形式:

當(dāng)網(wǎng)絡(luò)通信圖是無(wú)向連通圖時(shí),算法(5)-(6)都是指數(shù)收斂的.文獻(xiàn)[22]針對(duì)滿足聯(lián)合強(qiáng)連通性的分段時(shí)不變切換圖推廣了算法(5).文獻(xiàn)[16]利用一致算法和投影算子設(shè)計(jì)了兩類求解按行分解數(shù)據(jù)A的分布式連續(xù)時(shí)間算法,分別是“一致+投影”方法和對(duì)投影項(xiàng)進(jìn)行一致性操作的“投影一致”算法:

其中:xi(t)簡(jiǎn)記為xi,參數(shù)K為給定正常數(shù),Ai表示仿射空間{x|Aix=bi}.文獻(xiàn)[16]分析了這兩種算法在通信拓?fù)錇橐恢侣?lián)合強(qiáng)連通的時(shí)變有向圖時(shí)的收斂性.當(dāng)方程式(1)存在唯一的最小二乘解時(shí),文獻(xiàn)[16]證明了式(7)中的算法(a)能夠收斂到該最小二乘解的一個(gè)極小鄰域內(nèi),在固定圖前提下,算法(b)中所有智能體對(duì)解的估計(jì)值的均值將收斂到唯一最小二乘解.

在多數(shù)情況下,當(dāng)線性方程式(1)有解時(shí),求出其中任意一個(gè)解即可.如果線性方程式(1)的解的存在性未知或者該方程無(wú)解,那么尋找其最小二乘解[17,23-24]也是一類極其重要的問(wèn)題.另外在某些情形下,需求出滿足某些特殊性質(zhì)的解,例如文獻(xiàn)[25]在討論壓縮感知問(wèn)題時(shí),期望得到具有最小L1-范數(shù)的解,文獻(xiàn)[18,26]期望得到最小L2-范數(shù)解.這類問(wèn)題稱作尋找正則解,相應(yīng)的尋找正則解的分布式算法設(shè)計(jì)可參考文獻(xiàn)[18,27]等.在尋求最小二乘解或者正則解時(shí),常常用到第2類方法,把原問(wèn)題轉(zhuǎn)化成優(yōu)化問(wèn)題進(jìn)行求解,可以靈活設(shè)置目標(biāo)函數(shù)和約束條件,引入適當(dāng)?shù)淖兞窟M(jìn)行求解.文獻(xiàn)[17]中設(shè)計(jì)了Arrow-Hurwicz-Uzawa類型連續(xù)時(shí)間算法:

目前,大多數(shù)研究集中在對(duì)矩陣A按行劃分再利用分布式方法求解式(1),也有一些研究考慮的是按列、按塊或者求和形式等不同數(shù)據(jù)劃分方式下的分布式解法.不同的數(shù)據(jù)劃分方式可能由實(shí)際應(yīng)用需求和不同網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算能力等多方因素決定,然后數(shù)據(jù)劃分也直接影響著算法設(shè)計(jì)的適用性和不同算法的性能.文獻(xiàn)[19]考慮的是每個(gè)智能體已知矩陣A的某一列或者多列的信息,求解的變量只是整體變量的一部分(所求方程解的形式為所有智能體估計(jì)變量的匯總,即x=col{x1,··· ,xN}),這種情況下也不需要所有智能體的決策變量達(dá)到一致.另外,文獻(xiàn)[31]中的算法不需要對(duì)解是否存在做假設(shè),可以驗(yàn)證出方程式(1)是否存在精確解,并且在解存在時(shí)能直接求出一個(gè)精確解,在精確解不存在時(shí)求相應(yīng)的最小二乘解.文獻(xiàn)[20]構(gòu)建了一個(gè)雙層網(wǎng)絡(luò)結(jié)構(gòu),矩陣A的信息遵循先按行再按列或者先按列再按行的塊狀劃分方式,在假設(shè)原方程有解的情況下,分別提出了“全局一致+局部守恒”和“全局守恒+局部一致”的兩種對(duì)應(yīng)的分布式算法,但是當(dāng)不存在精確解時(shí)并不能直接用來(lái)求出最小二乘解.文獻(xiàn)[20,31]中提出的算法也都可以從第2類型的分布式優(yōu)化問(wèn)題的層面來(lái)理解.

第3類求解思路是當(dāng)求解方程中涉及的信息矩陣滿足某些特殊結(jié)構(gòu)時(shí),會(huì)考慮一些有針對(duì)性的算法,例如針對(duì)稀疏矩陣特性的消息傳遞(message-passing,MP)算法.MP算法一般是指在通信過(guò)程中,通信拓?fù)鋱D中的每條邊上傳遞和更新信息變量,然后進(jìn)行迭代計(jì)算.在與稀疏性相關(guān)的問(wèn)題中,MP算法常被用來(lái)求解壓縮感知問(wèn)題[32-33].最近MP算法在求解稀疏的代數(shù)方程Ax=b問(wèn)題中也有應(yīng)用,文獻(xiàn)[34]考慮矩陣A稀疏且滿足廣義對(duì)角占優(yōu)條件的情況.在文獻(xiàn)[34]的消息傳遞算法中,記A=[aij],與每個(gè)節(jié)點(diǎn)i有關(guān)的是對(duì)角數(shù)據(jù)aii和相應(yīng)bi,若矩陣A中元素aij ?=0,則代表其誘導(dǎo)的圖結(jié)構(gòu)中有一條邊(i,j),由此獲得的通信拓?fù)鋱D為一個(gè)多圈圖,選取其中任意一個(gè)節(jié)點(diǎn)作為根節(jié)點(diǎn),把原本的多圈圖展開(kāi)為樹(shù)結(jié)構(gòu)再按順序進(jìn)行消息傳遞,每個(gè)節(jié)點(diǎn)根據(jù)樹(shù)結(jié)構(gòu)中所傳遞的消息來(lái)更新傳遞值和狀態(tài)值,由此設(shè)計(jì)了離散的分布式算法.

現(xiàn)有的分布式求解代數(shù)方程的理論研究已經(jīng)取得了很多優(yōu)秀成果,但仍有一些不足限制了其實(shí)際應(yīng)用:首先,現(xiàn)有算法對(duì)通信代價(jià)的分析較少,結(jié)合計(jì)算節(jié)點(diǎn)的通信和計(jì)算能力,研究通信效率和計(jì)算平衡的分布式算法設(shè)計(jì)可能是一個(gè)重要的研究方向;其次,矩陣的數(shù)據(jù)和迭代計(jì)算過(guò)程都可能存在一定誤差,如何設(shè)計(jì)強(qiáng)魯棒性的分布式不精確算法也是一個(gè)需要解決的問(wèn)題.

3 線性矩陣方程的分布式求解方法

傳統(tǒng)意義上,多以集中式方法來(lái)求解各類矩陣方程,當(dāng)前很多實(shí)際應(yīng)用中卻關(guān)聯(lián)著大規(guī)模網(wǎng)絡(luò)系統(tǒng),傳統(tǒng)的集中式算法受限于整體數(shù)據(jù)的獲取和所需要的計(jì)算能力和通信能力,而不能適應(yīng)大規(guī)模方程計(jì)算的需求和分布式思想的發(fā)展,因此矩陣方程的分布式算法研究受到了研究學(xué)者們的廣泛關(guān)注.線性代數(shù)方程可以看做矩陣方程的一種特例.

大多數(shù)線性矩陣方程可被概括為廣義Sylvester方程的形式

其中未知變量為矩陣X.還有其他多種類型的廣義Sylvester方程在文獻(xiàn)[9]中被研究.當(dāng)矩陣E或B為零矩陣時(shí),式(9)成為一類重要的矩陣方程AXD=C,求解其中變量X的計(jì)算問(wèn)題在許多重要的應(yīng)用中起著決定性的作用,例如矩陣的廣義逆計(jì)算和廣義Sylvester方程的求解[5,35-37],該方程的集中式算法在文獻(xiàn)[37-40]等文中已有研究.另一類十分重要的線性矩陣方程是Sylvester方程AX+XB=C,即式(9)中矩陣D=E=I.在控制和自動(dòng)化領(lǐng)域中,許多的Sylvester-型矩陣方程是其中一些基本問(wèn)題和基本系統(tǒng)的原始模型.例如,通過(guò)設(shè)計(jì)機(jī)械振動(dòng)系統(tǒng)的控制器,可以使用Sylvester方程實(shí)現(xiàn)特征結(jié)構(gòu)配置[41-42];而當(dāng)B=AT時(shí),即為L(zhǎng)yapunov方程,該方程在線性時(shí)不變系統(tǒng)的穩(wěn)定性分析中起著十分重要的作用[6].1884年,Sylvester提出了方程AX+XB=C有唯一解的條件[43],而后,眾多研究學(xué)者們探討了Sylvester方程及其廣義形式的可解性條件[44-47],該方程有唯一解的充分必要條件為:矩陣A和?B沒(méi)有公共特征值.到目前為止,學(xué)者們已經(jīng)提出了該方程的許多集中式求解方法,例如,Hessenberg-Schur方法[48]、ADI迭代方法[49]以及Krylov-子空間方法[50]等.另外,考慮到求解大規(guī)模矩陣方程的需要,也有一些關(guān)于求解Sylvester類型方程的并行算法的研究[10-11].但是,注意到這些集中式算法和并行算法一般都要求有一個(gè)中心節(jié)點(diǎn)來(lái)處理和分發(fā)數(shù)據(jù)或者需要直接利用整個(gè)矩陣A,B,C,所以這些方法并不適合直接運(yùn)用到本文所探討的基于多智能體網(wǎng)絡(luò)來(lái)求解的情形.

研究矩陣方程的分布式算法的動(dòng)機(jī)主要來(lái)源于以下3個(gè)方面:

1) 把一般線性方程式(1)擴(kuò)展到矩陣方程并不是一個(gè)平凡的推廣,雖然向量化的矩陣方程也是可解的,但由于矩陣乘法帶來(lái)的性質(zhì),具體的數(shù)據(jù)適用情況和算法形式還有待研究.基于多智能體網(wǎng)絡(luò)下的矩陣信息的各種數(shù)據(jù)劃分方式,分布式求解矩陣方程的過(guò)程與處理方程式(1)有較大差異.

2) 在大規(guī)模應(yīng)用中,矩陣維數(shù)呈現(xiàn)爆炸性增長(zhǎng),如果采用集中式方法直接求解,對(duì)計(jì)算能力的要求是很高的.所以研究分布式求解矩陣方程算法的出發(fā)點(diǎn)在于緩解集中式計(jì)算的壓力和構(gòu)建去中心化的算法體系.

3) 針對(duì)某些應(yīng)用情況比如在復(fù)雜網(wǎng)絡(luò)中存在客觀上獨(dú)立的數(shù)據(jù)集,局部原始數(shù)據(jù)不能被他人所知,有著物理意義的這類矩陣方程所涉及的相關(guān)求解問(wèn)題自然需求分布式求解方法.

對(duì)線性矩陣方程而言,方程的解有3種類型:唯一解、無(wú)窮多解和無(wú)解.當(dāng)滿足唯一性假設(shè)時(shí),文獻(xiàn)[51-52]等文獻(xiàn)中研究其唯一解算法;當(dāng)存在無(wú)窮多解時(shí),有時(shí)候也只需要求解任意一個(gè)精確解即可[53-54],還可能需要求解的是滿足特定條件(如范數(shù)最小)的精確解;當(dāng)方程本身無(wú)解時(shí),求解其最小二乘解通常也是值得研究的問(wèn)題[55-56].有的方程會(huì)自帶對(duì)未知變量的約束,如Lyapunov方程求解正定解,Stein方程求解某個(gè)凸集中的解.

關(guān)于分布式求解矩陣方程的工作,大多數(shù)是把解方程問(wèn)題轉(zhuǎn)化成標(biāo)準(zhǔn)的分布式優(yōu)化問(wèn)題后再進(jìn)行求解的,其中的幾個(gè)關(guān)鍵點(diǎn)在于:

1) 根據(jù)數(shù)據(jù)劃分方式和參與計(jì)算的多智能體數(shù)目,待求解方程可以顯式表示成包含局部數(shù)據(jù)的方程組;

2) 選取適當(dāng)?shù)哪繕?biāo)函數(shù),其形式為每個(gè)智能體的局部目標(biāo)函數(shù)之和;

3) 按需添加一致性條件等約束,當(dāng)約束中含有耦合等式約束時(shí),需采取解耦方法,例如引入輔助變量列,把耦合約束拆分成多個(gè)單獨(dú)的約束.

4) 對(duì)分布式帶約束優(yōu)化問(wèn)題進(jìn)行求解時(shí),常用技巧包括原始對(duì)偶方法、投影算子、導(dǎo)數(shù)反饋等.

以下是現(xiàn)有工作中關(guān)于分布式求解幾類矩陣方程的介紹,分別考慮不帶約束和帶約束的矩陣方程,以及其他幾類矩陣相關(guān)的計(jì)算問(wèn)題,包括線性矩陣不等式(linear matrix inequality,LMI)和非線性矩陣不等式等.

3.1 無(wú)約束的矩陣方程求解

考慮一般矩陣方程AXB=F或者Sylvester方程,未知矩陣變量X屬于全矩陣空間,在無(wú)附加約束時(shí)求解其精確解或最小二乘解.

當(dāng)方程式(9)的等式左邊只有一項(xiàng)時(shí),文獻(xiàn)[57]首次用分布式方法求解了方程

并且分析了關(guān)于矩陣A,B,F的8種不同的行列數(shù)據(jù)劃分方式.這里使用3個(gè)字母的組合代表數(shù)據(jù)矩陣A,B,F的劃分方式,其中字母R和C分別代表行劃分和列劃分方式.這樣3個(gè)矩陣則有不同的劃分方式為RCC,RRR,RRC,CRC(另外4種劃分可由以上4種劃分經(jīng)原方程的轉(zhuǎn)置得到).針對(duì)每一種數(shù)據(jù)劃分方式,文獻(xiàn)[57]通過(guò)將方程等價(jià)轉(zhuǎn)化成與個(gè)體局部信息相關(guān)的多個(gè)等式,并添加必要的一致性等式約束.以RCC劃分為例,當(dāng)利用包含n個(gè)節(jié)點(diǎn)的多智能體網(wǎng)絡(luò)來(lái)進(jìn)行求解時(shí),引入輔助求解的變量Yi,滿足關(guān)系式Y(jié)iBli=Fli,AviXi=Yvii,其中數(shù)據(jù)Bli,Fli以及Avi為智能體i所知的局部數(shù)據(jù)信息.然后根據(jù)轉(zhuǎn)化后的方程組設(shè)計(jì)相應(yīng)的分布式優(yōu)化算法,比如求解一個(gè)分布式優(yōu)化問(wèn)題

在網(wǎng)絡(luò)通信圖無(wú)向連通的假設(shè)下,X?是方程式(10)的最小二乘解的充分必要條件是存在Y ?=AX?使得(1n ?X?,1?Y ?)是優(yōu)化問(wèn)題(11)的最優(yōu)解.然后利用修正的拉格朗日函數(shù)L,即在一般的拉格朗日函數(shù)的基礎(chǔ)上添加等式約束的最小二乘項(xiàng),來(lái)設(shè)計(jì)分布式原始對(duì)偶算法,如圖1.原始對(duì)偶方法(L函數(shù)的鞍點(diǎn)動(dòng)力學(xué))概述為

圖1 RCC劃分下的分布式原始對(duì)偶算法Fig.1 The distributed prime-dual algorithm under the RCC partition

其中:Zprimal表示Xi,Yi這類原始變量,Λdual表示優(yōu)化問(wèn)題(11)中根據(jù)等式約束引入的對(duì)偶變量.在某些情況下(如RRR,CCR劃分),文獻(xiàn)[57]中還添加了合適的導(dǎo)數(shù)反饋?lái)?xiàng)來(lái)實(shí)現(xiàn)算法系統(tǒng)的穩(wěn)定性.另外離散時(shí)間的算法也可以由類似方法寫(xiě)出.矩陣方程式(9)可以看做方程

在n=2時(shí)的情形.文獻(xiàn)[53,55]中研究的是一般線性

文獻(xiàn)[54,56]分別給出了Sylvester方程的精確解以及最小二乘解的分布式算法,實(shí)際上,按照數(shù)據(jù)矩陣A,B,C的行列劃分情況,Sylvester方程式(15)等價(jià)于表1中的幾種分布式形式.

表1 不同劃分下Sylvester方程的分布式表達(dá)Table 1 The distributed forms of the Sylvester equation under different partitions

以上考慮的3類方程式(10)(13)(15),文[53-57]中都是采用“將求解問(wèn)題轉(zhuǎn)化成優(yōu)化問(wèn)題”的思路,對(duì)應(yīng)于求解線性代數(shù)方程中的第2類方法.但是對(duì)比代數(shù)方程,矩陣方程中由于形式更復(fù)雜,會(huì)引入更多的對(duì)偶變量或者其他輔助變量來(lái)實(shí)現(xiàn)求解.

為了引入更少的變量,在同樣的存在精確解的假設(shè)下,文獻(xiàn)[58]求解的是式(15)的向量化的代數(shù)方程

特別地,考慮矩陣為方陣且行列數(shù)等于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)m=r=n的情況.針對(duì)矩陣B和C的列劃分,即每個(gè)智能體擁有局部數(shù)據(jù)A,Bli和Cli,智能體i求解子方程的解空間

在這個(gè)意義下,求解全局方程的解也就是求解多個(gè)凸集解空間的交集,即分布式凸交問(wèn)題,對(duì)應(yīng)于求解代數(shù)方程的第一類投影方法.因此,根據(jù)“一致+投影”的分布式算法,智能體按照各自動(dòng)力學(xué)

更新變量,其中xi=vec(Xi)是智能體對(duì)未知變量的估計(jì).式(19)與上一節(jié)求解線性代數(shù)方程式(7)中算法(a)一致,只是此處借助向量表示了矩陣變量和基于局部矩陣數(shù)據(jù)的投影子空間Si.文獻(xiàn)[58]還證明了該算法的指數(shù)收斂速率隨參數(shù)K的增加而單調(diào)非減的規(guī)律,當(dāng)K趨于無(wú)窮時(shí),明確了收斂速率的極限表達(dá)式.除此以外,文獻(xiàn)[58]也考慮了行列劃分中的RCC劃分以及雙層網(wǎng)絡(luò)結(jié)構(gòu)下的塊狀數(shù)據(jù)劃分,在輔助變量的幫助下也分別提出了分布式算法和討論了相應(yīng)的收斂性質(zhì).

文獻(xiàn)[56,58-60]都研究了Sylvester方程最小二乘解的分布式算法.其中,文獻(xiàn)[56,59]在轉(zhuǎn)化問(wèn)題時(shí)選取了不同的等式關(guān)系改寫(xiě)了分布式優(yōu)化問(wèn)題,再利用原始對(duì)偶方法設(shè)計(jì)相應(yīng)的連續(xù)時(shí)間算法來(lái)求解.文獻(xiàn)[60]利用分?jǐn)?shù)階方法來(lái)設(shè)計(jì)分布式算法,其階次設(shè)計(jì)有更高的自由度.

將求解無(wú)約束線性矩陣方程轉(zhuǎn)化成分布式優(yōu)化問(wèn)題再設(shè)計(jì)算法的思路具有一定代表性,是可以適用于大多數(shù)常見(jiàn)的數(shù)據(jù)劃分類型的,同時(shí)也可以統(tǒng)一處理精確解和最小二乘解的情形.雖然該類算法理論上可以達(dá)到指數(shù)收斂,但由于問(wèn)題轉(zhuǎn)化過(guò)程會(huì)產(chǎn)生多個(gè)等式約束從而需要引入多個(gè)輔助變量,導(dǎo)致每個(gè)智能體計(jì)算的變量規(guī)模變大,通信復(fù)雜度也會(huì)相應(yīng)增加.文獻(xiàn)[58]雖然表面上沒(méi)有引入過(guò)多的輔助變量,但其討論的數(shù)據(jù)劃分方式受限,且需要假設(shè)精確解的存在性.未來(lái)考慮分布式矩陣計(jì)算的實(shí)際應(yīng)用場(chǎng)景時(shí),變量規(guī)模和通信代價(jià)的優(yōu)化也將是值得研究的問(wèn)題.

3.2 帶約束的矩陣方程求解

部分矩陣方程的求解是帶有約束條件的,一方面可能是由于方程本身的約束,比如Lyapunov方程是求正定解;另一方面是人為對(duì)解的選取,比如需得到對(duì)稱解、核范數(shù)較小的解或者較為稀疏的最小二乘解等.而針對(duì)這類問(wèn)題的一般策略是利用正交投影算子,在常規(guī)的變量動(dòng)力學(xué)或者迭代關(guān)系式中額外添加一步投影.Lyapunov方程在系統(tǒng)穩(wěn)定性分析中有著重要意義,一般帶約束問(wèn)題在如低秩矩陣數(shù)據(jù)恢復(fù)或推測(cè)中廣泛應(yīng)用.

針對(duì)Lyapunov方程,文獻(xiàn)[51-52]分別考慮了離散時(shí)間Lyapunov 方程(discrete time Lyapunov equation,DTLE)和連續(xù)時(shí)間Lyapunov 方程(continuous time Lyapunov equation,CTLE)在某種特定數(shù)據(jù)劃分下的分布式算法.實(shí)際上,當(dāng)文獻(xiàn)[51-52]中假設(shè)方程具有唯一解時(shí),該解的正定性約束可以自然忽略.

DTLE的一般形式為

其中A,X,Q ∈Rn×n且矩陣Q和未知X都應(yīng)是對(duì)稱正定矩陣.文獻(xiàn)[51]在假設(shè)方程式(20)有唯一解的前提下,討論了矩陣A按行劃分、矩陣Q按列劃分后的分布式離散時(shí)間算法,對(duì)每個(gè)計(jì)算智能體引入輔助變量Yi,把式(20)改寫(xiě)成方程組

然后,根據(jù)方程組(21)中前兩個(gè)的最小二乘殘差以及一致性誤差取定優(yōu)化問(wèn)題的目標(biāo)函數(shù).當(dāng)?shù)仁綕M足唯一解假設(shè)時(shí),該無(wú)約束優(yōu)化問(wèn)題的目標(biāo)函數(shù)為嚴(yán)格凸函數(shù),有全局最優(yōu)解.每個(gè)智能體依照更新迭代規(guī)則更新變量Xi和Yi:

CTLE的一般形式為

文獻(xiàn)[52]則考慮了連續(xù)時(shí)間Lyapunov方程(CTLE)的一種數(shù)據(jù)劃分下的分布式算法,具體來(lái)說(shuō),CTLE的數(shù)據(jù)劃分滿足

其中Ω是矩陣空間Rm×n的一個(gè)閉凸子集.DTLE可以看作約束集為對(duì)稱正定矩陣集的一類特殊的Stein方程.文獻(xiàn)[61]針對(duì)Stein方程提出了一個(gè)基于投影和鞍點(diǎn)動(dòng)力學(xué)的連續(xù)時(shí)間分布式算法.同樣以數(shù)據(jù)矩陣A,B,C的RCC劃分為例,式(25)等價(jià)于數(shù)據(jù)劃分后的方程組形式,然后根據(jù)方程組寫(xiě)出相應(yīng)的分布式優(yōu)化問(wèn)題之后,利用修正的拉格朗日函數(shù)L的鞍點(diǎn)動(dòng)力學(xué)來(lái)設(shè)計(jì)算法,與第3.1小節(jié)中無(wú)約束解方程問(wèn)題不同的是,因?yàn)樽兞縓i是限制在約束集里的,所以Xi的動(dòng)力學(xué)需要借助投影算子:

文獻(xiàn)[61]證明了所設(shè)計(jì)的分布式算法可以收斂到Stein方程的一個(gè)最小二乘解,特別地,當(dāng)約束集Ω為全空間時(shí),該算法(不帶投影)滿足指數(shù)收斂性.

另一種帶約束的矩陣方程問(wèn)題包括求方程的正則解,比如尋找一個(gè)稀疏解或者低秩解.文獻(xiàn)[56]考慮了Sylvester方程的正則解問(wèn)題

其中正則函數(shù)g(·)可以是非光滑凸函數(shù),如‖X‖1.類似求最小二乘解的方法,把式(27)轉(zhuǎn)化成一個(gè)非光滑函數(shù)的分布式凸優(yōu)化問(wèn)題再設(shè)計(jì)分布式算法求解.當(dāng)假設(shè)Sylvester方程存在對(duì)稱解時(shí),為了解出一個(gè)對(duì)稱解,文獻(xiàn)[58]中針對(duì)向量化的代數(shù)方程,在“一致+投影”方法的基礎(chǔ)上添加了一項(xiàng)新的對(duì)稱化投影來(lái)實(shí)現(xiàn)求解.

為了尋找低秩解,文獻(xiàn)[62]研究了滿足矩陣線性關(guān)系式的核范數(shù)最小的解,文中模型可以用來(lái)求解滿足代數(shù)方程的稀疏向量問(wèn)題,低秩矩陣的補(bǔ)全問(wèn)題等.文獻(xiàn)[62]采取的方法是根據(jù)矩陣分析的有關(guān)性質(zhì)把最小化非光滑的核范數(shù)轉(zhuǎn)化成最小化另一個(gè)半正定矩陣的跡的問(wèn)題,利用新的分布式優(yōu)化問(wèn)題設(shè)計(jì)原始對(duì)偶算法進(jìn)行求解,部分變量還需要被投影到半正定矩陣空間.

針對(duì)帶約束的矩陣方程求解問(wèn)題,現(xiàn)有算法的關(guān)鍵在于引入投影操作,由于矩陣變量的維數(shù)可能較大且約束集合可能比較復(fù)雜,因此,投影的代價(jià)不能一概而論.為應(yīng)對(duì)實(shí)際應(yīng)用中投影代價(jià)高可能帶來(lái)的挑戰(zhàn),研究無(wú)投影的分布式矩陣方程求解方法是一個(gè)重要的研究方向,其中一個(gè)可能的方法是借鑒優(yōu)化中的條件梯度法.

4 其他分布式矩陣計(jì)算問(wèn)題

除了上述線性矩陣方程的分布式求解問(wèn)題,還有其他的矩陣計(jì)算相關(guān)的分布式算法的研究,包括分布式求解線性矩陣不等式(LMI)問(wèn)題和非線性矩陣不等式問(wèn)題等.

4.1 分布式LMI問(wèn)題

即現(xiàn)在所說(shuō)的Lyapunov不等式,它是LMI的一種特殊形式.Lyapunov還證明了這種方程可以被顯式求解.通常,LMI有如下一般形式:

它表示了一類矩陣負(fù)定(或半負(fù)定)的不等式,其中系數(shù)矩陣均為對(duì)稱矩陣,同時(shí)也可以看作變量x=col(x1,··· ,xm)的一個(gè)凸集約束條件.LMI問(wèn)題應(yīng)用廣泛,在系統(tǒng)理論、控制理論和系統(tǒng)辨識(shí)等領(lǐng)域的很多問(wèn)題都與LMI問(wèn)題相關(guān)[63-64],例如非線性矩陣不等式(如代數(shù)Riccati方程)可以利用Schur補(bǔ)轉(zhuǎn)化成一個(gè)新的LMI,特征值問(wèn)題和半定規(guī)劃問(wèn)題都可以表述成是在LMI約束下的優(yōu)化問(wèn)題等等.

LMI問(wèn)題的集中式解法包括橢球算法、內(nèi)點(diǎn)法等[63].而在分布式設(shè)定下,比較有效的方法也是類似上一小節(jié)中求解矩陣方程的分布式凸優(yōu)化方法.文獻(xiàn)[65]研究了一類線性矩陣不等式組(LMIs)的分布式求解方法.參與計(jì)算的n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)中的智能體i只能獲取各自獨(dú)立的一個(gè)LMI:

最終所有智能體需估計(jì)出同時(shí)滿足n個(gè)LMIs的一致解[xi,1··· xi,m]T.首先,針對(duì)每個(gè)不等式,文獻(xiàn)[65]中引入了兩類松弛變量:半正定矩陣變量Yi和不小于某個(gè)負(fù)常數(shù)的實(shí)變量θi.借此把LMIs求解問(wèn)題轉(zhuǎn)化成帶有等式約束和正定集合約束的分布式凸優(yōu)化問(wèn)題,然后通過(guò)添加一致性約束寫(xiě)出相應(yīng)的拉格朗日函數(shù),并設(shè)計(jì)了基于投影算子的分布式原始對(duì)偶算法.

半定規(guī)劃問(wèn)題(semi-definite programming,SDP)是一類實(shí)線性函數(shù)的極小化問(wèn)題,在組合優(yōu)化、控制理論和統(tǒng)計(jì)學(xué)等領(lǐng)域都有著重要的意義和應(yīng)用價(jià)值[66].通?？紤]的模型是變量同時(shí)滿足一個(gè)LMI約束,具有的一般形式為

其中F(x)是滿足式(29)中形式的LMI約束[67].在適當(dāng)?shù)男问睫D(zhuǎn)化下,SDP問(wèn)題也可以直接表示成一個(gè)正定矩陣優(yōu)化問(wèn)題.文獻(xiàn)[68]研究了關(guān)于SDP問(wèn)題的分布式算法,具體考慮了以下形式的問(wèn)題:

并采用帶投影和導(dǎo)數(shù)反饋的分布式原始對(duì)偶算法進(jìn)行求解,其中正定矩陣空間上的正交投影的計(jì)算是利用矩陣的特征分解給出確切表達(dá)式.值得一提的是,在已有的工作中,很多關(guān)于SDP的研究都是圍繞稀疏矩陣的情況展開(kāi)的,參考文獻(xiàn)[69-72].在稀疏SDP的分布式算法研究中,文獻(xiàn)[70]基于SDP的弦稀疏性提出了一階分裂算法,文獻(xiàn)[72]利用弦分解將大規(guī)模的SDP以原始或?qū)ε夹问竭M(jìn)行降階表述,應(yīng)用了交替方向乘子法(alternating direction method of multipliers,ADMM)來(lái)進(jìn)行求解.文獻(xiàn)[71]依托一個(gè)固有的樹(shù)結(jié)構(gòu),采用了消息傳遞方法來(lái)計(jì)算搜索方向和步長(zhǎng),收斂速度較快,但它要求了信息傳遞的順序性.在文獻(xiàn)[68]中,針對(duì)稀疏情況,數(shù)據(jù)矩陣中的局部數(shù)據(jù)F0,Fi均有相應(yīng)的稀疏表達(dá)

其中EJi代表單位矩陣中相應(yīng)非零行列組成的子矩陣,同時(shí)稀疏的正定變量Z也有弦圖Gz和相應(yīng)子矩陣ZCk的劃分,從而矩陣Z的正定性可以由所有子矩陣ZCk,k=1,··· ,n的正定性給出[69].然后經(jīng)過(guò)分布式設(shè)定下的矩陣處理,稀疏SDP情形下式(32)可以轉(zhuǎn)化成如下分布式形式:

4.2 非線性矩陣不等式的分布式計(jì)算

除了線性矩陣方程和不等式問(wèn)題,與非線性矩陣方程相關(guān)的求解問(wèn)題[74-76]也一直受到研究關(guān)注.但由于非線性問(wèn)題沒(méi)有一般規(guī)則和統(tǒng)一形式,研究難度較大,通常會(huì)考慮和研究具有特殊形式的非線性方程或者不等式,典型問(wèn)題包括代數(shù)Riccati等式和不等式問(wèn)題.

Riccati方程是系統(tǒng)控制領(lǐng)域中的一類重要問(wèn)題,在最優(yōu)控制和魯棒控制[77-78]等方面都有應(yīng)用.該類方程的集中式解法例如不變子空間方法、基于牛頓的方法、ADI方法和加倍算法等[79-82]都需要利用全局信息來(lái)求解,不能直接處理分布式情況.在研究用分布式方法求解非線性矩陣等式或不等式的兩種常用思路是:1)拆解集中式算法中的步驟,把其中的子問(wèn)題轉(zhuǎn)化成可以分布式求解的問(wèn)題并設(shè)計(jì)相應(yīng)算法;2)利用矩陣?yán)碚撝械南嚓P(guān)等價(jià)性把非線性問(wèn)題轉(zhuǎn)化成更高維的線性矩陣問(wèn)題,再考慮進(jìn)行分布式求解.

文獻(xiàn)[83-84]分別研究了一類重要的非線性矩陣等式和不等式--連續(xù)時(shí)間的代數(shù)Riccati等式(continuous time algebra Riccati equation,CARE)

和代數(shù)Riccati不等式(algebra Riccati inequality,ARI)

并針對(duì)這兩類方程各自的數(shù)據(jù)劃分提出了相應(yīng)的分布式算法.

文獻(xiàn)[83]是以一類集中式算法--迭代細(xì)化方法(iterative refinement method,IRM)[80]為出發(fā)點(diǎn)來(lái)設(shè)計(jì)求解非線性矩陣方程式(34)的分布式算法,具體做法是把集中式IRM算法中的3個(gè)步驟拆分成3個(gè)子問(wèn)題,再根據(jù)分布式數(shù)據(jù)劃分下每個(gè)參與求解的智能體利用局部信息依次使用分布式迭代的離散時(shí)間算法來(lái)分別求解這3個(gè)子問(wèn)題.IRM的算法步驟以及對(duì)應(yīng)的分布式算法模塊示意圖如圖2.其中,第1個(gè)子問(wèn)題是包含非光滑項(xiàng)的耦合不等式約束,文中采取分布式鄰近點(diǎn)梯度法來(lái)處理,避免了使用非光滑函數(shù)的次梯度信息;第2個(gè)子問(wèn)題利用的是交替更新的原始對(duì)偶方法;第3個(gè)子問(wèn)題采用了常用的分布式平均算法得到網(wǎng)絡(luò)智能體合作估計(jì)的均值,最終3個(gè)子問(wèn)題整合起來(lái)實(shí)現(xiàn)CARE的分布式求解.

圖2 分布式IRM的算法結(jié)構(gòu)示意圖Fig.2 The structure of the distributed IRM algorithm

而文獻(xiàn)[84]是利用Schur補(bǔ)定理把非線性問(wèn)題(35)等價(jià)轉(zhuǎn)換成了一個(gè)較高階的LMI問(wèn)題,同時(shí)通過(guò)引入松弛變量把不等式關(guān)系變成等式,然后針對(duì)新轉(zhuǎn)換的分布式帶約束凸優(yōu)化設(shè)計(jì)了嚴(yán)格收斂、可求解ARI的分布式連續(xù)時(shí)間的帶投影原始對(duì)偶算法算法.

現(xiàn)有的研究成果在計(jì)算效率方面仍存在一定改進(jìn)空間,一方面是由于矩陣變量通常需要是正定矩陣,而維數(shù)較大的矩陣向正定矩陣集合投影的運(yùn)算復(fù)雜度較高.另一方面是很多問(wèn)題具有低秩等結(jié)構(gòu),現(xiàn)有的方法并未很好利用其特殊結(jié)構(gòu).因此,通過(guò)Burer-Monteiro分解方法或者流形優(yōu)化等研究分布式矩陣求解算法,可能更好的利用矩陣的低秩等結(jié)構(gòu)并避免正定矩陣的投影預(yù)算帶來(lái)的復(fù)雜性,從而提高計(jì)算效率.

5 總結(jié)與展望

本文從矩陣方程類型、數(shù)據(jù)劃分形式、方程解的類型、分布式算法等角度對(duì)矩陣方程的分布式計(jì)算方法的相關(guān)工作進(jìn)行了簡(jiǎn)要介紹.當(dāng)前矩陣相關(guān)問(wèn)題的分布式計(jì)算仍然是一個(gè)重要的研究方向,但目前的算法中應(yīng)用矩陣本身特殊性質(zhì)的比較少,多是基于一般的分布式優(yōu)化模型,由此會(huì)引入較多的輔助變量.如果能夠進(jìn)一步發(fā)掘矩陣特性并將其合理利用到分布式算法中,對(duì)優(yōu)化計(jì)算復(fù)雜度等方面會(huì)有重要意義,在實(shí)際應(yīng)用中也會(huì)有較大的提升空間.未來(lái)的研究方向可能還會(huì)包括:

1) 矩陣方程的隨機(jī)和在線分布式求解方法.一方面,大規(guī)模矩陣數(shù)據(jù)中存在隨機(jī)性和不確定性,利用隨機(jī)優(yōu)化算法可以降低算法計(jì)算復(fù)雜度,并求解概率意義下的未知矩陣變量;另一方面,矩陣中的數(shù)據(jù)可能隨時(shí)間改變,或者是以數(shù)據(jù)流的形式獲取,需要可以處理在線增量矩陣方程的方法.

2) 結(jié)構(gòu)化大規(guī)模矩陣方程的低計(jì)算和通信復(fù)雜度的分布式求解方法.大規(guī)模矩陣方程常常具有一些稀疏性或特殊結(jié)構(gòu),研究這些情況下如何降低求解過(guò)程中的計(jì)算和通信復(fù)雜度以建立更高效的分布式算法,比如利用矩陣的稀疏或其他特殊結(jié)構(gòu)和性質(zhì)進(jìn)行降維變換.

3) 針對(duì)矩陣優(yōu)化問(wèn)題的分布式高效求解算法.針對(duì)更一般的矩陣優(yōu)化問(wèn)題,如何結(jié)合矩陣的代數(shù)或者幾何意義和分布式優(yōu)化理論來(lái)設(shè)計(jì)有效的分布式算法具有重要的研究意義.