随机互补问题的几类求解模型

刘红玲

摘 要： 随机变量的引入，使得互补问题的应用更加广泛，但也加大了该问题的求解难度，由于随机因素的存在，随机互补问题通常情况下无解，但是实际应用中，这类问题又十分重要.鉴于这种情况，学者常常考虑构造一个确定性模型，然后对这个确定性问题进行求解.本文介绍几种求解随机互补问题的方法.

关键词： 随机互补问题 NCP函数 期望

一、相关定义

定义1：随机互补问题就是求矢量x∈R，满足：

x≥0，F（x，ω）≥0，（x）（x，ω）=0.（1）

其中F：R→R映射，特殊的，当F是线性映射时，即F（x，ω）=M（ω）x+q（ω），称上述问题为随机线性互补问题SLCP，当F是关于x的非线性映射时，称上述问题为随机非线性互补问题，简记为SNCP.

定义2：如果函数Φ：R→R，满足Φ（a，b）=0？圳a≥0，b≥0，ab=0，那么称函数Φ为NCP函数.

常用的NCP函数为Fischer-Burmeister（FB）函数：Φ（a，b）=-（a+b）.

二、求解随机互补问题的几种模型

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

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

其中E表示关于ω的数学期望.由于E[F（x，ω）]通常情况下很难计算，当不能直接求得其期望值时，人们又提出了很多数值算法求解问题，详见[1].

（二）期望残差极小化模型（ERM）：根据NCP函数的定义，式（1）等价于下面的方程组：

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

其中Φ：R×Ω→R为：Φ（x，ω）=Φ（x，F（x，ω））Φ（x，F（x，ω）） …Φ（x，F（x，ω））

ERM模型就是使式（1）的期望残差极小化，也就是将式（1）转化为下面的确定性约束问题：

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

（三）CVaR模型[2]：利用NCP函数构造投资组合优化中的损失函数，给出求解SNCP的条件风险价值模型，进一步利用样本均值近似方法和光滑化方法给出该模型的近似问题.求解随机互补问题的风险价值模型如下：

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

其中[t]=max{t，0}，对任意t∈R，依蒙特卡罗样本均值近似方法，CVaR模型的近似问题如下：

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

事实上，即使F（x，ω）（i=1，2，…，n）是连续可微的，由于[t]的存在，上述优化问题通常不连续可微.为此，我们给出光滑化形式：对于给定光滑参数υ>0，定义：

[t]= t？摇 ？摇？摇t>υ（t+υ）？摇？摇？摇？摇？摇-υ

结合光滑化方法与蒙特卡罗样本均值近似方法，构造CVaR模型的近似问题为：

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

三、总结

随机互补问题的引入，极大地丰富了互补问题的应用，所以求解此类问题迫在眉睫.本文给出三种求解随机互补问题的模型，分析出相应的模型的核心思想，为进一步求解随机互补问题打下坚实的基础.

参考文献：

[1]杨少君.一类随机互补问题算法的研究.西安电子科技大学.中国知网，2011.

[2]申雪莹.关于随机互补问题的一类新模型.大连理工大学数学系.中国知网，2012.