求解廣義納什均衡問(wèn)題的指數(shù)型懲罰函數(shù)方法

許吉祥, 侯 劍, 譚彥華, 馮恩民

(1.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，遼寧 大連 116024; 2.天津職業(yè)技術(shù)師范大學(xué) 理學(xué)院，天津 300222; 3.內(nèi)蒙古工業(yè)大學(xué) 管理學(xué)院，內(nèi)蒙古 呼和浩特 010051; 4.河北工業(yè)大學(xué) 理學(xué)院，天津 300130)

?

求解廣義納什均衡問(wèn)題的指數(shù)型懲罰函數(shù)方法

許吉祥1,2, 侯 劍1,3, 譚彥華4, 馮恩民1

(1.大連理工大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，遼寧 大連 116024; 2.天津職業(yè)技術(shù)師范大學(xué) 理學(xué)院，天津 300222; 3.內(nèi)蒙古工業(yè)大學(xué) 管理學(xué)院，內(nèi)蒙古 呼和浩特 010051; 4.河北工業(yè)大學(xué) 理學(xué)院，天津 300130)

本文利用指數(shù)型懲罰函數(shù)部分地懲罰耦合約束,從而將廣義納什均衡問(wèn)題(GNEP)的求解轉(zhuǎn)化為求解一系列光滑的懲罰納什均衡問(wèn)題 (NEP)。我們證明了若光滑的懲罰NEP序列的解序列的聚點(diǎn)處EMFCQ成立,則此聚點(diǎn)是 GNEP的一個(gè)解。進(jìn)一步,我們把懲罰 NEP的KKT條件轉(zhuǎn)化為一個(gè)非光滑方程系統(tǒng),然后應(yīng)用帶有 Armijo 線搜索的半光滑牛頓法來(lái)求解此系統(tǒng)。最后,數(shù)值結(jié)果表明我們的指數(shù)型懲罰函數(shù)方法是有效的。

運(yùn)籌學(xué);指數(shù)型懲罰函數(shù);半光滑牛頓法;廣義納什均衡

0 引言

廣義納什均衡問(wèn)題(generalized Nash equilibrium problem簡(jiǎn)記為GNEP)是標(biāo)準(zhǔn)的納什均衡問(wèn)題(NEP)的推廣, 它允許每個(gè)參與人的目標(biāo)函數(shù)和策略集都可以依賴于競(jìng)爭(zhēng)者的策略. 這使得GNEP較NEP更適合于描述實(shí)際的競(jìng)爭(zhēng)市場(chǎng). GNEP的研究起源于1952年的經(jīng)典文獻(xiàn)[1]。1965年文獻(xiàn)[2]考慮了所有參與人的決策都滿足共享凸約束的GNEP。 隨后,1991年文獻(xiàn)[3]將GNEP變型為一個(gè)擬變分不等式(QVI),但是關(guān)于QVI的有效算法仍很少. 近期以來(lái)GNEP越來(lái)越多地被應(yīng)用于建模經(jīng)濟(jì)、工程、交通運(yùn)輸、電力、計(jì)算機(jī)、通信和環(huán)境等領(lǐng)域中的問(wèn)題(見(jiàn)綜述文章[4]),可是對(duì)GNEP數(shù)值方法的研究卻遠(yuǎn)不如對(duì)經(jīng)典NEP研究的那樣完善。

求解GNEP的數(shù)值方法,因問(wèn)題的不同背景及目標(biāo)的不同而各有差異。主要包括基于QVI變型[3]、基于正則化Nikaido-Isoda函數(shù)的優(yōu)化問(wèn)題變型、松弛方法、參數(shù)化變分不等式(VI)方法 (見(jiàn)綜述文章[4,5])。但是這些方法主要是處理標(biāo)準(zhǔn)的NEP或者共享凸約束的GNEP。盡管如此,對(duì)于無(wú)特殊結(jié)構(gòu)的GNEP而言,懲罰方法和使用KKT條件的方法大概是最有效的兩類方法[6]。特別地,文獻(xiàn)[7]提出了一個(gè)序列懲罰方法,其中序列中的每個(gè)懲罰問(wèn)題都是SC2光滑的懲罰 NEP。文獻(xiàn)[8]給出了一個(gè)求解GNEP的障礙函數(shù)懲罰方法。

本文的主要工作是,利用指數(shù)型懲罰函數(shù)提出一種新的求解一般形式的GNEP的序列懲罰方法,其中序列中的每個(gè)懲罰問(wèn)題都是光滑的C2懲罰NEP。我們證明了若光滑的懲罰NEP序列的解序列的聚點(diǎn)處EMFCQ成立,則此聚點(diǎn)是GNEP的一個(gè)解。進(jìn)一步,我們把懲罰NEP的KKT 條件轉(zhuǎn)化為一個(gè)非光滑方程系統(tǒng),然后再用帶有Armijo線搜索的半光滑牛頓法來(lái)求解此系統(tǒng)。最后,數(shù)值結(jié)果表明我們的指數(shù)型懲罰函數(shù)方法是有效的。

1 GNEP的定義及預(yù)備知識(shí)

GNEP是標(biāo)準(zhǔn)的NEP的推廣。具體地說(shuō),設(shè)有N個(gè)參與人,將每個(gè)參與人v∈{1,…,N}的決策變量記為xv∈nv,且令x=(x1,…,xN)T∈N是由這N個(gè)決策變量構(gòu)成的向量,其中n:=n1+…+nN。為了強(qiáng)調(diào)第v個(gè)參與人的決策變量,有時(shí)我們也將x寫(xiě)成x=(xv,x-v)T,這里x-v=(x1,…,xv-1,xv+1,…xN)T∈n-v表示x中除了第v個(gè)決策變量之外的其余所有決策變量按照原來(lái)順序構(gòu)成的向量,其中n-v=n-nv。設(shè)參與人v的效用函數(shù)為θv:n→R,策略集Xv(x-v)?nv依賴于其余參與人的決策變量。第v個(gè)參與人的目的就是,在給定其余參與人的決策變量x-v∈n-v之后,選擇自己的決策變量xv∈nv,使它滿足如下極小化問(wèn)題:

s.txv∈Xv(x-v)

下面介紹本文需要的兩個(gè)概念：Clarke廣義次微分、向量值函數(shù)的半光滑性。

令X,Y是有限維向量空間,O是X中的一個(gè)開(kāi)集,Φ:O?X→Y是一個(gè)定義在O上的局部 Lipschitz 連續(xù)函數(shù),由Rademacher 定理我們知道,Φ在集合O上幾乎處處Fréchet可微。用DΦ表示Φ在O上所有Fréchet可微點(diǎn)構(gòu)成的集合,則函數(shù)Φ在x∈O處的Bouligand次微分 (B-次微分) ?BΦ(x)定義為

?BΦ(x):={limk→∞JΦ(xk)|xk∈DΦ,xk→x}

其中JΦ(xk)為Φ在xk處的 Jacobian。

Φ在x處的Clarke意義下廣義次微分定義為?BΦ(x)的凸包[9,定理2.5.1],即?Φ(x)=conv{?BΦ(x)}，下面要介紹的半光滑性的概念最初由Mifflin[10]提出,之后由Qi和Sun[11]推廣到了向量值函數(shù)。

定義1 令Φ:O?X→Y是開(kāi)集O上的局部Lipschitz連續(xù)函數(shù),則稱Φ在x∈O處半光滑,若

(i)Φ在x處方向可微;

(ii)對(duì)任意XΔx→0和V∈?Φ(x+Δx)有Φ(x+Δx)-Φ(x)-V(Δx)=o(‖Δx‖)。

進(jìn)一步,我們稱Φ在x∈O處強(qiáng)半光滑,若Φ在x處半光滑,并且對(duì)于任意XΔx→0和V∈?Φ(x+Δx),有Φ(x+Δx)-Φ(x)-V(Δx)=O(‖Δx‖2)。

在求解一個(gè)由半光滑方程構(gòu)成的系統(tǒng)時(shí),下面給出的強(qiáng)BD-正則性條件在算法中所起的作用類似于求解一個(gè)由光滑方程構(gòu)成的系統(tǒng)時(shí)用到的Jacobian矩陣非奇異性條件。

定義2 設(shè)Φ:n→n在x處是局部Lipschitz 連續(xù),我們稱Φ在處是強(qiáng)BD-正則的,若對(duì)任意的H∈?BΦ(x),都滿足H是非奇異的。進(jìn)一步,若滿足系統(tǒng)Φ(x)=0且Φ在處是強(qiáng)BD-正則的,那么我們稱是該系統(tǒng)的強(qiáng)BD-正則解。

2 GNEP的指數(shù)型懲罰函數(shù)方法

在本文中,我們假設(shè)第v個(gè)參與人的策略集Xv(x-v)的表達(dá)形式如下:

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

(1)

其中,gv:n→mv是依賴于其他參與人的決策變量的,因此它被稱為GNEP的耦合約束.hv:nv→lv只依賴于第v個(gè)參與人的決策變量xv,因此它被稱為GNEP的自身約束。

那么,GNEP的第v個(gè)參與人面臨的優(yōu)化問(wèn)題如下:

(2)

對(duì)于每個(gè)參與人v=1,…,N, 我們做以下假設(shè):

注:上述關(guān)于GNEP的凸性的假設(shè)在GNEP的文獻(xiàn)中是標(biāo)準(zhǔn)的假設(shè), 而關(guān)于目標(biāo)函數(shù)和約束函數(shù)的光滑性的假設(shè)是為了設(shè)計(jì)局部超線性收斂算法的需要 (見(jiàn)綜述文章[4])。

由假設(shè)1可以知道,每一個(gè)參與人v面臨的優(yōu)化問(wèn)題(2)都是一個(gè)凸規(guī)劃,因此x*,v∈Xv(x*,-v)是(2)式的解當(dāng)且僅當(dāng)

〈▽xvθv(x*,v,x*,-v),xv-x*,v〉≥0, ?xv∈Xv(x*,-v)

這里〈c,d〉代表向量c和d的內(nèi)積cTd,接著通過(guò)定義

(3)

我們得到x*是GNEP的解當(dāng)且僅當(dāng)x*∈Ω(x*)且

〈F(x*),x-x*〉≥0, ?x∈Ω(x*)

(4)

這是一個(gè)擬變分不等式, 我們記為 QVI(F,Ω)。

為了強(qiáng)調(diào)GNEP的自身約束hv的作用,我們定義集合Xv?nv和X?n如下:

Xv:={xv∈nv|hv(xv)≤

那么,第v個(gè)參與人面臨的優(yōu)化問(wèn)題(2)也可以寫(xiě)為

(5)

眾所周知,求解一個(gè)經(jīng)典NEP要比求解一個(gè)GNEP容易得多,因此 我們求解GNEP的指數(shù)型懲罰函數(shù)方法的想法就是通過(guò)部分地懲罰GNEP中的那些困難的耦合約束,使得求解GNEP等價(jià)于求解一列經(jīng)典NEP。

這樣得到的NEP中的第v個(gè)參與人面臨的優(yōu)化問(wèn)題為:

(6)

接下來(lái)我們要證明,通過(guò)求解一列經(jīng)典NEP(6)可以得到原GNEP(2)的解。

(7)

和映射H:n→l為

(8)

則

Ω(x)=X1(x-1)×…×XN(x-N)

可以等價(jià)地表示為如下形式

Ω(x)={y∈n|G(x,y)≤0,H(y)≤0}

相應(yīng)地,我們也用QVI(F,G,H)來(lái)代表問(wèn)題(4)。為了討論方便,我們令

于是,對(duì)應(yīng)于每個(gè)參與人v=1,…,N面臨的優(yōu)化問(wèn)題(6)可以寫(xiě)為

(9)

并稱(9)為原GNEP(2)的懲罰NEP。很顯然由假設(shè)1知,任意給定x-v∈n-v,對(duì)應(yīng)于每個(gè)參與人的子問(wèn)題(9)都是凸的、C2光滑的優(yōu)化問(wèn)題,并且x∈X是懲罰 NEP的解當(dāng)且僅當(dāng)對(duì)于每個(gè)v=1,…,N,

(10)

顯然,組裝上述所有v=1,…,N的系統(tǒng)可得到如下的等價(jià)系統(tǒng)

(11)

下面我們給出廣義Mangasarian-Fromovitz約束規(guī)范(EMFCQ)[7]的定義, 這個(gè)定義在證明GNEP的指數(shù)型懲罰函數(shù)方法的收斂性時(shí)會(huì)用到。

(12)

我們還需要以下引理[12,定理6.14]。

(13)

對(duì)于每個(gè)參與人v=1,…,N,我們可以將問(wèn)題(5)的KKT條件寫(xiě)為

(14)

(15)

其中,λ=(λ,…,λm)T=((λ1))T,…,(λN)T)T和μ=(μ1,…,μl)T=((μ1)T,…,(μN(yùn))T)T。

下面一個(gè)引理證明了在恰當(dāng)?shù)臈l件下,(15)可以用來(lái)求解QVI(F,G,H)。

(16)

再由引理1可知,

因此,我們可以將(16)式等價(jià)地表示為

下面給出我們的指數(shù)型懲罰函數(shù)方法的收斂性定理。

(17)

(18)

(19)

(20)

3 半光滑牛頓法求解懲罰NEP及數(shù)值結(jié)果

接著,我們應(yīng)用半光滑牛頓法來(lái)求解懲罰NEP(9)。首先我們將與懲罰問(wèn)題(9)等價(jià)的問(wèn)題(11)的KKT系統(tǒng)等價(jià)地寫(xiě)成一個(gè)非光滑方程組的形式,然后應(yīng)用帶有Armijo線搜索的半光滑牛頓法來(lái)求解此系統(tǒng)。最后,我們給出了半光滑牛頓法求解該問(wèn)題的收斂性和收斂速度，數(shù)值結(jié)果表明我們的指數(shù)型懲罰函數(shù)方法是有效的。

問(wèn)題(11)的KKT條件為

(21)

(22)

算法1

步驟1 如果‖Ψ(ωk)‖≤ε,則停止,否則轉(zhuǎn)入步2。

步驟2 選取Hk∈?Φ(ωk)。求解系統(tǒng)

Hkd=-Φ(ωk)

(23)

的解dk。如果(23)不可解或者求解得到的dk不滿足條件

▽?duì)?ωk)Tdk≤-ρ‖dk‖k

則置dk=-▽?duì)?ωk)。

步驟3 令tk是{βj|j=0,1,2,…}中的最大者,并且滿足Ψ(ωk+tkdk)≤Ψ(ωk)+tkσ▽?duì)?ωk)Tdk。

步驟4 置ωk+1=ωk+tkdk,k=k+1,轉(zhuǎn)步 1。

下述定理給出了半光滑牛頓法1的收斂性和收斂速度,由于懲罰問(wèn)題(9)都是凸的、C2光滑的優(yōu)化問(wèn)題, 故這個(gè)定理的證明可直接參考文獻(xiàn)[13,定理11]。

定理2 假設(shè)算法1不在有限步終止,令{ωk}是由算法1產(chǎn)生的序列,則序列{ωk} 的每一個(gè)聚點(diǎn)ω*都是Ψ的穩(wěn)定點(diǎn)。進(jìn)一步,若ω*是系統(tǒng)Φ(ω)=0的強(qiáng)BD-正則解,則{ωk}超線性收斂于ω*。

注：關(guān)于ω*是Φ(ω)=0強(qiáng)BD-正則解的充分條件的討論可以參考[14]。

最后,我們應(yīng)用MATLAB 6.5編制了半光滑牛頓法的相應(yīng)計(jì)算機(jī)程序,并求解了文獻(xiàn)中的三個(gè)典型算例。

例1[15,16]這個(gè)算例是一個(gè)互聯(lián)網(wǎng)網(wǎng)絡(luò)模型。設(shè)有N個(gè)參與人,每個(gè)參與人的效用函數(shù)為

表1 例1的數(shù)值結(jié)果

例2[16]設(shè)有 3 個(gè)參與人,他們所控制的決策變量分別為x1∈3,x2∈2和x3∈2。每個(gè)參與人v的效用函數(shù)為

表2 例2的數(shù)值結(jié)果

例3[16.17]這是一個(gè)電力市場(chǎng)模型,在這個(gè)模型中有3個(gè)參與人。第一個(gè)參與人的決策變量x1∈,第二個(gè)參與人的決策變量)∈2,第三個(gè)參與人的決策變量)∈3。設(shè),這三個(gè)參與人的效用函數(shù)為

和

其中Ψ(x):=2(x1+…+x6)-378.4,常數(shù)ci,di,ei的取值在表3中給出。

表3 常數(shù)ci,di,ei的取值

對(duì)于x的各個(gè)分量有如下約束條件,0≤x1≤80,0≤x2≤80,0≤x3≤50,0≤x4≤55,0≤x5≤30,0≤x6≤40。

表4列出相應(yīng)的數(shù)值結(jié)果。

表4 例3的數(shù)值結(jié)果

4 結(jié)論

本文的主要工作是,利用指數(shù)型懲罰函數(shù)提出一種新的求解一般形式的GNEP的序列懲罰方法,其中序列中的每個(gè)懲罰問(wèn)題都是C2光滑的懲罰NEP。我們證明了若光滑的懲罰NEP序列的解序列的聚點(diǎn)處EMFCQ成立,則此聚點(diǎn)是GNEP的一個(gè)解。特別的,因每個(gè)懲罰問(wèn)題都是光滑的,從而允許我們?cè)O(shè)計(jì)局部快速的收斂算法。最后,數(shù)值結(jié)果表明我們的求解GNEP的指數(shù)型懲罰函數(shù)方法是有效的,從而進(jìn)一步豐富了求解GNEP的懲罰類型方法。與文獻(xiàn)[16]相比較知,本文的懲罰參數(shù)不必太大(ρ=100),從而求解懲罰問(wèn)題時(shí)降低了遇到數(shù)值病態(tài)的可能性,而相比之下文獻(xiàn)[16]的懲罰參數(shù)需要取到ρ=105;另一方面由于這些方法都是局部算法,對(duì)于例2而言,兩個(gè)算法收斂到了兩個(gè)不同的廣義納什均衡點(diǎn),從而設(shè)計(jì)新的全局算法是我們進(jìn)一步的研究方向。

[1] Debreu G. A social equilibrium existence theorem[J]. Proceedings of the National Academy of Sciences, 1952, 38: 886- 893.

[2] Rosen J B. Existence and uniqueness of equilibrium points for concave n-person games[J]. Econometrica, 1965, 33: 520-534.

[3] Harker P T. Generalized nash games and quasi-variational inequalities[J]. European Journal of Operational Research, 1991, 54: 81-94.

[4] Facchinei F, Kanzow C. Generalized nash equilibrium problems[J]. Annals of Operations Research, 2010, 175: 177-211.

[5] Krawczyk J. Numerical solutions to coupled-constraint(or generalised Nash)equilibrium problems[J]. Computational Management Science, 2007, 4: 183-204.

[6] Cominetti R, Facchinei F, Lasserre J B. Modern optimization modelling techniques[M]. New York: Birkh?user, 2012. 151-188.

[7] Fukushima M, Pang J S. Quasi-variational inequalities, generalized nash equilibria, and multi-leader-follower games[J]. Computational Management Science, 2005, 2: 21-56.

[8] Hou J, Lai J F. A penalty approach for generalized nash equilibrium problem[J]. Communications In Mathematical Research, 2012, 28: 181-192.

[9] Clarke F H. Optimization and nonsmooth analysis[M]. New York: John Wiley, 1983.

[10] Mifflin R. Semismooth and semiconvex functions in constrained optimization[J]. SIAM Journal on Control and Optimization, 1977, 15: 959-972.

[11] Qi L, Sun J. A nonsmooth version of newton’s method[J]. Mathematical Programming, Ser.A, 1993, 58: 353-368.

[12] Rockafellar R T, Wets R J B. Variational analysis[M]. Springer, 1998.

[13] Luca T D, Facchinei F, Kanzow C. A semismooth equation approach to the solution of nonlinear complementarity problems[J]. Mathematical Programming, 1996, 75: 407- 439.

[14] Hou J, Zhang L W. A barrier function method for generalized Nash equilibrium problems[J]. Journal of Industrial and Management Optimization, 2014, 10: 1091-1108.

[15] Kesselman A, Leonardi S, Bonifaci V. Game-theoretic analysis of internet switching with selfish users[A]. Deng X T, Ye Y Y. Lecture Notes in Computer Science[C]. Springer, 2005, 3828: 236-245.

[16] Facchinei F, Kanzow C. Penalty methods for the solution of generalized nash equilibrium problems[J]. SIAM Journal on Optimization, 2010, 20: 2228-2253.

[17] Contreras J, Klusch M, Krawczyk J B. Numerical solutions to nash-cournot equilibria in coupled constraint electricity markets[J]. IEEE Transactions on Power Systems, 2004, 19: 195-206.

Exponential Penalty Function Method for Generalized Nash Equilibrium Problem

XU Ji-xiang1,2, HOU Jian1,3, TAN Yan-hua4, FENG En-min1

(1.SchoolofMathematicalSciences,DalianUniversityofTechnology,Dalian116024,China; 2.SchoolofSciences,TianjinUniversityofTechnologyandEducation,Tianjin300222,China; 3.ManagementCollege,InnerMongoliaUniversityofTechnology,Hohhot010051,China; 4.SchoolofSciences,HebeiUniversityofTechnology,Tianjin300130,China)

This paper reformulates the generalized Nash equilibrium problem(GNEP)as a sequence of smoothing penalized NEPs by means of a partial penalization of the coupling constraints where the exponential penalty functions are used. We demonstrate that the limit point is a solution to the GNEP under the EMFCQ at a limit point of solutions to smoothing penalized NEPs. Further more, we formulate the Karush-Kuhn-Tucker(KKT)conditions for smoothing penalized NEPs into a system of nonsmooth equations, and then apply the semismooth Newton method with Armijo line search to solve the system. Finally, the numerical results show that our exponential penalty function method for GNEP is effective.

operational research; the exponential penalty function; semismooth Newton method; generalized Nash equilibrium problem

2013- 01- 08

863項(xiàng)目(2007AA02Z208);973項(xiàng)目(2007CB714304);國(guó)家自然科學(xué)基金項(xiàng)目(10871033,11171050)

許吉祥(1982-)，男，博士，助教。

O225

A

1007-3221(2015)01- 0081- 08