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

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

（沈陽航空航天大學 理學院，沈陽 110136）

0 引 言

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

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

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

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

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

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

性質1［15］如果函數Φ（x，y）：Rn×Rn→R是斜對稱的且關于第二元是凸的，則其關于第二元的梯度▽yΦ（x，x）是單調的，即有

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

將式（14）和式（15）相加，同時應用式（9）有

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

將式（13）與式（16）相加并結合性質1簡化計算得

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

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

2 數值實驗

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

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

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

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

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

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

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

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

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

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

3 結 論

本文建立了具有控制過程的微分方程系統(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］.沈陽師范大學學報：自然科學版，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.