 Advances in Applied Mathematics 应用数学进展, 2012, 1, 12-17 http://dx.doi.org/10.12677/aam.2012.11002 Published Online August 2012 (http://www.hanspub.org/journal/aam.html) Expected Residual Minimization Method for Stochastic Generalized Complementary Problems Meiju Luo1, Ou Wu2 1School of Mathematics, Li aoning University, Shenyang 2College of Science, PLA University of Science and Technology, Nanjing Email: meiju_luo@yahoo.cn, ouwu123@yahoo.com.cn Received: Jul. 3rd, 2012; revised: Jul. 10th, 2012; accepted: Jul. 23rd, 2012 Abstract: In practice, generalized complementary problems have many applications and many elements may involve uncertain data in applications. Therefore, we mainly consider the stochastic generalized complemen- tary problems. We employ the so called NCP function to give the expected residual minimization (ERM) model. Since the ERM formulation includes an integration, which is g enerally difficult to evaluate exactly, we propose the quasi-Monte Carlo method to give an approximation problem for ERM formulation. Furthermore, we show that the solutions of this approximation problem converge to the solution of the ERM formulation under very mild conditions. Keywords: Stochastic Generalized Complementary Problems; NCP Function; Expected Residual Minimization Method; Quasi-Monte Carlo Method 求解随机广义互补问题的期望残差最小化方法 罗美菊 1，吴 欧2 1辽宁大学数学院，沈阳 2中国人民解放军理工大学理学院，南京 Email: meiju_luo@yahoo.cn, ouwu123@yahoo.com.cn 收稿日期：2012 年7月3日；修回日期：2012 年7月10 日；录用日期：2012 年7月23 日 摘 要：由于广义互补问题有着广泛的应用，并且在实际应用中存在很多不确定因素。因此，本文主 要考虑随机广义互补问题。通过所谓的NCP 函数给出它的期望残差最小化(ERM)模型。由于所给出的 ERM 模型中含有一个积分计算。一般情况下，积分计算很难得到精确值。因此，本文引入拟蒙特卡罗 方法，并用此方法给出 ERM问题的近似问题。进一步，证明了在一定条件下，由ERM 问题的近似问 题得到的解的序列收敛到ERM 问题的解。 关键词：随机广义互补问题；NCP函数；期望残差最小化方法；拟蒙特卡罗方法 1. 引言 广义互补问题是非线性规划的重要组成部分，在工程、经济等领域具有广泛的应用[1,2]。但在实际生活中， 经常会遇到含有随机变量的情况，这就涉及到了随机广义互补问题。目前对于随机互补问题的研究较多，尤其 是对随机线性互补问题的研究已取得很多好的研究成果，详见[3-7]。然而对更一般形式的随机广义互补问题的 研究还很少。因此，本文考虑随机广义互补问题。这里，随机广义互补问题(SGCP)是指求 x ，使得 0,,0, .. F xGx a s 在给定的概率测度下，对 几乎处处成立。其中，“”表示在给定概率测度下“几乎真(almost surely)”..as Copyright © 2012 Hanspub 12  罗美菊，吴欧 求解随机广义互补问题的期望残差最小化方法 的缩写。 F 和 均为的映射，Gnm RR R nm R 为样本空间， ab 表示 0ab 。 由于随机变量的存在，SGCP 通常情况下无解。这就使得我们考虑要把 SGCP 中的随机变量去掉，也就是 构造一个确定性模型，然后再对这个确定性问题求解。那么怎样建立这个确定性的模型才是合理的呢？这又成 为求解 SGCP 的难点之一。 本文利用 NCP 函数，采用期望残差最小化方法(ERM)给出了求解SGCP 的模型。由于该模型中含有一个积 分计算，进一步，利用拟蒙特卡罗方法[8]给出它的近似问题。此后又研究了该近似问题的全局最优解的收敛性。 2. NCP函数 定义 2.1：函数 被称为“NCP 函数”，如果它满足这样的性质： 2 :RR ,ab 0当且仅当 。 0,ab0, 0ab 下面我们介绍两个非常重要且常用的 NCP 函数。一个是 FB 函数： 22 ,:ab a FB ba b 。它在 0ab 处不可微[9]，但在任意点 为可微，并且 ,ab, T ab 在平面上任意点为连续可微[10]。 2 FB 0 另一个是“min 函数”，即 min,ab min ,:ab ，值得注意的是min 函数在直线 上均不可微，这使得 映射 ab min 在所有满足 , x fx x fx的点处均不可微。此外，FB函数和 min 函数有如下关系[11]: min min ,, 22, 22 FB ab abab 2 . 3. 期望残差最小化方法 由于随机变量 的存在，对每个不同的 的取值，SGCP 都对应不同的解。因此，SGCP 在一般情况下没 有公共解。那么为了求解这个问题，我们试图找到一个合理的确定性模型。用这个确定性的模型的解作为SGCP 的解。由于NCP 函数可以对互补问题进行再定式。所以本文利用 NCP函数 22 , FB ababab , 给出期望残差最小化(ERM)模型。 根据 NCP函数的定义 SGCP等价于下面的带有随机变量的非线性方程组： ,0,.. x as 其中 。也就等价于下面的无约束优化问题： ,: 11 ,, , ,, , n n Fx Gx Fx Gx FB FB x 2 1 min:,. . 2 n xR x xa s 基于以上事实，我们给出求解SGCP 的ERM 模型如下： 2 1 min :, 2 n xR xEx 并称上述问题为ERM 问题。 4. ERM问题的近似问题及其收敛性结果 本文中，由于 ERM 问题中含有一个数学期望，对于连续性随机变量 来说也就是一个求积分的运算。通 常情况下，这个积分不容易求得。因此，我们将利用拟蒙特卡罗方法给出ERM 问题的近似问题对原问题进行逼 Copyright © 2012 Hanspub 13  罗美菊，吴欧 求解随机广义互补问题的期望残差最小化方法 近。这也就使得我们要考虑近似问题得到的解和原问题的解的关系。因此，我们试图讨论这样的结果：由近似 问题得到的全局最优解的点列的每一个聚点都是原问题的全局最优解。 对每个 ，令 k 2 1 :, 2ik ki k xx N i , 其中 是拟蒙特卡罗方法生成的点集， ,1,, i k iN kk ，且当 时，。 k k N 在余下的部分，我们将研究ERM 问题的近似问题，即 min nk xR x . 下面关于拟蒙特卡罗方法的收敛性结果是非常重要的。在下面的收敛性证明中将用到。 引理 4.1[12]：令 : H R 是上的可积函数。那么， 1 1 lim Nii i NHEH N 的 。这 里 是 概率密度函数。i 是由拟蒙特卡罗方法确定的点列。 在本文中，假设 , F G关于 x 是二次连续可微的，ERM问题的解集为且非空，它的近似问题的解集为且 非空。且有下面的条件成立： Sk S 1) 2 ,EFx ; 2) 2 ,EGx ; 3) 2 ,,1, i EFx i ,n ; 4) 2 ,;1, i EGx i ,n ; 5) . E 引理 4.2：假设函数, F G满足条件1)~2)，则对任意的 n x R都有 lim k k x x 。 n x R，由条件 1)~2)我们有 证明：对任意 2 22 1111 2 2 22 2 22 11 11 2 22 22 ,,,, , ,,,, ,,,, 2,, ,, 3, , . nnnn nn nn Fx GxFx Gx Ex E fx GxFx Gx Fx GxFx Gx EFx GxFx Gx EFx Gx (4.1) 再由引理 4.1的结论可知，对任意n x R， lim k k x x kk 。结论得证。 定理 4.1：假设条件1)~2)成立且对每个 ，k x S 。那么序列 k x 的每个聚点都包含在内。 S 证明：设 x 是 k x 的一个聚点，不失一般性，我们假设lim k。首先证明：当 时， k x x k 0 kk k xx . (4.2) 由式(4.1)的证明过程可知 22 ,3, ,xFxGx 2 , Copyright © 2012 Hanspub 14  罗美菊，吴欧 求解随机广义互补问题的期望残差最小化方法 进一步，我们可以得到 2 2 ,4, ,xFxGx , 也就是 ,2, ,xFxGx . 根据上式及条件1)~2) ，引理 4.1，我们有以下结论成立。 1, 1 lim,, , ,. ik ik i i k kikiiii kk x FxGxFx Gx N lim , 2 ki kx N (4.3 ) 另一方面，由微分中值定理，引理4.1 及条件3)可知对每一个 1, ,in都有 2 2 22 1 1 lim , 1 lim,0, . k ik ik kii i T ki ki i kk ki ki i kk Fy x x N Fyx xk N (4.4) 同理可得 lim, , iii kk Fx Fx N 2 1 lim, ,0, ik kii i kii k Gx Gxk N . (4.5) 又由引理 4.1及已知条件5)可知对每一个 1, ,in都有 2 22 22 ,, 1 lim ,, ,, ik ki i ii i kki kiii kii ii Fx Fx NFxGxFx Gx . (4.6) 同理，可得 2 22 22 ,, 1 lim ,, ,, ik ki i ii i kki kiii kii ii Gx Gx NFxGxFx Gx . (4.7) 进一步，由(4.4)~(4.7)可得 2 22 2 22 2 2 1 2 12 ,, ,, , 1 lim ki N ,, , ,,,, 2 lim ,, , 2 lim k kik k kii kii iiii ki kiii ii i nkikiii i ii ii i k ni ii kii k ii k k i FxFx FxFx Fx Fx GxF GxFx Gx GxGx Gx xGx N N 22 2 22 1 , ,, ,. ,0, ik ii i ki ni ikii i ii ii Gx FxGxFx Gk x (4.8) Copyright © 2012 Hanspub 15  罗美菊，吴欧 求解随机广义互补问题的期望残差最小化方法 综上我们有 2 22 1 2 222 2 1 1 1 lim,, 3 lim lim 3 lim, , 0 ,, ,, 3,, ,. ik ik ik ik kiii kk ni k ki kiii i i k iii k nkii i ii ki k iii nk ii i k xx N N Gx Gx N k FxGxFxGx FxFx N (4.9) 其中，第一个不等式可由 的定义及如下事实： 对任意 2222 0, 0, 0,3abc abcabc 得到并且由(4.4)~(4.5)，(4.8)可知极限成立。 再由 Cauchy-Schwarz不等式，可得 1 lim, ,0, ik kiii kk xx k N . (4.10) 最后由(4.3)和(4.10)可得 2 2 ,, 2 ,, ,, . k k k k iii ii iik i x N xx xx 1i kk xxx 1 k 2ik k N 0,k 因此，式(4.2)成立。 由(4.2)及引理 4.2 可知：当 时， k 0. kk kk kk xx x xx x 因为 kk x S，即k x 是ERM 近似问题的解，所以，对任意的n x R， kk k x x , 对上式两边同时取极限，有 lim lim kk k kk x xxx 对任意的 都成立。这表明 x n x R是ERM 问题的最优解。结论得证。 5. 结论 义互是素的 ，本文对随机广义互补问题给出了期望 残差最小化方法。通过使用NCP 函数，我们将求解随机互补问题的 ERM方法[13,14]推广到了求解 SGCP 上。此 广 补问题互补问题的更一般形式。由于不确定性因 存在 Copyright © 2012 Hanspub 16  罗美菊，吴欧 求解随机广义互补问题的期望残差最小化方法 Copyright © 2012 Hanspub 17 外，为了求解ERM 问题，通过使用拟蒙特卡罗方法给出了SG 的ERM 问题的近似问题。最后，在适当条件 下，我们证明了该近似问题的点列的每个聚点都是 SGCP 的ERM 问题的解的结论。 参考文献 (References) aramar ly and Applications, 1967, 8: 161-167 . F. Facchinei, J. S. Pang. Finite-dimensional variational inequalities and complementarity problems. New York: Springer, 2003. en, M. Fukushima. Expected residual minimization method for stochastic linear complementarity problems. Mathematics of Operations 2005, 30(4): 1022-1038. [4] s. SIAM Journal on Optimization, 2009, 20(2): 627-64 9 . [8] 雷桂媛. 关于蒙特卡罗及拟蒙特卡罗方法的若干研究[D]. 浙江大学, 2003. 式约束优化问题的 KKT 系统[D]. 北京工业大学, 2007. 论与算法[M]. 上海: 上海科学出版社, 2006: 1. eory and Ap- CP 的解组成 [1] S. V. Kdian. Generalized compementarity problem. Journal of Optimization Theor [2] [3] X. J. Ch Research, H. Fang, X. J. Chen and M. Fukushima. Stochastic R0 matrix linear complementarity problems. SIAM Journal on Optimization, 2007, 18(2): 482-506. [5] X. J. Chen, C. Zhang and M. Fukushima. Robust solution of monotone stochastic linear complementarity problems. Mathematical Program- ming, 2009, 117( 1): 51-80. [6] G. L. Zhou, L. Caccetta. Feasible semismooth Newton method for a class of stochastic linear complementarity problems. Journal of Optimiza- tion Theory and Ap pl i c a t io n s , 2008, 139(2): 379-392. [7] C. Zhang, X. J. Chen. Smoothing projected gradient method and its application to stochastic linear complementarity problem [9] 韩婷. 利用NCP 函数求解不等 [10] 韩继业, 戚厚铎. 非线性互补理 [11] P. Tseng. Growth behavior of a class of merit functions for the nonlinear complementarity problem. Journal of Optimization Th plications, 1996, 89(1): 17-37. [12] J. R. Birge. Quasi-Monte Carlo approaches to option pricing. Department of Industrial and Operations Engineering, University of Michigan, 1994. [13] X. Chen, M. Fukushima. Expected residual minimization method for stochastic linear complementarity problems. Mathematics of Operations Research, 2005, 30(4): 1022-1038. [14] C. Zhang, X. Chen. Stochastic nonlinear complementarity problem and applications to Trafic equilibrium under uncertainty. Journal of Opti- mization Theory and Applications, 200 8 , 137(2): 277-295. |