姜霞，曾憲琳，孫健,*,陳杰,3

1. 北京理工大學(xué) 自動化學(xué)院，北京 100081 2.北京理工大學(xué)重慶創(chuàng)新中心，重慶 401120 3.同濟(jì)大學(xué) 電子與信息工程學(xué)院，上海 200082

隨著航空任務(wù)范圍的不斷擴(kuò)大、任務(wù)復(fù)雜度的增加和網(wǎng)絡(luò)通信能力的快速發(fā)展，航空領(lǐng)域需要越來越多的獨(dú)立個體通信合作形成機(jī)群，來完成復(fù)雜的大規(guī)模航空任務(wù)[1-2]。比如多個無人機(jī)合作完成區(qū)域的覆蓋控制和監(jiān)測[3-4]、多個飛行器的編隊(duì)和跟蹤[5-7]、多個無人機(jī)完成對區(qū)域中事件/物體的定位[8-9]、多個體之間通信網(wǎng)絡(luò)的拓?fù)鋬?yōu)化[10]等。在大量由多個飛行器合作完成的航空任務(wù)中，飛行器之間的通信網(wǎng)絡(luò)狀態(tài)錯綜復(fù)雜，分布式的局部數(shù)據(jù)獲取和有限的通信能力增加了航空任務(wù)完成的難度。隨著航空集群規(guī)模的日益龐大，實(shí)現(xiàn)不同飛行個體之間合理的調(diào)度和優(yōu)化任務(wù)變得尤為重要。

針對航空領(lǐng)域中的各種復(fù)雜的多飛行器合作決策的任務(wù)需求，大量的研究工作分別從集中式和分散式不同角度給出任務(wù)規(guī)劃控制和優(yōu)化設(shè)計(jì)的方案[11-12]。在不同的任務(wù)規(guī)劃和優(yōu)化方案中，每一個飛行器都被看作為一個具有通信和信息處理能力的自治節(jié)點(diǎn)。在集中式方法中，存在一個集中的節(jié)點(diǎn)，從各個子節(jié)點(diǎn)收集局部檢測的數(shù)據(jù)，在集中節(jié)點(diǎn)進(jìn)行優(yōu)化決策，然后再傳輸給子節(jié)點(diǎn)進(jìn)行控制決策。每個節(jié)點(diǎn)都需要與集中節(jié)點(diǎn)進(jìn)行大量數(shù)據(jù)的雙向通信，通信負(fù)擔(dān)較大，并且集中式的方法對中心計(jì)算節(jié)點(diǎn)的算力要求很高。在分散式優(yōu)化方法中，部分?jǐn)?shù)據(jù)在子節(jié)點(diǎn)進(jìn)行局部處理時，仍然需要中心節(jié)點(diǎn)進(jìn)行融合處理并將結(jié)果反饋給子節(jié)點(diǎn)。由于航空任務(wù)中飛行個體物理隔離，任務(wù)數(shù)據(jù)分布在不同的個體上，并且個體之間的通信網(wǎng)絡(luò)由于通信帶寬和穩(wěn)定性等原因變得復(fù)雜多變，因此，集中式和分散式的優(yōu)化控制策略往往無法高效、魯棒地完成復(fù)雜的航空任務(wù)。

在由多個個體組成的網(wǎng)絡(luò)系統(tǒng)中，物理隔離的個體由于具有獨(dú)立的收集、處理和傳輸數(shù)據(jù)的能力，可以通過通信網(wǎng)絡(luò)以合作的方式，在本地利用局部和鄰居信息進(jìn)行總體優(yōu)化問題的求解，稱為分布式優(yōu)化[13]。近些年迅速發(fā)展的無人機(jī)集群作戰(zhàn)就是分布式優(yōu)化應(yīng)用的重要場景之一，例如對動態(tài)敵對環(huán)境或危險環(huán)境的信息搜集，包括野火監(jiān)測、搜索救援任務(wù)、偵察監(jiān)視任務(wù)等，多個飛行器的分布式協(xié)同優(yōu)化可以避開空間內(nèi)的障礙限制，最大限度地探測任務(wù)空間內(nèi)的事件，完成監(jiān)測事件有效的數(shù)據(jù)收集。飛行器在空中作戰(zhàn)或者網(wǎng)絡(luò)狀態(tài)不佳的領(lǐng)域中，通過機(jī)載的通信傳感器搭建通信網(wǎng)絡(luò)。通過對不同飛行器之間通信拓?fù)錉顟B(tài)的分布式優(yōu)化，增強(qiáng)飛行器之間通信的魯棒性，對環(huán)境干擾和敵方進(jìn)攻都有很好的抵御作用。與集中式和分散式優(yōu)化相比，分布式優(yōu)化方法具有很多優(yōu)點(diǎn)。在分布式優(yōu)化中，每個飛行器將局部感知信息存儲在本地，并在本地節(jié)點(diǎn)進(jìn)行迭代處理，由于本地數(shù)據(jù)規(guī)模較小，飛行器節(jié)點(diǎn)的計(jì)算和存儲負(fù)擔(dān)降低。每個飛行器通過和網(wǎng)絡(luò)拓?fù)渲械泥従语w行器節(jié)點(diǎn)進(jìn)行通信完成總體任務(wù)的優(yōu)化，無需中心節(jié)點(diǎn)的存在，不依賴于中心節(jié)點(diǎn)的處理，由此避免了與中心節(jié)點(diǎn)的雙向通信，可以及時對局部任務(wù)變化做出反應(yīng)，靈活性更高。分布式優(yōu)化具有更好的可擴(kuò)展性和魯棒性，可以有效實(shí)現(xiàn)數(shù)據(jù)的隱私保護(hù)，在航空應(yīng)用中有很重要的意義。基于以上優(yōu)點(diǎn)，分布式優(yōu)化在航空領(lǐng)域得到了廣泛的關(guān)注和應(yīng)用。

經(jīng)過近十年的發(fā)展，多飛行器的分布式優(yōu)化問題的研究無論是從理論層面還是在實(shí)際應(yīng)用中都取得了長足的發(fā)展，本文從分布式優(yōu)化的研究現(xiàn)狀、研究的熱點(diǎn)難點(diǎn)以及未來的研究發(fā)展方向這3方面對分布式優(yōu)化的理論研究工作進(jìn)行簡要的歸類介紹。由于近些年來國內(nèi)外的分布式優(yōu)化成果較多，雖不能求述其全貌，但盡可能地包含近些年來應(yīng)用最廣泛的成果和工作。

1 分布式優(yōu)化的研究現(xiàn)狀

1.1 問題模型

在分布式優(yōu)化問題中，每個個體僅知道自己的局部目標(biāo)函數(shù)和約束信息，且這些信息由于隱私、安全等原因無法通信，導(dǎo)致分布式優(yōu)化算法的設(shè)計(jì)和分析變得復(fù)雜。在由m個個體構(gòu)成的網(wǎng)絡(luò)系統(tǒng)中，個體之間通過通信網(wǎng)絡(luò)，分享局部優(yōu)化決策變量來共同最小化(最大化)一個全局目標(biāo)函數(shù)，稱為分布式優(yōu)化問題。本文主要討論基于個體間共識的分布式優(yōu)化問題，其全局目標(biāo)函數(shù)往往是個體局部目標(biāo)函數(shù)的和函數(shù)：

式中：x∈Rn是全局優(yōu)化決策變量。由于局部目標(biāo)函數(shù)信息fi分布在不同的個體上，因此需要在每個個體上對全局優(yōu)化變量x進(jìn)行局部估計(jì)，即局部估計(jì)變量xi。分布式優(yōu)化問題的信息分布如圖1所示，不同個體i∈{1,2,…,5}之間通過網(wǎng)絡(luò)通信局部決策變量。

圖1 分布式優(yōu)化問題模型Fig.1 Model of distributed optimization problem

對于分布式一致共識優(yōu)化問題，既需要達(dá)到全局目標(biāo)的最小化(最大化)，又需要保證網(wǎng)絡(luò)中不同個體i、j的局部估計(jì)優(yōu)化變量達(dá)到一致，即xi=xj。對于分布式資源分配等非基于個體間共識的分布式優(yōu)化問題，由于篇幅原因，本文暫不做討論，相關(guān)介紹可以參考文獻(xiàn)[14-16]。

分布式優(yōu)化問題的優(yōu)化模型包含四大要素：變量、代價函數(shù)、約束和通信網(wǎng)絡(luò)。

1) 變量：在分布式優(yōu)化中，不同個體之間由于隱私安全或者帶寬限制等原因，無法共享局部函數(shù)信息和約束信息，只通信局部優(yōu)化變量，對于帶約束問題，根據(jù)算法設(shè)計(jì)的需要，共享對偶變量和輔助變量。因此，分布式算法可以有效地保護(hù)局部信息的隱私。

2) 代價函數(shù)：對于不同的應(yīng)用場景，分布式優(yōu)化會有不同類型的代價函數(shù)，不同的代價函數(shù)有其特定的性質(zhì)，影響分布式優(yōu)化算法的收斂性能和適用范圍。按照代價函數(shù)是否光滑，可分為光滑函數(shù)、非光滑函數(shù)。按照函數(shù)的凹凸性分為凸函數(shù)、嚴(yán)格凸函數(shù)、強(qiáng)凸函數(shù)和非凸函數(shù)。按照函數(shù)信息是否隨時間實(shí)時變化分為時變函數(shù)和時不變函數(shù)。一個分布式優(yōu)化問題的代價函數(shù)可以由不同類型的函數(shù)構(gòu)成，比如在經(jīng)典線性回歸問題中，目標(biāo)函數(shù)由光滑凸函數(shù)和非光滑L1正則函數(shù)構(gòu)成。

3) 約束：實(shí)踐應(yīng)用中的分布式優(yōu)化問題，往往存在一些現(xiàn)實(shí)的約束。按照約束的類型，可以分為集合約束、等式約束和不等式約束。根據(jù)不同的實(shí)際應(yīng)用，集合約束既可以是全局的集合約束，也可以是多個局部集合約束的交集；等式約束可以是線性的或非線性的；不等式約束可以是凸的，也可以是非凸的。

4) 通信網(wǎng)絡(luò)：分布式優(yōu)化基于傳輸網(wǎng)絡(luò)進(jìn)行個體間信息的交互。根據(jù)實(shí)踐中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是否時變分為固定拓?fù)浜蛣討B(tài)拓?fù)?。根?jù)信息傳遞是否具有方向性分為無向圖和有向圖。根據(jù)網(wǎng)絡(luò)拓?fù)涞倪B接結(jié)構(gòu)可分為平衡圖和非平衡圖。在實(shí)際應(yīng)用中，網(wǎng)絡(luò)通信往往會出現(xiàn)擁堵，造成通信延遲，因此很多工作研究存在時間延遲的通信網(wǎng)絡(luò)下的分布式優(yōu)化[17-20]。

1.2 分布式優(yōu)化方法研究框架

本節(jié)將從不同角度對現(xiàn)有的分布式優(yōu)化方法的研究框架進(jìn)行分類介紹。

1.2.1 按原始變量和原始-對偶框架的算法分類

一般的分布式優(yōu)化問題形式為

(1)

式中：函數(shù)g是約束函數(shù)，對于分布式優(yōu)化問題，約束函數(shù)往往包括不同個體之間局部變量一致的等式約束；變量x是優(yōu)化問題的原始變量。該優(yōu)化問題的拉格朗日對偶函數(shù)為

對偶問題為

maximizeyr(y)

subject toy≥0

其中：變量y是優(yōu)化問題的對偶變量。函數(shù)

L(x,y)=f(x)+yTg(x)

稱為原始優(yōu)化問題的拉格朗日函數(shù)。對于不等式約束的凸優(yōu)化問題，在一定假設(shè)下，原始問題的最優(yōu)變量x*和最優(yōu)對偶變量y*滿足如下Karush-Kuhn-Tucker (KKT)條件，即

相關(guān)的理論證明可以參考文獻(xiàn)[21]。

直接對原始優(yōu)化問題進(jìn)行求解的方法稱為基于原始變量的優(yōu)化方法，例如對于一般無約束優(yōu)化問題，梯度法、牛頓法及其變種方法[21]都是原始變量法。對于帶有一致性約束的分布式優(yōu)化問題，可以通過變量一致技術(shù)[22-23]或者梯度跟蹤技術(shù)[24-27]實(shí)現(xiàn)對原始優(yōu)化問題的高效求解，具體的算法設(shè)計(jì)在1.3節(jié)中討論。對于帶有不等式約束的優(yōu)化問題，經(jīng)常用的算法之一是利用懲罰項(xiàng)將約束引入目標(biāo)函數(shù)，利用外罰函數(shù)法或者內(nèi)點(diǎn)法[28]進(jìn)行求解。這些方法都是原始變量法，直接對原始變量進(jìn)行迭代更新。

處理帶約束分布優(yōu)化問題的另外一種思路是通過引進(jìn)對偶變量，構(gòu)造最優(yōu)解的KKT條件，利用KKT條件構(gòu)造優(yōu)化算法。一些典型的原始-對偶法包括對偶分解法[29-30]、增廣拉格朗日乘子法[10]、原始-對偶法[31-33]、交換乘子算法(ADMM)[34-36]等。原始-對偶方法對比原始變量法，在進(jìn)行分布式優(yōu)化問題的算法設(shè)計(jì)時，設(shè)計(jì)代價較低，分析方法較為普適。但是對比原始變量法，其增加了優(yōu)化算法的維度，加大了存儲空間代價。

1.2.2 按梯度階數(shù)的算法分類

根據(jù)分布式優(yōu)化算法設(shè)計(jì)中使用的函數(shù)梯度信息分為一階梯度法、二階梯度法和零階梯度法。在算法迭代時，如果需要利用目標(biāo)函數(shù)的一階梯度信息，則該類算法稱為一階算法；如果變量迭代時需要利用函數(shù)的二階導(dǎo)數(shù)信息或者Hessian矩陣信息時，則該類算法稱為二階算法；如果算法迭代時，沒有利用到函數(shù)的任何梯度信息，則稱為零階算法。

一階算法[26,37-39]是處理分布式優(yōu)化問題最為常用的方法，因?yàn)槠湟浑A梯度的計(jì)算代價較低，易于寫成分布式的結(jié)構(gòu)，且一階算法的收斂性分析較為成熟，滿足大多數(shù)應(yīng)用對于收斂精度的要求。二階算法[40-42]在求解低維優(yōu)化問題時，往往比一階算法具有更快的收斂速度，但是函數(shù)的Hessian信息往往求解代價較大，無法應(yīng)用于高維復(fù)雜的優(yōu)化問題，因此很多工作[40,42]也在探究估計(jì)二階信息的方法，來彌補(bǔ)其求解代價大的不足。在一些實(shí)際應(yīng)用中，比如函數(shù)信息為噪聲函數(shù)值時，或者函數(shù)為區(qū)間函數(shù)時，精確的梯度信息往往求解困難，算法往往根據(jù)函數(shù)值來對梯度進(jìn)行估計(jì)。零階梯度法[43-45]利用近似梯度的思想，通過函數(shù)值對梯度信息進(jìn)行近似，實(shí)現(xiàn)只利用函數(shù)信息對問題進(jìn)行優(yōu)化。

1.2.3 按連續(xù)時間和離散時間的算法分類

根據(jù)變量迭代方式的不同，分為連續(xù)時間算法和離散時間算法。在節(jié)點(diǎn)位置配置、網(wǎng)絡(luò)拓?fù)鋬?yōu)化、資源能量分配等應(yīng)用場景中，適用離散時間算法[37-50]。而且離散時間算法可以利用高性能的計(jì)算機(jī)進(jìn)行快速迭代求解。但是在一些變量狀態(tài)連續(xù)變化的系統(tǒng)任務(wù)應(yīng)用[51]中，例如多運(yùn)動體的最優(yōu)編隊(duì)、最優(yōu)位置姿態(tài)控制等，離散算法無法保持變量值的連續(xù)。可以通過搭建模擬電路實(shí)現(xiàn)低成本、低功耗的連續(xù)時間求解器來求解問題。因此，近年來連續(xù)時間算法[52-54]受到了研究者的關(guān)注。

連續(xù)時間算法和離散時間算法除了在任務(wù)應(yīng)用和算法實(shí)現(xiàn)方面不同外，在算法的分析方面，也有較大的差異。離散時間算法的分析往往利用差分方程的分析思路討論優(yōu)化變量距離最優(yōu)解的距離變化，或者是函數(shù)值隨著迭代次數(shù)增加的收斂變化。而連續(xù)時間算法的分析往往是通過提出合理的李雅普諾夫函數(shù)，通過利用穩(wěn)定性理論來討論優(yōu)化變量和函數(shù)值的收斂變化。

1.3 典型的分布式優(yōu)化算法

針對分布式優(yōu)化問題的不同模型要素和研究框架，研究者提出了多種分布式優(yōu)化算法。由于工作較多，本文只簡要介紹無約束分布式凸優(yōu)化問題、集合約束的分布式凸優(yōu)化問題、不等式約束的分布式凸優(yōu)化問題和分布式非凸優(yōu)化問題的典型分布式一階算法研究成果。關(guān)于分布式二階算法和零階算法的研究，可以參考文獻(xiàn)[40-41，52]。在不加說明的情況下，本文的通信拓?fù)涠贾复鸁o向圖，除非另有說明為有向圖。

1.3.1 無約束分布式優(yōu)化

針對模型目標(biāo)問題為凸光滑函數(shù)的無約束優(yōu)化問題，其典型的應(yīng)用之一是多個體一致性問題。例如，文獻(xiàn)[55]提出的多個無人機(jī)的分布式優(yōu)化部署問題，需要在每架無人機(jī)上進(jìn)行本地運(yùn)算，單獨(dú)決定其運(yùn)動的控制框架就是一個典型的無約束優(yōu)化問題。

利用變量一致性技術(shù)，分布式梯度下降、分布式增量梯度下降法等都可以實(shí)現(xiàn)對優(yōu)化問題的高效分布式求解。無約束分布式優(yōu)化問題和算法設(shè)計(jì)架構(gòu)如下：

其等式約束是為了保證局部估計(jì)變量達(dá)到一致，局部變量估計(jì)xi∈Rn。對于分布式優(yōu)化問題，局部代價函數(shù)最優(yōu)并不等價于全局代價函數(shù)最優(yōu)，因此，需要在保證局部估計(jì)變量一致的約束下，優(yōu)化總體代價函數(shù)?；谧兞恳恢滦约夹g(shù)的經(jīng)典分布式梯度下降(DGD)算法設(shè)計(jì)為

(2)

式中：aij為拓?fù)鋱D鄰接矩陣的第i行第j列個元素，步長αi為衰減步長，可以保證算法的有效收斂。同時，為了加快收斂速度，很多優(yōu)秀的工作通過使用歷史信息，設(shè)計(jì)固定步長的分布式算法，典型的工作包括EXTRA[37]、PG-extra[46]以及EXTRA的推廣方法[47]?？紤]到個體更新梯度可能存在隨機(jī)誤差，文獻(xiàn)[23]提出在動態(tài)連通拓?fù)湎碌姆植际诫S機(jī)增量梯度法，使得不同個體的局部變量均收斂到共同的全局最優(yōu)解。

另外一種設(shè)計(jì)分布式優(yōu)化算法的思路是利用梯度跟蹤技術(shù)，根據(jù)不同梯度跟蹤方法，提出不同的分布式優(yōu)化策略DIGing(Distributed Inexact Gradient Tracking Method)[24]、Aug-DGM(Augmented Distributed Gradient Method)[25]、AsynDGM(Asynchronous Distributed Gradient Method)[26]和ATC-DIGing(Adapt-Then-Combine ariation of DIGing)[27]。經(jīng)典的方法之一如下該算法運(yùn)用固定迭代步長，可以實(shí)現(xiàn)靜態(tài)圖下不同個體變量收斂到共同的全局最優(yōu)解。進(jìn)一步的，DIGing算法和Push-DIGing算法[24]分別實(shí)現(xiàn)了動態(tài)拓?fù)鋱D和有向圖下的有效收斂。尤其，在優(yōu)化問題的代價函數(shù)為強(qiáng)凸時，梯度跟蹤方法可以達(dá)到比變量一致方法更好的指數(shù)收斂性能。圖2對以上所提算法之間的關(guān)系進(jìn)行了匯總比較，以上方法均為在原始域內(nèi)進(jìn)行優(yōu)化的分布式算法。

圖2 分布式算法關(guān)系圖Fig.2 Relationships of distributed algorithms

如果拓?fù)鋱D為無向圖，則L=LT，其對應(yīng)的原始-對偶變量迭代公式為

圖3 增廣拉格朗日法對應(yīng)比例積分反饋控制Fig.3 PI control viewpoint for augmented Lagrangian method

基于原始-對偶設(shè)計(jì)框架，提出不同的分布式優(yōu)化求解方法，包括原始-對偶方法[31,60-61]、對偶分解法[30,62]、交替方向乘子法(ADMM)[34-36]、交替最小化[42,63]等。在對無人機(jī)編隊(duì)問題中的協(xié)作問題，文獻(xiàn)[64]提出基于對偶分解技術(shù)的算法，直觀地用許多較小的可處理問題代替了一個大型的計(jì)算難題，返回原問題的一個可行解。類似的，在ADMM法、交替最小化方法中，原始變量不采用原始方法中的梯度下降迭代方法，而是采用當(dāng)前子優(yōu)化問題的最優(yōu)值。具體來說，對于多變量的無約束分布式優(yōu)化問題，通過引入連通拓?fù)鋱D的邊點(diǎn)關(guān)聯(lián)矩陣A∈Rmn，可以得到如下的優(yōu)化問題

式中:α為與時間無關(guān)的固定更新步長，其取值往往與目標(biāo)函數(shù)的參數(shù)有關(guān)。

雖然每次迭代都要求解一個子優(yōu)化問題，但是當(dāng)子問題可以獲得封閉解或者易于求解時，交替乘子算法往往具有更好的實(shí)際應(yīng)用性能。上述多變量算法實(shí)際上是針對雙變量分布式優(yōu)化問題的ADMM推廣，可以更為高效的求解多體分布式優(yōu)化問題[65]。進(jìn)一步的，文獻(xiàn)[66]給出了無次序更新的交換乘子分布式求解方法，減少了對于通信拓?fù)浜透马樞虻囊蕾?，擴(kuò)大了算法的應(yīng)用范圍。

1.3.2 集合約束的分布式優(yōu)化

對于凸集合約束下的優(yōu)化問題，在文獻(xiàn)[67]中，針對個體在障礙存在的環(huán)境下的路徑規(guī)劃問題，討論了如何建立問題的優(yōu)化模型，并設(shè)計(jì)算法有效求解多障礙集合約束下的優(yōu)化問題。在任務(wù)問題中，當(dāng)個體存在凸集合約束時，其分布式優(yōu)化問題模型為

式中：Ωi為個體i的局部凸集合約束，這樣的分布優(yōu)化問題又稱凸交問題。在多個飛行器任務(wù)中，由于單個飛行器的計(jì)算、通信和可見半徑有限，需與其鄰居共享信息以進(jìn)行協(xié)調(diào)，因此，在有動態(tài)或者靜態(tài)障礙物環(huán)境下的多個體編隊(duì)與導(dǎo)航就是一個典型的分布式凸交問題[68]。

當(dāng)優(yōu)化問題的集合約束為局部約束的交集時，文獻(xiàn)[13]提出固定/時變連通圖下的高效分布式投影算法為

式中：PΩi(·)為向局部可行集合Ωi投影操作。當(dāng)梯度為零時，該算法退化為求解一致性優(yōu)化問題的分布式算法，對應(yīng)的算法投影示意圖如圖4所示，其中對于i∈{1,2}，

圖4 分布式投影算法圖示Fig.4 Illustration of distributed projection algorithm

式中:aij(k)為k時刻的多節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)涞泥徑泳仃囋亍?/p>

文獻(xiàn)[69]進(jìn)一步將該算法拓展到時變有向平衡圖，并考慮了在存在各種不確定性的情況下，包括有噪聲的通信鏈路、隨機(jī)通信圖以及目標(biāo)函數(shù)次梯度評價中的隨機(jī)誤差時的分布式優(yōu)化問題。由于優(yōu)化問題信息的分散化和集合投影運(yùn)算代價較高，文獻(xiàn)[70]中提出不精確的凸投影共識算法，降低了投影運(yùn)算的代價，使不同個體達(dá)到全局凸交集中共同的最優(yōu)解。

1.3.3 不等式約束的分布式優(yōu)化

在一些多飛行器的應(yīng)用任務(wù)中，任務(wù)的個體既需要滿足自身的集合約束，又需要滿足不等式函數(shù)或者等式函數(shù)約束。由于等式約束可以用不等式約束表達(dá)，僅討論不等式約束的分布式優(yōu)化問題。包含多種集合和不等式約束的分布式優(yōu)化問題形式如下

式中：函數(shù)f(x)、g(x)為凸函數(shù)，全局不等式約束認(rèn)為是分量滿足的，也就是說分量gl(x)≤0，l∈{1,2,…,m}。不同個體的約束函數(shù)gl(x)既可以是統(tǒng)一約束函數(shù)，也可以不同。一般的優(yōu)化方法是通過引入對偶變量，根據(jù)優(yōu)化問題的KKT條件，設(shè)計(jì)對應(yīng)的求解算法。例如，在文獻(xiàn)[64]中利用原始-對偶的思想，對由大量的無人機(jī)組成的網(wǎng)絡(luò)，在分布式、易受干擾、可能存在競爭的環(huán)境下，研究了一個新的分布式控制框架，實(shí)現(xiàn)完全可重構(gòu)的無人機(jī)網(wǎng)絡(luò)平臺。針對優(yōu)化問題，其對應(yīng)的拉格朗日函數(shù)為

L(k)=f(x(k))+mμTg(x(k))=

式中，μ∈Rm為不等式約束對應(yīng)的對偶變量；Li(k)為個體i對應(yīng)的拉格朗日函數(shù)。基于拉格朗日函數(shù)鞍點(diǎn)的性質(zhì)，文獻(xiàn)[71]提出了分布式拉格朗日原始-對偶次梯度算法為

式中:Mi為對偶域，收斂步長α(k)為衰減步長。該算法實(shí)現(xiàn)了在切換有向拓?fù)溥B通下，漸近穩(wěn)定收斂到全局最優(yōu)點(diǎn)。然而，衰減步長算法隨著迭代次數(shù)的增加，收斂速度將受到限制。在固定連通拓?fù)湎?，文獻(xiàn)[32]提出了具有非一致固定步長的分布式優(yōu)化方法，并且在每個協(xié)商一致步驟中執(zhí)行多個協(xié)商一致更新的情況，加快了個體的收斂性能。文獻(xiàn)[33]研究了時變拓?fù)渚W(wǎng)絡(luò)中帶約束凸優(yōu)化問題的最小化問題，通過設(shè)計(jì)正規(guī)化的拉格朗日函數(shù)，提出了一種基于一致性的正則化原始-對偶次梯度法。該方法的實(shí)現(xiàn)只需要在最后一次迭代時進(jìn)行一次投影，避免了每次迭代都需要進(jìn)行投影運(yùn)算的代價。

1.3.4 分布式非凸優(yōu)化

在現(xiàn)實(shí)應(yīng)用中，由于很多任務(wù)目標(biāo)或者約束都是非凸的，非凸優(yōu)化的算法成為近些年來研究熱點(diǎn)和難點(diǎn)。航空任務(wù)中，比如路徑規(guī)劃、最優(yōu)覆蓋等任務(wù)中存在很多非凸問題。解決方法之一是將非凸優(yōu)化問題轉(zhuǎn)化為凸優(yōu)化問題，利用凸函數(shù)的性質(zhì)進(jìn)行求解。例如，針對基于非凸二次型的飛機(jī)三維路徑規(guī)劃問題，文獻(xiàn)[72]將非凸規(guī)劃問題轉(zhuǎn)換為半正定優(yōu)化問題，利用半正定優(yōu)化得到其最優(yōu)值的緊下界，然后再利用秩最小化得到規(guī)劃問題的最優(yōu)函數(shù)值。

非凸問題的另一種解決方法是直接針對非凸優(yōu)化問題，通過one-point凸技術(shù)或者近似技術(shù)提出有效的求解方法。針對具有特殊結(jié)構(gòu)的非凸優(yōu)化問題，文獻(xiàn)[73]提出了分布式梯度下降法，并證明了在一定條件下，算法收斂到非凸優(yōu)化問題的二階駐點(diǎn)(Second-Order Stationary Point)。分布式隨機(jī)梯度下降是目前直接處理非凸優(yōu)化問題的比較成熟的方法，可以有效逃離嚴(yán)格鞍點(diǎn)，具有較好的收斂性能，一些典型的分布式隨機(jī)梯度優(yōu)化算法工作包括文獻(xiàn)[74-78]，其經(jīng)典的算法設(shè)計(jì)如下：

αkgi(xi(k))

式中:αk、βk為可調(diào)節(jié)步長；aij為通信網(wǎng)絡(luò)鄰接矩陣元素；gi函數(shù)為局部函數(shù)梯度估計(jì)，該梯度既可以是簡單隨機(jī)梯度，也可以是小批量隨機(jī)梯度或隨機(jī)擬牛頓方向。上述算法是基于變量一致原則進(jìn)行分布式算法設(shè)計(jì)。針對經(jīng)驗(yàn)風(fēng)險最小化問題，即

文獻(xiàn)[79]中基于梯度跟蹤技術(shù)，給出如下分布式隨機(jī)梯度算法設(shè)計(jì)：

對于目標(biāo)函數(shù)中含有不可微子函數(shù)的雙變量非凸優(yōu)化問題[80]，優(yōu)化的思路是使用交替最小化的方法來解決，并進(jìn)一步推廣到多變量的情景。包含不可微的非凸優(yōu)化問題的一般形式為

minimizex,y∈Rnf(x,y)=J(x)+F(x,y)+R(y)

(4)

式中:γx、γy分別為可調(diào)節(jié)的更新步長。由于該算法的子問題往往無法得到封閉解，需要內(nèi)部子迭代，降低了算法的性能。針對這個缺點(diǎn)，文獻(xiàn)[81]中利用近似算子，提出線性化算法(5)，使得子問題可以進(jìn)行高效求解，提高了交換乘子法的性能,

(5)

其中，近似算子定義如下

算法(5)可以保證收斂到非凸問題的駐點(diǎn)，目前已有一些優(yōu)秀的工作探討了方法求解非凸優(yōu)化問題的收斂性能，并提出了該方法的加速和隨機(jī)版本[82-83]。方法(5)可以由處理雙變量問題擴(kuò)展到處理多個變量的問題，但是每個變量更新都需要完整的F函數(shù)的信息，不適用完全分布式的優(yōu)化問題。針對個體之間拓?fù)溥B通的情況，文獻(xiàn)[38]中，提出了完全分布式的近似梯度法(Prox-DGD)，保證了無向連通網(wǎng)絡(luò)中每個個體的局部變量都收斂到非凸問題的駐點(diǎn)。

針對不同類型優(yōu)化問題，本文提及的相關(guān)算法工作可以粗略匯總?cè)绫?所示。從表1數(shù)據(jù)可以看出分布式凸優(yōu)化成果豐富，而分布式非凸優(yōu)化的理論研究較少，尤其是集合約束下和不等式約束下的非凸優(yōu)化問題，這也是分布式優(yōu)化研究的難點(diǎn)方向之一。

表1 分布式算法工作匯總Table 1 Summary of distributed algorithm works

2 分布式優(yōu)化的研究難點(diǎn)和未來展望

2.1 分布式優(yōu)化的研究展望

由于數(shù)據(jù)規(guī)模的迅速增大和信息的分散化，分布式優(yōu)化的研究近些年來得到了廣泛的關(guān)注和長足的發(fā)展。未來分布式優(yōu)化的研究展望包括如何加速分布式優(yōu)化算法，在動態(tài)網(wǎng)絡(luò)連接狀態(tài)下分布式優(yōu)化算法設(shè)計(jì)以及對于復(fù)雜的帶約束非凸優(yōu)化問題，如何設(shè)計(jì)分布式優(yōu)化算法。

2.1.1 分布式加速算法

實(shí)現(xiàn)分布式優(yōu)化算法加速的另一個方法是利用方差減小(Variance Reduction)的技術(shù)。對于數(shù)據(jù)樣本量很大的優(yōu)化問題，求取完整的個體梯度仍然是一個耗時的操作，在對實(shí)時性要求較高的實(shí)際航空任務(wù)中，難以實(shí)現(xiàn)求取完整的個體梯度，因此很多研究工作中，采用隨機(jī)采樣個體本地的樣本數(shù)據(jù)求取個體的隨機(jī)梯度的方法來估計(jì)完整梯度。方差減小技術(shù)可以降低局部的梯度方差，使得個體可以用隨機(jī)采樣的個體梯度來估計(jì)完整的個體梯度。文獻(xiàn)[84，92，93]將不同的方差減少技術(shù)與基于變量一致的分布式算法結(jié)合，提出了更為高效的分布式優(yōu)化算法，降低了計(jì)算完整個體梯度的代價，使得算法在面對實(shí)際任務(wù)中大規(guī)模數(shù)據(jù)時仍然可以高效地決策控制，但是同時利用梯度跟蹤和方差減小技術(shù)實(shí)現(xiàn)局部和全局梯度的準(zhǔn)確估計(jì)，從而降低步長對于大規(guī)模數(shù)據(jù)樣本問題下優(yōu)化算法的影響，進(jìn)一步提高分布式算法的性能，目前還未有較為成熟的理論研究。

2.1.2 動態(tài)拓?fù)湎碌姆植际絻?yōu)化

針對大規(guī)模多個體網(wǎng)絡(luò)上的分布式優(yōu)化問題，分布式算法的性能受到個體之間網(wǎng)絡(luò)拓?fù)溥B接的影響。受航空任務(wù)環(huán)境中各種復(fù)雜因素的影響以及網(wǎng)絡(luò)通信帶寬的限制，個體之間的有向/無向拓?fù)溥B接往往是動態(tài)變化的。文獻(xiàn)[22]中，討論了在無向動態(tài)拓?fù)湎碌姆植际絻?yōu)化問題，并給出了基于變量一致的分布式梯度下降方法的收斂性能。對于基于梯度跟蹤技術(shù)的分布式優(yōu)化方法，文獻(xiàn)[24]中給出了其可以實(shí)現(xiàn)在動態(tài)拓?fù)渖线_(dá)到線性收斂速率的分析。由于網(wǎng)絡(luò)資源有限，在航空任務(wù)應(yīng)用中，無向網(wǎng)絡(luò)拓?fù)渫y以實(shí)現(xiàn)，飛行器之間大多以有向通信拓?fù)溥B接為主。針對動態(tài)有向拓?fù)湎碌姆植际酵?非凸優(yōu)化問題，文獻(xiàn)[95-97]提出了高效的分布式優(yōu)化算法，并給出了收斂性能分析。對于動態(tài)有向/無向連接拓?fù)?，文獻(xiàn)[98]使用通信輪數(shù)和梯度評估之間的優(yōu)化比率，實(shí)現(xiàn)算法快速收斂，并且，根據(jù)梯度評估的數(shù)量來衡量，該算法迭代收斂到全局最優(yōu)解的速度與集中式梯度下降相同。

2.1.3 帶約束的非凸優(yōu)化

在多飛行器完成的航空任務(wù)中，比如路徑規(guī)劃、最優(yōu)覆蓋等，很多任務(wù)目標(biāo)或者約束都是非凸的，文獻(xiàn)[72]已經(jīng)研究了在無約束情況下非凸二次型的飛機(jī)三維路徑規(guī)劃問題，當(dāng)非凸問題中包含集合或者不等式約束時，算法的設(shè)計(jì)需要進(jìn)一步改進(jìn)。對于帶有全局集合約束的分布式非凸優(yōu)化問題，文獻(xiàn)[99]基于梯度跟蹤的思路，提出了分布式非凸優(yōu)化方法，證明了個體局部變量達(dá)到一致的變量均值，并收斂到優(yōu)化問題的共同駐點(diǎn)。對于帶有線性等式函數(shù)約束的非凸優(yōu)化問題，文獻(xiàn)[80]從原始-對偶的角度給出了高效的分布式優(yōu)化算法，并證明了算法可以以次線性收斂速度，全局收斂于駐點(diǎn)集合。當(dāng)非凸優(yōu)化問題具有更為復(fù)雜的非線性耦合的非凸約束時，文獻(xiàn)[29]從對偶角度，提出了雙層迭代的優(yōu)化方法，并給出了可以收斂到優(yōu)化問題KKT解的嚴(yán)格證明。但是，目前對于各種約束下的非凸優(yōu)化問題的研究，都未給出收斂到全局最優(yōu)解的性能分析。對于現(xiàn)實(shí)航空任務(wù)中更為復(fù)雜約束下的非凸優(yōu)化問題，其高效的分布式算法設(shè)計(jì)仍然是目前的研究熱點(diǎn)。

2.2 分布式優(yōu)化的共性難點(diǎn)

在大規(guī)模多飛行器的分布式優(yōu)化中，個體之間借助機(jī)載通信設(shè)備網(wǎng)絡(luò)實(shí)現(xiàn)信息的交互。不同飛行器之間的計(jì)算時序和速度有差別，通信能力有限，且環(huán)境干擾因素較多，因此本節(jié)中對通信時延、干擾誤差、異步迭代和通信計(jì)算權(quán)衡等是分布式優(yōu)化算法設(shè)計(jì)中共有的難點(diǎn)進(jìn)行簡要介紹。

1) 通信時延是大型網(wǎng)絡(luò)中不可避免的通信問題。當(dāng)個體在與鄰居之間的通信延遲時間一致并可能無限大時，文獻(xiàn)[17]給出了分布式算法求解可微凸目標(biāo)函數(shù)的收斂速度與網(wǎng)絡(luò)大小、拓?fù)浣Y(jié)構(gòu)和處理器間通信延遲的函數(shù)關(guān)系的上界?；跓o源性理論，文獻(xiàn)[18]分析了在無向固定拓?fù)湎?，連續(xù)時間算法求解分布式無約束和有約束優(yōu)化問題時，如何有效處理任意未知的恒定通信延遲。對于梯度連續(xù)的強(qiáng)凸代價函數(shù)，文獻(xiàn)[19]研究了在具有時變延時的有向圖下，分布式算法保證所有的個體收斂于系統(tǒng)最優(yōu)解的充分條件。但是針對實(shí)際應(yīng)用中更為一般的優(yōu)化問題，如何在復(fù)雜的網(wǎng)絡(luò)通信情況下保證分布式算法的收斂性能仍然是目前的難點(diǎn)問題。

2) 個體迭代利用的梯度信息無法精確獲得。單個個體在利用梯度信息進(jìn)行迭代時，由于外界環(huán)境的干擾或者自身運(yùn)算誤差等原因，往往無法得到精確的梯度信息。在動態(tài)切換拓?fù)溥B通圖下，文獻(xiàn)[23]針對全局集合約束的分布式凸優(yōu)化問題，提出了分布隨機(jī)次梯度投影算法，探討了隨機(jī)次梯度誤差對算法收斂性能的影響，保證算法的有效收斂。文獻(xiàn)[19]進(jìn)一步將工作擴(kuò)展到非凸優(yōu)化問題，證明了通過合理調(diào)整步長，分布式隨機(jī)梯度方法仍然可以收斂到問題的臨界點(diǎn)集合。但是對于非凸優(yōu)化問題，并未給出全局收斂的理論研究結(jié)果，隨機(jī)梯度誤差對任務(wù)中復(fù)雜有向拓?fù)湎路植际剿惴ǖ氖諗啃阅艿挠绊懩壳斑€沒有研究成果。

3) 同步的全局時鐘在分布式算法應(yīng)用中難以滿足。在分布式系統(tǒng)中，同步的分布式算法需要全局時鐘進(jìn)行時序控制，因此往往無法適用于實(shí)際的應(yīng)用場景。在無法保證同步的全局時序情況下，大量的工作研究分布式異步算法，以確保個體在本地時鐘下局部迭代仍然可以實(shí)現(xiàn)全局收斂，而無需時鐘同步。異步的分布式優(yōu)化方法同時也解決了由信息時延帶來的無法獲得實(shí)時信息的問題。異步優(yōu)化方法可以分為完全異步方法和部分異步方法，相關(guān)的工作可以參考文獻(xiàn)[100-103]。完全異步方法由于假設(shè)嚴(yán)格，只有少數(shù)算法可以在滿足假設(shè)的情況下，實(shí)現(xiàn)高效異步收斂；而對于部分異步方法，目前的分布式算法研究主要集中在收斂性上，而對于算法的收斂速度以及動態(tài)有向拓?fù)渚W(wǎng)絡(luò)下的分布式算法研究成果較少。

4) 合理地平衡分布式算法的計(jì)算負(fù)擔(dān)和通信負(fù)擔(dān)是影響算法性能的重要因素。在多個體網(wǎng)絡(luò)中，由于不同個體在物理環(huán)境中分離，個體之間的通信帶寬有限且不穩(wěn)定，迫切需要減輕網(wǎng)絡(luò)的通信負(fù)擔(dān)。研究分布式優(yōu)化算法的通信效率問題，尤其是在經(jīng)驗(yàn)風(fēng)險最小化方面，近年來得到蓬勃發(fā)展。文獻(xiàn)[104]系統(tǒng)地探討了分布式算法的收斂速度與節(jié)點(diǎn)通信的網(wǎng)絡(luò)的結(jié)構(gòu)和性質(zhì)之間的關(guān)系，介紹了目前先進(jìn)的分布式算法在不同的網(wǎng)絡(luò)拓?fù)鋱鼍跋碌男阅芊治?。文獻(xiàn)[105]針對協(xié)調(diào)控制方案中全局決策變量的快速分布式計(jì)算任務(wù)，分析了重復(fù)通信與計(jì)算之間的權(quán)衡問題。文獻(xiàn)[39]強(qiáng)調(diào)了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)、跨個體的數(shù)據(jù)同質(zhì)性以及全球通信和本地計(jì)算之間的精確權(quán)衡影響。但對于在實(shí)際應(yīng)用中，如何在動態(tài)通信網(wǎng)絡(luò)狀態(tài)下，合理平衡計(jì)算和通信仍是目前研究的難點(diǎn)。

3 總結(jié)與展望

本文聚焦于航空領(lǐng)域現(xiàn)有和未來可能出現(xiàn)的分布式優(yōu)化的問題，從研究框架、主要研究成果、研究難點(diǎn)和未來展望3個方面出發(fā)，對近些年來分布式優(yōu)化的研究工作進(jìn)行了簡要介紹。根據(jù)優(yōu)化問題的差異，對無約束的分布式凸優(yōu)化、集合約束的分布式凸優(yōu)化、不等式約束的分布式凸優(yōu)化和分布式非凸優(yōu)化目前的典型研究工作進(jìn)行了概述。其中，一些無約束和有約束的分布式凸優(yōu)化問題，已經(jīng)有很多成熟的算法工作，形成了解決方案，應(yīng)用在商業(yè)軟件中，用來解決國民生產(chǎn)、軍事國防中遇到的各種分配和優(yōu)化問題。針對由多個個體組成的大規(guī)模網(wǎng)絡(luò)系統(tǒng)，分布式優(yōu)化工作仍是一個研究熱點(diǎn)。

目前的分布式優(yōu)化工作在航空任務(wù)應(yīng)用中仍然存在很多不足。① 多機(jī)體之間的通信速度和帶寬的限制在分布式算法設(shè)計(jì)時沒有充分考慮。② 在執(zhí)行任務(wù)時存在大量信號干擾，導(dǎo)致算法迭代存在誤差，無法精確執(zhí)行。③ 在實(shí)際應(yīng)用中，難以保證不同機(jī)體間時鐘同步，高效的異步分布式算法研究不足。④ 單個機(jī)體的通信能力和計(jì)算能力很有限，而且隱私數(shù)據(jù)無法進(jìn)行傳輸分享，這對如何在實(shí)際應(yīng)用中合理平衡計(jì)算與通信提出挑戰(zhàn)。這些也是分布式優(yōu)化算法理論研究的熱點(diǎn)，如果能將目前理論研究的成果與航空領(lǐng)域中出現(xiàn)的優(yōu)化問題有效結(jié)合，可以為多機(jī)體的航空任務(wù)提供更有效的解決方案。