（运筹学与控制论专业论文）求解余强制变分不等式的投影收缩算法研究.pdf

s u p e r v i s e db yp r o f e s s o rc h e ng u o q i n g s c h o o lo fm a t h e m a t i c a ls c i e n c e s ， i n n e rm o n g o l i au n i v e r s i t y , h o h h o t ，0 1 0 0 2 1 m a y ，2 0 1 0 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有 权将学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和 磁盘，允许编入有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编 学位论文。为保护学院和导师的知识产权，作者在学期间取得的研究成果属于内蒙古大 学。作者今后使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间 导师的同意；若用于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：驻指导教师签名：二记召睦鸱 指导教师签名：z 伫：7 不等式问题，构造了一种下降方向，沿此方向取得更长的校正步长 给出基本校正步长与最优校正步长的关系，使得算法更易执行以 具有双层规划结构的实际经济均衡问题为例，进行了数值实验，结 果表明所提出算法的有效性 关键词：变分不等式，余强制映射，自适应规则，预测校正，投影收 缩，经济均衡 n e wd e s c e n td i r e c t i o ni sd e r i v e da l o n gw h i c hab e t t e rc o r r e c t i o ns t e ps i z ec a nb eo b - t a i n e d m e a n w h i l e ，i no r d e rt om a k et h em e t h o di m p l e m e n t a b l e ，t h er e l a t i o n s h i pb e t w e e n t h eb a s i ca n dt h eo p t i m a lc o r r e c t i o ns t e ps i z ei se s t a b l i s h e d a san u m e r i c a le x a m p l e ，a ne c o n o m i ce q u i l i b r i u mp r o b l e mw i t hb i - l e v e lp r o g r a m - r u i n gs t r u c t u r ew a sc a r r i e do u t ，t h en u m e r i c a lr e s u l ts h o wt h ea l g o r i t h mi se f f i c i e n t k e y w o r d s v a r i a t i o n a li n e q u a l i t y ，c o - c o e r c i v em a p p i n g ，s e l f - a d a p t i v er u l e ，p r e d - i c t i o na n dc o r r e c t i o n ，p r o j e c t i o na n dc o n t r a c t i o n ，e c o n o m i ce q u i l i b r i u m i i 录 第三章求解变分不等式的投影收缩类算法概述 3 1 投影收缩类算法起源 3 2 投影收缩类算法的基本框架 3 3 投影收缩类算法下降方向的构造方式 3 4 投影收缩类算法步长规则的构造方式 3 5 小结 第四章 4 1 4 2 4 3 4 4 参考文献 致谢 两种改进的求解余强制变分不等式的自适应投影收缩类算法 求解余强制变分不等式的改进算法 收敛性分析及进一步改进的算法 源于经济均衡问题之中的余强制变分不等式 数值实验 i l 2 6 7 7 加 n 埒 m 坞 毖 嚣 勰 盯 缸 s ； 砸 w 第一章引言弟一早，l 函 设qc 研为非空闭凸集，f ：q 彬为给定的连续向量函数有限维变分 不等式问题，记为w ( n ，f ) ，是指求t i + q ，使得： ( t 上一u 。) t f ( t 正) 0 ，v t 正q ( 1 0 1 ) 称集合nc 研为变分不等式的约束集具体应用中q 一般为闭凸集，实际中 许多情况下为凸多面体 1 1 1 3 1 当q = 殁时，( 1 0 1 ) 退化成为非线性互补问题，记为n c p ( f ) ，即求u 研 使得 让0 ，f ( u ) 0 ，u t f ( u ) = 0 当q = 研时，( 1 0 1 ) 便为求解f ( u ) = 0 的经典非线性方程组问题若nc 衍为 多面体，即： q = t 叠妒i 胤+ b 0 ，t o ， 其中a 为给定m n 矩阵，b 舻为给定t n 维向量，则称( q ，f ) 为线性约束变 分不等式( 1 i n e a r c o n s t r a i n e dv a r i a t i o n a li n e q u a l i t y ) 若nc 皿竹为多面体，f c u ) = m u + q 为仿射函数，其中m 为给定他n 矩阵( 不必对称) ，q 研为给定竹维向量，则 称( q ，f ) 为线性变分不等式( 1 i n e a rv a r i a t i o n a li n e q u a l i t y ) 若qc 研为如下箱形约束时， 【a ，b l ：= 皿矿i 啦嵋巩，i = 1 ，2 ，n ) ， 称( q ，f ) 为箱约束变分不等式( b o x c o n s t r a i n e d v a r i a t i o n a l i n e q u a l i t y ) ，记为b v i ( a ，b ，f ) ， 其中 - - o o a 玩+ o o ， = 1 ，2 ，n ， 若对某些指标i 有a = 一o o 或玩= + o o ，则上式中的相应不等号“”理解为严格 不等号“ o ) ，为一标量序列，t | 知q 若( 1 0 1 ) 中f 单调，则 子问题( 1 1 2 ) 中映射q 七f - t - i 强单调，进而比原问题易求解，许多求解强单调变 分不等式问题的算法可以用来求解该问题 如果邻近点算法中新的迭代点1 - k + 1 恰为变分不等式子问题( 1 1 2 ) 的解，则 称为精确邻近点算法精确形式的p p a 算法每一步要求解一个只是条件好一 些的同样规模的变分不等式，其意义主要在于理论分析而非实际具体算法 二十世纪七十年代，r o c k f e l l a r 提出了非精确邻近点算法1 1 】此算法中新的 迭代点u k + 1 只需要满足 + o o t | m 一仳m + | l 亿，f 亿 + c o ， - - j k = o 或者 时+ 1 一u k + l * i l 0 ，使得熙糊= 口，则称算法 所产生的迭代点列 u 七) 具有q 一线性收敛速度 ” 2 1 投影算子及其性质 定义2 1 1 【3 】设集合qc 研非空闭凸，对任意让研，称 d i s t ( “，q ) _ m i n ti l u 一口 7 ( 2 1 1 ) 内蒙古大学硕士学位论文 为点u 到凸集q 的距离函数，其中i l u 一秒0 = 再= 百严再二面 式( 2 1 1 ) 为严格凸规划，对给定的t l 研，其最优解存在唯一，称之为点 u 研到闭凸集q 上的e u c l i d 正交投影，记为 j 【铿】：= a r g m i n l l u v l 移q ) ，t 五护( 2 1 2 ) 称【】：形_ q 为e u c l i d 正交投影算子显然有d i s t ( u ，n ) = 0 u 一m i | 设g 为正定矩阵，则在g 一范数意义之下的投影可定义为 p a ，g - i ：= a r g m i n ( 1 l u v i l elu q 】，t 卫妒 显见，当g 为单位矩阵时，g 一范数意义之下的投影便为e u c l i d 正交投影 投影算子应用广泛且被系统研究【9 】对e u c l i d 正交投影，罗列如下基本性质对 一般g 一范数意义下的投影，可类似给出 引理2 1 1 【3 】1 9 】设集合qc 群非空闭凸，则 ( 1 ) 对任意t 研，有 面= p n m = 争面q ，( 口一面) t ( 云一t 上) 0 ，v v q ( 2 1 3 ) ( 2 ) 下述不等式成立 ( u 一 ) r ( 忍心1 一p n ) i i p n m 一岛f 】1 1 2 ，v u 皿妒，v v 眉矿( 2 1 4 ) ( 3 ) 投影算子忍【】非膨胀，从而全局l i p s c h i t z 连续，即 ，i l j 【u 】一j 【u 】l l l l u u 0 ，v u r n ，v v 匠n ( 2 1 5 ) ( 4 ) 下述不等式成立 l l 忍f 叫一训1 2 l l u v i i 2 0 t 一p - 1 1 2 ，v u 耐。，v v n ( 2 1 6 ) ( 5 ) 平方距离函数d i s t 2 ( u ，q ) 可微，且v d i s t 2 ( t ，n ) = 2 ( 乱一忍【t j ) 在后文将会看到，此引理之结论( 4 ) 在验证投影类算法的收敛性以及求取 步长方面起到重要作用 引理2 1 2 【9 】【2 5 】设p a l 】：研n 为e u c l i d 正交投影算子，则有 ( 1 ) 给定t l q 和d 掰，一p a i u q 圳关于o z 0 为单- i # l 递增函数； ( 2 ) 给定t i q 和d 皿n ，业二掣关于口 o 为单调递减函数 8 或 0m i n 【牡七，f c u 七) ) i | e ， 作为算法终止准则 现给出一重要不等式据引理2 1 1 ( 2 1 3 ) ，有 即 于是 ( t 上一o t f ( u ) 一p n u q f ( 仳) 】) 丁( 忍【u o l f ( u ) 】一牡) 20 ，v q o ，讹q ， e ( 钍，q ) t 【e ( t ，q ) 一a f ( u ) 】0 ， c a o ，v u q ， a e ( u ，q ) t f c u ) i i e ( u ，a ) 1 1 2 ，比 o ，v u q ( 2 1 8 ) 后文将会领略到，此不等式在构造下降方向有重要作用 由( 2 1 8 ) 易见，亦可将 e ( 乜) t f c u ) ， 作为算法终止条件 9 内蒙古大学硕士学位论文 引理2 1 3 s l l g 给定牡q 和d 聊定义函数 妒( a ) = i i p n u q d 】一u + q d l l 2 ，a 0 则妒7 ( a ) = 2 d 丁( p n i u q 司一t 上+ q d ) 因在投影类算法最优校正步长的求取以及超平面的构造所起关键作用之 故，文【8 】称1 ；f i ( q ) 为最优价值函数( o p t i m a lv a l u ef u n c t i o n ) 引理2 1 4 【8 】【9 】在前述引理之条件下，有 ( 1 ) 对o t 0 ，0 忍【t | 一q d 】一t i + qd i l 单调递增； ( 2 ) 对o l 0 ， ( 3 ) 对q 0 ， ( 4 ) 对o l 0 ， ! l 鱼巴二竺翊二竺竺剑单调递增； q d t ( u 一忍 t t q 司) 单调递增； 篓生二鱼堕二竺望2 单调递减 t ：l t 2 2 变分不等式的等价形式 本节给出变分不等式v i ( n ，f ) 的等价形式及相关概念 引理2 2 1 【3 】若qc 研非空闭凸，则t i + 为变分不等式v i ( n ，f ) 之解，当且 仅当 t = 阻+ 一a f ( u + ) 】，v q 0 ( 2 2 1 ) 特别地，t + 一忍【札+ 一a f ( u ) 】- 0 易知，在g 一范数意义之下，有如下结论： 引理2 2 2m 若qc 研非空闭凸，g 研为正定矩阵，则矿为变分不等 式( q ，f ) 之解，当且仅当 t l = p n ，g 【t l + 一q g 一1 f ( t l + ) 1 ，v q 0 ( 2 2 2 ) 此引理表明，当约束集q 为非空闭凸集时，变分不等式( q ，f ) 可等价转 化为不动点问题( f i x e dp o i n tp r o b l e m ) ：“= r 【t i q f ( u ) l ，比 0 当q 0 充分小 时，可保证忍【j q f 】是个压缩算子，据此可建立求解( q ，f ) 的投影迭代法： t 七+ 1 = 只l 【“七一o l k f ( u 七) l ，( 2 2 3 ) 其中，q 七 0 以适当方式确定 3 1 利用标度投影残量，引理2 2 1 可表述为如下： 1 0 内蒙古大学硕士学位论文 引理2 2 31 2 0 1 2 5 】若qc 彬非空闭凸，则t 。q 为变分不等式w ( n ，f ) 之解， 当且仅当 r ( i t ，a ) = 0 ，v a 0 ( 2 2 4 ) 易见，解变分不等式v i ( a ，f ) 等价于求解非线性投影方程u r 【t 一q f ( t 1 ) 】= 0 特别地，当f ( t 1 ) = m u + q ，m 为半正定矩阵时，易知f ( u ) 为单调函数，此时变 分不等式问题w ( n ，f ) 等价转化为线性投影方程u p n 阻一( m u + q ) 】= 0 h e 在文 【3 7 】对此进行了深入的研究 2 3变分不等式问题之解的存在唯一性 定义2 3 1 1 1 3 1 向量函数f ：qc 研- 册称为 ( 1 ) 在集合q 上单调( m o n o t o n e ) ，若 【f ( u ) 一f ( u ) 1 丁( u t ，) 0 ，v u ，u f ； ( 2 ) 在集合q 上伪单调( p s e u d om o n o t o n e ) ，若 f ( u ) r ( t i t ，) 20 令f ( u ) t ( t 一u ) 0 ，v u ，u f t ； ( 3 ) 在集合q 上严格单调( s t r i c t l ym o n o t o n e ) ，若 【f ( u ) 一f ( u ) 】t ( 乱一t ，) 0 ，v u ，口q ，t l t ，； ( 4 ) 在集合q 上强单调( s t r o n g l ym o n o t o n e ) ，若存在p 0 使得 【f ( j l i ) 一f ( t j ) 】t ( i t 一影) p l i t 正一t ，0 2 ，v u ，勘q ； ( 5 ) 在集合q 上余强制( c o - c o e r c i v e ) ，若存在c 0 使得 【f ( t 1 ) 一f ( ) 】r ( t 一”) t i l e ( ? 2 ) 一f ( v ) 1 1 2 ，v u ，t ，q ； ( 6 ) 在集合q 上是l i p s c h i t z 连续的，若存在l 0 使得 i i f ( ? 2 ) 一f ( v ) l i l l l ? 2 一t ，i | v u ，口q 由上述引理可知，余强制蕴含单调和l i p s c h i t z 连续，但不一定是严格单调 或强单调的，而强单调和l i p s c h i t z 连续函数必然是余强制的因此，余强制是 处于一般单调和强单调之间的一个中间概念 变分不等式( q ，f ) 解存在性的最基本结果要求qc 研有界闭凸，且函数 f ：q _ 皿“连续这一基本结果可以用b r o u w e r 不动点定理于t = p n i i t f ( u ) 】而 得到 1 1 内蒙古大学硕士学位论文 引理2 3 1 【3 】( b r o u w e r 不动点定理) 若5 2c 彬非空有界闭凸，t ：q q 连 续，则t 有不动点：t t = t ( u ) 定理2 3 1 【3 】设qc 衍非空有界闭凸，f ：q - 形连续，则( q ，f ) 有解， 且解集为有界闭集 当约束集q 无界( 如n c p ( f ) 情形) ，对( q ，f ) 须引入某种强制性条件 ( c o e r c i v e n e s sc o n d i t i o n ) 以建立w ( 5 2 ，f ) 解的存在性如 强制性条件1 3 若存在非空有界开集dcq 及护qnd 使得 ( 护一t ) t f ( u ) 0 为一常数，l o ，1 ) 是一给定的整数， 凤) 是正的参 数序列，并且i l l f 凤】i = 鼬n n 如果某一算法产生的迭代序列 铲) 满足 l i “七+ 1 一u + 1 1 2 i i u 七一t 正4 1 1 2 一c o l l e ( u k + , 凤) 1 1 2 ，讹+ q + ，( 2 4 1 ) 则 u 七) 收敛于( n ，f ) 的一个解 证明令牡是v i ( n ，f ) 的一个解由( 2 4 1 ) ，可得 + c o l l e ( u k + z , 凤) 0 2 i l u o 一矿i | 2 ， k = o 于是 1 i me ( u 七，凤) = 0 又凤触n ，据引理2 1 2 有 1 i r ae ( u 七，卢矗i 。) = 0 据( 2 4 1 ) 又可得到序列 u 七 是有界的，因此其至少有一聚点设u 为序列 铲 的一个聚点，则存在一子序列 u b ) 收敛于u 又因e ( 缸，风i n ) 关于札是连续的， 子序列取极限可得 e ( t i ，p i n i 。) = j i me ( u 向，卢i n i n ) = 0 因此，t 是( q ，f ) 的一个解 下面，证明序列 u 七】有唯一的聚点假设面是序列 u 七】的另一聚点，且记 6 ：= 忙一t t + 0 0 因为u 是【u 七) 的聚点，则存在b 0 ，有 o u 幻一t + l i 昙 另一方面，由于t l q ，因此 i l u 七一t + 0 0 札b u i i v k k o 从而有 o u 七一面i i 1 1 豇- u * l l l l u 知一札+ l l 妻，v k 这与假设相矛盾，于是序列 u 七) 收敛于t t + q + 证毕 1 3 此算法与基本投影法的显著不同之处是，在每一次迭代中，函数f 进行了两 次估值，需要进行两次投影运算 借用计算数学之术语，此算法亦可称为基于邻近点算法的一种预测校正算 法( p r e d i c t i o n - c o r r e c t i o na l g o r i t h m ) ：可将豇南看作预测步，u k + l 看做校正步在f 伪 单调且以常数ll i p s c h i t z 连续，0 q 之条件下，由此外梯度法产生的点列 【缸詹) 收敛到变分不等式问题( q ，f ) 之解，详见文【1 1 1 3 1 显见，为保证收敛，此 算法仍需估计f 的l i p s c h i t z 系数即使f 为仿射函数，估计f 的l i p s c h i t z 系数也 极其困难，此外，l i p s c h i t z 连续的假设条件依然太强，限制了此算法的应用 为克服算法的收敛性需要估计参数的缺点，在1 9 8 7 年，k h o b o t o v 将外梯度 法进行了推广【2 3 】【2 5 】，首次提出可依照某种适当方式动态选取步长q ，称k k m 算 法( k o r p e l e v i c h - k h o b o t o vm e t h o d ) 1 9 9 5 年，s u n 等学者提出外梯度法可与a r m i j o 类一维线性搜索技术求取步 长相结合【2 0 l 2 5 】，此种求取步长的方式亦称为自适应规则( s e l f - a d a p t i v er u l e ) ，但预 测与校正步长取为相同为了改进算法的数值计算效率，s u n 在文【2 0 1 1 2 1 1 中提 出了新的步长规则，显著的改进是利用a r m i j o 类一维线性搜索技术求取预测 步长，校正步之中沿着未知距离函数翔仳一让0 2 之下降方向并结合投影算子的 性质求取校正步长 对于上述所提及的k k m 算法，何炳生在文【2 3 1 中指出，此算法所产生的步 1 4 内蒙古大学硕士学位论文 长参数序列 仇 为单调递减，将导致算法收敛缓慢，故而针对 凤) 进行了改 进在f 单调的情形之下，文【2 3 】采用外梯度方向作为未知距离函数如t t u + 0 2 1 z 的下降方向，且采用新的最优校正步长，并论证得出校正步长大于妻作者在 文f 1 5 】中指出，k o r p e l e v i c h - k h o b o t o v 之外梯度方法，改用文【2 3 1 所提出的最优步 长以后，对实际宏观调控问题的算例，收敛速度提高7 倍以上同时指出，在 求解实际问题的只用函数值的算法中，当函数值的获取代价较高时，采用文 1 2 3 1 的算法，可节约8 0 的工作量 在校正步仍采用外梯度方向一f ( p t 2 u k - - a k f ( u 七) 】) 作为未知距离函数- ：t l u 一札0 2 下降方向的情况下，修乃华 8 1 1 9 1 1 z s 等给出一种新的预测步长规则，允许预测步 长q 奄非常大，甚至 q 南) 可能无界，取消了有界性的限制，为一广义a r m i j o 线 性搜索规则此规则较之其它，有实质性区别，有利于算法的快速收敛在文 f 8 】f 9 】中，对其合理性详加论证由此可见，步长选择策略在投影类算法中起到 了关键的作用，文【9 1 给出了关于外梯度法步长规则的综述报告 值得注意的是，一般情况之下，投影算子的计算代价是很大的，因其相当 于需要解决一个最优化问题此时，设计算法的一个重要任务就是在每次迭代 时减少投影运算的次数，而目前已知的改进的外梯度算法，在利用a r m i j o 类一 维线性搜索确定预测步长时，大都需要一次额外的投影运算为此，s o l o d o v 和 s v a i t e r 在文【1 3 】中提出一种新的算法，其主要思想是通过修正投影区域达到减 少投影运算的目的，具体做法为：在当前迭代点u 知，计算出投影点e n u k f ( u k ) 1 后，用一个简单的a r m i j o 类线搜索在连接两点让七与局【u 七一f ( u k ) 1 的线段上确定 一个点，使超平面 月k ：= u 五妒l ( 牡一z k ) t f ( z 知) = 0 将u 知与v i ( n ，f ) 之解集严格分离一旦超平面构造完毕，将u 七投影到可行域n 与半平面 月i ：= t 皿ni ( u z k ) r f ( z 七) 0 ) 的交集之上，得到迭代点小“文【1 3 】中通过几何直观和严格论证，表明u 七+ 1 较t t 更接近于v i ( n ，f ) 之解集此文之算法，在每一次迭代中，进行一次到 可行域的投影( 为构造超平面) ，又进行一次到qn 仇的投影运算，以给出下一 迭代点u 知+ 1 因此，文【2 5 】称其为双投影算法( d o u b l e - p r o j e c t i o na l g o r i t h m ) 关于 此类算法，还可参阅【7 】【1 0 】f 1 2 】值得注意的是，s o l o d o v 和s v a i t e r 在文【1 3 】中进一 步指出，文【1 3 】所构造的算法与i u s e m 和s v a i t e r 所提出的平面投影法( h y p e r p l a n e p r o j e c t i o nm e t h o d ) 有很大的区别，较之后者有较好的效率在文【10 】中，在f 伪 】5 下 给出了一种投 ( 3 0 2 ) ( 3 0 3 ) ( 3 0 4 ) ( 3 0 5 ) 法优于外梯度 射f 通常没有 估计或观察得 出在此情形之下，若变分不等式问题w ( a ，f ) 之中的映射f 为余强制的，那 么自然的想法是利用g o l d s t e i n ，l e v i t i n 和p o l y a k 所提出的基本投影法( t h eb a s i c p r o j e c t i o nm e t h o d ) ，即有迭代格式： t 七+ 1 = ，h 【t 七一a k f ( u 詹) 1 由专著1 可知，步长序列_ a 七) 满足 ( 3 0 6 ) 0 o i l i n f a k s u p ( q k o l u 0 ， 的零点因此，基本投影法之迭代格式( 3 0 6 ) 亦可表述为 t 七+ 1 = u 七一e ( u 知，o c k ) ( 3 0 8 ) 】6 内蒙古大学硕士学位论文 引理3 0 11 1 1 4 5 1 6 1 2 r 设t i + q + 为变分不等式( q ，f ) 的一个解点，则对任 意t 皿竹，有 ( u u 。) 丁e ( u ，口) ( 1 一勃e ( 邺) 1 1 2 ( 3 0 9 ) 由此结论可知，当0 0 ，( 3 0 1 3 ) 内蒙古大学硕士学位论文 j 萨= p a 扩卅“扩溉) 】，( 3 o 1 4 ) iu 1 = p a u 七一- r ( o ：e ( u h , 凤) + ( 铲一铲) ) 1 ， 、。 2 ( 1 一甓) i | e ( u 七，凤) 0 2 i i - 七一豇七1 1 2 一( t 七( p q l ) - - o u 七一氲知| 1 2 ) e ( t 知，卢七) t ( t l 七一面七) 凳三葛孳翌蕉鬈酽而旷一， 小南胁，= 熊瑞筹窨酱枯等精萨幽 p ( u k ，o l k ，- - - - r a i n ( 1 一丽高篱蛊晦两) ，( 3 0 1 7 ， 内蒙古大学硕士学位论文 文【5 1 5 亦论证得出， e ( u 知，q 膏) t g ( u 七，口括) 、1 似u 七，q 七) 0 2 + 2 e ( u ，a 南) ? g ( u 七，a k ) 二4 即步长p ( u 七，q 七) 有正下界文【5 】构造性地求取步长p ( u 七，q 七) ，是借鉴了h e 在文 【2 3 】中求取步长的方式 显见，文【4 】【5 】【2 7 】【3 2 】所提之算法需预先已知函数f 的余强制模c ，或者对c 进行一种粗略的估计h e 在文【6 】中亦指出，在实际应用中，余强制性归因于 现实问题之特性，即使f 为仿射函数，亦极难估计其余强制模c ，而保守的估 计又会致使算法收敛极其缓慢因此文【4 】f 5 】【2 7 】所提之算法虽有理论价值，然 而在应用中不可行鉴于此，h e 等在文1 6 】6 中依旧采用基本投影法( 3 0 6 ) ，求解 余强制变分不等式( q ，f ) 其算法如下 算法3 0 1 8 1 自适应投影算法 初始步眺给定 0 ，p ( 0 ，1 ) ，6 ( 0 ，2 ) ，a 0 0 ，仳1 q 置k = 1 迭代步s 1 ：对给定的铲和q 七一l ，若l i e ( “七) i l ，停止，输出u k ；否则，求出 最小非负整数m 南( 始于m 知= o ) ，q 奄= p m - q 七一1 ，并计算 t 知+ 1 = 【t 一a k f ( u 七) 】，( 3 0 1 9 ) 使其满足 叠尝豁掣裂弘五( 3 0 2 0 f ( u k 1 ) ( t 上七一“七+ 1 ) 丁( f ( t 正七) 一+ ) ) 二 7 令a 知+ 1 = o t 七；置k = k + 1 ；转s 1 显见，此算法无需预先已知或对余强制模c 进行估计h e 等在文【6 】6 中指 出，此算法所产生的序列 a 知) 单调非增且有正下界，同时序列 l l e ( u 七，q 七) 1 1 ) 单 调递减最后，文【6 1 6 通过较为复杂的间接方式论证得出此算法的全局收敛性 3 1 投影收缩类算法起源 目前，求解变分不等式的投影类算法，都可以看做从邻近点算法，亦称 p p a 算法( p r o x i m a lp o i n ta l g o r i t h m ) 和d o u g l a s - r a c h f o r d 算子分割法( o p e r a t o rs p l i t t i n g m e t h o d ) 演化而来如下首先简要介绍邻近点算法 熟知，变分不等式问题v i ( q ，f ) 的另一等价形式为如下的多值方程： 0 t ( 乱) = ：f ( t t ) + n n ( t ) ，( 3 1 1 ) 其中，( ) 为约束集q 的法锥算子，即： ( u ) ： 掣沪t w 0 对此问题，经典的求解方法为邻近点算法( p r o x i m a lp o i n ta l g o r i t h m ) ：给定初始点 u 0 q ，据如下迭代格式解出u k + l ： 0 ( t 正知+ l t 奄) + a k t ( u 知+ 1 ) ， 其中， q 七) c 【q i n i n ，o o ) ，q i l l i n 0 ，为一标量序列可得等价形式 一【( t 正七+ 1 一t 知) + o t k f ( u k + 1 ) 1 n n ( u 七+ 1 ) 换言之，对给定的u 七q ，新的迭代点t 七+ 1 通过解不等式 t q ，( 一t 1 ) t 【 一t 上七) + q 奄f ( t i ) 】0 ，v u q ，( 3 1 3 ) 而得结合前述知识，易得t 七+ 1 为投影方程 t i = 忍 t t 一【( t l 一矿) + a 七f ( h ) 】) ， 之解于是 t 七+ 1 = 【u 知一a k f ( u 七+ 1 ) 】( 3 1 4 ) 由于u k + l 出现在方程( 3 1 4 ) 的两边，因此称其为隐式算法( i m p l i c i tm e t h o d ) 注意到，u 七+ 1 为变分不等式问题( 3 1 3 ) 之解较原变分不等式问题( 1 0 1 ) 而言， 变分不等式问题( 3 1 3 ) 为一好条件问题( w e l lc o n d i t i o n e dp r o b l e m ) 在函数f 单调 和解集q 非空之条件下，易证此法之全局线性收敛性，详见文1 2 3 特别地，对线性变分不等式，方程( 3 1 4 ) 可考虑通过矩阵分裂算法( m a t r i x s p l i t t i n ga l g o r i t h m ) 解缺【2 5 1 显见，邻近点算法通过序列求解( 可放宽为不精确求解) 条件较好的同类子 问题而得原变分不等式之解精确形式的p p a 算法每一步要求解一个只是条 件好一些的同样规模的变分不等式，且方法只具线性收敛性，因此不便直接 运用于实际计算1 2 5 1 类似于常微分方程，可考虑利用预测校正法( p r e d i c t i o na n d c o r r e c t i o nm e t h o d ) ：将经典邻近点算法中子问题求解的不精确准则放松到极致， 得到的点称预测点，新的迭代点只利用预测点的函数值并通过投影易校正得 到具体做法为：首先利用g o l d s t e i n - l e v i t i n p o l y a k 方法做一预测： ( p ) 铲= p n 【t | 七一c l k f ( u 七) 1 ， 2 0 得： 易得所产生的序列 u 七) 满足： 0 u 知+ 1 一t + 1 1 2si l u 知一t i + 2 一( 1 一v 2 ) 0 e ( t 七，卢k ) 1 1 2 c 3 1 5 ) 根据前述收敛定理，易得此算法收敛于原变分不等式之解，详见文【2 3 】 如下简要介绍d o u g l a s - r a c h f o r d 算子分割法 因变分不等式问题( q ，f ) 等价于( 3 1 1 ) 所表示的多值方程，利用d o u g l a s - r a c h f o r d 算子分割法求解此多值方程的迭代格式为： t 销= ( j + f l f ) 一1 ( j + 卢盹) 一1 【j p f l + 卢f u k ( 3 1 6 ) 由于( ) 为约束集q 的法锥算子，则( j + 9 n n ) 一1 即为研到q 的投影算子，从 而( 3 1 6 ) 可表示为： t 七+ 1 = p n p z k f ( u 南) 】+ 凤( f ( u 七) 一f ( u 知+ 1 ) ) ( 3 1 7 ) 易见，u 七+ 1 出现在方程( 3 1 7 ) 的两边，借用数值分析的术语，可称其为隐式算 法同样可用g o l d s t e i n - l e v i t i n - p o l y a k 方法做一预测： ( p ) 矿= 昂f t 七一凤f ( u 七) 】， 后用d o u g l a s - r a c h f o r d 算子分割法做一校正： ( c ) t 工七+ 1 = 五七十凤( f ( t 七) 一f ( a 岛) ) 因铲= t 一e ( u 七，熊) ，则校正步可表示为： ( c ) t i 七+ 1 = t 知一【e ( u 奄，p 七) 一凤( f ( 札詹) 一f ( f i 知) ) 】 在适当的步长规则之下，可证此算法所产生的迭代序列 扩) 收敛于原变分不 等式问题之解 2 1 内蒙古大学硕士学位论文 3 2 投影收缩类算法的基本框架 投影收缩算法之基本思想是根据变分不等式的性质，构造一个方向一d ( u ) ， 使其对一切u q 都有 ( t 一u + ) t d ( u ) 妒( ) 6 8 e ( “) 1 1 2 ，( 3 2 1 ) 其中j 0 为常数尽管解点牡+ 是所求的，( 3 2 1 ) 表明一d ( t ) 为未知距离函数 三i l u - u * 1 1 2 的一个下降方向 如果( 3 2 i ) 式仅对u q 成立，为了保证新的迭代点在约束集q 内，同时考 虑到投影是在欧式范数意义下进行，则采用迭代公式 t i 七+ 1 = 忍p a k d ( u 七) 】，( 3 2 2 ) 其中o t 七为步长， q 知= 蒜 ( 3 2 3 ) 毗2 薪。 。 值得注意的是，何炳生在文【1 6 】中指出，可据d ( u ) 构造一“更好”的方向 一d b ( u ) ，即满足 d ) = d b ( u ) + d n ( u ) ，d b ( u ) 上d ( t ) ， 且有 ( t 一1 l ) t d b ( u ) ( t 一仳) t d ( t ) ， 即沿方向一d b ( u ) 的下降量会更大 ( 3 2 1 ) 式所产生的迭代序列 u 南) cq ，经简单计算，可知 u 七) 满足 i i t 七+ 1 一t 41 1 2 i l u 七一t 1 1 2 一o t k 妒( u 七) ( 3 2 4 ) 如果( 3 2 1 ) 式对一切t 研都成立，则可选取适当的对称正定矩阵g ，取 方向 - g ( u ) = - g _ 1 d ( t i ) ，( 3 2 5 ) 以步长 小) = 赫， ( 3 2 6 ) 的迭代公式 “1 = t 七一p ( t 七) 9 ( u 七) ，( 3 2 7 ) 产生的序列 铲) 不一定在f l 内，却满足 i l u 七+ 1 一t + | l 苔0 u 七一乱i i 刍一p ( u 七) 妒( t 七) ( 3 2 8 ) 内蒙古大学硕士学位论文 换言之，如果( 3 2