半分布式forward-reflected-Douglas-Rachford分裂算法求解廣義納什平衡點(diǎn)

潘曉偉 劉忠信 陳增強(qiáng)

(1.南開(kāi)大學(xué)人工智能學(xué)院,天津 300350;2.南開(kāi)大學(xué)智能機(jī)器人技術(shù)重點(diǎn)實(shí)驗(yàn)室,天津 300350)

1 引言

納什平衡問(wèn)題(Nash equilibrium problems,NEP)由John Nash在文獻(xiàn)[1-2]中正式提出.廣義納什平衡問(wèn)題(generalized Nash equilibrium problems,GNEP)是NEP的拓展,由Gerard Debreu在文獻(xiàn)[3-4]中正式提出,其特點(diǎn)是每個(gè)參與者的約束集合也依賴于其他參與者.GNEP在許多領(lǐng)域中都有所應(yīng)用,如電信系統(tǒng)、環(huán)境污染控制等,參考綜述文獻(xiàn)[5].

近年來(lái),基于算子分裂框架的求解方法正在得到越來(lái)越多的關(guān)注,其基本思路是將GNEP轉(zhuǎn)化為算子的尋零問(wèn)題,然后應(yīng)用不同的算子分裂方法,可以得到相應(yīng)的求解算法[6].基于兩算子分裂方法的有: forward-backward(half)forward splitting[7-8,12],forward-backward splitting[9-10],forward-reflected-backward splitting[13]等.

基于forward-backward-forward splitting的算法[7],[8,算法2],每一輪迭代需要進(jìn)行兩次信息交換;基于forward-backward-half forward splitting 的算法[8,算法3],[12,Eqn.(6.11)]和基于forward-backward splitting的算法[9],需要假設(shè)偽梯度映射是強(qiáng)單調(diào)的,而另一基于forward-backward splitting的算法[10],則需要假設(shè)偽梯度映射是協(xié)強(qiáng)制的;基于forward-reflectedbackward splitting 的算法[13,算法5],其每一輪迭代只進(jìn)行一次信息交換,而且只需要假設(shè)偽梯度映射是單調(diào)的和李普希茨的.

其他的求解算法有連續(xù)時(shí)間算法[11],鄰近點(diǎn)算法(proximal point algorithm,PPA)[13,算法6],[14],交替方向乘子法(alternating direction method of multipliers,ADMM)[15]等.文獻(xiàn)[11]中的算法要求偽梯度映射是嚴(yán)格單調(diào)的;文獻(xiàn)[13]中的算法6只是針對(duì)一類具有特殊結(jié)構(gòu)的聚合博弈設(shè)計(jì)的,其只需要假設(shè)偽次梯度映射是單調(diào)的;文獻(xiàn)[14]中的算法需要假設(shè)代價(jià)函數(shù)是可導(dǎo)的,而在GNEP中會(huì)有非光滑項(xiàng);文獻(xiàn)[15]中的算法4.1經(jīng)過(guò)變換之后,其實(shí)是一種forward-backward算子分裂方法.

根據(jù)上述內(nèi)容可知,在基于算子分裂設(shè)計(jì)的方法中,要么對(duì)偽梯度映射均有較強(qiáng)的假設(shè)條件,要么每次迭代需要交換兩次信息.

針對(duì)前述問(wèn)題,本文的主要工作在于,基于三算子分裂算法forward-reflected-Douglas-Rachford(FRDR)算法[17],提出一種半分布式的FRDR算法.該算法有如下特性: 可以實(shí)現(xiàn)鄰點(diǎn)映射和投影映射分別進(jìn)行計(jì)算,因此更適用于分開(kāi)計(jì)算時(shí)可以得出具體表達(dá)式的情形,而省去解決一個(gè)優(yōu)化子問(wèn)題;不需要假設(shè)偽梯度映射是協(xié)強(qiáng)制的或者強(qiáng)單調(diào)的;通過(guò)存儲(chǔ)上一輪交換的信息,可以做到所需信息在每一輪迭代中只進(jìn)行一次交換;同時(shí),也給出了迭代殘差的收斂速率,即o(1/(k+1)).跟本文算法比較相似的是基于forward-reflected-backward splitting的算法[13,算法5],區(qū)別在于FRDR 算法中鄰點(diǎn)映射和投影映射的計(jì)算是分開(kāi)進(jìn)行的;此外,文獻(xiàn)[13]中的算法5是針對(duì)聚合博弈設(shè)計(jì)的,而本文算法是針對(duì)一般的GNEP設(shè)計(jì)的.

本文的主要結(jié)構(gòu)如下.第2節(jié)包括后續(xù)分析所需的預(yù)備知識(shí)以及對(duì)所研究問(wèn)題的描述.第3節(jié)給出了半分布式FRDR算法的設(shè)計(jì)及其收斂性分析.第4節(jié)給出了仿真例子用來(lái)驗(yàn)證算法的有效性.最后是全文總結(jié).

2 預(yù)備知識(shí)和問(wèn)題描述

令Rm表示m維歐式空間,〈.,.〉是內(nèi)積.Im表示m×m維單位矩陣.A ?B表示矩陣A和B的克羅內(nèi)克積.對(duì)于向量x,‖x‖表示歐式范數(shù);對(duì)于矩陣C,‖C‖表示導(dǎo)出范數(shù).文中出現(xiàn)的向量,除非特別說(shuō)明,均指列向量.(x1,...,xn)表示由列向量x1,...,xn等按列排列生成的列向量.diag{A1,...,An}表示由矩陣A1,...,An生成的分塊對(duì)角陣.0m表示m維零向量.

2.1 算子理論及圖論

集合S ?Rm是凸的,若,?0＜α＜1,有αx+(1-α).intS表示集合S的內(nèi)點(diǎn).非空凸集S在處的法錐定義為NS(x):Rm|〈y-x,ξ〉≤0;若,則NS(x):?.點(diǎn)R到非空閉凸集S的投影映射定義為projS(x):≤0.函數(shù)f:Rm →R是凸的,若其上圖epif:{(x,u)Rm×R|f(x)≤u}是凸集,其次微分定義為?f(x):Rm|f(y) ≥f(x)+Rm},其鄰點(diǎn)映射定義為proxγf(x):

對(duì)于集值算子F:Rm?Rm,其圖像定義為gphF:{(x,u)Rm×Rm|y F(x)}.算子F是單調(diào)的,若?(x,u),(y,v)gphF,有〈x-y,u-v〉≥0是極大單調(diào)的,若F是單調(diào)的且不存在單調(diào)算子使得其圖像能夠真包含gphF是嚴(yán)格單調(diào)的,若?(x,u),(y,v)gphF且,有〈x-y,u-v〉＞0是強(qiáng)單調(diào)的,若F -σId是單調(diào)的,其中σ ＞0.算子F的預(yù)解算子定義為JγF:(Id+F)-1,其中Id是單位算子.算子F的零點(diǎn)定義為zer(F):Rm|0(x)}.單值算子T:Rm →Rm是協(xié)強(qiáng)制的,若Rm,有〈x-y,T(x)-T(y)〉≥η‖T(x)-T(y)‖2,其中η＞0是李普希茨的,若Rm,有‖T(x)-T(y)‖≤?‖x-y‖,其中? ＞0.

以上內(nèi)容均參照文獻(xiàn)[18]給出.以下為圖論相關(guān)內(nèi)容.

智能體之間的通信拓?fù)淇捎蒅(V,E)描述,其中V{1,...,n}是頂點(diǎn)集合,E ?V ×V是連接邊的集合.令cij≥0表示邊(i,j)上的權(quán)重,若cijcji則表示G是無(wú)向圖.定義圖G的拉普拉斯陣為L(zhǎng)c:[lij]i,j∈V,其 中l(wèi)ij-cij,當(dāng);lii令μmax表示Lc的最大特征值.圖G是連通的當(dāng)且僅當(dāng)Lc的零特征值是單根.

2.2 問(wèn)題描述

考慮n個(gè)智能體參與的廣義納什平衡問(wèn)題,智能體之間的通信拓?fù)錇镚(V,E).對(duì)于,其模型描述為

假設(shè)1對(duì)于,給 定x-i,fi(.,x-i)是 凸的,連續(xù)可導(dǎo)的,且其導(dǎo)數(shù)關(guān)于x是連續(xù)的;gi是正常且下半連續(xù)的凸函數(shù);集合Si是閉凸集.

那么,在假設(shè)1和假設(shè)2成立的條件下,由文獻(xiàn)[15]中的定理3.3和引理3.5可知,x*是v-GNE當(dāng)且僅當(dāng),存在Lagrange乘子,滿足

假設(shè)3偽梯度映射是單調(diào)的.

假設(shè)4智能體之間的通信連接圖G是無(wú)向連通的.

那么,可以得到與文獻(xiàn)[9]中定理2類似的結(jié)論.

引理1在假設(shè)1-4均成立的條件下,有如下結(jié)論:

1) 若

2) zer(G+F+C+NS×R?mn×R?mn)/?.

引理1的證明與文獻(xiàn)[16]中引理1的證明類似,此處不再給出.

3 算法設(shè)計(jì)與分析

為表示方便,令B:F+C,通過(guò)引理1,求解式(1)的v-GNE的問(wèn)題可轉(zhuǎn)化為求解滿足0(w)+B(w)+的w.這是關(guān)于3個(gè)算子的尋零問(wèn)題,因此,可以應(yīng)用文獻(xiàn)[17]中的算法進(jìn)行求解

假設(shè)5偽梯度映射是ρ-Lipshitz連續(xù)的.

應(yīng)用forward-reflected-Douglas-Rachford分裂算法[17]可得

關(guān)于v的更新律為

關(guān)于u的更新律為

消去vy和vλ,可得

因此,把uy和uλ的初值設(shè)為0,繼續(xù)化簡(jiǎn)可得

注1從式(3)中可以看出,函數(shù)g的鄰點(diǎn)映射與關(guān)于S的投影映射是分開(kāi)計(jì)算的.文獻(xiàn)[13]中的Algorithm 5需要計(jì)算函數(shù)gi+的鄰點(diǎn)映射,其中為集合Si的示性函數(shù).因此,當(dāng)分開(kāi)計(jì)算相較于合起來(lái)計(jì)算更容易時(shí),式(3)更為適用.此處所指為可以得出具體表達(dá)式的情形,而省去解決一個(gè)優(yōu)化子問(wèn)題.例如,令P表示{1,...,m}的一個(gè)劃分,x:(ˇx,t)∈Rm-1×R,函數(shù)g(x):其中,x[p]表示對(duì)應(yīng)p的分量.根據(jù)文獻(xiàn)[20,§6.5.4],可以計(jì)算g(x)的鄰點(diǎn)映射為

注2得益于FRDR算法的特性,式(3)所代表的算法,其收斂不需要假設(shè)偽梯度映射是強(qiáng)單調(diào)的或協(xié)強(qiáng)制的.后續(xù)將會(huì)給出證明.

式(3)的偽代碼如算法1所示.

定理1在假設(shè)1-5均成立的情況下,若β ＞0,且0＜γ ＜β/(1+2?β),則有算法1中的xk收斂到v-GNE.

證

步驟1首先,證明wk收斂到zer(G+B+).

由假設(shè)1可知,G和N??S都是極大單調(diào)的;由假設(shè)3和假設(shè)4可知,B是極大單調(diào)的;由假設(shè)5以及F和C的定義可知,B是?-Lipshitz連續(xù)的,其中?ρ+μmax+‖C‖.根據(jù)文獻(xiàn)[17]中的定理5.1可得,wk收斂到zer(G+B+).

步驟2然后,證明xk收斂到v-GNE.

根據(jù)引理1,由wk收斂到zer(G+B+)可得,xk收斂到v-GNE.

證畢.

注3算法1之所以叫作半分布式,是因?yàn)楫?dāng)目標(biāo)函數(shù)依賴于所有智能體的xi時(shí),獲取全部的信息需要通過(guò)中心結(jié)點(diǎn)來(lái)實(shí)現(xiàn);而當(dāng)其僅受鄰居影響時(shí),該算法就是分布式的.無(wú)論如何,對(duì)偶變量λi的信息總是通過(guò)分布式的方式獲取.所以,采用半分布式來(lái)命名該算法.

注4從算法1中可以清楚地看到,每個(gè)智能體通過(guò)存儲(chǔ)上一輪收集到的信息,從而實(shí)現(xiàn)了每一輪迭代中只進(jìn)行一次信息交換.另外,也可以將上一輪計(jì)算的偽梯度信息存儲(chǔ)下來(lái),這樣的話,每一輪迭代只需要計(jì)算一次偽梯度.

盡管算法的收斂速率并未在文獻(xiàn)[17]中直接給出,但是根據(jù)其定理5.1的證明可推出如下結(jié)論.

推論1對(duì)于式(2)所產(chǎn)生的序列{(wk,uk)},有如下關(guān)系成立:

證令

根據(jù)文獻(xiàn)[19]中的引理1第4部分可得

利用范數(shù)的等價(jià)性.證畢.

4 數(shù)值仿真

考慮由編號(hào)1,...,21共21個(gè)公司(智能體)和編號(hào)M1,...,M6共6個(gè)市場(chǎng)組成的網(wǎng)絡(luò)化古諾博弈,其網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示,其中圓形表示公司,方形表示市場(chǎng),箭頭表示公司向市場(chǎng)供應(yīng)產(chǎn)品.智能體之間的通信連接如下圖2所示.

圖1 網(wǎng)絡(luò)化古諾博弈的網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Structure of networked Cournot game

圖2 智能體之間的通信拓?fù)銯ig.2 Communication topology between agens

給定目標(biāo)函數(shù)為

圖3-5分別表示迭代殘差,一致性誤差和約束殘差的變化趨勢(shì).從圖3-5中可以看出,迭代殘差和約束殘差以及一致性誤差都呈現(xiàn)出減小的趨勢(shì),說(shuō)明{xk}是逐漸收斂的且趨向于約束集合,同時(shí){λi,k}逐漸達(dá)到一致.

圖3 迭代殘差Fig.3 Iteration residual

5 結(jié)論

本文基于三算子分裂算法forward-reflected-Douglas-Rachford(FRDR)算法,提出一種半分布式的FRDR算法.該算法有如下特性: 可以實(shí)現(xiàn)鄰點(diǎn)映射和投影映射分別進(jìn)行計(jì)算,因此在計(jì)算上更適用于分開(kāi)計(jì)算簡(jiǎn)單而合起來(lái)計(jì)算困難的情形;而且不需要假設(shè)偽梯度映射是協(xié)強(qiáng)制的或者強(qiáng)單調(diào)的;通過(guò)存儲(chǔ)上一輪交換的信息,可以做到所需信息在每一輪迭代中只進(jìn)行一次交換.此外,數(shù)值仿真驗(yàn)證了所提算法的有效性.

圖4 一致性誤差Fig.4 Consensus error

圖5 約束殘差Fig.5 Constraint residual