摘要：近年來，許多學(xué)者致力于運(yùn)用精確罰函數(shù)法對廣義納什均衡博弈進(jìn)行研究。該文針對既有等式約束，也有不等式約束的廣義納什均衡問題，根據(jù)拉格朗日乘子法思路，給出相同結(jié)構(gòu)類拉格朗日函數(shù)，設(shè)計了一個類乘子算法，在較弱的情況下，進(jìn)行可行性和收斂性的分析證明，在具體的數(shù)值實(shí)驗(yàn)中，該文給出的算法與經(jīng)典的PHR算法相比較，在時間和迭代步數(shù)上都呈現(xiàn)較好的效果，說明算法的有效性。

關(guān)鍵詞：廣義納什均衡"類乘子算法"拉格朗日算法"精確罰函數(shù)

中圖分類號：O225"""""""文獻(xiàn)標(biāo)識碼：A

Research"on"the"Multiplier-like"Algorithm"for"the"Generalized"Nash"Equilibrium"Problem

YANG"Di

（Shiyuan"College"of"Nanning"Normal"University，"Nanning，"Guangxi"Zhuang"Autonomous"Region，"530000"China）

Abstract：In"recent"years，"many"scholars"have"been"studying"the"generalized"Nash"equilibrium"game"by"using"the"exact"penalty"function"method."Aiming"at"the"generalized"Nash"equilibrium"problem"with"both"equality"constraints"and"inequality"constraints，"this"paper"gives"a"Lagrange-like"function"of"the"same"structure"according"to"the"idea"of"the"Lagrangian"multiplier"method，"and"designs"a"multiplier-like"algorithm"to"analyze"and"prove"the"feasibility"and"convergence"under"weak"conditions."In"specific"numerical"experiments，"compared"with"the"classical"PHR"algorithm，"the"algorithm"presented"in"this"paper"presents"better"results"in"time"and"iteration"steps，"indicating"the"effectiveness"of"the"algorithm.

Key"Words：""Generalized"Nash"equilibrium;"Multiplier-like"algorithm;"Lagrange"algorithm;"Exact"penalty"function

近年來，隨著經(jīng)濟(jì)的發(fā)展和市場競爭的日趨激烈，越來越多的學(xué)者研究納什均衡博弈的拓展形式——廣義納什均衡博弈。在非合作博弈當(dāng)中，局中人會根據(jù)自己的情況來選擇策略，如果只考慮自身的情況（局中人本身受到的約束），完全不考慮其他局中人已選策略，不一定得到在大環(huán)境下的最優(yōu)策略。在真實(shí)情況下，局中人在選擇策略的時候，應(yīng)該充分考慮其他局中人已選或者必選的優(yōu)勢策略。只有在這種情況下，自己的優(yōu)勢策略和其他局中人的優(yōu)勢策略才更可能得到一個均衡，減少自己的不必要的損失。這意味著，在實(shí)際情況量化后，局中人的策略集不是只依賴自身決策變量的一個集合，而是充分依賴其他局中人的決策。

該文是圍繞廣義納什均衡問題（Generalized"Nash"Equilibrium"Problem，GNEP）和罰函數(shù)方法來展開論述的。

用罰函數(shù)方法來逼近GNEP最初是由Pang和Fukushima[1，2]提出的。他們提出了一系列的罰函數(shù)來逼近GNEP的解并求解其中可微發(fā)問題的一個無限序列。近年來對求解GNEP方面已有了一些研究。FACCHINEI"F等人[3]提出了一個求解一般GNEP的精確罰函數(shù)方法。這個方法有很好的數(shù)值效果，"同時能夠切實(shí)求解具有不同性質(zhì)的GNEP。FACCHINEI"F等人[4]設(shè)計了“偏”罰函數(shù)系統(tǒng)，保持獨(dú)立約束，不把它納入“罰”項(xiàng)。文獻(xiàn)[3，4]的方法很大程度上依賴這樣的一個事實(shí)：利用模

來定義精確罰函數(shù)，其中。這里取的模在任意不可行點(diǎn)都是可微的。這是一個很明顯的優(yōu)勢，而文獻(xiàn)[3，4]都要求。

在現(xiàn)有的廣義納什均衡問題的求解方法中，大多是罰函數(shù)算法、數(shù)值算法、下降算法等，其中罰函數(shù)算法中，大多采用精確罰函數(shù)算法，從而得到原問題的精確解。而近年運(yùn)用拉格朗日乘子法去求解問題上，多運(yùn)用在矩陣填充問題和改進(jìn)的經(jīng)典增廣拉格朗日方法來處理多目標(biāo)優(yōu)化問題。羅美菊，吳歐[5]在經(jīng)典增廣拉格朗日乘子算法的基礎(chǔ)上，"通過定義混合型奇異值閾值算子，"得到了一種求解矩陣填充問題的新的混合型增廣拉格朗日乘子算法。張艷芬[6]提出一種部分增長拉格朗日乘子算法在雙層規(guī)劃問題求解中的應(yīng)用改進(jìn)。王俊霞等人[7]以奇異值閾值方法為基礎(chǔ)，"針對符號矩陣填充提出了修正的增廣Lagrange乘子法。文獻(xiàn)[8-11]"是通過改進(jìn)經(jīng)典增廣拉格朗日方法來處理多目標(biāo)優(yōu)化問題。目前對乘子法等在廣義納什均衡問題中的應(yīng)用未見過多涉及。在此方面具有一定的研究價值。該文目的是，根據(jù)Lagrange乘子法的思想，設(shè)計了一個類乘子法，由此給出算法來求解廣義納什均衡問題，得到其精確解。一般的乘子法是以增廣拉格朗日函數(shù)為基礎(chǔ)，要求約束條件為等式約束，對不等式約束也采用轉(zhuǎn)換為等式約束后再討論的方法。與一般的乘子法不同，該文設(shè)計的類乘子法是基于類增廣拉格朗日函數(shù)，針對具有不等式約束和等式約束的混合約束的情況，同樣給出相同結(jié)構(gòu)類拉格朗日函數(shù)，提出一個類乘子算法，同時進(jìn)行可行性和收斂性的分析證明，最后給出數(shù)值實(shí)驗(yàn)說明算法的優(yōu)越性。

1"預(yù)備知識

假設(shè)在非合作博弈當(dāng)中，一共有個局中人，每一個局中人都會從自己的策略集中選取一個策略。會得到個局中人的一個策略組合．本文為強(qiáng)調(diào)，記，其中表示除以外其他局中人的策略。策略組合形成的集合為局中人策略集的笛卡爾積，即."我們稱為策略組合集。令為局中人的目標(biāo)函數(shù)，并假設(shè)對為凸。則向量稱為一個納什均衡（NE），如果滿足對，

上述問題就是納什均衡問題（NEP）。

在實(shí)際中博弈，經(jīng)常出現(xiàn)每個局中人的策略會與其他局中人的策略相關(guān)的情況，為表示相關(guān)性，每個局中人的策略集表示為，并定義相關(guān)策略組合即為。那么向量稱為一個廣義納什均衡（GNE），如果滿足對，

上述問題就是廣義納什均衡問題（GNEP）。

顯然，GNEP是NEP的拓展形式，其中每個參與者的策略可能依賴于競爭對手的策略。

在實(shí)際問題中，博弈中的局中人擁有共同的一些資源，比如政策、市場環(huán)境等，這樣共有的資源可以量化為共享約束來表現(xiàn)。在共享約束中，根據(jù)實(shí)際情況，分為等式約束和不等式約束。這種帶有共享約束的廣義納什均衡問題，是廣義納什均衡問題的重要形式。

2"問題等價分析

對約束條件既有等式組，也有不等式組的混合約束的GNEP，該文的目的是通過類乘子法來求解GNEP，考慮可行即為

這種最一般的情況。不等式組，和等式組，為局中人的依賴約束，并且對為凸。那么該文所要解決的局中人問題就變?yōu)?/p>

其中，的維數(shù)為。對所有，同樣地，針對原問題（1）作以下假設(shè)：

（1）為連續(xù)可微，對為凸；

（2），連續(xù)可微，并且對為凸。

針對混合約束，該文對每個局中人的廣義納什均衡問題設(shè)計了類增廣Lagrange函數(shù)：

得到了增廣Lagrange罰函數(shù)：

同樣地，對不同的局中人具有不同的乘子和罰參數(shù)，為了書寫簡便，統(tǒng)一去掉標(biāo)記，并記。"因此類增廣Lagrange罰函數(shù)問題可等價地表示為

稱問題（4）為類乘子罰問題。

現(xiàn)在分析和證明問題（1）與問題（4）等價。

顯然有，

注意到，，"具有模同樣的性質(zhì)，在不可行點(diǎn)處是連續(xù)可微的。并且有，"。

定理1"若為原問題（1）的局部極小值點(diǎn)，為相應(yīng)的乘子，若二階條件成立，即

則存在，當(dāng)時，為的最優(yōu)解。反之，若為原問題（1）的可行點(diǎn)，且為的極小點(diǎn)，則為原問題的最優(yōu)解，其中為相應(yīng)的乘子。

證""必要性。由

其中，，可知

從而

因?yàn)樵瓎栴}（1）的局部極小值點(diǎn)，所以，.又因二階條件成立，必有

而

故為的最優(yōu)解。

充分性．因?yàn)闉樵瓎栴}（1）的可行點(diǎn)，滿足，，且為的極小點(diǎn)，那么對任意靠近的可行點(diǎn)，，，有

從而為原問題（1）的最優(yōu)解。

3"算法和收斂性分析

為了得到算法的收斂性，在這里有如下定義：

定義1""定義

定義2""若，，。則稱在點(diǎn)上滿足約束規(guī)。

定理2"假設(shè)條件成立，為的最優(yōu)解必為原問題（1）的最優(yōu)解。

證明"根據(jù)定理1，只要證明為原問題的可行點(diǎn)就行。假設(shè)存在和的解序列是原問題的不可行點(diǎn)，即，且。不失一般性，設(shè)。而連續(xù)可微，滿足

即

易知時，

，

上式成立必有，。

這顯然與條件矛盾，所以為原問題的可行點(diǎn)。由定理1，"為的最優(yōu)解必為原問題（1）的最優(yōu)解。命題得證。

現(xiàn)在我們考慮的是乘子的迭代。可知

我們得到乘子的修正公式為

假設(shè)1"對乘子和罰函數(shù)，

的解存在。

下面給出具體的算法。

算法1

歩0"給出初始值，，，誤差，，。

歩1"求出，令．"若，停止。

歩2"令，對每個，若

（6）

轉(zhuǎn)歩3；否則使罰參數(shù)加倍（）。

歩3"利用（5）式計算，令，，轉(zhuǎn)歩1。

下面證明算法1的收斂性。

定理3"原函數(shù)（1）滿足條件，設(shè)為算法1產(chǎn)生的序列，乘子集有界，則算法有限歩終止，序列的極限點(diǎn)為原函數(shù)的解。

證"根據(jù)定理2可知算法產(chǎn)生的序列的極限點(diǎn)為原函數(shù)的解。假設(shè)算法不有限歩終止，即存在。不妨假設(shè)在每個迭代點(diǎn)都更新，并且有。因在處連續(xù)可微，根據(jù)算法歩2有

因目標(biāo)函數(shù)的連續(xù)性，乘子集的有界性以及，有

，

即，"。

由的定義有，，顯然與假設(shè)條件成立矛盾，因此算法有限歩終止。定理得證。

4"數(shù)值結(jié)果

本節(jié)將用例子來說明本章所提算法的可行性和有效性。cm表示罰因子增加的倍數(shù)，s.p.表示初始點(diǎn)，T表示運(yùn)算的時間（單位為秒），表示誤差容忍度，term為相關(guān)的終止條件，iter表示算法迭代次數(shù)。對算法的歩1，我們?nèi)圆捎脭M牛頓法來計算。初始罰參數(shù)統(tǒng)一設(shè)置為，初始乘子為。

首先考慮的是約束為不等式約束的GNEP。接下來運(yùn)用Matlab"7.12.0（R2011a）來完成算法1和經(jīng)典的PHR算法對下列的計算。

例1""考慮的博弈：

局中人有一個決策變量，局中人有一個決策變量。他們有共同的等式約束。

由于這兩個算法在同樣的誤差內(nèi)所得的最優(yōu)點(diǎn)是一樣的，在數(shù)據(jù)上不進(jìn)行對比，僅比較它們的迭代步數(shù)和運(yùn)行時間。算法1和經(jīng)典的PHR算法得出的實(shí)驗(yàn)結(jié)果如表1，其中phr和yphr分別表示經(jīng)典的PHR算法和算法1。從表1的測試數(shù)據(jù)可以看出，算法1在迭代步數(shù)要優(yōu)于經(jīng)典的PHR算法，而相對地，在運(yùn)行時間上，算法1比經(jīng)典的PHR算法要更短。同時也可以看出，當(dāng)要求的精確度越高時，算法1的優(yōu)勢就越明顯（如時，PHR算法的迭代歩是14歩，算法1的只為10歩，而當(dāng)時，PHR算法的迭代歩是20歩，算法4.1的只為9歩）。

例2""考慮，約束條件為等式的博弈：

算法1和經(jīng)典的PHR算法針對例2得出的實(shí)驗(yàn)結(jié)果如表2。從前兩組數(shù)據(jù)可以看出算法1在迭代步數(shù)和時間上比經(jīng)典的PHR算法更優(yōu)越。但是若是改變了罰因子的倍數(shù)或是增大容忍度（如后兩組數(shù)據(jù)），雖然PHR算法的時間很短，但是它的迭代步數(shù)仍是比算法1要多，而且它的最后迭代點(diǎn)不是精確最優(yōu)點(diǎn)。這說明就精確度來說PHR算法對多個因素敏感，而算法1則較為穩(wěn)定。

例3""考慮，一般情形的博弈：

算法1和經(jīng)典的PHR算法得出的數(shù)值結(jié)果如表3。從第二組數(shù)據(jù)可看出，算法1對罰因子的增長倍數(shù)有一定的要求，但效果與PHR算法不相上下。而第一組和第三組數(shù)據(jù)表明算1在迭代步數(shù)和時間上確實(shí)比經(jīng)典的PHR算法要優(yōu)越。

5"總結(jié)與展望

該文主要是利用罰函數(shù)方法來求解廣義納什均衡問題，分別對各種約束條件下的目標(biāo)函數(shù)進(jìn)行討論。通過研讀相關(guān)文獻(xiàn)，分別針對不等式約束，等式約束和混合約束，在新提出的類拉格朗日函數(shù)模型的基礎(chǔ)上，仿效乘子法的思路得到類乘子法，并證明它們在適當(dāng)條件下的全局收斂性。數(shù)值結(jié)果表明三個算法是可靠有效的。

廣義納什均衡問題在各個領(lǐng)域應(yīng)用的增多，意味著我們需要解決具有各式各樣要求的問題?，F(xiàn)有求解GNEP的罰函數(shù)算法都具有一定的局限性，與實(shí)際應(yīng)用還存在一定的距離。往后，我們的研究方向仍有很多。比如對罰因子的選取，要提出一個更為有效的方法；對更一般目標(biāo)問題，像目標(biāo)函數(shù)不為凸函數(shù)或約束函數(shù)不是凸函數(shù)的情況，還可提出對不是凸規(guī)劃的算法等。

參考文獻(xiàn)

[1]"PANG"J"S，F(xiàn)UKUSHIMA"M."Quasi-variational"Inequalities，"Generalized"Nash"Equilibria"and"Multi-leader-follower"Games[J]."Computational"Management"Science，"2005，"2（1）："21-56.

[2]"PANG"J"S，F(xiàn)UKUSHIMA"M.Quasi-variational"Inequalities，"Generalized"Nash"Equilibria，"and"Multi-leader-follower"Games[J].Computational"Management"Science，2009，6（3）：373-375.

[3]"FACCHINEI"F，KANZOW"C."Penalty"Methods"for"the"Solution"of"Generalized"Nash"Equilibrium"Problems"[J]."Society"for"Industrial"and"Applied"Mathematics，"2010，20（5）：2228–2253.

[4]"FACCHINEI"F，LAMPARIELLO"L.Partial"Penalization"for"the"Solution"of"Generalized"Nash"Equilibrium"Problems[J]."Journal"of"Global"Optimization，"2011，"50（1）："39-57.

[5]"羅美菊，吳歐．求解廣義納什均衡問題的增量罰算法[J]．純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué)，2012，28（5）：599-603.

[6]張艷芬.部分增長拉格朗日乘子算法在雙層規(guī)劃問題求解中的應(yīng)用改進(jìn)[J].北京工業(yè)職業(yè)技術(shù)學(xué)院學(xué)報，2020，19（3）：24-27.

[7]王俊霞，申倩影，王川龍.符號矩陣填充的修正增廣拉格朗日乘子算法[J].工程數(shù)學(xué)學(xué)報，2021，38（3）：343-352.

[8]"WANG"X"Y，WANG"Y"J，WANG"G."An"Accelerated"Augmented"Lagrangian"Method"for"Multi-criteria"Optimization"Problem[J]."Journal"of"Industrial"amp;"Management"Optimization，"2018，"16（1）"："1-9.

[9]孫月明.約束多目標(biāo)優(yōu)化問題的罰函數(shù)方法及其應(yīng)用[D].重慶：重慶郵電大學(xué)，2021.

[10]"LIANG"Y"C，YE"J"J."Optimality"Conditions"and"Exact"Penalty"for"Mathematical"Programs"with"Switching"Constraints[J]."Journal"of"Optimization"Theory"and"Applications，2021，190（1）：1-31.

[11]COCCHI"G，LAPUCCI"M."An"Augmented"Lagrangian"Algorithm"for"Multi-objective"Optimization[J]."Computational"Optimization"and"Applications："An"International"Journal，"2020，"77（1）"："29-56.