廣義納什均衡問題類乘子算法研究

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

關鍵詞：廣義納什均衡"類乘子算法"拉格朗日算法"精確罰函數

中圖分類號：O225"""""""文獻標識碼：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

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

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

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

來定義精確罰函數，其中。這里取的模在任意不可行點都是可微的。這是一個很明顯的優勢，而文獻[3，4]都要求。

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

1"預備知識

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

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

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

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

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

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

2"問題等價分析

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

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

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

（1）為連續可微，對為凸；

（2），連續可微，并且對為凸。

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

得到了增廣Lagrange罰函數：

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

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

現在分析和證明問題（1）與問題（4）等價。

顯然有，

注意到，，"具有模同樣的性質，在不可行點處是連續可微的。并且有，"。

定理1"若為原問題（1）的局部極小值點，為相應的乘子，若二階條件成立，即

則存在，當時，為的最優解。反之，若為原問題（1）的可行點，且為的極小點，則為原問題的最優解，其中為相應的乘子。

證""必要性。由

其中，，可知

從而

因為原問題（1）的局部極小值點，所以，.又因二階條件成立，必有

而

故為的最優解。

充分性．因為為原問題（1）的可行點，滿足，，且為的極小點，那么對任意靠近的可行點，，，有

從而為原問題（1）的最優解。

3"算法和收斂性分析

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

定義1""定義

定義2""若，，。則稱在點上滿足約束規。

定理2"假設條件成立，為的最優解必為原問題（1）的最優解。

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

即

易知時，

，

上式成立必有，。

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

現在我們考慮的是乘子的迭代。可知

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

假設1"對乘子和罰函數，

的解存在。

下面給出具體的算法。

算法1

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

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

歩2"令，對每個，若

（6）

轉歩3；否則使罰參數加倍（）。

歩3"利用（5）式計算，令，，轉歩1。

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

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

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

因目標函數的連續性，乘子集的有界性以及，有

，

即，"。

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

4"數值結果

本節將用例子來說明本章所提算法的可行性和有效性。cm表示罰因子增加的倍數，s.p.表示初始點，T表示運算的時間（單位為秒），表示誤差容忍度，term為相關的終止條件，iter表示算法迭代次數。對算法的歩1，我們仍采用擬牛頓法來計算。初始罰參數統一設置為，初始乘子為。

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

例1""考慮的博弈：

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

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

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

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

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

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

5"總結與展望

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

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

參考文獻

[1]"PANG"J"S，FUKUSHIMA"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，FUKUSHIMA"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]．純粹數學與應用數學，2012，28（5）：599-603.

[6]張艷芬.部分增長拉格朗日乘子算法在雙層規劃問題求解中的應用改進[J].北京工業職業技術學院學報，2020，19（3）：24-27.

[7]王俊霞，申倩影，王川龍.符號矩陣填充的修正增廣拉格朗日乘子算法[J].工程數學學報，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]孫月明.約束多目標優化問題的罰函數方法及其應用[D].重慶：重慶郵電大學，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.