廣義納什均衡問題的精確指數(shù)—對數(shù)罰函數(shù)算法

楊 迪 何家文

1.南寧師范大學(xué)師園學(xué)院 廣西南寧 530226;2.南寧學(xué)院通識教育學(xué)院 廣西南寧 530200

納什均衡問題是博弈論中一種非常重要的研究類型。廣義納什均衡問題(Generalized Nash Equilibrium Problem,GNEP)是納什均衡問題的一種拓展形式,其中涉及的局中人決策影響其他局中人決策的情況,更能體現(xiàn)博弈問題中局中人之間普遍聯(lián)系的實際情況。近年來,全球范圍內(nèi)經(jīng)濟的發(fā)展和市場競爭日趨激烈,已經(jīng)不再是單個局中人選擇策略就能達到最優(yōu)策略的效果。單純的納什均衡問題已經(jīng)不能滿足實際需求,越來越多的學(xué)者通過研究廣義納什均衡博弈相關(guān)問題,以求能更好地推動社會和經(jīng)濟的發(fā)展。

本文在對指數(shù)精確罰函數(shù)和對數(shù)罰函數(shù)相關(guān)內(nèi)容的基礎(chǔ)上,利用這兩個互為反函數(shù)的函數(shù)特征,提出一個指數(shù)—對數(shù)精確罰函數(shù)方法,用以求得廣義納什均衡(縮寫為GNE),從而解決GNEP。

常用的約束最小值問題為:

minf(x)
s.t.gi(x)≤0.i=1,…,m,

(1)

其中f(x),gi(x):Rn→R是連續(xù)可微函數(shù)。

針對問題(1),文獻[1]提出了一個聯(lián)合指數(shù)罰函數(shù)法。這個方法在運行初始是不需要內(nèi)點初始點,在選擇初始點時有很大的選擇空間,這樣也能得到一個解,這是這個算法的優(yōu)勢,可惜效果跟內(nèi)點法相似,不一定得到精確解。在文獻[2]中,針對凸規(guī)劃,利用精確指數(shù)乘子函數(shù),也得到一個最優(yōu)解。在前文基礎(chǔ)型上,文獻[3]則提出了一個精確的對數(shù)—指數(shù)乘子罰函數(shù),得到一個較好的結(jié)果,這對提出新的罰函數(shù)算法給出了一個很好的示范。文獻[4]利用指數(shù)型懲罰函數(shù),對部分耦合約束進行懲罰,將廣義納什均衡問題的求解轉(zhuǎn)化為求解一系列光滑的懲罰納什均衡,進而得到想要的結(jié)果。文獻[5-6]在研究串聯(lián)機械臂系統(tǒng)軌跡規(guī)劃問題、復(fù)雜的大規(guī)模極大極小值問題中,提出聯(lián)合指數(shù)或?qū)?shù)罰函數(shù)法進行操作,給出相關(guān)算法的實際應(yīng)用價值。這些學(xué)者在利用指數(shù)或?qū)?shù)罰函數(shù)來求解相關(guān)問題都做了有益的嘗試,有利于我們進一步對廣義納什均衡問題進行探討。

1 預(yù)備知識

假設(shè)博弈中有N個局中人,每一個局中人v∈{1,…,N}都有自己的策略集Xv,從自己的策略集Xv中選取一個策略xv。將每個局中人給出的策略形成一個組合,由此得到博弈中N個局中人的一個策略組合x=(x1,…,xN)。為突出我們所研究的某個局中人v的策略xv,記x=(xv,x-v),其中x-v=(x1,…,xv-1,xv+1,…,xN)表示除了局中人v之外,其他局中人所選擇的策略形成的組合。我們以策略組合x為元素,構(gòu)成局中人策略的集合,記為局中人策略集的笛卡爾積X,即x∈X:=X1×…×XN,并稱X為局中人的策略組合集。令θv:Rn→R為博弈中每個局中人v的目標(biāo)函數(shù),為了更好地分析,假設(shè)θv(xv,x-v)對xv為凸。如果x*,v滿足對v=1,…,N,(NEP)θv(x*,v,x*,-v)≤θv(xv,x*,-v),?xv∈Xv。則向量x*=(x*,v,x*,-v)∈X稱為一個納什均衡(Nash Equilibrium,NE)。上述問題就是納什均衡問題(Nash Equilibrium Problem,NEP)。

對現(xiàn)實當(dāng)中的很多情況,博弈中的每個局中人在選擇的策略的過程中,不僅要考慮自身情況,還要考慮其他局中人所選擇的策略,由此來得到自身最大的收益或者付出最小的代價。為表示局中人在策略選擇過程中策略之間的相關(guān)性,將每個局中人v的策略集表示為Xv(x-v):={xv|(xv,x-v)∈X},由此特別定義策略集組合集為Ω(x):=X1(x-1)×…×XN(x-N)。如果x*,v滿足對v=1,…,N,(GNEP)θv(x*,v,x*.-v)≤θv(xv,x*,-v),?xv∈Xv(x-v)。稱向量x*∈Ω為一個廣義納什均衡(GNE),此問題就是本文重點要研究的廣義納什均衡問題(GNEP)。

在GNEP中,每一個局中人選擇的策略與競爭對手所選擇的策略是有相關(guān)性的。這更體現(xiàn)出在一些實際博弈中,局中人在進行策略選擇時的相互影響。

針對GNEP,本文考慮了約束是不等式組的情況。在約束中,其中一部分是局中人v=1,…,N選擇的策略依賴于其他局中人所選策略的約束,簡稱為依賴約束;另一種就是獨立約束,即每個局中人的策略不依賴其他局中人的策略選擇的約束。

針對局中人v,本文考慮的GNEP,只有依賴約束的最小值問題:

minxvθv(xv,x-v)
s.t.gv(xv,x-v)≤0,

(2)

Xv(x-v):={xv|gv(xv,x-v)≤0}

對所有v=1,…,N,針對原問題(2)需要一個全局假設(shè):(1)目標(biāo)函數(shù)θv:Rn→R是連續(xù)可微的,并且對所給xv為凸;(2)約束條件gv:Rn→R對所有i=1,…,m是連續(xù)可微的,并且對xv為凸。

2 精確指數(shù)—對數(shù)罰函數(shù)算法及其收斂性證明

針對廣義納什均衡問題(2),本文設(shè)計一個新的精確指數(shù)—對數(shù)罰函數(shù):

由此得到一個精確指數(shù)—對數(shù)罰問題:

minxvMv(x,ρv)

(3)

經(jīng)過分析計算,可得目標(biāo)函數(shù)的梯度為:

如果出現(xiàn)這樣的情況,就可以通過增大罰參數(shù)來強迫可行性,直至找到合適的解。

根據(jù)以上分析,給出精確指數(shù)—對數(shù)罰函數(shù)算法1。

算法1

步驟1 若xk是GNEP的解。停止。

步驟2 若xk不可行,且對任意v,若

(4)

則對所有v,使罰參數(shù)ρv加倍,令k←k+1,轉(zhuǎn)步驟1。

下面證明原問題(2)與罰問題(3)是等價的。

定理1 如果算法1是有限步終止迭代,則原問題(2)的解與問題(3)的解等價。

反過來,要證問題(3)的解x*為(2)的解,我們只需證明x*為可行點。假設(shè)x*是不可行點,M(x,ρ*)在x*的鄰域上連續(xù)可微,有:

0=?xvM(x*,ρ*)

血管淋巴管瘤合并血管瘤屬于特殊類型之一，就目前而言，臨床報道較少，多以個案報道為主。影像學(xué)檢查發(fā)現(xiàn)，以淋巴管和血管構(gòu)成比不同而表不一為主，其中淋巴管患者的表現(xiàn)類似于淋巴瘤患者，血管瘤患者的表現(xiàn)類似于血管瘤。王小巖[10]在相關(guān)報道中發(fā)現(xiàn)，脾臟血管淋巴管瘤3例患者中，CT檢查顯示血管瘤樣強化特征共計2例。瘤體內(nèi)有出血表現(xiàn)時則清晰可見“液-液”平面現(xiàn)象。

故有:

算法1要求cv∈(0,1),那么對某些v和充分大的k,必定都會滿足(4),根據(jù)算法1要求,更新罰參數(shù),與題設(shè)條件產(chǎn)生矛盾。由此可得x*是可行點,而x*是可行點,就有問題(3)的解x*為(2)的解,本定理得證。

根據(jù)文獻[3-4],我們新定義一些約束規(guī)格CQγ:

定義1 定義

定理2 假設(shè)由算法1產(chǎn)生的序列{xk}有界,對以下3個結(jié)論:(a)在xk的極限處,MFCQ成立,則CQ0條件成立;(b)在xk的極限處,CQ0條件成立,則罰參數(shù)只更新有限次。

對其中適當(dāng)?shù)淖恿?有下面的結(jié)論:

由于滿足EMFCQ條件,當(dāng)?shù)仁絻蛇呁瑫r乘以dv時,就可以給出:

顯然這是矛盾的。因此(a)成立。

3 數(shù)值結(jié)果

接下來的數(shù)值例子來說明算法1的可行性和有效性。

例1 考慮N=2的博弈:

其中局中人v=1決策變量為x1,局中人v=2的決策變量為x2,他們所受的共享約束是g(x1,x2)=x1+x2-1≤0。可得此博弈的最優(yōu)解集為:

由此可以看出對α∈[1/2,1],本例是有無窮多個解(α,1-α)。根據(jù)文獻[7],例1有唯一的變分均衡點(3/4,1/4)。

表1中p和pel分別表示經(jīng)典罰函數(shù)算法和算法1,初始罰參數(shù)設(shè)置為ρ0=2。表1的數(shù)據(jù)表明,本文所提出的算法與經(jīng)典罰函數(shù)相比,在迭代步數(shù)和時間上法不相上下,對任取初始點,都能得到有效數(shù)據(jù)。這說明提出的新算法是可行且穩(wěn)定有效的。表1的數(shù)據(jù)也表明,在同樣的誤差內(nèi),算法1得到的解要比經(jīng)典算法更為精確,這是新算法的優(yōu)勢所在。即在比較大的誤差范圍內(nèi)(如ε=1.0e-3),算法1仍能保證最終迭代點與最優(yōu)點的基本一致,比經(jīng)典算法更加精確且迭代時間更短。

表1算法1和經(jīng)典的罰函數(shù)算法得出的實驗結(jié)果1

例2 考慮N=2的博弈:

局中人v=1的決策變量為x1,局中人v=2的決策變量為x2。他們有共同的約束g(x1,x2)=x1+x2-1≤0。分析可知例2唯一的最優(yōu)點為x=(0,1),由此得到最優(yōu)值-3。數(shù)值實驗如下面的表2所示。

表2 算法1和經(jīng)典的罰函數(shù)算法得出的實驗結(jié)果1

從表2數(shù)據(jù)中可看出,在比較大的誤差范圍內(nèi),本文提出的新算法得到的解要比經(jīng)典算法更為精確。通過綜合表1與表2的數(shù)據(jù),也可以看出在比較大的誤差范圍內(nèi),新算法得到的解要比經(jīng)典算法更為精確,在多數(shù)情況下,迭代時間也要更短。這就意味著,在實際情況中,算法1滿足在較低的要求下,仍然可以得到經(jīng)典罰函數(shù)算法在高要求下才得到的解。這樣就更能貼近現(xiàn)實生活的需求,顯然是本文罰函數(shù)算法的優(yōu)勢所在。

結(jié)語

本文主要是利用精確罰函數(shù)方法來求解廣義納什均衡問題,針對不等式約束,提出了一個精確的指數(shù)—對數(shù)罰函數(shù)算法,并通過討論算法的全局收斂性,給出數(shù)值結(jié)果來說明算法的有效性與可行性。

隨著社會的發(fā)展,廣義納什均衡問題在現(xiàn)實世界中各個領(lǐng)域的應(yīng)用越來越多,意味著我們需要解決具有各式各樣要求的問題,并且這些問題內(nèi)部聯(lián)系越來越緊密。現(xiàn)有求解GNEP的罰函數(shù)算法都具有一定的局限性,與實際應(yīng)用還存在一定的距離。往后,我們的研究方向仍有很多,比如,對更一般目標(biāo)問題,像目標(biāo)函數(shù)不為凸函數(shù)或約束函數(shù)不是凸函數(shù)的情況,還可提出對不是凸規(guī)劃的算法等。