分散式最佳化

分散式最佳化是通過多智慧型體之間的合作協調有效地實現最佳化的任務，可用來解決許多集中式算法難以勝任的大規模複雜的最佳化問題。

基本介紹

• 中文名：分散式最佳化
• 外文名：Distributed optimization

簡介

近年來，隨著高科技的蓬勃發展,特別是雲計算和大數據等新興領域的出現。分散式最佳化理論和套用得到了越來越多的重視，並逐漸滲透到科學研究、工程套用和社會生活的各個方面，分散式最佳化是通過多智慧型體之間的合作協調有效地實現最佳化的任務，可用來解決許多集中式算法難以勝任的大規模複雜的最佳化問題。如今如何設計出有效的分散式最佳化算法並對其進行收斂性和複雜性的分析成了最佳化研究的主要任務之一。與集中式算法的主要區別在於分散式算法還不得不考慮通訊和協調在最佳化中起到的重要作用。

發展背景

最佳化與博弈是運籌學和控制論理論研究中的核心問題之一, 同時還在包括系統科學、人工智慧、生物生
態、壓縮感知、計算機通訊等很多領域有著廣泛的套用。 已有成熟的最佳化與博弈算法大多是集中式的，但是隨著現代科學的發展, 在生物、物理、社會和工程等眾多學科中出現了許多新問題亟待解決, 包括如何有效處理大數據、進行雲計算等。 另外, 通信和微電子技術也在迅猛發展, 為此提供了大量的高效、廉價且性能穩定的感測器、處理器以及各種執行器件, 這極大地支持和拓展了各種分散式算法的套用範圍, 促進分散式最佳化的理論研究不斷取得新的成果。
現在隨著多智慧型體(multi-agent)系統理論和協調技術的發展, 許多分散式最佳化算法可以通過藉助多智慧型體網路的方式來實現。 多智慧型體系統是由一群具備一定的感知、通信、計算和執行能力的智慧型個體通過通訊等方式關聯成的網路系統。從某種意義上說,分散式技術與多智慧型體網路是一對孿生兄弟, 或者是一個事物的兩個不同的側面: 分散式強調技術實現的一個事物的兩個不同的側面: 分散式強調技術實現的系統, 分散式方法比傳統集中式方法更為靈活且操作更為方便, 這也使得分散式最佳化與控制的研究得到了迅速發展. 而且已被越來越多的工業和國防套用領域,包括智慧型電網、感測器網路、社會網路、信息物理系統(cyber-physical system)等所關注。

電網中的分散式最佳化

分散式最佳化理論和套用已經成為當代系統和控制科學的重要發展方向之一。在最佳化理論研究過程中,最佳化算法的設計、收斂性的證明、複雜性(包括分析複雜性和算術複雜性)的分析是其中幾個關鍵性的研究問題. 在分散式最佳化中, 相應的問題正在吸引著來自諸多領域的科技工作者的巨大研究興趣. 近年來相關的研究人員在分散式最佳化上已經取得了一系列重要成果(特別是對一些典型分散式算法收斂性等的分析), 並在不同科研領域中的多種期刊和會議上發表。
現在的分散式最佳化有兩大類研究問題: 一類是對性能指標函式的最佳化， 另一類是對系統動態過程的最佳化。 由於分散式最佳化剛剛興起，主要的突出理論研究成果還是屬於第一類最佳化中。在一些重要的現實問題中, 比如資源分配, 感測器網路中的定位等問題，每個個體往往有一個代價函式， 且整個網路的代價由這些個體的代價函式和來表示。此網路的目的是通過個體間的局部信息交流而完成整個網路代價函式的最佳化。其中每個個體只知道自己的代價函式，在給定的分散式最佳化算法下可以得出保證其收斂的條件。 另一類是對系統動態過程的最佳化，此類分散式最佳化問題往往涉及到分散式的(隨機)動態規劃， 現在雖然已經有些研究， 但大多結果往往是初步的或因所需條件很強難以做深入的理論分析。
在最佳化理論發展過程中, 凸最佳化因為其基本且簡單一直受到廣泛的關注, 很多實際的最佳化問題都轉化或近似成凸最佳化問題來做。主要有

1）無約束凸最佳化;

2) 帶約束凸最佳化;

3) 博弈和Nash均衡等。

分散式無約束最佳化

正如凸最佳化是集中式最佳化中的基本問題,無約束分散式凸最佳化也是分散式最佳化中最基本的問題和研究的出發點。在無約束最佳化問題中一個典型而簡單的分散式最佳化問題是分散式凸交計算，通常可以用梯度方法對它進行研究，在它的算法中梯度就是對凸集的投影。

分散式凸交計算

這幾年,分散式凸交計算(Distributed convex intersec-tion computation)越來越受到研究人員的重視,並在包括圖像重構中原像的恢復、凸投射的最佳逼近和目標定位等實際問題中有大量的套用.比如,在目標定位問題中,目標源以一定的功率發射某一信號,網路中的多個感測器會接收到隨著傳輸距離變大而衰減的帶量測噪聲的信號,目標定位的目的是通過網路中感測器接收到的信號以找到目標源的位置.對應於接收到的信號,每個感測器都會有一個(凸)感知區域.當這些感知區域具有非空交集時,目標定位問題可以轉化為一個凸交計算問題.近幾十年來,凸交計算問題(也稱凸可行性問題)得到廣泛的研究.當初的研究通常是集中式的,隨後這幾年開始了分散式凸交計算的研究。

次梯度方法(Sub-gradient method)

基於次梯度的常步長算法往往不能保證算法的收斂性,或者說即使收斂性能夠得到但不能保證一定能收斂到最優解集上.為了保證算法收斂的最優性,步長漸近收斂到 0的條件是必要的,但是該條件又會帶來收斂速度慢的弊端。隨著分散式最佳化的深入發展，近些年來，研究人員取得了很多基於(次)梯度的變形算法和研究成果。比如：

a) 基於量化信息的分散式最佳化。

在基於量化信息的分散式最佳化這一問題里,每個個體由於通訊能力的限制,不能完全量化得到其他個體的信息,而只能得到通訊量化後的信息.大部分基於次梯度的方法,雖然給出了固定或者切換拓撲下分散式最佳化的算法的收斂性分析,但是在實際套用中由於量化誤差的存在,不能達到精確解,並且其精確程度與量化的精度有關.在該問題中,有一些基本的問題還沒有完全解決,特別是:

i)如何實現(在切換拓撲下)不受量化誤差影響的精確最佳化?

ii)如何在能夠實現最佳化的前提下減少信息傳輸率?

b) 隨機最佳化。

在一些現實問題中,比如從社會觀點動力學的角度而言,個體在做決策時往往會相互獨立地以一定的機率堅持自己的觀點,以一定機率會受到鄰居個體觀點的影響。

分散式帶約束最佳化

現實中的很多最佳化問題是帶有約束的,其約束形式包括受限集、等式及不等式約束。 同樣,在解決分散式最佳化問題中,也會碰到不少約束問題.實際上,很多非凸的最佳化問題可以近似為帶約束的凸最佳化問題.

在分散式最佳化中,有兩類約束用在最佳化算法中.一類是最佳化問題中不得不考慮的客觀給定約束,還有一類是最佳化問題中自身隱含的約束.對於客觀存在的約束,研究者不得不去面對和處理,但在不好處理時就採取方法取代或逼近這些約束條件.而後一類約束往往是所研究的最佳化問題中自然滿足的,有時可以主動加入這些輔助約束以提高算法的效率。