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

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

1 引言

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

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

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

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

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

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

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

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

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

3) 特殊矩陣結構下的方程求解,如滿足稀疏性.

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

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

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

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

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

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

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

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

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

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

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

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

研究矩陣方程的分布式算法的動機主要來源于以下3個方面:

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

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

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

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

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

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

2) 選取適當?shù)哪繕撕瘮?shù),其形式為每個智能體的局部目標函數(shù)之和;

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

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

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

3.1 無約束的矩陣方程求解

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

當方程式(9)的等式左邊只有一項時,文獻[57]首次用分布式方法求解了方程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 帶約束的矩陣方程求解

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

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

DTLE的一般形式為

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

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

CTLE的一般形式為

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

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

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

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

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

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

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

4 其他分布式矩陣計算問題

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

4.1 分布式LMI問題

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

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

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

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

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

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

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

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

4.2 非線性矩陣不等式的分布式計算

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

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

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

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

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

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

圖2 分布式IRM的算法結構示意圖Fig.2 The structure of the distributed IRM algorithm

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

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

5 總結與展望

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

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

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

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