多飛行器的分布式優化研究現狀與展望

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

1. 北京理工大學 自動化學院，北京 100081 2.北京理工大學重慶創新中心，重慶 401120 3.同濟大學 電子與信息工程學院，上海 200082

隨著航空任務范圍的不斷擴大、任務復雜度的增加和網絡通信能力的快速發展，航空領域需要越來越多的獨立個體通信合作形成機群，來完成復雜的大規模航空任務[1-2]。比如多個無人機合作完成區域的覆蓋控制和監測[3-4]、多個飛行器的編隊和跟蹤[5-7]、多個無人機完成對區域中事件/物體的定位[8-9]、多個體之間通信網絡的拓撲優化[10]等。在大量由多個飛行器合作完成的航空任務中，飛行器之間的通信網絡狀態錯綜復雜，分布式的局部數據獲取和有限的通信能力增加了航空任務完成的難度。隨著航空集群規模的日益龐大，實現不同飛行個體之間合理的調度和優化任務變得尤為重要。

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

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

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

1 分布式優化的研究現狀

1.1 問題模型

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

式中：x∈Rn是全局優化決策變量。由于局部目標函數信息fi分布在不同的個體上，因此需要在每個個體上對全局優化變量x進行局部估計，即局部估計變量xi。分布式優化問題的信息分布如圖1所示，不同個體i∈{1,2,…,5}之間通過網絡通信局部決策變量。

圖1 分布式優化問題模型Fig.1 Model of distributed optimization problem

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

分布式優化問題的優化模型包含四大要素：變量、代價函數、約束和通信網絡。

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

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

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

4) 通信網絡：分布式優化基于傳輸網絡進行個體間信息的交互。根據實踐中網絡拓撲結構是否時變分為固定拓撲和動態拓撲。根據信息傳遞是否具有方向性分為無向圖和有向圖。根據網絡拓撲的連接結構可分為平衡圖和非平衡圖。在實際應用中，網絡通信往往會出現擁堵，造成通信延遲，因此很多工作研究存在時間延遲的通信網絡下的分布式優化[17-20]。

1.2 分布式優化方法研究框架

本節將從不同角度對現有的分布式優化方法的研究框架進行分類介紹。

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

一般的分布式優化問題形式為

(1)

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

對偶問題為

maximizeyr(y)

subject toy≥0

其中：變量y是優化問題的對偶變量。函數

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

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

相關的理論證明可以參考文獻[21]。

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

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

1.2.2 按梯度階數的算法分類

根據分布式優化算法設計中使用的函數梯度信息分為一階梯度法、二階梯度法和零階梯度法。在算法迭代時，如果需要利用目標函數的一階梯度信息，則該類算法稱為一階算法；如果變量迭代時需要利用函數的二階導數信息或者Hessian矩陣信息時，則該類算法稱為二階算法；如果算法迭代時，沒有利用到函數的任何梯度信息，則稱為零階算法。

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

1.2.3 按連續時間和離散時間的算法分類

根據變量迭代方式的不同，分為連續時間算法和離散時間算法。在節點位置配置、網絡拓撲優化、資源能量分配等應用場景中，適用離散時間算法[37-50]。而且離散時間算法可以利用高性能的計算機進行快速迭代求解。但是在一些變量狀態連續變化的系統任務應用[51]中，例如多運動體的最優編隊、最優位置姿態控制等，離散算法無法保持變量值的連續。可以通過搭建模擬電路實現低成本、低功耗的連續時間求解器來求解問題。因此，近年來連續時間算法[52-54]受到了研究者的關注。

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

1.3 典型的分布式優化算法

針對分布式優化問題的不同模型要素和研究框架，研究者提出了多種分布式優化算法。由于工作較多，本文只簡要介紹無約束分布式凸優化問題、集合約束的分布式凸優化問題、不等式約束的分布式凸優化問題和分布式非凸優化問題的典型分布式一階算法研究成果。關于分布式二階算法和零階算法的研究，可以參考文獻[40-41，52]。在不加說明的情況下，本文的通信拓撲都指代無向圖，除非另有說明為有向圖。

1.3.1 無約束分布式優化

針對模型目標問題為凸光滑函數的無約束優化問題，其典型的應用之一是多個體一致性問題。例如，文獻[55]提出的多個無人機的分布式優化部署問題，需要在每架無人機上進行本地運算，單獨決定其運動的控制框架就是一個典型的無約束優化問題。

利用變量一致性技術，分布式梯度下降、分布式增量梯度下降法等都可以實現對優化問題的高效分布式求解。無約束分布式優化問題和算法設計架構如下：

其等式約束是為了保證局部估計變量達到一致，局部變量估計xi∈Rn。對于分布式優化問題，局部代價函數最優并不等價于全局代價函數最優，因此，需要在保證局部估計變量一致的約束下，優化總體代價函數。基于變量一致性技術的經典分布式梯度下降(DGD)算法設計為

(2)

式中：aij為拓撲圖鄰接矩陣的第i行第j列個元素，步長αi為衰減步長，可以保證算法的有效收斂。同時，為了加快收斂速度，很多優秀的工作通過使用歷史信息，設計固定步長的分布式算法，典型的工作包括EXTRA[37]、PG-extra[46]以及EXTRA的推廣方法[47]。考慮到個體更新梯度可能存在隨機誤差，文獻[23]提出在動態連通拓撲下的分布式隨機增量梯度法，使得不同個體的局部變量均收斂到共同的全局最優解。

另外一種設計分布式優化算法的思路是利用梯度跟蹤技術，根據不同梯度跟蹤方法，提出不同的分布式優化策略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]。經典的方法之一如下該算法運用固定迭代步長，可以實現靜態圖下不同個體變量收斂到共同的全局最優解。進一步的，DIGing算法和Push-DIGing算法[24]分別實現了動態拓撲圖和有向圖下的有效收斂。尤其，在優化問題的代價函數為強凸時，梯度跟蹤方法可以達到比變量一致方法更好的指數收斂性能。圖2對以上所提算法之間的關系進行了匯總比較，以上方法均為在原始域內進行優化的分布式算法。

圖2 分布式算法關系圖Fig.2 Relationships of distributed algorithms

如果拓撲圖為無向圖，則L=LT，其對應的原始-對偶變量迭代公式為

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

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

式中:α為與時間無關的固定更新步長，其取值往往與目標函數的參數有關。

雖然每次迭代都要求解一個子優化問題，但是當子問題可以獲得封閉解或者易于求解時，交替乘子算法往往具有更好的實際應用性能。上述多變量算法實際上是針對雙變量分布式優化問題的ADMM推廣，可以更為高效的求解多體分布式優化問題[65]。進一步的，文獻[66]給出了無次序更新的交換乘子分布式求解方法，減少了對于通信拓撲和更新順序的依賴，擴大了算法的應用范圍。

1.3.2 集合約束的分布式優化

對于凸集合約束下的優化問題，在文獻[67]中，針對個體在障礙存在的環境下的路徑規劃問題，討論了如何建立問題的優化模型，并設計算法有效求解多障礙集合約束下的優化問題。在任務問題中，當個體存在凸集合約束時，其分布式優化問題模型為

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

當優化問題的集合約束為局部約束的交集時，文獻[13]提出固定/時變連通圖下的高效分布式投影算法為

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

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

式中:aij(k)為k時刻的多節點網絡拓撲的鄰接矩陣元素。

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

1.3.3 不等式約束的分布式優化

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

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

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

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

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

1.3.4 分布式非凸優化

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

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

αkgi(xi(k))

式中:αk、βk為可調節步長；aij為通信網絡鄰接矩陣元素；gi函數為局部函數梯度估計，該梯度既可以是簡單隨機梯度，也可以是小批量隨機梯度或隨機擬牛頓方向。上述算法是基于變量一致原則進行分布式算法設計。針對經驗風險最小化問題，即

文獻[79]中基于梯度跟蹤技術，給出如下分布式隨機梯度算法設計：

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

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

(4)

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

(5)

其中，近似算子定義如下

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

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

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

2 分布式優化的研究難點和未來展望

2.1 分布式優化的研究展望

由于數據規模的迅速增大和信息的分散化，分布式優化的研究近些年來得到了廣泛的關注和長足的發展。未來分布式優化的研究展望包括如何加速分布式優化算法，在動態網絡連接狀態下分布式優化算法設計以及對于復雜的帶約束非凸優化問題，如何設計分布式優化算法。

2.1.1 分布式加速算法

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

2.1.2 動態拓撲下的分布式優化

針對大規模多個體網絡上的分布式優化問題，分布式算法的性能受到個體之間網絡拓撲連接的影響。受航空任務環境中各種復雜因素的影響以及網絡通信帶寬的限制，個體之間的有向/無向拓撲連接往往是動態變化的。文獻[22]中，討論了在無向動態拓撲下的分布式優化問題，并給出了基于變量一致的分布式梯度下降方法的收斂性能。對于基于梯度跟蹤技術的分布式優化方法，文獻[24]中給出了其可以實現在動態拓撲上達到線性收斂速率的分析。由于網絡資源有限，在航空任務應用中，無向網絡拓撲往往難以實現，飛行器之間大多以有向通信拓撲連接為主。針對動態有向拓撲下的分布式凸/非凸優化問題，文獻[95-97]提出了高效的分布式優化算法，并給出了收斂性能分析。對于動態有向/無向連接拓撲，文獻[98]使用通信輪數和梯度評估之間的優化比率，實現算法快速收斂，并且，根據梯度評估的數量來衡量，該算法迭代收斂到全局最優解的速度與集中式梯度下降相同。

2.1.3 帶約束的非凸優化

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

2.2 分布式優化的共性難點

在大規模多飛行器的分布式優化中，個體之間借助機載通信設備網絡實現信息的交互。不同飛行器之間的計算時序和速度有差別，通信能力有限，且環境干擾因素較多，因此本節中對通信時延、干擾誤差、異步迭代和通信計算權衡等是分布式優化算法設計中共有的難點進行簡要介紹。

1) 通信時延是大型網絡中不可避免的通信問題。當個體在與鄰居之間的通信延遲時間一致并可能無限大時，文獻[17]給出了分布式算法求解可微凸目標函數的收斂速度與網絡大小、拓撲結構和處理器間通信延遲的函數關系的上界。基于無源性理論，文獻[18]分析了在無向固定拓撲下，連續時間算法求解分布式無約束和有約束優化問題時，如何有效處理任意未知的恒定通信延遲。對于梯度連續的強凸代價函數，文獻[19]研究了在具有時變延時的有向圖下，分布式算法保證所有的個體收斂于系統最優解的充分條件。但是針對實際應用中更為一般的優化問題，如何在復雜的網絡通信情況下保證分布式算法的收斂性能仍然是目前的難點問題。

2) 個體迭代利用的梯度信息無法精確獲得。單個個體在利用梯度信息進行迭代時，由于外界環境的干擾或者自身運算誤差等原因，往往無法得到精確的梯度信息。在動態切換拓撲連通圖下，文獻[23]針對全局集合約束的分布式凸優化問題，提出了分布隨機次梯度投影算法，探討了隨機次梯度誤差對算法收斂性能的影響，保證算法的有效收斂。文獻[19]進一步將工作擴展到非凸優化問題，證明了通過合理調整步長，分布式隨機梯度方法仍然可以收斂到問題的臨界點集合。但是對于非凸優化問題，并未給出全局收斂的理論研究結果，隨機梯度誤差對任務中復雜有向拓撲下分布式算法的收斂性能的影響目前還沒有研究成果。

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

4) 合理地平衡分布式算法的計算負擔和通信負擔是影響算法性能的重要因素。在多個體網絡中，由于不同個體在物理環境中分離，個體之間的通信帶寬有限且不穩定，迫切需要減輕網絡的通信負擔。研究分布式優化算法的通信效率問題，尤其是在經驗風險最小化方面，近年來得到蓬勃發展。文獻[104]系統地探討了分布式算法的收斂速度與節點通信的網絡的結構和性質之間的關系，介紹了目前先進的分布式算法在不同的網絡拓撲場景下的性能分析。文獻[105]針對協調控制方案中全局決策變量的快速分布式計算任務，分析了重復通信與計算之間的權衡問題。文獻[39]強調了網絡拓撲結構、跨個體的數據同質性以及全球通信和本地計算之間的精確權衡影響。但對于在實際應用中，如何在動態通信網絡狀態下，合理平衡計算和通信仍是目前研究的難點。

3 總結與展望

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

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