兩類分布式優(yōu)化問題關(guān)系初探

劉長有 李 磊

(1.泰山學(xué)院后勤產(chǎn)業(yè)管理處，山東 泰安 271016； 2.泰山醫(yī)學(xué)院管理學(xué)院，山東 泰安 271000)

?

兩類分布式優(yōu)化問題關(guān)系初探

劉長有1李 磊2

(1.泰山學(xué)院后勤產(chǎn)業(yè)管理處，山東 泰安 271016； 2.泰山醫(yī)學(xué)院管理學(xué)院，山東 泰安 271000)

討論了兩類重要的分布式優(yōu)化問題之間的關(guān)系，給出了這兩類分布式優(yōu)化問題的數(shù)學(xué)表達(dá)，并利用拉格朗日對偶原理得出了它們的關(guān)系，即一類問題可以表示為另一類問題的對偶問題。

凸優(yōu)化，分布式，對偶優(yōu)化

隨著復(fù)雜大系統(tǒng)和大型網(wǎng)絡(luò)的興起，分布式優(yōu)化也在很多領(lǐng)域中起著越來越重要的作用。比如在分布式模型預(yù)測控制、分布式信號處理等領(lǐng)域，分布式優(yōu)化都起著很重要的作用[1]。分布式優(yōu)化中有兩類非常重要的問題：在第一類分布式優(yōu)化問題中，每個智能體都有自己的目標(biāo)函數(shù)和約束集合，并且每個智能體并不知道其他智能體的目標(biāo)函數(shù)和約束集合。但是，所有的智能體卻有著公共的優(yōu)化變量[2]。我們稱這類優(yōu)化問題為Ⅰ類分布式優(yōu)化問題。在另一類分布式優(yōu)化問題中，每個智能體都有自己的目標(biāo)函數(shù)、約束集合和優(yōu)化變量，并且每個智能體并不知道其他智能體的目標(biāo)函數(shù)。但是，這些智能體之間的約束集合并不是相互獨(dú)立的，它們的約束集合是相互影響的。我們稱這類分布式優(yōu)化問題為Ⅱ類分布式優(yōu)化問題。這兩類分布式優(yōu)化問題在現(xiàn)實(shí)中有著非常重要的應(yīng)用，學(xué)者也為這兩類優(yōu)化問題設(shè)計(jì)出了種種不同的算法。在這樣的背景下，探討這兩類問題之間的關(guān)系就顯得非常重要，因?yàn)榕宄怂鼈冎g的相互關(guān)系后，我們可以根據(jù)它們之間的關(guān)系設(shè)計(jì)更加有效的算法來解這兩類分布式優(yōu)化問題。本文的探討表明這兩類分布式優(yōu)化問題有著非常深刻而重要的聯(lián)系：Ⅱ類分布式優(yōu)化問題的拉格朗日對偶問題是Ⅰ類分布式優(yōu)化問題。

1 預(yù)備知識

在本節(jié)中，我們介紹凸優(yōu)化和拉格朗日對偶優(yōu)化的相關(guān)知識。

1.1 凸優(yōu)化

集合C是凸集，如果?x,y∈C,αx+(1-α)y∈C，?α∈[0,1],亦即，以C中任意兩點(diǎn)為端點(diǎn)的線段也在C中。函數(shù)f是凸函數(shù)，如果它的定義域D是凸集，并且滿足如下條件:

f(αx+(1-α)y)≤αf(x)+(1-α)f(y),?α∈[0,1],?x,y∈D。

每個凸函數(shù)在它定義域的內(nèi)部都是連續(xù)函數(shù)。

一個優(yōu)化問題是凸優(yōu)化問題，如果它的目標(biāo)函數(shù)和約束集合都是凸的，亦即有如下問題:

subject to x∈X。

該問題是凸優(yōu)化問題，如果f(x)是凸函數(shù)，并且x是凸集合。

當(dāng)優(yōu)化問題表示為如下形式時：

(1)

它是一個凸優(yōu)化問題，如果fi(x)(i=0，1，…,m)是凸函數(shù)而且hj(x)(j=1,…，p)是線性函數(shù)。

1.2 對偶優(yōu)化問題

在這一部分，我們介紹如何得到凸優(yōu)化問題(1)的對偶問題。

首先，問題(1)的拉格朗日函數(shù)為:

對該拉格朗日函數(shù)取關(guān)于x的最小值，我們得到問題(1)的拉格朗日對偶函數(shù):

其中，D為fi(x)(i=0，1，…,m)和hj(x)(j=1,…，p)的公共定義域；g(λ,v)為關(guān)于(λ,v)的凹函數(shù)。

那么，優(yōu)化問題(1)的拉格朗日對偶問題如下：

(2)

對于拉格朗日對偶問題(2)，我們有如下引理：

引理1：拉格朗日對偶問題(2)是一個凸優(yōu)化問題。

令p*為原優(yōu)化問題(1)的最優(yōu)值，d*為對偶問題(2)的最優(yōu)值。則弱對偶d*≤p*始終成立。而強(qiáng)對偶d*=p*在一定條件下成立。對于強(qiáng)對偶，我們有如下引理：

引理2(Slater’s Condition):如果存在點(diǎn)x使得下式成立:

fi(x)<0i=1,…，m,

hi(x)=0i=1,…，p。

則當(dāng)優(yōu)化問題(1)是凸優(yōu)化問題時，強(qiáng)對偶d*=p*成立。

2 分布式優(yōu)化

本節(jié)中，我們介紹兩類分布式優(yōu)化問題。首先我們介紹Ⅰ類分布式優(yōu)化問題。

2.1 Ⅰ類分布式優(yōu)化問題

在該類問題中，每個智能體都有自己的目標(biāo)函數(shù)和約束集合，但是所有的智能體共享公共的優(yōu)化變量。在數(shù)學(xué)上，該類問題可以表示如下：

(3)

其中，fi(i=1,…,n)為每個智能體自己的目標(biāo)函數(shù)；Xi(i=1,…，n)為每個智能體自己的約束集合；全局約束集合X為所有Xi(i=1,…，n)的交集。在Ⅰ類分布式優(yōu)化問題(3)中，所有智能體共享公共的優(yōu)化變量x。

2.2 Ⅱ類分布式優(yōu)化問題

在該類問題中，每個智能體都有自己的目標(biāo)函數(shù)和優(yōu)化變量，但是不同智能體的約束集合卻是相互影響的。在本文中，我們只討論帶有線性等式和線性不等式約束的Ⅱ類分布式優(yōu)化問題。其在數(shù)學(xué)上可以表示為：

(4)

其中，fi(i=1,…,n)為每個智能體自己的目標(biāo)函數(shù)；xi(i=1,…，n)為每個智能體自己的優(yōu)化變量；x=(x1,…，xn)為所有智能體優(yōu)化變量。我們看到，在Ⅱ類分布式優(yōu)化問題(4)中，不同智能體之間的約束是以加法的形式相互影響的。

3 兩類分布式優(yōu)化問題的關(guān)系

在本節(jié)，我們通過拉格朗日對偶優(yōu)化原理，得出Ⅱ類分布式優(yōu)化問題(4)可以通過拉格朗日對偶方法轉(zhuǎn)化為Ⅰ類分布式優(yōu)化問題(1)。

首先，Ⅱ類分布式優(yōu)化問題(4)的拉格朗日函數(shù)為:

其中v,λ均為問題(4)的對偶變量；上標(biāo)T為轉(zhuǎn)置。

為對該拉格朗日含對求關(guān)于xi的最小值，我們令:

那么將xi代入上面的拉格朗日函數(shù)，我們得到:

則問題(4)的對偶問題為：

maxg(v,λ)

subject toλ≥0。

我們得到Ⅱ類分布式優(yōu)化問題(4)的對偶問題為:

(5)

我們看到，問題(5)實(shí)際上是Ⅰ類分布式優(yōu)化問題(3)的一個特殊形式。當(dāng)Ⅱ類分布式優(yōu)化問題(4)滿足引理2中的Slater’s Condition時，強(qiáng)對偶成立。這是我們可以從問題(5)的最優(yōu)解得到問題(4)的最優(yōu)解。所以，我們可以通過拉格朗日對偶方法，將Ⅱ類分布式優(yōu)化問題(4)轉(zhuǎn)化為其拉格朗日對偶問題來解，而問題(4)的拉格朗日對偶問題恰好是Ⅰ類分布式優(yōu)化問題(3)的一種特殊形式。

4 結(jié)語

我們探討了兩類重要的分布式優(yōu)化問題的關(guān)系。我們利用拉格朗日對偶優(yōu)化原理，得出Ⅱ類分布式優(yōu)化問題可以通過對偶原理轉(zhuǎn)化為Ⅰ類分布式優(yōu)化問題。

[1] J.Mota,J.Xavier,P.Aguiar,et al.Distributed optimization with local domains:Applications in mpc and network flows[J].Automatic Control,2015,60(7):2004-2009.

[2] A.D’Amico,L.Sanguinetti,D.Palomar.Convex separable problems with linear constraints in signal processing and communications[J].Signal Processing,2014,62(22):6045-6058.

On relationship of two distribution optimization

Liu Changyou1Li Lei2

(1.Logistics Industrial Management Office, Taishan College, Tai’an 271016, China;2.School of Management, Taishan Medical University, Tai’an 271000, China)

The paper discusses the relationship between the two important distributions optimization, provides the mathematical expression for the two distribution optimization, and concludes their relationship by using Lagrangian duality principle, so the kind of problem can be expressed as the duality of the other problem.

convex optimization, distribution, duality optimization

1009-6825(2016)34-0257-02

2016-09-21

劉長有(1980- )，男，助理工程師； 李 磊(1981- )，女，講師

O224

A