隨機(jī)互補(bǔ)問題的幾類求解模型

劉紅玲

摘 要： 隨機(jī)變量的引入，使得互補(bǔ)問題的應(yīng)用更加廣泛，但也加大了該問題的求解難度，由于隨機(jī)因素的存在，隨機(jī)互補(bǔ)問題通常情況下無解，但是實(shí)際應(yīng)用中，這類問題又十分重要.鑒于這種情況，學(xué)者常?？紤]構(gòu)造一個(gè)確定性模型，然后對(duì)這個(gè)確定性問題進(jìn)行求解.本文介紹幾種求解隨機(jī)互補(bǔ)問題的方法.

關(guān)鍵詞： 隨機(jī)互補(bǔ)問題 NCP函數(shù) 期望

一、相關(guān)定義

定義1：隨機(jī)互補(bǔ)問題就是求矢量x∈R，滿足：

x≥0，F(xiàn)（x，ω）≥0，（x）（x，ω）=0.（1）

其中F：R→R映射，特殊的，當(dāng)F是線性映射時(shí)，即F（x，ω）=M（ω）x+q（ω），稱上述問題為隨機(jī)線性互補(bǔ)問題SLCP，當(dāng)F是關(guān)于x的非線性映射時(shí)，稱上述問題為隨機(jī)非線性互補(bǔ)問題，簡(jiǎn)記為SNCP.

定義2：如果函數(shù)Φ：R→R，滿足Φ（a，b）=0？圳a≥0，b≥0，ab=0，那么稱函數(shù)Φ為NCP函數(shù).

常用的NCP函數(shù)為Fischer-Burmeister（FB）函數(shù)：Φ（a，b）=-（a+b）.

二、求解隨機(jī)互補(bǔ)問題的幾種模型

（一）期望值模型（EV）：求向量x∈S滿足：

x≥0，E[F（x，ω）]≥0，（x）E[F（x，ω）]=0.（2）

其中E表示關(guān)于ω的數(shù)學(xué)期望.由于E[F（x，ω）]通常情況下很難計(jì)算，當(dāng)不能直接求得其期望值時(shí)，人們又提出了很多數(shù)值算法求解問題，詳見[1].

（二）期望殘差極小化模型（ERM）：根據(jù)NCP函數(shù)的定義，式（1）等價(jià)于下面的方程組：

Φ（x，ω）=0，ω∈Ω，a.s.

其中Φ：R×Ω→R為：Φ（x，ω）=Φ（x，F(xiàn)（x，ω））Φ（x，F(xiàn)（x，ω）） …Φ（x，F(xiàn)（x，ω））

ERM模型就是使式（1）的期望殘差極小化，也就是將式（1）轉(zhuǎn)化為下面的確定性約束問題：

ξ（x）=E[||Φ（x，ω）||]（3）

（三）CVaR模型[2]：利用NCP函數(shù)構(gòu)造投資組合優(yōu)化中的損失函數(shù)，給出求解SNCP的條件風(fēng)險(xiǎn)價(jià)值模型，進(jìn)一步利用樣本均值近似方法和光滑化方法給出該模型的近似問題.求解隨機(jī)互補(bǔ)問題的風(fēng)險(xiǎn)價(jià)值模型如下：

minθ（x，u）=u+（1-α）E[||Φ（x，ω）||-u]（4）

其中[t]=max{t，0}，對(duì)任意t∈R，依蒙特卡羅樣本均值近似方法，CVaR模型的近似問題如下：

minθ（x，u）=u+（1-α）∑[||Φ（x，ω）||-u]

事實(shí)上，即使F（x，ω）（i=1，2，…，n）是連續(xù)可微的，由于[t]的存在，上述優(yōu)化問題通常不連續(xù)可微.為此，我們給出光滑化形式：對(duì)于給定光滑參數(shù)υ>0，定義：