基于CVaR的一类随机拟变分不等式的逼近算法

马会强，王磊

基于CVaR的一类随机拟变分不等式的逼近算法

马会强1，王磊2

(1.西南民族大学经济学院，四川成都610041;2.西南财经大学经济数学学院，四川成都610074)

主要考虑基于CVaR的一类随机拟变分不等式问题的逼近算法.将随机拟变分不等式问题的正则gap函数看作一个损失函数，将随机拟变分不等式问题转化为损失函数CVaR值的最小化问题.利用光滑技术和蒙特卡洛方法，获得CVaR最小化问题的逼近问题，并考虑了逼近问题的最优解和稳定点的收敛性.

随机拟变分不等式;CVaR;正则gap函数;光滑技术;蒙特卡洛方法

拟变分不等式问题是研究广义均衡问题的一种非常重要和强有力的工具，它被广泛的应用于研究广义Nash均衡问题［1－5］.

拟变分不等式问题是求解x*∈S(x*)满足

其中，F:Rn→Rn，符号?·，·?是空间Rn上的内积，S:Rn→2Rn是一集值映射，并且对任意的x，S(x)是Rn上的闭凸子集.特别地，当S是一闭凸子集并且对任意的x满足S(x)=S时，拟变分不等式(1)就退化成了经典的变分不等式:求解x*∈S满足

在许多实际应用中，函数F经常会受到一些随机因素的干扰，如果将这些随机因素的扰动引入到拟变分不等式(1)中，就得到了随机拟变分不等式问题.设(Ω，F，P)是一概率空间，则随机拟变分不等式问题为求解x*∈S(x*)满足

或者等价于

其中F:Rn×Ω→Rn.相应的随机变分不等式问题为求解x*∈S满足由于随机因素ω的引入，随机变分不等式问题能够更加精确的描述现实问题，同样的，也吸引了众多学者参与到随机变分不等式问题的研究中来［6－12］.一般来说，不能找到一个向量x*∈S(x*)使得(3)式以概率1成立.也就是说，如果想在随机因素ω实现之前求解(3)式是一项不可能的任务.因此，如果重新定义(3)式的一个合理的解就成了随机拟变分不等式问题研究中的一个关键问题.

在文献［6，8，13］中，对随机变分不等式问题的处理方法主要有3种.一种方法是期望值方法，一种方法是期望残值最小化方法，另外一种方法是条件风险价值CVaR最小化方法.

期望值方法的主要思路是将随机变分不等式的解定义为如下问题的解:求x*∈S满足

其中，E是期望算子.期望残差最小化方法首先是X.J.Chen等［13］提出来的，用于求解随机线性补问题.M.J.Luo等［8］将该方法推广应用到求解随机变分不等式问题(4).通过利用正则间隙函数

他们将随机变分不等式问题的解定义为下面优化问题的解其中a是一给定的正数.条件风险价值CVaR最小化方法则是从投资组合的观点出发，X.J.Chen等［6］将D－间隙函数

视为投资组合理论中的“损失函数”，利用条件风险价值CVaR提出了一种求解随机变分不等式的方法.具体来说，就是把随机变分不等式的解定义为如下问题的解

其中，CVaRα(x)是关于x的损失函数θab(x，ω)的条件期望.对于固定的置信水平α∈(0，1)，关于x的损失函数的CVaR定义为

其中

H.Q.Ma等［9］将正则间隙函数视为损失函数，结果发现这一替换会使条件风险价值CVaR最小化方法适用于求解更一般的随机变分不等式问题.H.Q.Ma等［10］考虑了比CVaR更具优势的风险度量方法混合CVaR来度量损失函数的风险，并在混合CVaR下考虑了随机变分不等式的求解问题.

受到上述工作的启发，本文将CVaR最小化方法推广应用到随机拟变分不等式问题的求解.将正则间隙函数视为损失函数，得到了CVaR最小化问题.利用光滑技术和蒙特卡洛方法，获得了CVaR最小化问题的逼近解，证明了逼近问题的最优解和稳定点分别收敛于损失函数CVaR的最小化问题的最优解和稳定点.结果改进并推广了文献［6，9］的相关结果.

1 预备知识

其中λmin和λmax分别是G的最小特征值和最大特征值.

拟变分不等式(1)的正则间隙函数为

其中a是一正的参数.记(1)式的可行集为

对于正则间隙函数(9)和拟变分不等式(1)，有如下结论.

引理1.1［14－15］对于任意的x∈X，fa(x)≥0.进一步地，fa(x*)=0和x*∈X当且仅当x*是拟变分不等式问题(1)的解.因此，(1)式等价于求解下面的优化问题

需注意的是，尽管正则间隙函数fa(x)在合适的条件下是方向可微的［14－15］，但是，在一般条件下，fa(x)是不可微的.如果将S(x)限制为S(x)=S+m (x)，其中m(x):Rn→Rn，则有如下结论.

引理1.2［16］如果S(x)=S+m(x)，其中m(x):Rn→Rn并且S是一闭凸集，则

进一步地，如果m(x)和F(x)是连续可微的，则正则间隙函数fa(x)也是连续可微的，并且其梯度为

其中

I是n×n的单位矩阵.随机拟变分不等式(3)的正则间隙函数为

条件风险价值CVaR最小化方法下，求解随机拟变分不等式(3)等于求解如下的优化问题

其中

由文献［17］中的定理14可得，问题(12)等价于

其中

并且(x*，u*)是(13)式的解当且仅当x*和u*分别是(12)式和

的解.

注意到目标函数Θ(x，u)是非光滑的并且含有期望算子.在对问题(13)的求解中，将利用到光滑技术和蒙特卡洛方法.光滑技术主要是为了处理目标函数中出现的非光滑函数［·］+.对［·］+的一类光滑近似［18］如下:给定一个很小的数μ＞0，定义

很容易得知

并且有下面引理.

引理1.3对任意实数t和s，下列关系式成立

蒙特卡洛方法主要是为了处理目标函数中出现的期望算子.在本文中，假设目标函数中的

是很难直接计算出来的，因此需要通过蒙托卡洛样本均值来近似它.对于可积函数φ:Ω→R，用样本均值

来近似计算期望值E［φ(ω)］，其中ω1，ω2，…，ωNk是ω的独立同分布的随机样本并且Ωk={ω1，ω2，…，ωNk}.由大数法则知下面引理.

引理1.4设φ(ω)是可积的，则

令

应用光滑技术和蒙特卡洛方法，得到问题(13)的逼近问题如下

其中，当k→∞时，μk↓0，Nk↑∞.

2 解的收敛性

本节主要证明逼近问题(15)的解收敛到问题(13)的解.假设

其中M:Ω→Rn×n和Q:Ω→Rn，并且满足

这就意味着

并且，对任意的数α有

引理2.1对任意的(x，u)∈X×R，下面的关系成立

证明由引理2.1知

对任意的(x，u)∈X×R和μk有

因此(19)式成立.

证明由于

只需证明

由微分中值定理可得

其中，yki=λkixk+(1－λki)x*，λki∈［0，1］.

由投影算子的非扩张性可知，对任意的y∈X和ω∈Ω有

和

由(16)和(17)式可知，(24)式的右式收敛到0，因此有

又因为

所以(22)式的右式收敛到0并且(21)式成立，这就意味着(20)式也成立.

证明由引理2.3可知

由引理2.2可知，上式的右式以概率1收敛到0，这就意味着(26)式成立.

定理2.1假设m(x)=Nx.如果对任意的k，(xk，uk)是优化问题(15)的最优解，则{(xk，uk)}的任意一聚点都是优化问题(13)的最优解.

证明假设(x*，u*)是{(xk，uk)}的一个聚点.不失一般性，假设(xk，uk)收敛到(x*，u*).显然

对任意的k，因为(xk，uk)是(15)式的最优解，所以，对任意的(x，u)∈X×R，下式成立

由引理2.1和引理2.3，上式两边同时取极限可得

这就意味着(x*，u*)是问题(13)的最优解.

注2.1本文并没有证明优化问题(13)和(15)是凸的.实际上，在合适的条件下，采用文献［16］中方法可以证明(13)和(15)式均是凸的.

注2.2定理3.1说明文献［6，9］中处理随机变分不等式的CVaR最小化方法同样可以应用到求解随机拟变分不等式问题.

3 稳定点的收敛性

一般来说，通过优化算法来寻找优化问题(15)的全局最优解是比较困难的，然而寻找稳定点则是相对比较容易的.在本节中，主要研究优化问题(15)稳定点的极限行为.显然，当S(x)=S+Nx并且S是闭凸集时，可行集X是一闭凸集.

定义3.1(i)称(xk，uk)为优化问题(15)的稳定点，如果

其中NX×R(xk，uk)是X×R在(xk，uk)处的法锥［19］并且

(ii)称(x*，u*)为优化问题(13)的稳定点，如果

其中ɚ(x，u)Θ(x*，u*)是Θ(x，u)在(x*，u*)处的Clarke广义梯度［20］，并且**

DΘ(·)是点(x*，u*)附近的，表示Frechét可微的点的集合，“conv”表示集合的凸包.

引理3.1［21］设{(xk，uk)}是优化问题(15)的稳定点，(x*，u*)是{(xk，uk)}的一聚点.如果C是以概率1包含点(x*，u*)的某个邻域的X×R的紧子集，并且存在μ0＞0和可积函数κ(ω)满足

引理3.2假设m(x)=Nx.对任意的(珋x，珔u)∈X ×R，下式成立

证明设B是以(珋x，珔u)为中心的单位球.对任意的(xx，xu)，(¨x，¨u)∈B，由中值定理可得

‖ProjS，G［(I－N)z］－［(I－N)z］‖≤c成立.因此

由(16)～(18)式及(28)～(29)式可知，对任意的(xx，xu)，(¨x，¨u)∈B，存在一可积函数κ:Ω→R+满足

由文献［22］中第二章定理9可知(27)式成立.

定理3.1假设m(x)=Nx.如果，对任意的k，(xk，uk)是优化问题(15)的稳定点，则{(xk，uk)}的任意一聚点(x*，u*)均是优化问题(13)的稳定点.

证明不失一般性，假设{(xk，uk)}本身收敛到(x*，u*).对于任意的t∈R和μ＞0，显然有

成立，并且

由(29)式可知，对于任意的μ0＞0和包含(x*，u*)的某邻域的紧子集C，存在可积函数κ':Ω→R满足

因此，由引理3.1可知

又因为［t］μ满足梯度一致性［21］，因此

这意味着

由(27)式可知

致谢西南民族大学中央高校基本科研业务费专项资金(2014SZYQN54)对本文给予了资助，谨致谢意.

［1］HARKER P T.Generalized Nash games and quasi－variational inequalities［J］.Eur J Oper Res，1991，54(1):81－94.

［2］KUBOTA K，FUKUSHIMA M.Gap function approach to the generalized Nash equilibrium problem［J］.J Optim Theory App，2010，144(3):511－531.

［3］丁协平.抽象经济的平衡和拟变分不等式［J］.四川师范大学学报(自然科学版)，1994，17(4):29－34.

［4］丁协平.含没有开截口的对应的抽象经济的平衡［J］.四川师范大学学报(自然科学版)，1995，18(6):5－11.

［5］PANG J S，FUKUSHIMA M.Quasi－variational inequalities，generalized Nash equilibria，and multileader－follower games［J］.Comput Manag Sci，2005，2(1):21－56.

［6］CHEN X J，LIN G H，CVaR－based formulation and approximation method for Stochastic variational inequalities［J］.Numerical Algebra，Control and Optimization，2011，1(1):35－48.

［7］LIN G H，FUKUSHIMA M.Stochastic equilibrium problems and stochastic mathematical programs with equilibrium constraints:a survey［J］.Pacific J Optimization，2010，6(3):455－482.

［8］LUO M J，LIN G H.Expected residual minimization method for stochastic variational inequality problems［J］.J Optim Theory App，2009，140(1):103－116.

［9］MA H Q，HUANG N J.CVaR－based formulation and approximation method for a class of stochastic variational inequality problems［J］.Math Inequal Appl，2013，16(4):981－998.

［10］MA H Q，HUANG N J.Neural network smoothing approximation method for stochastic variational inequality problems with mixed CVaR risk measure［J］.J Ind Manag Optim，2015，11(2):645－660.

［11］MA H Q，HUANG N J.Expected residual minimization method for stochastic variational inequality problems with nonlinear perturbations［J］.Appl Math Comput，2013，219(11):6256－6267.

［12］吴定平.随机变分不等式和随机相补问题［J］.四川师范大学学报(自然科学版)，2005，28(5):535－537.

［13］CHEN X J，FUKUSHIMA M.Expected residual minimization method for stochastic linear complementarity problems［J］.Math Oper Res，2005，30(4):1022－1038.

［14］FUKUSHIMA M.A class of gap functions for quasi－variational inequality problems［J］.J Ind Manag Optim，2007，3(2): 165－171.

［15］TAJI K.On gap functions for quasi－variational inequalities［J］.Abstr Appl Anal，2008(1):1－7.

［16］MA H Q，HUANG N J.Expected residual minimization method for a class of stochastic quasi－variational inequality problems［J］.J Appl Math，2012(1):1－15.

［17］ROCKAFELLAR R T，URYASEV S.Conditional value－at－risk for general loss distributions［J］.J Bank Finance，2002，26(7): 1443－1471.

［18］CHEN C H，MANGASARIAN O L.A class of smoothing functions for nonlinear and mixed complementarity problems［J］.Comput Optim Appl，1996，5(2):97－138.

［19］BONNANS J F，SHAPIRO A.Perturbation Analysis of Optimization Problems［M］.New York:Springer－Verlag，2000.

［20］CLARKE F H.Optimization and Nonsmooth Analysis［M］.New York:John Wiley Sons，1983.

［21］XU H F，ZHANG D L.Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications［J］.Math Program，2009，119(2):371－401.

［22］RUSZCZYNSKI A，SHAPIRO A.Stochastic Programming［M］.Amsterdam:Elsevier，2003.

CVaR-based Formulation and Approximation Method for a Class of Stochastic Quasi-variational Inequality Problems

MA Huiqiang1，WANG Lei2
(1.School of Economics，Southwest University for Nationalities，Chengdu 610041，Sichuan; 2.Department of Economic Mathematics，South Western University of Finance and Economics，Chengdu 610074，Sichuan)

In this paper，we consider a CVaR-based formulation and an approximation method for a class of stochastic quasi-variational inequality problems.We regard the regularized gap function for stochastic quasi-variational inequality as a loss function and reformulate the stochastic quasi-variational inequality problem as a CVaR of the loss function minimization problem.By using the smoothing techniques and Monte Carlo method，we get an approximation problem of the CVaR minimization problem and consider the convergence of optimal solutions and stationary points of the approximation problems.The results presented in this paper generalize some known results in the literature.

stochastic quasi-variational inequality problem;CVaR;regularized gap function;smoothing technique;Monte Carlo method

O211.2

A

1001－8395(2016)03－0354－08

10.3969/j.issn.1001－8395.2016.03.010

(编辑陶志宁)

2015－03－10

国家自然科学基金(11401484)

马会强(1984—)，男，讲师，主要从事随机变分不等式理论的研究，E－mail:huiqiangma@hotmail.com

2010 MSC:90C33;90C15