（运筹学与控制论专业论文）广义变分不等式的广义f投影算法.pdf

广义变分不等式的广义，一投影算法 运筹学与控制论 研究生李雪梅指导教师何诣然( 教授) 论文摘要：本文在希尔伯特空间中，利用广义，投影将s o l o d o v 提出的二次投 影算法以及w a n g 提出的外梯度算法推广到一类广义变分不等式；证明了当f 是连 续伪单调映射，是真凸下半连续可微函数时，这两种算法中产生的序列具有全局 收敛性；最后，证明了在广义户投影的二次投影算法中添加扰动后，其算法中产生 的序列具有全局收敛性 关键词：投影算法；外测度算法；广义产投影；伪单调；变分不等式；广义变分 不等式；收敛性；扰动 第i 页 g e n e r a l i z e df - p r o j e c t i o nf o rg e n e r a l i z e dv a r i a t i o n a l i n e q u a l i t y m a j o r ：o p e r a t i o n a lr e s e a r c ha n dc y b e r n e t i c s w r i t e r ：l ix u e m e i s u p e r v i s o r ：h ey i r a n a b s t r a c t ：i nt h i sp a p e r ，w ep r e s e n tam o d i f i c a t i o no fad o u b l ep r o j e c t i o n a l g o r i t h mp r o p o s e db ys o l o d o va n da ne x t r a g r a d i e n tm e t h o dp r o p o s e db yw a n g t of i n das o l u t i o no fac l a s so fg e n e r a l i z e dv a r i a t i o n a li n e q u a l i t i e si nh i l b e r ts p a c e t h em a i nm o d i f i c a t i o no ft h et w om e t h o d si st oc h a n gm e t r i cp r o j e c t i o ni n t og e n e r a l i z e df - p r o j e c t i o n ，f o rs o l v i n gt h eg e n e r a l i z e dv a r i a t i o n a li n e q u a l i t y g l o b a l c o n v e r g e n c eo ft h et w om e t h o d si sg u a r a n t e e dw h e nf i sp s u d o m o n o t o n ec o n t i n - u o u sm a p p i n ga n dfi sap r o p e r ，c o n v e x ，a n dl o w e rs e m i - c o n t i n u o u sf u n c t i o n m i nh i l b e r ts p a c e f i n a l l yw ea d da p e r t u r b a t i o ni ng e n e r a l i z e df - p r o j e c t i o na l g o - r i t h ma n dt h ep e r t u r b e dm e t h o di sa l s op r o v e dt ob eg l o b a l l yc o n v e r g e n tu n d e r v e r ym i l da s s u m p t i o n k e yw o r d s ：p r o j e c t i o nm e t h o d ；e x t r a g r a d i e n tm e t h o d ；g e n e r a l i z e d - p r o j e c t i o no p e r a t o r ；g e n e r a l i z e dv a r i a t i o n a li n e q u a l i t y ；p s e u d o m o n t o n e ；p e r - t u r b a t i o n ；c o n v e r g e n c e 四川师范大学学位论文独创性及 使用授权声明 本人声明：所呈交学位论文，是本人在导师衄主置然熬援指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何 其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。 本人承诺：已提交的学位论文电子版与论文纸本的内容一致。如因不符而 引起的学术声誉上的损失由本人自负。 本人同意所撰写学位论文的使用授权遵照学校的管理规定： 学校作为申请学位的条件之一，学位论文著作权拥有者须授权所在大学拥 有学位论文的部分使用权，即：1 ) 已获学位的研究生必须按学校规定提交印刷 版和电子版学位论文，可以将学位论文的全部或部分内容编入有关数据库供检 索；2 ) 为教学、科研和学术交流目的，学校可以将公开的学位论文或解密后的 学位论文作为资料在图书馆、资料室等场所或在有关网络上供阅读、浏览。 论文作者签名：专雪牌 2 0 0 9 年4 月 己i 吉 ji 口 希尔伯特和巴拿赫空间中的度量投影算子被广泛地应用于数学的很多领 域，如优化理论和逼近问题，控制论中的算法研究，非线性分析和随机模型，变 分不等式和相补问题，以及博弈论等等【1 8 】 经典的变分不等式问题v i ( f , k ) ，是要找到一个点矿k ，满足 ( f ( x ) ，z z + ) 0 ，v x k 其中k 是p 中的闭凸子集，f 是从p 到自身的映射，( ，) 表示p 中的 内积我们知道如果矿是变分不等式的解当且仅当矿= i i g ( 矿一f ( x ) ) ，其 中( ) 是到k 的度量投影度量投影的定义： i i k x 】：= 口r 9 m i n l l 可一x l l ：y k 】 其中k 是p 中的闭凸集，l i 0 是由内积诱导的范数因为经典变分不等式的解 与度量投影映射有这样密切的联系，所以用投影型算法来求变分不等式的近似 解成了很多学者研究的对象 这些问题最早是由s i b o n y 9 ，b a k u s i u s k j i 和p o l y a k 1 0 在二十世纪七十年代 研究的，现在已经被很多研究者广泛的发展 1 1 1 4 】这些方法的一般结构可以 用如下迭代方式来表示：z 七+ 1 = i i a k ( 矿一q 七d 奄) 其中q 知是与定义域k 有关 系的闭凸集，当前迭代点是矿，以是搜索方向，q 七是由一定规则限定的步长， i i n 。( ) 是到q 詹的度量投影在x i u 和z h a n g 1 5 有投影型算法的具体细节假 设由这样的迭代方式产生的序列为 矿) ，如果变分不等式至少有一个解矿，则 有l i r a 矿= 矿因此我们说这个投影方法产生的迭代序列具有收敛性，即该 序列收敛到解矿几乎所有的投影型算法都有这个性质，如外测度算法【1 6 】以及 它的改进算法【1 2 1 4 ，1 7 1 在【17 】中用同样的方法我们可以证明如果一种投影型 算法有收敛性，则算法中产生的序列的有界性与变分不等式的解的存在性是等 价的 由于只用一次投影来求解变分不等式常常需要比较强的假设条件，所以后 来s o l o d o v 和s v a i t e r 1 1 1 引入度量投影的二次投影算法，这种二次投影算法也在 很多文献中被研究【l8 】文 1 1 】中提供的算法是其中一种比较有效的方法它包 第1 页 引言 括两步首先限定了一个严格划分当前迭代点和解集的超平面，这个超平面的 定义需要一次a r m i j o 型线性搜索其次下一个迭代点是当前点在可行域与超平 面交集上的投影产生的，因为每次迭代需要两次投影，所以这种方法, q - 次投 影算法 a l b e r 1 首先在1 9 9 4 年将从希尔伯特空间中的广义投影算子推广到了一致 凸一致光滑的巴拿赫空间，并在【1 9 】中证明了在一致凸一致光滑的巴拿赫空间 中用近似投影算法求解非线性等式和变分不等式时产生的迭代序列是收敛 的近年来l i 【7 】又对广义投影算子的定义进行了推广定义7 r k ：b _ k ，其 中b 是自反的巴拿赫空间，b + 是它的对偶空间，k 是b 中的非空闭凸子集 l i 2 1 ，2 2 】研究了广义投影算子的性质，以及巴拿赫空间中如何用广义，投影来 求变分不等式问题解 本文研究的广义变分不等式问题，是要找到一个点矿k 满足 ( f ( x + ) ，y z ) + 厂( y ) 一f ( x ) 0 ，v y k ， 其中k 是p 中的闭凸子集，f 是从舻到自身的映射，是从k 到r u + o 。) 的函数，( ，) 表示p 中的内积w - u 和h u a n g 2 4 在巴拿赫空间中引入了一类新 的广，- 投影算子这推广了a l b e r 1 和l i 7 引入的广义投影算法他们证明了广 义，一投影算子的一些性质作为应用他们还证明了这类变分不等式在巴拿赫空 间中解的存在性定理进而他们又在【2 6 】中证明了广义，一投影算子是极大单调 的，并提出了用一个迭代方法来求这类广义变分不等式问题的近似解 由上面工作的激励，我们考虑将巴拿赫空间中定义的广义厂- 投影算子应用 到有限维的希尔伯特空间中来求广义变分不等式的解 本文第二章中，我们将s o l o d o v 和s v a i t e r 1 1 1 提出的二次投影算法利用广 义厂- 投影推广到广义变分不等式若用k 表示广义变分不等式的解集证明了 当k 4 0 ，并且f 满足对任意的y k ，矿k + 都有( f ( y ) ，y z ) 0 ，则这 种算法中产生的迭代序列具有全局收敛性 本文第三章中，我们将w a n g ，x i u ，和z h a n g 在 2 9 1 中提出的改进的外梯度算 法利用广义。厂一投影推广到广义变分不等式证明了这种算法产生的序列与初始 迭代点的距离越来越大，且距离有上界如果产生的迭代序列是发散的，则解集 为空集还证明了如果广义变分不等式的解集非空，且f 是连续伪单调映射， 第2 页毕业论文 引言 是真凸下半连续可微函数时，则这种方法所产生的迭代序列是全局收敛的 本文第四章中，由于投影算法常常不能精确求解，所以在广义变分不等式的 广义，一投影算法中添加了扰动这样我们在f 是连续伪单调且，是真凸下半连续 可微函数的条件下证明了算法中所产生的迭代序列具有全局收敛性 第3 页毕业论文 第一章预备知识 1 1常用符号 本文除了特别说明外，设b 是巴拿赫空间b 是它的对偶空间，日是希尔 伯特空间日是它的对偶空间，p 是有限维的希尔伯特空间，k 和q 都是p 中的非空闭凸子集，f 是从瞅到自身的映射，厂是从k 到ru + o o ) 的函数， “) 表示 中的内积 本文研究的广义变分不等式问题，是要找到一个元素矿k 满足 ( f ( x + ) ，y z ) + i ( y ) 一f ( x + ) 0 ，v k ，( 1 1 ) 其中k 是瞅中的闭凸子集，f 是从舻到自身的映射，是从k 到r u + o o 的函数，( ，) 表示p 中的内积 用k + 表示广义变分不等式的解集 用1 1 0 表示范数 1 2 常用定义和引理 定义1 2 1 设q 是p 中的闭凸子集，z 胀到q 上的投影定义为： l - l a x 】：= a r g m i n l l y z l i ：y q ) 由投影映射的定义我们有如下性质 引理1 2 1 设q 是r n 中的闭凸子集，q 【】是到q 的投影映射，则对任意 的z ，y 1 王n ，和z q ，有 ( 1 ) ( q i x 一z ，z 一q 【叫) o ； ( 2 ) ( q 【叫一r t q y l ，z y ) o ； ( 3 ) l i r i q x l n n y l l l l l z y l l ； ( 4 ) l i q m z l l 2 i z 一2 1 1 2 一l l q p 】一z i | 2 ； ( 5 ) i i y i n x 】一n q y 1 1 2 l i z 一引1 2 一l i n q x l z + y n q y 1 1 2 第4 页 第一章预备知识 定义1 2 2 函数f 是伪单调的，如果f 满足 ( f ( y ) ，z y ) 0 辛( f ( z ) ，z y ) 0vz ，y k ( 1 2 ) 定义1 2 3 设x 是线性空间，c 为x 中的凸子集，妒：c ru + ) 妒 称为凸泛函，如果对任意的z ，y g 和任何的【0 ，1 】有 妒( 亡z + ( 1 一t ) y ) 妒( z ) + ( 1 一t ) 妒 ) 定义1 2 4 设x 是一拓扑线性空间，妒：x _ ru + o 。) 是一真泛函妒称 为在x 上是下半连续的，如果对任一网 z a ) ，当x a z o 时，有 妒( 黝) l i r ai 1 1 f 妒( ) ，忱印x * n o o 引理1 2 2 设x 是巴拿赫空间，妒：x ru + o 。) 是一真凸泛函，则下列 结论等价 ( 1 ) v 是弱下半连续的； ( 2 ) 妒是下半连续的； ( 3 ) 妒是连续的； ( 4 ) 妒是局部利普希茨的； ( 5 ) 存在非空开凸集vcx ，使得s u p q v ( x ) y ) ，若果对任意 的z ，掣u ，极限 h m 崆剑二幽 t - - * 0 t 存在，则称b 是一个光滑的巴拿赫空间 引理1 2 3 【3 0 】一个巴拿赫空间b 是光滑( 严格凸) 的，当且仅当它的对偶空 间矽是严格凸( 光滑) 的 定义1 2 9 2 6 】如果b 是一个巴拿赫空间矿是它的对偶空间，k 是b 中 的一个非空闭凸子集对任意固定的常数p 0 ，令g ：b + k _ ru + o 。) 是一个有如下定义的函数 g ( 妒，z ) = 0 妒j j 2 2 ( 妒，z ) + 0 z i l 2 + 2 p f ( z ) ， 其中妒b ，z b ，而f ：k _ ru + o o ) 是一个真凸下半连续可微函数 注1 2 1 由g 和，的定义【2 4 】，可以得到下面的性质： ( 1 ) g ( 妒，z ) 是凸的，当z 固定时，a ( v ，z ) 关于妒是连续的； ( 2 ) g ( 妒，z ) 是凸的，当妒固定时，g ( 妒，z ) 关于z 是下半连续的； ( 3 ) ( i l 妒| i i i x l l ) 2 + 2 p f ( x ) g ( 妒，z ) ( i i 妒0 + i i x l l ) 2 + 2 p f ( x ) 定义1 2 1 0 设x 是一赋范线性空间，x 为其对偶空间映像j ：x _ 2 j x ：= 【，x + ：( ，z ) = i i x l l 2 = l i f i 2 ，z x ) ， 称为x 上的正规对偶映像 注1 2 2 由定义直接可得到下面的一些性质： ( 1 ) j 是奇映像，即了( 一z ) = 一，( z ) ； ( 2 ) j 是正齐次的，即对一切入 0 ，( 地) = 入j p ) ，和有界的； ( 3 ) 对偶映像可以等价地定义作凸泛函妒 ) = 洲z i l 2 的次微分； ( 4 ) 可以证明当x + 是严格凸的，对偶映像了是单值的 定义1 2 1 l 2 6 如果b 是一个巴拿赫空间b 是它的对偶空间，是b 中 的一个非空闭凸子集且7 r 乏：矽_ 2 k 满足 叮乏妒= 牡k ：g ( 垆，乱) = i n ，：f ，g ( 妒，耖) ) ，v 妒b ， 则丌乏叫做从b 到2 广义，一投影算子 第6 页毕业论文 第一章预备知识 引理1 2 4 【2 4 ，定理2 1 】如果b 是自反的巴拿赫空间b + 是它的对偶空间， k 是b 中的非空闭凸子集，则对任意的妒b 都有7 唼妒o 引理1 2 5 【2 4 ，定理2 2 】如果b 是自反的巴拿赫空间矽是它的对偶空间， k 是b 中的非空闭凸子集，则有下面的性质： ( 1 ) 对任意的妒b + ，7 乏妒是k 中的有界非空闭凸子集； ( 2 ) 7 吱妒是单调的，既对任意的妒1 ，妒2 b ，z 1 7 妒l 和z 2 7 丢妒2 有 ( z 1 一z 2 ，妒1 一妒2 ) o ； ( 3 ) 如果b 是光滑的，则对于任意的妒b ，z 7 r 之妒1 当且仅当对任意 的y k 2 ( 妒一，( z ) ，z y ) + s ( u ) 一，( z ) 0 ， 其中j 是矽到b 的正规对偶映射，其定义和相关性质可以见【2 4 】 引理1 2 6 【2 6 ，定理3 3 】如果f 是光滑的自反巴拿赫空间b 到其对偶空 间b + 的算子，b + 且p 0 则点矿kc b 是下面广义变分不等式的解 ( f ( x ) 一，y z ) + i ( u ) 一，( z ) 0 ，vy k ， 当且仅当矿满足矿砭( ，( 矿) 一p ( f ( x + ) 一) ) 引理1 2 7 【2 6 ，定理3 4 】如果b 是严格凸的自反巴拿赫空间b + 是它的对 偶空间，k 是b 的一个非空紧凸子集，且，：k _ ru + o o ) 是真凸下半连续 正同胚的，则砭：b _ k 是连续的 当巴拿赫空间退化到有限维的希尔伯特空间p 时，我们给出类似的定义 和结论 定义1 2 1 2 对任意固定的常数p 0 ，定义g ：p k _ ru + o 。) 是一 个有如下定义的函数 g ( 妒，x ) = l i 妒| 1 2 2 ( 妒，z ) + l i 圳1 2 + 2 p s ( z ) ， 其中妒p ，z l r ，：kc 融_ ru + ) 是一个真凸下半连续可微函数 显然在希尔伯特空间中有g ( 妒，z ) = 忪一z i l 2 + 2 p ，( z ) 第7 页毕业论文 第一章预备知识 定义1 2 1 3 如果h 是一个希尔伯特空间，h + 是它的对偶空间，k 是h 中 的一个非空闭凸子集则砭：h 一2 k 是广义厂投影算予，如果，丢满足 以妒= 钍k ：g ( 妒，u ) 甜i n k fg ( 妒，砒v 妒h + 因为希尔伯特空间是自反的空间，所以由引理1 2 4 容易得到下面的结果 引理1 2 8 如果日是希尔伯特空间，日是它的对偶空间，k 是日中的非空 闭凸子集，则对任意的妒h 都有7 丢妒o 引理1 2 9 设日是一个希尔伯特空间，日是它的对偶空间，k 是日中 的一个非空闭凸子集，砭：h + 一2 k 是广义，投影算子则对任意固定 的妒h ，孟7 吱妒当且仅当 ( z 一牙，牙一y ) + f ( y ) 一f ( x ) o ，vy k ； 证明参见文献 2 4 】 引理1 2 1 0 设日是一个希尔伯特空间，k 是口中的一个非空闭凸子集 则对于任意矿k ，孟= k 【叫有 g ( 孟，z ) c ( x ，z 4 ) 一l | z 一圣| j 2 证明 因为g ( 妒，z ) = 一z i | 2 - i - 2 p f ( x ) ，由投影映射i i k 】的引理1 2 1 中 的( 2 ) 可得 g ( z ，z ) 一g ( 孟，z ) = i f z z f 1 2 一f l 孟一z + 1 1 2 忪一刮 ( 1 4 ) 引理1 2 1 1 设f 是从舭到r n 的映射，k 是p 中的非空闭凸子集， 是k 到酞u 0 同时注意到对任意的i 都有k 假设 对某个i 无论k 取什么值( 2 2 ) 都不成立即 ( f ( z 一，y 后7 ( z ) ) + o s ( z 一，y 詹r ( z ) ) ，r ( z ) ) 0 证明 因为z = 一班r ( ) ，所以x 一z = y i r ( x ) 则有如下式子 h i ( x 。) = ( f ( z 。) ，矿一) + ，( 矿) 一，( 矿) ( f ( 矿) ，矿一矿) + ( a ，( ) ，矿一矿) ( 2 - 8 1 = ( f ( z 。) + o f ( z 。) ，依r ( 矿) ) 仡盯 ( 矿) 1 1 2 上面第一个不等式由次微分的定义得到，第二个不等式由( 2 5 ) 得到因 为琅，仃( 0 ，1 ) ，所以很显然如果r ( ) 0 ，则h ( x i ) 0 下面我们用f 的伪单调证明h i ( x + ) 0 因为矿s 且z k ，所以在1 1 中令y = z ，有 ( f ( x + ) ，矿一z + ) + f ( z 。) 一f ( x ) 0 又因为f 是伪单调的则 ( f ( z 。) ，一z ) + f ( z 。) 一，( z ) 0 即 ( f ( z ) ，z 一z ) + ，( z + ) 一f ( z ) 0 因此由玩( ) 的定义知h i ( x ) 0 第1 1 页 毕业论文 第二章广义变分不等式的二次广义产投影算法 引理2 1 3 如果，是开集u 内一阶连续可微函数则，在u 中是局部利普 希茨连续的特别地，如果s 是u 中的紧子集，则，在s 上是利普希茨连续的， 且利普希茨常数是l ：- - - m a x i l l ( z ) i i ：z s ) 证明因为，在开集u 内一阶连续可导，所以，在u 中局部有界即对 于任意e 0 存在6 0 使得 s ( b ( x o ；巧) ) cb ( ，( 。o ) ；e ) ，x o 矿 因为对于任意的z u 存在b ( z ；5 ) 使得 ，( 曰( z ；j ) ) c 日( o ；k ) 所以对任意的y ，名b ( z ；6 ) 有 ，( ) s ( z ) = ( ，( 荨) ，y z ) j | ，。( ) i i3 一z l l l i l ij y z i j ， 其中b ，z 1 引理2 1 4f 2 7 设k 是有限维空间r n 中的一个闭凸集，h ：r n ru + o o ，是有限维空间p 中实值函数，集合的定义如下 c ：- - z k ：h ( x ) so 】 如果c d 并且h 在k 上是局部利普希茨连续的，且对每个z k 利普希茨 常数是p ( z ) 0 则有 d i s t ( x ，c ) p ( z ) 一1 m a x h ( x ) ，0 ) vz k ，( 2 - 9 ) 其中d i s t ( x ，c ) 表示从z 到集合c 的距离 证明很显然如果z c 则2 9 成立现在假设z k 且z 岳c 因为c 是 闭凸集，所以存在y ( x ) c ，使得忙一训= d i s t ( x ，k ) 由h 的局部利普希茨性 得到 。 l h ( x ) 一九( ( z ) ) i 9 ( z ) l l z 一可( z ) l i = 口( z ) d b t ( z ，c ) 又因为z 隹c 且可( z ) ，我们有危( z ) 0 和九( 秒( z ) ) 0 则 ( z ) h ( z ) 危( y ( z ) ) = i ( z ) 一九( y ( z ) ) i 0 ( z ) d i s t ( x ，c ) 第1 2 页毕业论文 第二章广义变分不等式的二次广义产投影算法 2 2 算法的收敛性证明 定理2 2 1 设函数f ( x ) 是连续伪单调的，k 是r n 中的闭凸集，是从k 到ru + o 。】i 的真凸下半连续下有界的可微函数且对任意的z k 都 有，( z ) 0 假设广义变分不等式( 1 1 ) 的解集k + 非空则算法1 2 1 中产生的 序列 收敛到变分不等式( 1 1 ) 的解 证明引理2 1 1 已经证明了算法1 2 1 中的线性搜索是有意义的所以现在 我们来证明 ) 的收敛性因为+ 1 = 托陋刁所以由引理1 2 9 我们可以得到 g ( z + 1 ，z 4 ) v ( x ，z ) 一l i z + 1 一z 1 1 2 = v ( x ，z ) 一d i s t 2 ( z ，甄)( 2 1 0 ) 由不等式2 一l o 我们可知序列 i l z 件1 一矿1 1 2 】- 是不增的，所以它是一个收敛序列 因此f 】有界且 1 i md i s t ( x 。，垃) = 0 ( 2 1 1 ) 又因为f ( ) ，k ( ) 和砝( ) 是连续的，所以 f ( ) ) 是有界序列，即对任意的i 存在某个m 0 使得 l l f ( z 。) | l m ( 2 - 1 2 ) 下面我们证明函数也在集合k 上是局部利普希茨连续的，且对每个z k 利 普希茨常数是口( z ) 0 因为对任意的x k 存在x 的邻域u ( x ，6 ) ，使得对任意 的y u ( z ，6 ) 有 1 h i ( y ) 一九 ) 0 = i i ( f ( ) ，y z ) + ( y ) 一， ) i l i f ( ”i l u - = 1 1 + i i ( y ) 一m ) 1 1 ( 2 - 1 3 ) i l f ( z 。) 0 i l u z 0 + e ( x ) 0 2 1 一z 2 0 。 ( m + 口( z ) ) j | z 1 一z 2 | i 上面第一个不等式成立是由范数的三角不等式得到的，第二个不等式是由，的 局部利普希茨性得到的由此可以知道函数鬼在集合k 上是利普希茨连 续的，且对任意的z k ，其利普希茨常数是e ( x ) = m + 日 ) 所以由引 理2 1 4 和芒k ，我们得到对任意的i 有 d i s t ( x 。，甄) 口( z 。) 1 h i ( x 。) ( 2 - 1 4 ) 第1 3 页毕业论文 第二章广义变分不等式的二次广义产投影算法 再由2 - 1 4 和引理2 1 2 司得 d i s t ( x ，k ) o ( x ) - 1 ( ) p ( ) - 1 叩i a h r ( x ) 1 1 2 ；( 2 - 1 5 ) 所以由2 1 1 可知 1 i m 叩, l l r ( x 。) 1 1 2 = 0 ( 2 - 1 6 ) 如果l i m s u p 汕仇 0 ，则我们有l i m i n f i i i r ( x ) l l = 0 因为r ( x ) 是连续的 且 ) 是有界序列，则序列 ) 存在一个聚点孟使得r ) = 0 这表明孟是广 义变分不等式( 1 1 ) 的解用矿来替换孟，我们得到序列 i l 一列) 是不增的所 以收敛又因为叠是序列 ) 的一个聚点，则序列 l l x 一刮) 的存在子序列收 敛到零这表明整个序列 l l 一一刮) 收敛到零，则有l i 驰- - + o o x i = 牙 如果l i m i _ 仇= 0 令牙是序列 ) 的聚点，则存在序列 ) 的子序 列 幽) 收敛到亳由算法2 1 1 中仇的选择，我们知道 ( f ( x j 一( 仇。，y ) r ( z 巧) ) ，r ( z 巧) ) 仃| f r ( z 巧) f | 2 上面不等式两边取极限得 ( f ( y c ) ，r ( 孟) ) 盯07 ( 孟) 1 1 2 由因为盯( 0 ，1 ) 且 ( f ( 牙) ，r ( 牙) ) 0 r ( 牙) 1 1 2 所以我们有i i r ( 至) l i = 0 ，则牙是广义变分不等式( 1 1 ) 的解 第1 4 页毕业论文 第三章改进的广义，一投影外梯度算法 本章介绍在r 竹空间中，用改进的广义，- 投影求广义变分不等式近似解的二 次投影算法同样假设广义变分不等式( 1 一1 ) 的解集非空，即k 。0 且函数f 是连续伪单调的，即满足 ( f ( y ) ，z y ) 0 号( f ) ，2 一y ) 0 妇，y k ( 3 - 1 ) 由定理1 2 1 1 ，有矿k i t 是广义变分不等式( 1 一1 ) 的解当且仅当x + 砭防一f ( x + ) j ，其中砭：h _ k 是广义，一投影 3 1 算法 设7 吱是日4 到k 的广义户投影算子投影剩余的定义如下： ， ( z ) = z z ，z 7 吱陋一f ( z ) 】 显然，( z ) = 0 等价于z k 算法3 2 1 在集合k 中选定一个z o ，并且限定参数盯，7 ( 0 ，1 ) 令i = 0 步骤1 计算r ( ) ，如果r ( 一) = 0 则停止；否则到步骤2 步骤2 计算夕= 一 l i t ( x i ) ，其中依= ，y ，而是满足下面不等式的最小正 整数 ( f ( x i 一7 k r ( x ) ) + a ，( z 一7 k r ( x ) ) ，r ( z ) ) 仃i l r ( z ) 1 1 2 ( 3 - 2 ) 步骤3 计算x i + 1 = i 1 9 2 n 彤n k 【z o 】，其中 研= z r n ：( f ( z ) ，z z ) + ， ) 一s ( z ) o ) ；( 3 - 3 ) h 2 = z r n ：( z 一，z o 一) o ) 步骤4 让i = i + 1 然后回到步骤1 由引理2 1 1 ，步骤2 中的线性搜索是合理的设 h i ( x ) ：= ( f ( z ) ，z z ) + ，( z ) 一f ( z ) ， 第1 5 页 ( 3 - 4 ) ( 3 - 5 ) 第三章改进的广义产投影外梯度算法 其中= 一仇r ( ) 结合引理2 1 2 ，我们有如下定理 引理3 1 1 若广义变分不等式( 1 1 ) 的解集k + 非空，且函数f ：p _ 舯是 伪单调的，则对算法3 1 1 中产生的序列 ) 有 ( 1 ) h i ( x ) , l t o l l r ( x ) 1 1 2 且对任意矿k + 有鬼( 矿) o ； ( 2 ) 特别的如果r ( x ) 0 ，则( ) 0 ； ( 3 ) 对任意的i 有k + 研n k 证明 ( 1 ) ，( 2 ) 在引理2 1 2 中已经证明 ( 3 ) 因为对任意矿k + 都有鬼( 矿) 0 ，由研的定义知z 研，又 k + ck ，所以k + 研nk 引理3 1 2 【2 7 】设k 是有限维空间p 中的一个闭凸集，h ：p ru + o o ) 是有限维空间p 中实值函数，集合c 的定义如下 c ：= z k ：h ( x ) 0 ) 如果c d 并且h 在k 上是局部利普希茨连续的，且对任意的z k 其利普 希茨常数是e ( x ) 0 则有 d i s t ( x ，c ) 6 - 1 ( x ) m a x h ( x ) ，o ) vz k ， ( 3 - 6 ) 其中d i s t ( x ，c ) 表示从z 到集合c 的距离 如果广义变分不等式( 1 1 ) 的解集非空，则k 。研n 研nk ，并且研n 研nk d 引理3 1 3 如果k 是p 中的个非空闭凸子集，f 是k 上的连续伪单 调映射，且广义变分不等式( 1 d ) 的解集k + 非空则对任意的i ，都有k + h ：n h ；nk 证明由引理3 1 1 中的( 3 ) 知k 研nk ，所以只需证明对任意的i ， 有k + 砰在此我们用第一数学归纳法来证明 首先很显然有k 。瑶= 假设当i = k 时有k + 磁，即有k + 磁n 磁n k 第1 6 页毕业论文 第三章改进的广义，- 投影外梯度算法 则当i = k + 1 时，因为z 七+ 1 = 峨n 磁似【z o 】，且对任意的矿k + ，有矿 磁n 磁n k ，所以由投影映射的性质有 ( z + 一x k + lz o z 七+ 1 ) 0 则矿磙+ 1 ，即有k 磁+ lf 3 硌1nk 所以对任意的i ，都有k 研n 田n k 3 2 算法的收敛性证明 定理3 。2 1 设f 是k 上的连续伪单调映射，算法3 1 1 中产生的无穷序列 为 ) ，z = 一y i r ( x ) 若广义变分不等式1 1 的解集非空，则序列 有界， 且它所有的聚点都是解 证明首先我们假设1 1 的解集非空因为z 件1 = 研n 研n k ( 护) 由引 理3 1 3 和投影映射的定义，对任意的矿k + 有 l l z 件1 一x o i lsl | z + 一x 0 | | 所以序列 】是有界序列又因为z 件1 研，所以肼( z 件1 ) = x i + l ，由投影 映射的定义，对任意的 仁一z ，z o 一) 0z 研 则= r i h z ( z o ) ，由引理2 1 有 i l 砰( z 件1 ) 一1 - t h ( z o ) 1 1 2 i i x 件1 一x o i l 2 一i i n 肿, ( z 件1 ) 一z 件1 + z o 一孵( z o ) 1 1 2 因为z 件1 = 聊( + 1 ) ，= n n 2 ( z o ) ，所以 i i x 件1 一1 1 2 i l z 件1 一x 0 0 2 一i i x 一x 0 1 1 2 即 l i x 件1 一x 0 0 2 i i x 一x o i l 2 + i i z 件1 一x i i | 2 由此可知序列 l i 一x o l l 是不减有上界的序列，则收敛即 l i m 桫+ 1 一x i 0 2 = 0 因为z 件1 研，所以 i i x 一x i + 1 i | l i x 一脚( x i ) l i = d i s t ( x ，研) 第1 7 页毕业论文 第三章改进的广义，投影外梯度算法 则 1 i md i s t ( x 。，研) = 0 ( 3 - 7 ) 又因为f ( ) ，k ( ) 和7 丢( ) 是连续的，所以【f ( z ) ) 是有界序列，即对任意的i 存在某个m 0 使得 i i f ( z 。) l l m 下面我们证明函数在集合k 上是局部利普希茨连续的，且对每个z k 利 普希茨常数是p ( z ) 0 因为对任意的z k 存在x 的邻域u ( x ，6 ) ，使得对任意 的y u ( z ，5 ) 有 i h i ( y ) 一玩( z ) 0 = l i ( f ( z 。) ，y z ) + f ( y ) 一f ( x ) l f i i f ( z 。) l l 。i i 秒- z l l + h f ( y ) ，( z ) 1 1 ( 3 - 8 ) 冬i i f ( z 。) 0 i l u z i j + 口( z ) i i x l z 2 l i 、。 ( m + p ( z ) ) i i z , 一z 2 1 1 上面第一个不等式成立是由范数的三角不等式得到的，第二个不等式是由，的 局部利普希茨性得到的由此可以知道函数乜在集合k 上是利普希茨连 续的，且对任意的z k ，其利普希茨常数是p ( z ) = m + p ( z ) 所以由引 理2 1 4 和岳k ，我们得到对任意的i 有 d i s t ( x 。，托) 9 ( z 。) h i ( x i ) ( 3 - 9 ) 再由3 - 9 和引理2 1 2 可得 d i s t ( x i , k ) 一( z ) 一1 ( z ) 护( z ) 一1 ，7 i a i r ( x ) 1 1 2 ( 3 - 1 0 ) 所以由孓7 可知 1 i m 训r ( 矿) 1 1 2 = 0 ( 3 - 1 1 ) 如果l i r a s u p t 。仡 0 ，则我们有l i m i n f i l i r ( 一) l l = 0 因为r ( x ) 是连续 的且 ) 是有界序列，则序列 ) 存在一个聚点牙使得r ( 牙) = 0 这表明牙是 广义变分不等式( 1 1 ) 的解用矿来替换牙，我们得到序列圳一引l 】是不增的 所以收敛又因为牙是序列 ) 的一个聚点，则序列 | f 一牙i f ) 的存在子序列 收敛到零这表明整个序列 l l x 一引i ) 收敛到零，则有l i 驰。= 孟 如果l i n a 依= 0 令孟是序列 ) 的聚点，则存在序列 ) 的子序 第1 8 页 毕业论文 第三章改进的广义产投影外梯度算法 列 硝) 收敛到牙由算法3 1 1 中纭的选择，我们知道 ( f ( 1 一一( 矾，y ) r ( z q ) ) ，r ( z 巧) ) s 盯1 1 7 i ( z 巧) 0 2 上面不等式两边取极限得 ( f ( 牙) ，r ( 牙) ) a l l r ( z ) 1 1 2 由因为矿( 0 ，1 ) 且 ( f ( 孟) ，r ( 厉) ) 2l i r ( z ) 1 1 2 所以我们有i i r ( z ) i i = 0 ，则雪是广义变分不等式( 1 1 ) 的解 一 第1 9 页毕业论文 第四章广义厂一投影添加扰动后的二次投影算法 在本章中介绍p 空间中，由于投影算法常常不能精确求解，所以在广义 变分不等式的广义厂一投影算法中添加了扰动假设广义变分不等式的解集非空， 即k + 仍这样我们在f 是连续伪单调且，是真凸下半连续可微函数的条件下证 明了算法中所产生的迭代序列具有全局收敛性 由定理1 2 1 1 ，有x k 毋是广义变分不等式( 1 1 ) 的解当且仅当矿 7 r 【矿一f ( x + ) 】，其中7 r 乏：h + 一k 是广义，- 投影 4 1 算法 由于投影算法常常不能精确求解，所以我们在投影剩余中添加扰动让7 丢 表示到k 的广义，投影投影剩余的定义如下： r ( 7 x ) = z z ，z 砭p f ) 】) = z z ，z 丌七 z 一，【z ) j 贝0r ( x ) = 0 等价于z s 添加扰动后的定义 r i ( x ) ：= z z + 一，z 7 r 之k f ( z ) 】，罂。一 0 证明 因为矿s ，所以在1 1 中令y = 兹有 ( f ( x ) ，五一z + ) 4 - ，( 忍) 一f ( w + ) 0 由f ( ) 的伪单调性可得 ( f ( z d ，z i 一矿) + f ( z i ) 一f ( w ) 0 所以勉( 矿) 0 又因为对任