（运筹学与控制论专业论文）求解单调变分不等式问题的一类效益函数方法.pdf

大连理工大学硕士学位论文 摘要 本文提出了一个求解结构型单调变分不等式的效益函数方法，并用数值实验验证了 该方法的有效性 1 自从二十世纪六十年代产生以来，有限维变分不等式的理论和算法得到了迅速 的发展，变分不等式与互补问题是应用数学中的一个十分重要的研究领域，它不仅在非 线性最优化中具有广泛的应用，而且在微分方程、力学、控制论、对策论、经济平衡理 论、社会和经济模型等许多方面都有重要应用因此，变分不等式问题的研究和应用已 经成为了数学的一个热点课题 2 本文第3 章对结构型单调变分不等式进行了研究，构造了一个解这类问题的效 益函数模型，将问题转化为一个最优化问题该问题结构比较简单，易于计算最后， 分析了其全局最优性条件 3 本文第4 章介绍了解变分不等式问题的一些算法，并分别以球约束和箱式约束 为例，运用第3 章所介绍的效益函数方法，对问题进行了求解数值结果表明，此方法 是有效的 关键词：变分不等式；效益函数；投影；最优性条件 求解一类单调变分不等式问题的效益函数方法 m e r i tf u n c t i o nm e t h o df o rs t r u c t u r e dm o n o t o n ev a r i a t i o n a l i n e q u a l i t i e s a b s t r a c t t h i sp a p e rp r e s e n t sam e r i tf u n c t i o nm e t h o df o rs t r u c t u r e dm o n o t o n ev a r i a t i o n a l i n e q u a l i t i e s n u m e r i c a lr e s d t si l l u s t r a t e st h ee f f i c i e n c yo f t h i sm e t h o d 1 s i n c e19 6 0 s ，t h et h e o r ya n da l g o r i t h m sf o rf i n i t e d i m e n s i o n a lv a r i a t i o n a l i n e q u a l i t i e sd e v e l o p e dr a p i d l y v a r i a t i o n a li n e q u a l i t i e sa n dc o m p l e m e n t a r i t y 2 3 p r o b l e m sh a v e b e e nd e v e l o p e da ni m p o r t a n tf i e l di na p p l i e dm a t h e m a t i c s t h e y h a v eb e e nw i d e l yu s e dn o to n l yi nn o n l i n e a rp r o g r a m m i n gb u ti nd i f f e r e n t i a l e q u a t i o n ，m e c h a n i c s ，c y b e m e t i c s ，g a m et h e o r y ，e c o n o m i ce q u i l i b r i u mt h e o r y ，s o c i a l a n de c o n o m i cm o d e l ，e t c t h e r e f o r e ，v a r i a t i o n a li n e q u a l i t ya n di t sa p p l i c a t i o nh a v e b e c o m eaf o c u si nm a t h e m a t i c s i nc h a p t e r3 ，w ec o n s t r u c t e dam e r i tf u n c t i o nb a s e dt h em o d e lf o rs t r u c t u r e d m o n o t o n ev a r i a t i o n a li n e q u a l i t i e s w et r a n s f o r m e dt h eo r i g i n a lp r o b l e mt oa l l o p t i m i z a t i o np r o b l e mw h i c hp o s s e s s e sav e r ys i m p l es t r u c t u r ef o rc a l c u l a t i o ni no u r m e t h o d a tl a s t ，w eg a v et h eg l o b a lc o n v e r g e n c ec o n d i t i o n i nc h a p t e r4 ，w ei n t r o d u c e ds o m ea l g o r i t h m sf o rv a r i a t i o n a lp r o b l e m s s o m e n u m e r i c a le x a m p l e sw i t hb a l lc o n s t r a i n t so rb o xc o n s t r a i n t sw e r eg i v e n n u m e r i c a l r e s u l t sv e r i f i e dt h ev a l i d i t yo ft h em e t h o dp r o v i d e di nc h a p t e rt h r e e k e yw o r d s ：v a r i a t i o n a li n e q u a l i t y ；m e r i tf u n c t i o n ；p r o j e c t i o n ； 0 p t i m a l i t yc o n d i t i o n s i i 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文 作者签名 导师签名 日 日 孝聋 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意 若有不实之处，本人愿意承担相关法律责任 学位论文题目：盛簋二娄皇词变金丕笠式闽题鲍效益函数左法 作者签名：逍出一吼手月当日 大连理工大学硕士学位论文 引言 本文研究如下形式的结构型单调变分不等式问题： 求z f q ，使( z f 一甜) 7f ( 甜) 0 ，v “q 甜= 砌) _ ( 捌，耻融川悱劬“加砂叫 其中，xc 尺”，ycr ”为非空闭凸集合，厂：x 寸r ”，g ：】厂j 灭”为连续单调映射， a r “”，b r “”，为满秩矩阵，b r 7 为，维列向量 本文中假设，聊，且( o 1 ) ( o 2 ) 的解集非空，并记为q 求解这种结构型单调变分不等式问题有很多有效的算法，如交替方向方法，下降方 法等本文通过效益函数方法对该问题进行研究 求解一类单调变分不等式问题的效益函数方法 1绪论 1 1 变分不等式问题的背景和研究现状 “变分不等式是“v a r i a t i o n a li n e q u a l i t y ”的中文译名，也有人译为“变分不等方 程”变分不等式作为变分原理的主要推广，是一类非常重要的非线性问题，产生于许 多不同的领域，如物理学，工程学和金融管理科学等等 人们对变分不等式的兴趣始于一些力学问题的研究1 9 3 3 年，s i g n o r i n i i l l 在研究一 个线性弹性体与刚性体的无摩擦接触时导出了一个变分不等式，称为s i g n o r i n i 问题然 而，变分不等式作为一个重要的数学分支则始于上世纪六十年代关于s i g n o r i t r i 问题的 变分不等式的第一个严格的分析是在f i c h e r a 2 j 中给出的几乎同时，s t a m p a c c h i a 做出 了变分不等式这一数学学科的奠基性贡献1 9 6 4 年，s t a n l p a c c 。u 4 1 3 1 把l a x m i l g r a m 定理 由h i l b e r t 空问推广到其非空闭凸子集的情形，得到了变分不等式的第一个解的存在唯 一性定理在l i o n s 和s t a m p a c c h i a 4 j 这篇著名的论文中给出了变分不等式的一些数学理 论d u v a u t 和l i o n s 5 】在变分不等式的框架下研究了许多力学和物理学问题l i o n s ，l e w y ， b r e z i s 等人发表了一系列文章，为变分不等式理论奠定了初步的基础2 0 世纪7 0 年代， 变分不等式在最优控制问题，弹性问题，弹塑性问题及渗流问题领域中得到了成功的应 用2 0 世纪8 0 年代以来，作为现代偏微分方程理论重要部分的变分不等式理论得到了 深入发展，至今已较为成熟 2 0 世纪6 0 年代以来，l i o n s ，b r o w d e r ，s t a m p a e e h i a ，k yf a n ，l e r n k ，c a r e ，d a n t i z i n g 等提出和创立了变分不等式和互补问题的基本理论经过许多学者的努力，变分不等式 理论及应用的研究已取得重大的进展，在微分方程，力学，控制论，对策论，经济平衡 理论，交通运输，社会和经济模型等很多方面有着重要的应用，应用前景非常广阔而 且数学规划中的很多问题也可以归结为变分不等式问题来研究，因此，变分不等式问题 的研究和应用也是数学规划和运筹学等领域的一个重要课题 对变分不等式的研究主要分为理论和算法两大方面理论研究的焦点集中在变分不 等式解的存在性，唯一性和灵敏性等而算法方面主要是研究如何引进和借助各种技术， 概念和思想等以建立各种类型的变分不等式的具体解法( 见文献 6 8 】) 经过许多学者的 辛勤研究，在算法方面取得的丰硕的成果， 在推广方面，对变分不等式的研究又有将标准变分不等式推广到广义变分不等式 g v i ( k ，t 3 和拟变分不等式q v i ( k ，f ) 再到广义拟变分不等式g q v i ( k ，f ) ，还有学者从更基 大连理工大学硕士学位论文 本的拓扑和泛函的观点上研究了无限维赋范空间的变分不等式问题所有这些都推动了 般点到集值映射的发展及其在数学规划中的应用 变分不等式的数值解法一直是一个备受关注的热点问题，下面我们概述一下变分不 等式问题的一些算法方面的研究现状 许多数学工作者根据所研究变分不等式的特点，提出了各种各样行之有效的算 法但是对于一般变分不等式的算法研究相对较少许多学者利用不同的技巧( 如投影 算法、辅助原理、w i e n e r - h o o f 方程等) 提出了解一般变分不等式的一些算法n o o r 9 】首 先建立了一个不动点方程；p a n g 和y a o 【1 0 1 给出了解的存在性的一些充分条件，并研究了 其的稳定性；h e 1 1 1 提出了一个非精确的稳定投影方法；2 0 0 0 年，n o o r l l 2 1 应用分裂技巧， 提出了三步分裂迭代解法；2 0 0 2 年，n o o r l l 3 利用新的搜索方向，在解集非空和映射为 单调的情况下提出一种修正投影算法 针对单调变分不等式，g o l d s t e i n 1 e v i t i n p o l y a k 1 4 - 1 5 利用“u 是经典变分不等式的 解等价于u = 毗( “一p f ( u ) ) ”，提出了显式投影方法，迭代格式为： u h l = p r o j n ( u 。一成f ( u 。) ) 其中p ，毗( ) 是q 上的正交投影，尾 0 是选定的任一步长但为了证明算法的收 敛性，单值映射f 必须是l i p s c h i t z 连续且强单调1 9 9 9 年，n o o r 1 6 1 和z h a o 1 7 1 就单调变 分不等式问题分别提出了改进的投影算法 之后，k o r p e l e v i c h 1 8 】提出了改进方法，即著名的外梯度法，迭代格式为： 万。= p r q 如( ”2 一j 6 i t f ( u 2 ) ) ， 材“1 = p r o j o ( u 2 一成f ( 订。) ) ( 1 1 1 ) 其中尾是选定的任一步长当单值映射，是l i p s c h i t z 连续时，此算法收敛但如 果f 不是l i p s c h i t z 连续或l i p s c h i t z 常数不确定时，为了得到新步长，在每一试验点都 需要进行h r r n i j o 线性搜索，这就大大增加了计算量因此人们对外梯度算法进行大量 的改进：i u s e m 和s v a i t e r t l 9 】的算法只需一个投影就可得到步长成，而且全局收敛的条件 没有增力n ；s o l o d o v 和s v a i t e r l 2 0 j 使用相同的搜索方向，通过修改投影区域得到了更好的步 长规则；2 0 0 1 年，王宜举2 1 1 改进了外梯度算法的搜索方向，同时在1 2 2 1 中提出了一种外 梯度算法的统一框架；2 0 0 2 年，何炳生掣2 3 】将外梯度算法( 1 1 ) 的步长成做了改进，大 大提高了算法效率 此后，针对单调变分不等式，学者们又提出了各种解法八十年代，g a b a y l 2 4 】引入 一个罚参数并提出交错方向法，但如果罚参数选择不当，求解时间就会大大增加为此， 求解一类单调变分不等式问题的效益函数方法 可变的罚参序列被用来代替固定的罚参数但是选择合适的初始罚参数也很难，h e e t a l 【2 5 】 通过使用自适应法则来调整罚序列，得到了较好的结果 t e n g 2 6 】基于线性约束的凸可分规划的内点法，提出了路径跟踪法来解单调变分不等 式其主要思想是在每一个迭代步，用一个n e w t o n 法不精确地解一个原始问题的参量 化光滑逼近，并且以几何速率使参数逼近零点这个算法可从任何一个内点开始，而且 全局收敛c h e n 和h a r k e r l 2 7 1 也将互补问题的路径跟踪法推广到了变分不等式，并加以改 进，得到的算法可在任意一个初始点开始，而且不要求中间点一定为可行点1 9 9 8 年， k c h r i s t i a n 和j i a n g 2 8 1 提出一种类内点连续算法 单调变分不等式的自由导数法，没有用到映射的j a c o b i a n 矩阵，而是利用各种价值 函数来解决，所以这种方法适合解大规模的变分不等式p e n g 2 9 】利用一个所谓的d 一 间隙函数，可看作是隐式l a g r a n g e 算子从互补问题到变分不等式的一种推广，将变分不 等式转化为无约束的价值函数极小化问题可参看文献 3 0 3 1 】 对于一些带有可分结构的大规模变分不等式问题，可用分解法将原始问题分解为一 系列低维数的子问题引入一个拉格朗日乘子( 向量) 后，通过一定的规则进行迭代它 是增广拉格朗日算子方法的推广，可参看文献 3 2 】 对于带有约束集的变分不等式，如果约束集由一些不等式定义，而且一些标准的约 束限定成立，那么问题可转化为一个k k t 系统；利用f i s c h e r 函数【3 3 j 可将k k t 系统转 化为一个非光滑方程组或者是极小化问题，可参看文献 3 4 3 5 除了可将变分不等式转 化为无约束优化问题外，一些学者还考虑将它转化为约束优化问题，可参看文献 3 6 】这 种转化的一个原因就是变分不等式中的函数可能仅定义在一个约束集上在多数情况 下，要找一个优化问题的全局最小解是很困难的，并且许多优化技巧只局限于价值函数 的一个平稳点虽然给出了保证价值函数的一个平稳点是变分不等式或互补问题的解的 条件，但是仍存在不是原始问题解的平稳点，这样会增加计算量 特别地，对于箱约束变分不等式，q i ，s u n 和z h o u l 3 7 1 引入额外人工变量，将变分不 等式问题化为菲线性互补问题来研究，而后利用光滑牛顿法得出其迭代算法，但从计算 角度讲显然是不经济的2 0 0 2 年，陈国庆，曹兵【3 8 】引入一种新的间断函数并提出了广 义牛顿法：同年，陈国庆，刘水霞【3 9 】针对不可微箱约束变分不等式提出了下降算法 大连理工大学硕士学位论文 1 2 变分不等式效益函数的研究进展 近年来，一部分学者致力于将变分不等式问题与互补问题通过一个效益函数( m e r i t f u n c t i o n ) 转化为一个最优化问题来求解对于变分不等式问题： 求x x ，使( y x ) 7 1 f ( x ) 0 ，b 夕x ( 1 2 1 ) 其中xc r “为非空闭凸集，：r ”一尺”为连续映射厂称为变分不等式( 1 2 1 ) 的效 益函数，如果厂的全局最小解集与( 1 2 1 ) 的解集致 若厂为变分不等式的效益函数，则变分不等式问题可以等价地转化为如下的极小问题： m i nf ( x ) s i x x( 1 2 2 ) a u s l e n d e r 删和h e r a n 4 1 】分别独立提出变分不等式的效益函数，也称为g a p 函数函 数定义如下： g ( x ) = s u p ( f ( x ) ，x j ，) ：y x ( 1 2 3 ) g ( x ) 有如下性质1 4 2 1 ： i ) g ( x ) 0 ， v x x ； i i ) g ( x ) = 0 ， 当且仅当x 为变分不等式( 1 2 1 ) 的解 由这两条性质，变分不等式问题( 1 2 1 ) 可转化为如下最优化问题 m i ng ( x ) s 1 x x ( 1 2 4 ) 一般的，对于上述变分不等式问题，转化为优化问题后，优化函数的可微性得不到 保证，而且当可行集x 无界时，函数g ( x ) 可能取无限值，直到后来，f u k u s h i m a l 4 3 】和a u c h m u t y 4 4 l 几乎同时独立地提出了如下效益函数，避免了这个问题： ( 戈) = s u p ( f ( x ) ，x y ) 一等| i x - - y l l 2 ) ( 1 2 5 ) y e x 二 其中a 为一个正的参数，这个函数被称作正则化g a p 函数对于正则函数g a ( x ) 而言，x 是变分不等式的一个解当且仅当g o ( x ) 在工上取极小值0 ，在此意义上，函数g 口( 工) 也 构成了变分不等式问题的一个等价约束最优化转化形式后来，w u 等人【加】又对这个正 则化g a p 函数进行了一些推广f u k u s h i m a 在这个函数的基础上，引入正定对称矩阵g ， 提出如下的正则化g a p 函数： g 口( x ) = s u p ( f ( x ) ，z y 一导0 x y 0 三) ， ( 1 2 6 ) y e x z 其中g r “”，为正定对称矩阵i | 1 l g 定义为0 x l l g = ( x ，g x ) 2 这就是本文将要用到的 效益函数 另外，p e n g 4 5 1 还考虑了如下定义的函数坂：r ”寸r ，m o ( x ) ：= 蜀口( x ) 一( x ) ， 其中g a 为( 1 2 5 ) 所定义的正则化g a p 函数，口 l 是个常数p e n g 证明了函数心可 以形成变分不等式问题的一个无约束可微最优化转化由于此函数是用两个正则间隙函 数的差来定义的，所以称之为d g a p 函数，这里的d 代表“d i f f e r e n c e y a m a s h i t a t a f t 求解一类单调变分不等式问题的效益函数方法 和f u k u s l l i m a 【4 6 1 推广了p e n g 的结果，他们研究了按如下定义的广义d g a p 函数的各 种性质，踟：= g a ( x ) - g 卢( x ) ，其中a 和卢为任意正的参数且口 一a 妒( x ，y ) ，函数妒：月2 ”一r 满足如下 条件： ( c 1 ) 妒在r 2 ”上连续可微； ( c 2 ) 在r 2 “上非负； ( c 3 ) 妒( 而- ) 在x 上是一致强凸的，即存在常数a 0 ，使得对任意_ ) f r ”，有 ( x ，y 1 ) - # ( x ，儿) ( v y ( 石，y 2 ) ，y l y 2 ) + 九i i y l y 2 1 1 2 ，v y l ，y 2 r ”； ( c 4 ) 砂( x ，y ) = 0 当且仅当工= y 称满足条件( c 1 ) - ( c 4 ) 的函数为广义距离函数，它显然是函数驴( 五y ) - i x y l 2 2 的推广 1 3 本文的主要工作 正如我们所介绍的那样，效益函数受到很多学者的重视，用效益函数把变分不等式 问题转化成一个最优化问题来求解是个非常有效的方法到目前为止，效益函数方法解 变分不等式问题仍然存在许多值得研究的课题 1 我们对变分不等式问题的条件要求比较强，我们可以尝试有针对性地减弱条件， 并分析这些条件下变分不等式的一些性质 2 对于一些比较特殊的变分不等式闷题，我们可以构造一些特定的效益函数来求 解，并且如何设计全局收敛算法也是一个值得研究的课题 本文针对上述的结构型单调变分不等式，通过使用效益函数将问题转化成一个极小 问题来求解，成果如下： 第3 章通过引入一个拉格朗日乘子将问题分解成两个子变分不等式问题，用效益函 数将子问题转化为结构比较简单的最优化问题，将两个子问题之间的约束纳入最优化问 题的约束条件，并对最优化问题的全局最优性条件行了分析第4 章则在现有一些算法 的基础上，对这个问题设计了一个下降算法，并给出收敛性证明，数值试验表明，本算 法有效 一6 一 大连理工大学硕士学位论文 2 预备知识 2 1 变分不等式问题预备知识 设日为一个实h i l b e r t 空间，( ， 表示日的内积当日= r ”时，日为e u c l i d e a n 空间，它是一个n 维欧氏空间，q 是r ”的一非空闭凸集f ，g ：r ”专r ”是非线性映 射，且g 可逆一般变分不等式问题形式如下： 求x r ”，g ( x ) q ，使得 ，( x ) 。( g ( y ) 一g ( x ) ) 0 ，v g ( y ) q( 2 1 1 ) 如果g ( 力= x ，问题( 2 1 1 ) 等价于求z q ，使得 f ( 工) 1 ( y x ) 0 ，v y q 这类问题就是经典变分不等式问题 如果q ”= x r ”i 0 ，使得，满足 ( f ( x ) 一f ( y ) ，x y ) - 口l l x y 旷 则称f 在集合x 上是强单调的； 求解一类单调变分不等式问题的效益函数方法 2 2 投影的一些性质 定义2 2 1 非空闭凸集x c r “中，点x 在x 上关于g - 范数的投影，记为慨g ( x ) ， 即满足如下性质的点： 卜i x 魄，g ( x ) 忆= r a i n i i x - z z e x ( 2 2 1 2 ) 这里g r “”，为正定对称矩阵1 1 1 | g 的定义为| g = ( x ，g x ) 2 显然，若x x ，则 x = p r o j g ( x ) 定理2 2 1 设xcr ”为非空闭凸集，则对任意的点x x ，x 在x 上关于g 范数的投 影, p r o j x g ( x ) 存在且唯一，且满足 ( x p r 魄g ( x ) ，g ( y p r o j x g ( x ) ) ) 0 ( v y x ) ( 2 。2 2 ) 定理2 2 2 设xcr ”为非空闭凸集，则有下式成立： i p r o j ，g ( x ) 一p r o j x o ( y ) 0 g l i x y l l 6 ，x , y r ” ( 2 2 3 ) 定理2 2 2 揭示了任意两点间的距离不因到闭凸集上的投影而扩大这一事实这就意味 着，当把投影p r o j x g ( x ) 看作从r ”n r ”的映射时，它具有所谓的非扩张性质 在g = i 的情况下，上面两个定理已经被证明，参见文献 4 0 ，4 1 】，有此不难把它推广到g 范数的投影 2 3 效益函数的一些性质 变分不等式效益函数的定义见章节1 2 2 ，不难看出，x 在非空闭凸集x 上关于g 范数的投影p 嘞g ( x ) ，且p o n - f 极小问题的解： m i n y x 队 ( 2 3 1 ) s t y x 根据参考文献 4 3 ，有如下命题成立： 命题2 3 1 令x r ”为任一固定点，则问题： s u p ( ，( x ) ，x y ) 一判x y 悒 ( 2 3 2 ) s t y x 与极小问题： m i n 0 j ，一( x 一口1 g 。1 f ( x ) ) i 芒 一8 一 大连理工大学硕士学位论文 s t y x 等价 以下为叙述方便，h ( x ) = p r o j x- 1 1 ，( x ) ) ，则由命题2 3 1 ， 函数( 6),a(x-or gg a p 1 2 也就可以写为如下显式形式： & ( z ) = 伊( z ) ，x 一日( x ) 一等0 x - - 日( x ) 屺 根据参考文献 4 7 ，有如下命题成立： 命题2 3 2vx r ”，h ( x ) 为( 2 3 2 ) 的唯一解，且x 为变分不等式问题( 1 2 1 ) 的 解当且仅当x 为h ( x ) 的稳定点，即x = 日( x ) 根据参考文献 4 3 】，有如下命题成立： 命题2 3 3 若映射f ：r ”一r ”连续，则对应的g a p 函数( 1 2 6 ) 也连续，若f 连续可 微，则g a p 函数也连续可微，且其梯度由下式给出 v ( x ) = f ( x ) 一( v f ( x ) 一a g ) ( h ( x ) 一x ) 求解一类单调变分不等式问题的效益函数方法 3 解结构型单调变分不等式的效益函数方法 3 1引言 考虑如下的变分不等式问题： 求u q ，使( z f 一甜) 7 f ( u ) 0 ，v u7 q ( 3 1 1 ) 这里 群= 盼) ( 捌肚他川悱x 鹏l a x + b y _ 6 ) ( 3 1 2 ) 其中，xcr ”，ycr ”为非空闭凸集合，f ：x - - - r ”，g ：y _ r ”为连续单调映射， a 足“”，b r “”，为满秩矩阵，b r 为，维列向量 本文中，假设，m ，且问题( 3 1 1 ) ( 3 1 2 ) 的解集非空，并记为q 这种问题称为结构型单调变分不等式问题很多的应用问题，特别是经济和交通均 衡问题【4 7 ，4 8 1 ，都可以转化为形如( 3 1 1 ) ( 3 1 2 ) 的变分不等式问题来进行求解许多 解决这个问题的算法【4 9 - 5 3 1 ，是将问题分解成两个子变分不等式问题，然后使用交互方向 方法或下降方法，对两个子变分不等式问题进行迭代，通过解一系列的变分不等式来逼 近最优解本文则是使通过使用效益函数将问题转化成最优化问题来进行求解 首先，对线性约束叙+ e y = b 引入一个拉格朗日乘子a r ，变分不等式问题( 3 1 1 ) ( 3 1 2 ) 可以转化为如下比较紧凑的形式 4 9 - 5 3 】： 求w w ，使( w 7 一们7m ( w ) 0 ，v w 7 w ( 3 1 3 ) 其中， 肛 m ( w ) = 厂( x ) 一a 7 允 g ( y ) 一b ，a a x + b y b ，w ；x y xr 7 ( 3 1 4 ) 显然，v ( x ，y + ) q ，存在a r 7 ，使w ：= ( x ，y ，a ) 为问题( 3 3 3 ) 的解，即当q 非 空时，( 3 1 3 ) 的解集也非空解这个问题的一个经典的解法就是交互方向方法，最先 由g a b a y 和m e r c i e r 5 4 1 提出以下则是本文所用到的效益函数方法 不难得出，问题( 3 1 3 ) 一( 3 1 4 ) 等价于如下的子变分不等式问题： ( x 一x ) r ( 厂( x ) 一a r a , ) 0 ( 少- y ) 7 ( g ( j ，) 一b7 1 a ) 0 血+ 影一b = 0 ( 3 1 5 ) 大连理工大学硕士学位论文 其必要性显然，充分性只需在( 3 3 ，中分别取w ，= 三 ，= 三 ，w ，= ( 至p ， 即可 3 2 等价最优化问题 分别对子变分不等式问题( ，一功7 1 ( 八z ) 一a r 旯) o 和( 少一y ) 7 ( g ( 力一b7 见) 0 取 由( 1 2 6 ) 式给出的正则化g a p 函数，e y 帅( x ，a ) 和( y ，九) ，其函数表达式；n t ： 够( t a ) - s ，u p ( x 一) ，( 厂( 力一么，允) 一副z 一训三 ， 一e xz “ 妒( y ，a ) - s u ，p ( y y ) 7 1 ( g ( 力一b r 九) 一副少一y 咖 ，e y么 “ 由命题2 3 1 ， ( 3 2 1 ) 和( 3 2 2 ) 可以表示为： 9 ( x ，a ) = ( x q ( x ，a ) ) 7 ( m ) 一4 7 1 a ) 一弘一q ( 五榄， ( 3 2 1 ) ( 3 2 2 ) ( 3 2 3 ) 妒( y ，允) = ( y h 2 ( y ，a ) ) f ( g ( y ) 一b f a ) 一等0 y h 2 ( y ，a ) i l 2 ( 3 2 4 ) 其中h 1 ( x ，a ) = 魄6 ( x a - 1 g - 1 ( 厂( x ) 一a7 a ) ) ，h ，( y ，a ) = p r o j r ，g ( y - a - 1 g 卅( g ( y ) - b 7 a ) ) 在由命题2 3 3 知，厂( x ) ，g ( 少) 连续可微时，妒( 工，见) ， 妒( y ，允) 也连续可微，且： v ，妒( z ，a ) = ( z ) 一彳7 a 一( v 厂( 石) 一a g x h , ( x ，1 ) - x ) ， ( 3 2 5 ) v ，驴( y ，九) = g ( y ) 一b 7 a 一( v g ( y ) - a g ) ( h 2 ( 少，z ) - y ) ( 3 2 6 ) 定理3 2 1 9 ( x ，a ) ，( y ，a ) 的定义如( 3 2 1 ) ( 3 2 2 ) ，则有9 ( 五a ) + 妒( y ，a ) 0 ， f - x 1 v ，2j 少i y ，其中矿：= ，：x x ，ye y ，a x + b y = b ，a , er 7 ) 且妒( 墨a ) + 妒( y ，a ) = o 当且 l 九j 仅当( z ，y ) 为变分不等式问题( 3 1 1 ) ( 3 1 2 ) 的解 证明：记f ( x ，允) ：= 厂( x ) 一a7 九，则 妒( x ，a ) = ( x q ( x ，a ) ) 7 1 ( 厂( 功一彳7 1 允) 一副x q ( 五九) 晤 求解一类单调变分不等式问题的效益函数方法 = o c - 1 g 。1 f ( 艺桃一( m ) 一功i _ g - i g 。1 琢，榄 = 铷x ( x - a - g 。1 瞰驯h q ( 蜊一( x - - o c - i g 一以圳心 而q ( 兑_ , ) = p r o j x g 一口一g 1 f o ) ) ，由投影的定义2 2 1 ，即得妒( x ，允) 0 同理可得， 另外，由于妒( t a ) 0 ，妒( 少，a ) 0 ，故9 ( 允) + 妒( 弘九) = 0 当且仅当9 ( 工，允) = 0 ，多( 少，a ) = 0 时取得，即x = h ，( 艺a ) ，y = h 2 ( y ，兄) 由命题2 3 2 不难得出，这个条件也就等价于( x ，y ) s j v = ( 三 y ( 3 2 7 ) 其中9 ( x ，a ) ，妒( y ，允) 定义见( 3 2 1 ) ，( 3 2 2 ) ，v 的定义见定理3 2 1 以下我们研究问题( 3 2 7 ) 的全局最优性条件 3 。3 全局最优性条件 一般情况下，我们只能的得到极小问题( 3 2 7 ) 的局部最优解，但是当f ( x ) ，g ( y ) 满足一定条件时，可以证明所求得( 3 2 7 ) 的局部最优解即为其全局最优解从而我们 设计算法时只要致力于求得一个局部极小点即可 定理3 3 ，1 设f ( x ) ：r 8 一r ”为连续可微函数，若f ( x ) 强单调，则夥( x ) 处处正定 证明：f ( x ) 强单调，即3 r l 0 ，v x ，y ，有： ( 厂( x ) 一厂( y ) ，x y ) 叩i x - y l l 。 不难验证，f ( y ) 一( x ) = v f ( x + t ( y x ) ) ( y - x ) d t 于是： 7 7i l y - x l l 。( y x ) 7 ( 厂( y ) 一厂( x ) ) = ( y z ) 7 【v f ( x + f ( y x ) ) ( y - x ) d t ( 3 3 1 ) 大连理工大学硕士学位论文 取x 少，在上不等式两边同时除以i l y x l l 2 ，有： 叩锱f w 伊砌晶卉 记z 2 网( y - x ) ，并令y _ x ，上式取极限即得： ，7 z tf 夥( x ) z d t = z r v f ( x ) z 其中z 为单位向量由x ，y 的任意性可知，v f ( x ) 处处正定证毕 对于定理3 3 1 厂 ) 严格单调时并不能保证v f ( x ) 的处处正定性，因为对应( 3 3 1 ) 式的不等式o 0 是一个固定的常数如果口 0 充分小，f 是强单调和全局l i p s c h i t z 连续的，则利用b a n a c h 不动点定理，很容易得到这个方法是全局线性收敛的 2 外梯度法 1 9 7 6 年，g m k o r p e l e v i c h 1 8 】把式( 1 2 3 ) 中的两个相邻的迭代合并成一次迭代从 而得到下面的迭代公式： 舅= p r 巧y ( x 一a f ( x t k ) ) ) ， x “= p r o j x ( x 一仅f ( 曼) ) 虽然和不动点迭代法相比，这种方法增加了计算量，但仍属于简单迭代其优点是 把f 的强单调性假设降低为单调性关于这种方法的详细内容，请参考 5 8 5 9 后来， a n i u s e m 等在 1 9 ，6 0 6 2 中改进了这种方法，m v s o l o d o v 和p t s e n g 6 3 1 还给出了一 大连理工大学硕士学位论文 些比外梯度方法更加有效的新的投影型算法，可以在f 伪单调的条件下得到算法的全局 收敛性 3 超平面投影法 外梯度法需要给出映射f 的l i p s c h i t z 常数，然而一般情况下，这个常数我们是不 知道的而超平面法可以被看作是改进的外梯度型法，它的收敛性证明既不要求，是 l i p s c h i t z 连续的，也不需要一些潜在的未知常数例如：1 9 8 6 年，m f u k u s h i m a 6 4 1 利 用松弛投影法求解了变分不等式问题，即将算法的每步迭代投