具有約束條件的均衡規(guī)劃問題的微分方程方法

王 莉，王虎彬，王詩云，孫菊賀

（沈陽航空航天大學(xué) 理學(xué)院，沈陽 110136）

0 引 言

具有約束條件的均衡規(guī)劃問題是指：求解x＊∈Ω滿足

其中Φ：Rn×Rn→R，g：Rn→Rm是兩個映射；Ω?Rn是一閉凸集。假設(shè)Φ（x，y）對于任意的x∈Ω在y∈Ω處是凸的，向量值函數(shù)g（y）的每個分量函數(shù)都是凸的。假設(shè)極值映射≤0，y∈Ω｝對任意的x∈Ω都是定義好的，并且原問題（1）的解集Ω＊?Ω是非空的。根據(jù)文獻(xiàn)AUBEN和EKELAND［1］可知，如果Ω是凸緊致的且Φ（x，y）在x處是下半連續(xù)的在y處是凸的，則上述最后的假設(shè)可成立。

許多著名的問題，如文獻(xiàn)NIKAIDO和ISODA［2］及VENETS［3］研究的鞍點問題，文獻(xiàn)ANTIPIN［4］研究的在Nash均衡條件下的n人博弈問題，以及ANTIPIN等［5］提出的許多優(yōu)化反問題等都可以轉(zhuǎn)化為具有約束條件的均衡規(guī)劃問題，這使得關(guān)于具有約束條件的均衡規(guī)劃問題的求解方法的研究成為一項重要的任務(wù)。趙新斌等［6］運用Douglas－Rachford分離技巧解決了具有線性約束的最小矩陣秩優(yōu)化問題。由ARROW 等［7］，F(xiàn)IACCO等［8］與EVTUSHENKO［9］所提出的微分方程方法在求解優(yōu)化問題時起著非常重要的作用。微分方程方法是將一個約束優(yōu)化問題轉(zhuǎn)化為一個微分方程系統(tǒng)，當(dāng)微分方程中的參量t趨于無窮大時，微分方程系統(tǒng)的解就會收斂于優(yōu)化問題的解。這一經(jīng)典的微分方程方法已被許多學(xué)者進(jìn)行研究［10－15］。

本文運用微分方程方法的思想求解具有約束條件的均衡規(guī)劃問題。運用拉格朗日函數(shù)和投影算子，將具有約束條件的均衡規(guī)劃問題（1）轉(zhuǎn)化為方程組。運用該方程組建立具有控制過程的微分方程系統(tǒng)，并證明了該微分方程系統(tǒng)的解的全局收斂性。最后，運用具有控制過程的微分方程系統(tǒng)求解了2個算例，并描繪了每個算例的微分方程系統(tǒng)的解的軌跡圖，從而說明了微分方程方法求解具有約束條件的均衡規(guī)劃問題的可行性。

下面介紹ANTIPIN［4，15］所提出的斜對稱函數(shù)的定義及其性質(zhì)。

定義1［4］稱函數(shù)Φ（x，y）：Rn×Rn→R是斜對稱的，如果滿足下面的不等式

性質(zhì)1［15］如果函數(shù)Φ（x，y）：Rn×Rn→R是斜對稱的且關(guān)于第二元是凸的，則其關(guān)于第二元的梯度▽yΦ（x，x）是單調(diào)的，即有

到凸集上的投影算子在將具有約束條件的均衡規(guī)劃（1）轉(zhuǎn)化為方程組的過程中起著非常重要的作用，這里關(guān)于投影算子的定義不做回顧，只介紹其重要性質(zhì)：

引理1［8］設(shè)H是一個實Hilbert空間，C是一閉凸子集。對于給定的z∈H，u∈C滿足不等式〈z－x，x－u〉≥0，?x∈C當(dāng)且僅當(dāng)u＝ΠC（z），其中ΠC是H到C上的一個投影。

1 微分方程系統(tǒng)

運用拉格朗日函數(shù)和投影算子，建立微分方程系統(tǒng)，并證明微分方程系統(tǒng)的解的收斂性。

具有約束條件的均衡規(guī)劃問題的拉格朗日函數(shù)為

如果函數(shù)的約束條件是正則的，則該問題可轉(zhuǎn)化為拉格朗日函數(shù)L（x＊，y，u）的鞍點問題，即

如果g（y）是可微的，上面的不等式系統(tǒng)可轉(zhuǎn)化為下面的變分不等式

其中，Jg（x＊）是映射g在x＊處的Jacobian陣。

根據(jù)引理1上述的變分不等式組（2）可等價地表示成下面的方程組

其中參數(shù)α＞0，ΠΩ和Π＋分別是向量到集合Ω和正卦限Rn＋上的投影算子。

根據(jù)上面的方程組（3）可以建立下面的具有控制過程的微分方程系統(tǒng)

如果映射g，?yΦ和JgT均是Lipschitz連續(xù)的，且Lipschitz常數(shù)分別是｜g｜，｜?yΦ｜和｜Jg｜，而且‖‖≤C0，其中C0是一個常數(shù)，則容易得到下面的估計式

成立，其中C＝｜?yΦ｜＋C0｜Jg｜。

由于向量值函數(shù)g（y）的每個分量函數(shù)都是凸的，（2）的第一式可轉(zhuǎn)化為下式

下面證明具有控制過程的微分方程系統(tǒng)（4）的解的聚點是具有約束條件的均衡規(guī)劃問題（1）的解。

定理1 設(shè)具有約束條件的均衡規(guī)劃問題（1）的解集Ω＊是非空的，Φ是斜對稱的函數(shù)，g是凸的、可微的和Lipschitz連續(xù)的且其Lipschitz常數(shù)為｜g｜，Ω?Rn是閉凸集。如果Φ（x，y）對任意的x∈Ω關(guān)于變量y∈Ω是凸的且可微的，▽yΦ和JgT是Lipschitz連續(xù)的且Lipschitz常數(shù)分別是｜▽yΦ｜和則在條件下，具有控制過程的微分方程系統(tǒng)（4）的解x（t）的軌跡的聚點就是具有約束條件的均衡規(guī)劃問題（1）的解。

證明 在（5）中令y＝x＊∈Ω＊，在（7）中令y＝x＋分別可得

其中，C＝｜?yΦ｜＋C0｜Jg｜。將式（11）和式（12）相加，再由函數(shù)g是凸的可得

在不等式（10）中令y＝并與上式相加得

在式（6）中令v＝u＊，在（8）中令v＝u＋˙u可分別得

將式（14）和式（15）相加，同時應(yīng)用式（9）有

由于〈ˉu，g（x＊）〉≤0和〈u＊，g（x＊）〉＝0，可將上式轉(zhuǎn)化為

將式（13）與式（16）相加并結(jié)合性質(zhì)1簡化計算得

則存在t的子列｛ti｝使得當(dāng)i→∞時有（ti）‖→0。由于x（t）與y（t）都是有界的，則x（ti）與u（ti）也都是有界的，從而存在｛ti｝的子列｝使得存在x′和u′有當(dāng)j→∞時以及成立。在（7）中取子列｛tij｝時該式仍成立，則令j→∞可得

其與式（3）一致，即x′∈。證畢。

2 數(shù)值實驗

運用具有控制過程的微分方程系統(tǒng)（4）求解2個算例，并在每個算例中描繪了微分方程系統(tǒng)的解的軌跡圖。

例1 考慮下面的具有約束條件的均衡規(guī)劃問題

該問題的解為x＊＝（4.5，1.5，0）T。

圖1為例1的微分方程系統(tǒng)（4）的解的軌跡圖。

在本實驗中，選取的參數(shù)α＝0.05。圖1描繪了例1的具有約束條件的均衡問題的微分方程系統(tǒng)（7）的解x（t）和u（t）從五個隨機(jī)產(chǎn)生的初始點的軌跡隨時間的變化關(guān)系圖。

圖1 例1的微分方程系統(tǒng)（4）的解的軌跡圖

圖2 例2的微分方程系統(tǒng)（4）的解的軌跡圖

例2 考慮下面的具有約束條件的均衡規(guī)劃問題

該問題的解為x＊＝（0，2，0，0）T。

在本實驗中，選取的參數(shù)α＝0.1。圖2描繪了例2的具有約束條件的均衡問題的微分方程系統(tǒng)（4）的解x（t）和u（t）從6個隨機(jī)產(chǎn)生的初始點的軌跡隨時間的變化關(guān)系圖。

3 結(jié) 論

本文建立了具有控制過程的微分方程系統(tǒng)求解了具有約束條件的均衡規(guī)劃問題，證明了該微分方程系統(tǒng)的解的聚點是具有約束條件的均衡規(guī)劃問題的解。運用具有控制過程的微分方程系統(tǒng)求解了2個具體的具有約束條件的均衡規(guī)劃問題，并且針對每個問題都描繪了微分方程系統(tǒng)的解隨時間變化的軌跡圖，從圖中可以看出由均衡規(guī)劃問題得到的具有控制過程的微分方程系統(tǒng)（4）的解收斂于均衡規(guī)劃問題的解，從而說明了微分方程方法求解均衡規(guī)劃問題的可行性。

［1］AUBEN G P，EKELAND I.Applied nonlinear analysis［M］.New York：John Wiley ＆Sons，Inc，1984.

［2］NIKAIDO H，ISODA K.Note on noncooperative convex games［J］.Pacific J Math，1955，5（1）：807－815.

［3］VENETS V I.A continuous algorithm for searching the saddle points of convex－concave functions［J］.Avtomat Telemekh，1984，45（1）：42－47.

［4］ANTIPIN A S.Evolving systems equilibrium programming：gradient methods［J］.Automation and Remote Control，1997，58（8）：1337－1347.

［5］ANTIPIN A S.Inverse optimization problem：its formulation and solution approaches［M］.Moscow：Comupting Center，Russian Academy of Sciences，1992.

［6］趙新斌，單曉成.矩陣秩優(yōu)化問題的一種分離算法［J］.沈陽師范大學(xué)學(xué)報：自然科學(xué)版，2012，30（4）：454－458.

［7］ARROW K J，HURWICZ L.Reduction of constrained maxima to saddle point problems［C］∥Proceedings of the 3rd Berkeley Symposium on Mathematical Statistics and Probability，Berkeley：University of California Press，1956：1－26.

［8］FIACCO A V，MCCORMICK G P.Nonlinear programming：sequential unconstrained minimization techniques［M］.New York：John Wiely，1968.

［9］EVTUSHENKO Y G.Two numerical methods of solving nonlinear programming problems［J］.Sov Math Dokl，1974，15（2）：420－423.

［10］FRIESZ T L，BERNSTEIN D H，MEHTA N J.Day－to－day dynamic network disequilibria and idealized traveler information systems［J］.Operations Research，1994，42（2）：1120－1136.

［11］LI Yang，ZHANG Liwei.A differential equation method for solving box constrained variational ineauality problems［J］.J Ind Manag，2011，7（1）：183－198.

［12］JIN Li，ZHANG Liwei.Two differential equation systems for equality constrained optimization［J］.Appl Math Comput，2007，190（2）：1020－1039.

［13］JIN Li，ZHANG Liwei.Two differential equation systems for inequality constrained optimization［J］.Appl Math Comput，2007，188（2）：1334－1343.

［14］ANTIPIN A S.Differential equations for equilibrium problems with coupled constraints［J］.Nonlinear Analysis，2001，47（4）：1833－1844.

［15］ANTIPIN A S.The fixed points of extremal maps：computation by gradient methods［J］.Zh Vychisl Mat Fiz，1997，37（1）：42－53.