潘曉偉 劉忠信 陳增強

(1.南開大學人工智能學院,天津 300350;2.南開大學智能機器人技術重點實驗室,天津 300350)

1 引言

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

近年來,基于算子分裂框架的求解方法正在得到越來越多的關注,其基本思路是將GNEP轉(zhuǎn)化為算子的尋零問題,然后應用不同的算子分裂方法,可以得到相應的求解算法[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],每一輪迭代需要進行兩次信息交換;基于forward-backward-half forward splitting 的算法[8,算法3],[12,Eqn.(6.11)]和基于forward-backward splitting的算法[9],需要假設偽梯度映射是強單調(diào)的,而另一基于forward-backward splitting的算法[10],則需要假設偽梯度映射是協(xié)強制的;基于forward-reflectedbackward splitting 的算法[13,算法5],其每一輪迭代只進行一次信息交換,而且只需要假設偽梯度映射是單調(diào)的和李普希茨的.

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

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

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

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

2 預備知識和問題描述

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

2.1 算子理論及圖論

集合S ?Rm是凸的,若,?0＜α＜1,有αx+(1-α).intS表示集合S的內(nèi)點.非空凸集S在處的法錐定義為NS(x):Rm|〈y-x,ξ〉≤0;若,則NS(x):?.點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},其鄰點映射定義為proxγf(x):

對于集值算子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是嚴格單調(diào)的,若?(x,u),(y,v)gphF且,有〈x-y,u-v〉＞0是強單調(diào)的,若F -σId是單調(diào)的,其中σ ＞0.算子F的預解算子定義為JγF:(Id+F)-1,其中Id是單位算子.算子F的零點定義為zer(F):Rm|0(x)}.單值算子T:Rm →Rm是協(xié)強制的,若Rm,有〈x-y,T(x)-T(y)〉≥η‖T(x)-T(y)‖2,其中η＞0是李普希茨的,若Rm,有‖T(x)-T(y)‖≤?‖x-y‖,其中? ＞0.

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

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

2.2 問題描述

考慮n個智能體參與的廣義納什平衡問題,智能體之間的通信拓撲為G(V,E).對于,其模型描述為

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

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

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

假設4智能體之間的通信連接圖G是無向連通的.

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

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

1) 若

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

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

3 算法設計與分析

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

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

應用forward-reflected-Douglas-Rachford分裂算法[17]可得

關于v的更新律為

關于u的更新律為

消去vy和vλ,可得

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

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

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

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

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

證

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

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

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

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

證畢.

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

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

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

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

證令

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

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

4 數(shù)值仿真

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

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

圖2 智能體之間的通信拓撲Fig.2 Communication topology between agens

給定目標函數(shù)為

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

圖3 迭代殘差Fig.3 Iteration residual

5 結(jié)論

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

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

圖5 約束殘差Fig.5 Constraint residual