（运筹学与控制论专业论文）一类随机变分不等式的抽样平均近似方法.pdf

大连理工大学硕十学位论文 摘要 确定型变分不等式问题( v a r i a t i o n a li n e q u a l i t yp r o b l e m ) 最初出现在数理方程中。1 9 6 4 年l i o n s jl 与t a m p a c c h i ags 等学者首先建立了初期变分不等式( v i p ) 理论，随 着变分不等式理论和运用的日益完善，变分不等式被广泛应用于工程，经济，交通运输， 运筹学与网络中。由于现实问题中往往存在许多不确定性因素，这样建立的变分不等式 模型中往往卷入不确定参数，即称之为随机变分不等式( s t o c h a s t i cv a r i a t i o n a li n e q u a l i t y p r o b l e m ) 。随机变分不等式的研究刚刚引起学者关注，文献还不多见。 抽样平均近似( s a m p l ea v e r a g ea p p r o x i m a t i o n ) 方法是利用蒙特卡洛模拟来求解随机 优化的一种非常有力的方法，在这个技术中随机问题的期望目标函数通过平均样本来近 似，然后利用确定性的优化方法对平均样本近似问题进行求解，从而得到原问题的一个 近似解。 本硕士论文在前人工作的基础上利用抽样平均近似方法对随机变分不等式问题进 行研究。我利用f u k u s h i m a 提出的正则化g a p 函数，给出了随机变分不等式的简单约束 优化表达以及抽样平均近似问题，进而对抽样平均近似问题的最优值与最优解进行分 析，为了验证所提出的抽样平均近似方法的有效性和可行性，我们对几个随机变分不等 式实例进行了测试，数值结果表明我们的方法是可行的、有效的。 关键词：随机变分不等式；抽样平均近似方法；正则化g a p 函数；收敛性分析 一类随机变分不等式的抽样平均近似方法 t h es a m p l ea v e r a g e a p p r o x i m a t i o nm e t h o df o rt h es t o c h a s t i c v a r i a t i o n a li n e q u a l i t yp r o b l e m a b s t r a c t v a r i a t i o n a li n e q u a l i t yp r o b l e m s ( i ns h o r tv i p s ) f i r s t l ya p p e a r e di nt h ep h y s i c se q u a t i o n s l i o n sjla n dt a m p a c c h i agsf i r s te s t a b l i s h e dt h ei n i t i a lt h e o r yo fv a r i a t i o n a li n e q u a l i t yi n 19 6 4 w i t ht h eg r e a ti m p r o v e m e n ti nt h et h e o r yo fv a f i a t i o n a li n e q u a l i t i e s ，v i p sh a v eb e e n e f f e c t i v e l ya p p l i e dt om o d d i n gar a n g eo fe q u i l i b r i u mp r o b l e m si ne n g i n e e r i n g ，e c o n o m i c s ， t r a n s p o r t a t i o n ，o p e r a t i o n sr e s e a r c h ，a n dn e t w o r k s a sm a n yp r a c t i c a lp r o b l e m sm a yi n v o l v e u n c e r t a i nf a c t o r s ，b ym o d e l i n g ，m o d e l so b t a i n e da r ev a r i a t i o n a li n e q u a l i t i e sm o d e l sw h e r e u n c e r t a i n t i e sa r ei n v o l v e d w ec a l lt h e ms t o c h a s t i cv a r i a t i o n a li n e q u a l i t i e s i nt h el i t e r a t u r e ， m a n yr e s e a r e r sa n dp r a c t i c e r sh a v eb e g u nt o h a v ei n c r e a s i n g i n t e r e s t i n g i ns t o c h a s t i c v a r i a t i o n a li n e q u a l i t yp r o b l e m s ，b u tt h e r eo n l ye x i s taf e wp a p e r so ns t o c h a s t i cv a r i a t i o n a l i n e q u a l i t yp r o b l e m s t h es a m p l ea v e r a g ea p p r o x i m a t i o nm e t h o di so n eo fe f f e c t i v ea p p r o a c h sf o rs o l v i n g s t o c h a s t i co p t i m i z a t i o np r o b l e m sb yu s i n gm o n t ec a r l os i m u l a t i o n i nt h i st e c h n i q u et h e e x p e c t e do b j e c t i v ef u n c t i o no ft h es t o c h a s t i cp r o b l e mi sa p p r o x i m a t e db yas a m p l ea v e r a g e f u n c t i o n f u r t h e r ，t h es a m p l ea v e r a g ep r o b l e mi ss o l v e db yd e t e r m i n i s t i co p t i m i z a t i o nm e t h o d s t h es o l u t i o no ft h es a m p l ea v e r a g ep r o b l e mi sar e a s o n a b l ea p p r o x i m a t i o ns o l u t i o no ft h e o r i g i n a lp r o b l e m s o nt h eb a s i so fp r e v i o u sw o r k ，w em a k eu s eo ft h es a m p l ea v e r a g ea p p r o x i m a t i o nm e t h o d t of i n ds o l u t i o n so fs t o c h a s t i cv a r i a t i o n a li n e q u a l i t yp r o b l e m s i nt h i st h e s i s ，1w i l lf o r m u l a t et h e s t a o c h a s t i cv a r i a t i o n a li n e q u a l i t yp r o b l e ma ss i m p l yc o n s t r a i n e do p t i m i z a t i o n p r o b l e mb y u s i n gr e g u l a r i z e dg a pf u n c t i o n b a s e do nt h i sr e f o r m u l a t i o n , ip r o p o s e ds a m p l e a v e r a g e a p p r o x i m a t i o nm e t h o df o rs o l v i n gt h i ss t o c h a s t i cv a r i a t i o n a li n e q u a l i t yp r o b l e ma n dp r o v ei t s c o n v e r g e n c e i no r d e rt ov e n f ye f f e c t i v e n e s sa n df e a s i b i l i t yo ft h ep r o p o s e ds a m p l ea v e r a g e a p p r o x i m a t i o nm e t h o d ，af e ws i m p l et e s t i n g so fs t o c h a s t i cv a r i a t i o n a li n e q u a l i t yp r o b l e m sa r e g i v e n n u m e r i c a lr e s u l t ss h o wo u rm e t h o di sv e r ye f f e c t i v ea n df e a s i b l e k e yw o r d s ：s a m p l ea v e r a g ea p p r o x i m a t i o n ；s t o c h a s t i cv a r i a t i o n a li n e q u a l i t y p r o b l e m ；r e g u l a r i z e dg a pf u n c t i o n ；c o n v e r g e n c ea n a l y s i s 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：二叁盍姿塑塞釜整墼坠塑塾垦竺堕苎 作者签名：重圣垒日期：塑旦年王月j 旦日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：_ 趣迭分客矽哆噼哪_ 哗蟹 作者签名： 函丝： 导师签名 日期：趔年1 月上日 吼砰年二月厶日 大连理工大学硕士研究生学位论文 1 绪论 1 1 研究的背景与意义 众所周知，确定型变分不等式已有相对完善的理论和方法，包括解的存在性、唯一 性和收敛性等等，并且已经成功地应用到经济、供应链网络、交通运输、和力学等实际 问题。 随着信息化的进一步发展以及一些突发事件的发生，实际问题中涉及许多不确定性 因素。通过数学工具建立的变分不等式模型卷入许多随机参数，即随机变分不等式。许 多现有的求解确定型变分不等式的方法( 如：牛顿法，投影法等) 都不能直接用来计算 随机变分不等式问题，由于其中所涉及的期望函数e ( f ( x ，w ) 1 往往很复杂，无法直接计 算或者只能通过抽样得到，基于此我们想到利用抽样平均近似方法对随机变分不等式问 题进行求解。由于抽样平均近似方法思想简单，在随机优化的求解中得到了广泛的应用。 关于抽样平均近似方法的理论与应用的研究，可参见【啦】。最近m e n gf a n w e n & x u h u i f u 【3 】利用了抽样平均近似方法对对一类互补约束随机规划( s m p c c ) 进行了求解，并在一定 的条件下证明了抽样平均近似问题的解以指数速率收敛到原来问题的解。r a m a m u r t h y b a l a j i & x uh u i f u 【4 】在给出b a n a c h 空间的集值映射的一致强大数定律的基础上，得到非 光滑随机优化问题的抽样平均近似解的指数收敛性，本文利用f u k u s h i m a 在文章【5 】提出 的变分不等式的g a p 函数，将随机变分不等式转化为等价的简单约束优化问题，进而利 用抽样平均近似方法对该问题进行了有效求解。本文将抽样平均近似方法应用于随机变 分不等式的求解，无论是对抽样平均近似方法本身，还是对随机变分不等式计算的研究 都有着重要贡献。 1 2 国内外研究现状 1 2 1 变分不等式问题研究现状 变分不等式( v a r i a t i o n a li n e q u a l i t y ) 起源于对数学物理问题及非线性规划问题的研 究，目前在物理学、工程、经济等领域中得到了广泛应用。数学物理中最早的变分不等 式出现于2 0 世纪6 0 年代初；特别是在1 9 6 4 年，得到了变分不等式的第一个解得存在 唯一性定理。其后，l i o n sjl 、l e w y h 、l e w yh 、b r e z i s d eh 等【6 】发表了一系列文章， 为变分变分不等式的理论奠定了初步基础：2 0 世纪7 0 年代，变分不等式在最优控制问 题、弹性问题、弹塑性问题及渗流问题等领域中得到了成功的应用；2 0 世纪8 0 年代以 来，作为偏微分方程理论重要部分的变分不等式理论得到了深入发展，至今已经非常成 一类随机变分不等式的抽样平均近似方法 熟。另一方面，2 0 世纪6 0 年代中期，在非线性规划的研究中出现了线性与非线性互补 问题，进一步发展为有限维空间的变分不等式。2 0 世纪9 0 年代，m a t h p r o g r a m m i n g 杂 志出版了非线性互补问题与变分不等式的专辑，标志了变分不等式已成为非线性规划的 一个重要研究领域。经过4 0 多年的发展，确定型变分不等式已经成为数学规划中发展 相当完善的课题。关于确定型变分不等式的理论、算法、应用的研究，可以参见文献【_ 7 。j 。 由于现实问题中往往涉及到许多不确定性因素，使得确定型变分不等式往往卷入不确 定因子，即：随机变分不等式( s t o c h a s t i cv a r i a t i o n a li n e q u a l i t y ) 。作为确定型变分不等式的 一个延伸，对随机变分不等式的研究也得到了人们的普遍关注。目前，对于随机变分不 等式的研究，国内外学者主要提出了两种表达：第一种是期望值表达( e x p e c t e dv a l u e ， e v ) ：第二种是期望剩余最小表达( e x p e c t e dr e s i d u a lm i n i m i z a t i o n ，e r m ) 。 对于随机变分不等式的期望值表达，最早f l j r o c h a f e l l a r t l 2 & r o b i n s o n 1 3 】提出。k i n ga j & r o c h a f e l l a rrt 【1 2 】考虑了一类广义随机方程( 包含随机变分不等式) ，并对其解得收 敛性进行了考虑，在该文中形成了随机变分不等式期望值表达的雏形。随后g 玉r k a n g ，o 。z g eay & r o b i n s o nsm 【1 3 】提出了如下形式的随机变分不等式： 寻找点x ：使得f x x 1 1e lf ( x ，w 1i 0 ，觇s 成立 ( 1 1 ) 并且利用样本路径优化( s a m p l ep a t ho p t i m i z a t i o n ) 对随机变分不等式的期望值表达进行 了求解。至此，国内外一些学者开始了对随机变分不等式的理论和算法算法进行了研究。 由于随机因素表达的复杂，致使目前没有随机变分不等式的统一定义形式，2 0 0 9 年 l u o & l i n ”】又提出了一类新的随机变分不等式定义： 寻找点x ：使得 ( x x t ，( x ，w ) o ，v x s ，口名w q ( 1 2 ) 其中q 为样本空间。今年来，学者们主要对这两种形式的随机变分不等式进行了研究。 l u o 与l i n 1 5 1 研究了形如( 1 2 ) 形式的线性变分不等式在c h e nx & f u l ( i l s h i m a 【1 6 】提出的 随机变分不等式的期望剩余最小表达基础上，又提出了随机线性变分不等式的e r m 表 达，并且建立了抽样平均近似方法及收敛性。 进一步，l u o 与l i n r 7 】研究了形如( 1 2 ) 的非线性随机变分不等式的期望剩余极小化 表达并且建立了抽样平均近似方法及收敛性。 最近，j i a n g & x u 1 4 】基于投影算子和g a p 效益函数给出了两类求解随机变分不等式期 望值表达的随机逼近方法( t h es t o c h a s t i ca p p r o x i m a t i o nm e t h o d s ) ，并且证明了其收敛性。 本文基于上述文献的分析，利用抽样平均近似方法对形如( 1 1 ) 的随机变分不等式问 题进行了研究。 一2 一 大连理工大学硕+ 研究生学位论文 1 2 2 粒子群算法研究现状 粒子群算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 是由美国社会心理学家k e n n e d y j s u 电气工程g 币e b e r h a r trc 在1 9 9 5 年共同提出的d 8 3 9 】，其基本思想是受他们早期对鸟 类群体行为研究结果的启发。由于算法的易实现性和高效性，该算法已经成功地运用 到了很多函数优化和工程技术领域，并取得了很好的效果。目前，已有很多学者对p s o 算法的性能和收敛性分析进行了深入的研究 2 0 - 2 3 1 。 到目前为止，p s o 算法还很不成熟，存在着很多不完善和未涉及的问题。如何利用 有效的数学工具对p s o 算法的收敛性以及计算复杂性进行分析、如何根据群体进化行为 完善p s o 算法，同时将群体的智能行为引入至u p s o 算法中，以充分借鉴生物群体进化规律 是目前研究的主要方向。 1 3 本文的研究内容与文章结构 随机变分不等式是基于确定型变分不等式的基础上发展而来的，由于随机因子的存 在，往往使得随机变分不等式的不易求解，为此，本利用抽样平均近似方法对随机变分 不等式问题进行了研究，具体内容安排如下： 第二章，介绍了抽样平均近似方法和随机变分不等式有关的一些预备知识。对于抽 样平均近似方法在理论上和计算上的一些结果进行了介绍；并且对于变分不等式的效益 函数( m e r i tf u n c t i o n ) 有关内容进行了介绍。 第三章，利用f u k u s h i m a 提出的正则化g a p 函数，给出了随机变分不等式的简单约 束优化表达以及抽样平均近似，进而得到抽样平均近似问题的最优值与最优解的收敛性 分析。从而给出了求解随机变分不等式的抽样平均近似方法。在结合粒子群算法的基础 上给出了实例的数值结果，所得到的数值结果表明我们的方法是可行的、有效的。 最后对全文的工作进行了总结，并对今后的研究工作和发展方向提出了展望。 一类随机变分不等式的抽样平均近似方法 2 预备知识 2 1抽样平均近似方法概述 抽样平均近似方法是以蒙特卡洛模拟为基础的求解随机优化的一种有效方法，对 该方法的理论，计算及应用的研究正日趋完善，下面将加以介绍。 对于随机规划问题，往往涉及形如e lf ( x ，f ( 彩) ) l 的期望值函数的估计，大量的 以样本为基础的方法被提出。我们可以将这些方法分为两类：内样本法与外样本法。在 内样本法中，样本优化进程内部不断被调整。在外样本法中，首先生成一个样本容量为 n 的样本，然后将对一个确定性的优化问题进行求解。相对而言，外样本法对问题的具 体形式的要求较少，适应性较强。而抽样平均近似方法，又被称为简单路优化，就是用 样本平均函数近似替代期望值函数的一个外样本法，被s h a p i r o 等对理论及算法进行了深 入的分析【2 4 2 9 1 。 2 1 1 抽样平均近似方法求解随机离散优化 考虑这样形式的离散优化问题： 卿 g ( x ) ：= e p g ( x , w ) ( 2 1 ) 其中s 是一个有限集，w 是具有分布p 的随机变量。针对这样的离散优化问题，目标函 数往往难以计算，s h a p i r o 1 z j 亡2 0 0 1 年提出了求解这类随机离散优化的抽样平均近似方 法。 对于问题( 2 2 1 ) ，令w 1 ，w 是随机变量w 的n 个独立同分布随机样本。则相应 的样本平均函数( s a m p l ea v e r a g e f u n c t i o n ) 为；( x ) 穿百i p g ( x ，) ，对应的样本近似 问题( s a m p l ea v e r a g ea p p r o x i m a t i o np r o b l e m s ) 为： m 独g ( z ) ( 2 2 ) 令问题( 2 1 ) 与( 2 2 ) 的最优值分别为1 ，与乱，最优解分别为与。利用( 强) 大数定律，s h a p i r o 得到了最优值孔以概率1 收敛到v ，最优解以概率1 收敛到。利 用大偏差理论l a r g ed e v i a t i o n s ( l d ) ，得到了以下重要结果： 尸( 嚣岱s 占) l s s 8 i p m p 芦 ( 2 3 ) 一4 大连理工大学硕士研究生学位论文 i m 一s u p l l o g 1 一p ( o c s f ) 一7 ( 万，s ) c 2 4 ， 其中s 8 = 淞( x ) v + s ) ，蠹= x ，三( x ) ；+ s ) ，r ( 6 ，s ) 一础丽ni x ( 一万) 。 上述结果保证了当n 的取值充分大时， 志崦( 掣 ， 眩5 ， 有。 尸( 磷c s 8 l - a ( 2 6 ) 即抽样平均近似问题的万最优解包含于原来的离散优化的s 最优解的概率不小于1 一口。 从而保证了s a a 方法在大规模取样本的情况下，能够得出原问题的一个合理近似解。 2 1 2 抽样平均近似方法求解两阶段随机规划 一个标准的两阶段随机规划问题如下式所示： m i n g ( x ) ：= c 7 x + e q ( 圳) ) ( 2 7 ) 其中q ( x ，w ) ：= i y g q7 y ：w y _ h t x ，w ：= ( g ，丁，形，h ) 为第二阶段问题的参数向量。 对应的样本近似问题为： m i n 三小) ：彩x 坩1 善nq ( 删”) ) 8 ， 其中q ( x ，w ”) ：= i n t t q r y ：吃少吃一乙x ，：= ( ，呢，吃，乙) 是w 的n 个独立同分布样 本。 对于为一类为常数，】，是一个整数集( y z ”) 的两阶段随机规划，s h a p i r o 3 0 3 1 1 对于该类问题利用抽样平均近似方法结合分支界定算法可以进行有效求解。 2 1 3 抽样平均近似方法求解均衡约束数学规划 我们称形如下列形式的问题为均衡约束数学规划问题： ，。m j ，i “n ) e e f ( x ，y ( w ) ，善( w ) ) ( 2 9 ) o h ( x ，y ( w ) ，孝( w ) ) + _ ( y ( w ) ) ，口p we q 其中xcr ”，f ：r ”r ”r ”一r ，h ：r ”r ”r ”一r ”，孝( w ) 是定义在概率空间 ( q ，f ，p ) 上的随机变量，c 是r 中的非空闭凸集。f ( y ) 是集合c 在y 处的法锥，即： 一类随机变分不等式的抽样平均近似方法 n c ( y ) ：= z r 珊：z r ( y - y ) o ，砂c 当y c 时， m ( y ) ：= o当y 芒c 时候。 注意到均衡约束数学规划问题本质上即是一类两阶段随机规划问题，由于该两阶段随机 规划问题的第二阶段涉及的变分不等式约束常常被解释为均衡约束。 s h a p i r oa & x uhf 【2 7 】利用抽样平均近似方法对该类问题进行研究，得到了局部以 及全局最优解的收敛性，进一步得到了抽样平均近似问题的一致指数收敛性，从而对给 出了求解抽样平均近似问题的样本容量的一个合理估计。 2 1 4 抽样平均近似方法的计算研究 由于抽样平均近似方法涉及到一个重复抽样的过程，尽管大量的理论研究表明抽样 平均近似问题的解会随着样本规模的增大快速的逼近原来问题的解。但是我们依然需要 考虑样本规模的选择。尽管式( 2 5 ) 通常给出了样本规模的一个估计，但往往过于保 守且该估计也不易计算。容易知道，样本规模选择越大，样本近似问题的目标函数与原 目标函数越接近，但同时往往需要的计算代价也越大。特别是在多维向量问题的计算时， 样本规模的选择涉及到了问题的精确性与复杂性的权衡。当样本近似问题的计算复杂性 随着样本规模呈线性增加时，人们往往可以采取使用一个较小的样本规模，并进行重复 试验，从而试图在精确性与复杂性之间谋求一个较好的平衡。关于该方法的计算分析， 可参见文献【2 1 。 2 2 随机变分不等式概述 2 0 世纪6 0 年代，l i o n s ，b r o w d c r 等提出和创立了变分不等式和互补问题的基本理 论，经过许多学者的努力，变分不等式理论及应用的研究已取得重大的进展，在微分方 程，力学，控制论，对策论，经济平衡理论，交通运输，社会和经济模型等很多方面有 着重要的应用，应用前景非常广阔。而近年来，由于f u k u s h i m a 、s h a p i r o 等学者的努 力，对于具有随机因素的随机变分不等式的研究也日益引起国内外学者的普遍关注。 下面我们将给出关于随机变分不等式的相关概念。 2 2 1 随机变分不等式的有关定义 定义1 令s 为一个非空闭凸集，：r ”专酞”是r ”到r ”的一个映射，如下的问题即为 变分不等式( v i p ) 问题：寻找一点x s ，使得 f x x 1f fx 1 0 ， v x s ( 2 1 0 ) 定义2 设函数f ：r ”jr ”， 一6 一 大连理工大学硕士研究生学位论文 ( 1 ) 若对于任意的x ，y x ，f 满足 ( f ( z ) 一f ( y ) ，x - y ) 0 则称，在集合彳上是单调的； ( 2 ) 若对于任意的x ，y x ，f 满足 ( ，( x ) 一f ( 少) ，x - y ) 0 则称f 在集合x 上是严格单调的； ( 3 ) 若对于任意的x ，y x ，存在口 0 ，使得f 满足 0 ，e f ( x ，国) o ( x ，f ( x ，国) ) = 0 其中( ，) 表示向量的内积。当s r ”时候，随机变分不等式问题即变成了随机方程组： 找点x 科，使得：e f ( x ，彩) = o 2 2 2 变分不等式效益函数的有关定义 对于一般的变分不等式问题： 求x s ，使( j ，一z ) r f ( x ) 0 ，v y s ( 2 1 5 ) 其中scr ”为非空闭凸集，f ：r ”_ r ”为连续映射 定义6厂称为变分不等式( 2 1 5 ) 的效益函数，如果厂的全局最小解集与( 2 1 5 ) 的 解集一致。 若厂为变分不等式的效益函数，则变分不等式问题可以等价地转化为如下的极小问 题： m i n 厂( x ) ( 2 1 6 ) s t x s 效益函数中的很重要一类即为所谓的g a p 撇，m a r e o t t e & d u s s a u l t 3 4 】使用如下的g a p 函数： g ( x ) = m a x ( f ( x ) ，x y ) l y s ( 2 1 7 ) 作为效益函数，将变分不等式问题转化为等价的极小问题。但是该函数g ( x ) 往往不可 微，而且需要s 为紧集以保证g ( x ) 有定义，这样就使得变分不等式中很重要的互补问题 被排除在外。 f u k u s h i m a 【5 1 将m a r c o t t e 的g a p 函数加以改进，提出了一类具有很好性质的函数， 正则化g a p 函数： g 口( x ) = m a x ( x j ，) rf ( x ) 一争一y l l 2 = ( f ( x ) ，z 一以( z ) ) 一割x - - 以( x ) 1 1 2 ( 2 1 8 ) 其中 玩( x ) = p r o j s ( x - - 口_ 1 ( x ) ) ，p ，畎( ) 为瓞”到s 上的投影算子。 大连理工大学硕+ 研究生学位论文 定义7非空闭凸集sc r ”中，点芳在x 上关于g 一范数的投影，记为p r o j s g ( x ) ，即满 足如下性质的点： i i x - - m o j s ，g ( x ) 1 1 g = m i n l l x z 0 giz s ( 2 1 9 ) 性质1 1 3 5 1 设scr ”为非空闭凸集，则有下式成立： i p r 。j s ，g ( x ) - p r o j 。，g o ， e l - 警x e s 盟竿- - 掣x o l l 幽i 。哺一 l 2 - j 利用f a t o u 引理我们可以得到下式： 一1 1 口一2 1 j di 熊 p 一肛 e 一 一类随机变分不等式的抽样平均近似方法 ，秽e 盟一h i 融m i n f 逝一 o 利用条件口忪i i o ( 3 7 ) 其中 咖一鬻盟竿掣i i 趔 8 ， m l _ i | “o 那么当o 口- 2 1 1 g i i qe 7 7 ( ，国) 时有 瞄l i mg ( x ) 2 佃 ( 3 9 ) 3 3 抽样平均近似方法的收敛性分析 在这一节里，我们研究抽样平均近似方法的收敛性及有关性质。令( - 0 1 国2 ，缈是 随机变量缈的独立同分布抽样。这样，我们得到( 3 3 ) 的抽样平均近似问题： i 脚n f g ( x ) ( 3 1 0 ) 大连理工人学硕士研究生学位论文 其中g ( x ) 定义如f ： 咖) = 磐卜) r 睫枷归卜y i i ：) 通过计算我们可以知道g ( z ) 与g ( x ) 的显式表达式如下： g ( x ) = ( x 一日( x ) ) 7 厂( x ) 一等怯一日( x ) 眨 g ( x ) = ( x 一峨( x ) ) 7 ( x ) 一等忙一峨( x ) 眩 其中 h ( x ) = 鸭，g ( x 一口q g - 1 厂( x ) ) 表示点x 一口- 1 g - 1 厂( x ) 到s 上的投影， s - s ( x ) = 钒 g ( x 一口_ g 。1 ( x ) ) 表示点x 一口。1 g 。1 ( x ) 到s 上的投影， ( x ) = e l f ( 毛w ) ，厶( x ) 2 专荟f ( 毛) 。 现在我们给出以后要用到的假设条件： ( a 1 ) 集合s 是非空紧的。 ( a 2 ) 对于每一个彩q ，函数，( ，f _ o ) 在集合s 上是连续的。 ( a 3 ) 函数f ( ，彩) 被一个可积函数控制，即存在一个可积函数矽( 缈) 使得 s u p 。0 f ( x ，缈) f | 矽( 国) 对于随机变量国几乎友e 友b 成立。 ( 3 1 ，1 ) ( 3 1 2 ) ( 3 1 4 ) ( 3 1 5 ) 从文献r u b i n s t e i n & s h a p i r o l 2 6 1 的第2 6 节我们可以得到下面的引理。 引理3 1 假设( a 1 ) 一( a 3 ) 成立，则有下面的结论成立： ( 1 ) 函数( x ) 处处取有限值且在集合s 上是连续的。 ( 2 ) 函数列 厶( x ) 在集合s 上依概率1 致收敛到函数厂( x ) ，即几乎处处有。 艘 噤慨( x ) 一( 圳= o ( 3 1 6 ) 成立。 定理3 1 假设( a 1 ) 一( a 3 ) 成立，则函数列 g ( x ) 在集合s 上依概率1 一致收敛到函数 g ( x ) 。 证明：根据函数g ( x ) 和g ( x ) 的定义，有 一类随机变分不等式的抽样平均近似方法 g ( x ) - g ( x ) i = x - h ( x ) ) ) 一弘一h ( 砒一( x 一风( x ) ) 7 1 ( x ) + - 手n x - ( 玑 卜日( x ) ) rm ) 一( x 一风( x ) ) r ( x ) i +争一巩( 巩一弘一日( 玑 = l ( x 一日( z ) ) r ( 厶( x ) 一厂( x ) ) 一( 风( x ) 一日( x ) ) 7 ( z ) | + 詈肛一风( x ) 眨一忙一日( x ) 旺 l l ( x - ( x ) ) i | | | 厶( x ) 一厂( x ) i l + 0 巩( x ) 一日( x ) | | j | 厶( x ) 0 + 詈i i | x 一巩( x ) 眨一忙一日( x ) 蛙 因此有： s x u l g ( x ) 一g ( x ) 怿罂黔一日( x ) ) 卅翟忱( x ) 一厂( x ) 卜s 删u p l l h n ( x ) 一日( 卅攀忱( x ) + h s u 加p 一巩( 巩一卜日( 堀l 因为函数g ( x ) 0 ，所以有 等忙一日( x ) 眨x - - 日( x ) ) 7 ( x ) _ 7 导忙一日( x ) i l g 0 厂( z ) 、 其中缸是矩阵g 的最小特征值，那么进一步可知， 由于集合s 是非空紧集，所以一定存在一个正常数m 使得 进一步，我们有 类似的我们可以得到 粤x ) l i m ，霉m x ) i i m 粤卜日( x ) i l 0 时几乎处处有 咧k 卜八力o 可哥一 s j 用( 3 1 7 ) 进一步可得 s 删u p i g ( x ) 一踟( z ) i _ f ( x ) ， ( 2 ) 存在一个收敛到z 的数列 使得l i ms u p 无( x n ) s ( x ) 。 那么我们说下半连续函数列 z 上图收敛( 印i c o 曲e r g e n c e ) 到下半连续函数厂。 定义3 3 ( 大数定律) 设磊，乞，是一列独立同分布的随机变量，且数学期望存在： e 【舌】- 口，i , 1 2 则对任意的s 0 ，有 熙尸峙和i 0 ，存在一个万 0 和丙 o 使得当n 一n 和 慨一x i i 万有 峨( h ) 一( h ) 0 s ， i i s ( x ) - s ( x ) 0 s 进一步，我们得到： l i m ( x ) - m ( x ) l l = l l f m ( x ) 一厂( h ) + ( h ) 一厂( 圳 大连理工大学硕+ 研究生学位论文 0 厶( h ) 一( h ) i j + i i 厂( h ) 一厂( x ) 0 2 s 这显然满足上图收敛( e p i c o n v e r g e n c e ) 的定义，因此函数列 厶 上图收敛到函数厂 又因为日( ) 和风( ) 是连续函数，所以如果取万= s 有 0 巩( x ) 一日( x ) l i = i l 嘲，g ( h 一口1 g 卅 ( h ) ) 一p r o j s ，gx n - a g1 厂( 洲 - l l ( x 一x - - o ：一g 1 ( 厶( h ) 一厂( x ) ) 0 - l l ( x - x ) i l + 口一f i g 。1 i | i i ( ( h ) 一厂( 训 ( 1 + 2 口。1i i g i i ) 占 进一步，我们知道 l i m 巩( h ) = 日( x ) 我们知道： g ( x ) = ( z 一胃( x ) ) r 厂( x ) 一鲁忙一日( x ) 眨 g ( x ) = ( x 一巩( x ) ) r 厶( x ) 一翻x 一风( x ) 略 从而我们可以得到： l i mg ( x ) = g ( x ) 这证明了函数列 g 几乎处处上图收敛( e p i c o n v e r g e n c e ) 到函数g 定理3 3 如果假设( a 2 ) 和( a 3 ) 成立，那么几乎处处有熙 堪g ( x ) = i n f g ( z ) 成 立。 证明：对于任意的正数占，令x 满足g ( x ) i n f g u ) ( 3 2 2 ) 川+ e 6h o 结合( 3 2 1 ) 和( 3 2 2 ) 可以知道， l i ml i 刷n f g ( x ) = 赠g v ( x ) 如果集合s 是紧集，根据定理3 3 ，立即可以得到下面的定理。 定理3 4 如果假设( a 1 ) - ( a 3 ) 成立，那么几乎处处有熙 嘹g ( x ) ；2 m 刷i n g ( x ) 。 定义3 4 3 2 1 假设集合 g 是r ”上的闭集合序列。集合序列 g ) 的外极限和内极限定义 分别如下： 居g = 印k ：g ，舻l i m x 。 ， ( 3 2 3 ) l i c = x ，j 吒) ：g ，x = l 鳃 3 2 4 ) 义a r g i n f g 表示优化问题( 3 1 0 ) 的极小点集合；a r g i n f g 表示优化问题( 3 3 ) 的极 小点集合。 定理3 5 如果假设( a 2 ) 与( a 3 ) 成立，则几乎处处有艮 a r g i n f g ca r g i n f g 成立。 证明：令x me a r g i n f g u ) ，s ) ，假设舰h = x e s ，下面我们证明 x a r g i n f g ( u ) ，甜s 根据上图收敛的定义，我们可以得到 l i m 。i 。n fg m ( x m ) g ( x ) 由( 3 2 1 ) 可知， 大连理工大学硕士研究生学位论文 1 1 黜p 戆 g ( ) 蝶g ( “) 综合这两个不等式，我们可以得到 g ( x ) i 瞄n f g ( u ) 因为z s ， 所以有x a r g i n f g ( u ) ，甜s 。 这就证明了几乎处处 l s a r g i n f g | ca r g i n f g 成立。 引理3 2 【8 1 令k 互r ”是非空闭凸集，f ：q3k 一瞅在开集q 上连续。令c 0 ，g 为 对称正定矩阵，则有下列式子成立： ( 1 ) v x q ，有此( x ) = p r o j ( x c g 。1 f ( x ) ) 。 ( 2 ) 包( x ) 在q 连续，在k 上非负。 ( 3 ) 包( x ) = o ，x k 当且仅当x s o l ( k ，f ) ( 4 ) 如果f 在q 上连续可微，则见( x ) 也连续可微，并且 v 包( 工) = f ( x ) + ( j f ( x ) - c g ) 7g 一 ( x ) ) 定理3 6 如果假设( a 2 ) 和( a 3 ) 成立且对于每个w q ，函数f ( x ，w ) 关于x 是强单 调的，即存在一个可积函数c ( w ) 且满足e ( c ( w ) ) 有限使得 ( z y ) 7 ( f ( x ，w ) 一f (