[科普中國]-分布式優(yōu)化

簡介

近年來，隨著高科技的蓬勃發(fā)展,特別是云計算和大數據等新興領域的出現。分布式優(yōu)化理論和應用得到了越來越多的重視，并逐漸滲透到科學研究、工程應用和社會生活的各個方面，分布式優(yōu)化是通過多智能體之間的合作協調有效地實現優(yōu)化的任務，可用來解決許多集中式算法難以勝任的大規(guī)模復雜的優(yōu)化問題。如今如何設計出有效的分布式優(yōu)化算法并對其進行收斂性和復雜性的分析成了優(yōu)化研究的主要任務之一。與集中式算法的主要區(qū)別在于分布式算法還不得不考慮通訊和協調在優(yōu)化中起到的重要作用。1

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

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

1）無約束凸優(yōu)化;

2) 帶約束凸優(yōu)化;

3) 博弈和Nash均衡等。

分布式無約束優(yōu)化正如凸優(yōu)化是集中式優(yōu)化中的基本問題,無約束分布式凸優(yōu)化也是分布式優(yōu)化中最基本的問題和研究的出發(fā)點。在無約束優(yōu)化問題中一個典型而簡單的分布式優(yōu)化問題是分布式凸交計算，通?？梢杂锰荻确椒▽λM行研究，在它的算法中梯度就是對凸集的投影。

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

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

a) 基于量化信息的分布式優(yōu)化。

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

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

ii)如何在能夠實現優(yōu)化的前提下減少信息傳輸率?

b) 隨機優(yōu)化。2

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

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

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