（应用数学专业论文）变分不等式的算法研究.pdf

摘要 变分不等式是非线性互补问题的推广，它的提出统一了优化问题和均衡问题 的研究，并且在数学领域中作为大量数学问题实际求解的统一框架。变分不等式 广泛地应用于工程优化，经济学和交通运输的均衡问题，对数学各个领域，计算 机科学等方面都产生了巨大的影响。由于变分不等式和人们的实际生活联系紧密， 因此，如何有效求解变分不等式问题一直是数学工作者和经济学家研究的热点。 本文主要研究基于变分不等式k k t 条件的求解方法。 首先，简单回顾了变分不等式的起源和发展历史，分析了求解该问题现有的 算法，给出了本文所需的基本概念和数学背景知识。然后，基于优化技巧，利用 两个新的半光滑n c p 函数，将变分不等式的k k t 条件转化为半光滑非线性方程 组，并利用价值函数进一步转化为无约束极小化问题，提出了半光滑牛顿算法， 并在理论上证明了算法的全局和局部二次收敛性，通过数值实验说明了算法的有 效性。接着，基于一个新的光滑n c p 函数，将k k t 条件转化为等价的光滑非线 性方程组，提出了非内点光滑算法，且在理论上证明了算法的适定性和收敛性， 数值结果说明算法是有效的。最后总结了本文的工作。 关键词：变分不等式半光滑牛顿法非内点光滑化法k k t 条件 a b s t r a c t t h ev a r i a t i o n a li n e q u a l i t y , w h i c hi sag e n e r a l i z a t i o no ft h en c p , p r o v i d e sab r o a d u n i f y i n gs e r i n gf o rt h es t u d yo fo p t i m i z a t i o na n de q u i l i b r i u mp r o b l e m sa n ds e r v e sa s t h em a i nc o m p u t a t i o n a lf r a m e w o r kf o rt h ep r a c t i c a ls o l u t i o no fah o s to fc o n t i n u u m p r o b l e m si nt h em a t h e m a t i c a ls c i e n c e s i th a saw i d er a n g eo fi m p o r t a n ta p p l i c a t i o n si n e n g i n e e r i n go p t i m i z a t i o n ，e c o n o m i ca n dt r a f f i ce q u i l i b r i u m sa n dh a sh e a v yi n f l u e n c eo n t h ev a r i o u sm a t h e m a t i c a lf i e l da n dc o m p u t e rs c i e n c e sa n ds oo n d u et ot h ec o n n e c t i o n s w i t ht h er e a l - l i f ee c o n o m i c s ，i ti sa l w a y sah o ti s s u ei nf i n d i n ge f f i c i e n ta n dr o b u s t m e t h o d sf o rs o l v i n gv 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 sf o rm a t h e m a t i c i a n sa n de c o n o m i s t s i nt h i sp a p e r , w ef o c u so nt h es t u d yo fm e t h o d sf o rs o l v i n gt h ek k t - c o n d i t i o n so f t h ev a r i a t i o n a li n e q u a l i t y f i r s t l y , t h eo r i g i na n dh i s t o r i c a ld e v e l o p m e n to fv a r i a t i o n a li n e q u a l i t yh a v eb e e n i n t r o d u c e d t h e ni ta n a l y z e st h ee x i s t i n gm e t h o d sf o rs o l v i n gt h ev 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 a l s oi tp r e s e n t st h eb a s i cc o n c e p t i o n sa n d r e l a t e dm a t h e m a t i c a lk n o w l e d g e s e c o n d l y , b a s e d o nt h e o p t i m i z a t i o nt e c h n i q u e ，t h i sp a p e r s t u d i e st w on e w n c p f u n c t i o n sw h i c ha r eu s e dt or e f o r m u l a t et h ek k t - c o n d i t i o n sa ss e m i s m o o t h s y s t e mo fe q u a t i o n sw h i c ha lef u r t h e rf o r m u l a t e da sa nu n c o n s t r a i n e dm i n i m i z a t i o n p r o b l e m t h es e m i s m o o t hn e w t o nm e t h o di sg i v e na n dc a nb ep r o v e dg l o b a l l y c o n v e r g e n ta n dl o c a ls u p e r l i n e a rc o n v e r g e n t t h en u m e r i c a lr e s u l t si n d i c a t et h a tt h e a l g o r i t h m i s e f f i c i e n t m o r e o v e r , c o n s i d e r i n g an e ws m o o t h i n gf u n c t i o n ，t h e k k t - c o n d i t i o n sa l ee q u i v a l e n tt oas m o o t h i n gn o n l i n e a rs y s t e mo fe q u a t i o n s ，w h i c hc a n b es o l v e db yn o n i n t e r i o rs m o o t h i n gm e t h o du n d e rs o m em i l da s s u m p t i o n s i ta l s o s h o w st h ea l g o r i t h mi sw e l l d e f i n e da n dc o n v e r g e n t t h en u m e r i c a le x p e r i m e n tp r o v e s t h a tt h em e t h o di sp r o m i s i n g f i n a l l y , t h es t r e n g t h sa n dw e a k n e s so ft h ea l g o r i t h m sa r e c o n c l u d e d 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 yp r o b l e m s s e m i s m o o t hn e w t o nm e t h o d n o n i n t e r i o rs m o o t h i n gm e t h o dk k t - c o n d i t i o n s 西安电子科技大学 学位论文独创性( 或创新性) 声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在 导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标 注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成 果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说 明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期垦! 堡! ：! 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位仍然为西安电子科技大学。 ( 保密的论文在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 日期皇! 丝：! ：! 日期坐! ! ：? ：j 埤华 名 名 签 签 人 师 本 导 第一章绪论 第一章绪论 本章首先回顾了变分不等式的起源和历史发展，然后介绍本文所研究的问题 及求解该问题现有的算法，接着给出了本文所需的基本概念和数学背景知识，最 后列出了本文的章节安排。 1 1 变分不等式 变分不等式是非线性互补问题( n c p ) 的推广。它的提出，统一了优化和均 衡问题的研究，并且在数学科学领域中作为大量数学问题实际求解的统一计算框 架。 变分不等式较早来源于力学的相关问题，包括阻力问题，自由边界问题，相 切问题，弹性塑料问题等。二十世纪六十年代早期，意大利数学家g u i d o s t a m p a c c h i a 和他的同事第一次把变分不等式作为研究自由边界问题的分析工具， 从此开始了变分不等式的系统研究。1 9 6 4 年，s t a m p a c c h i a 首次证明了变分不等式 解的存在性和唯一性。随后，便涌现出大量关于无限维变分不等式及其相关问题 的文献，特别是b a i o c c h i 和c a p e l o t 5 3 1 以及k i n d e r l e h r e r 和s t a m p a c c h i a t 5 4 1 在其书中 详细介绍了无限维空间中变分不等式的应用。但是，由于无限维空间的抽象性， 本文重点研究的对象是有限维空间中的变分不等式。 1 9 6 7 年，s c a r f 首次提出了用迭代法近似求解连续映射的不动点。由于不动点 法的全局收敛性，许多著名的研究员包括e a v e s ，g a r c i a ，g o u l d ，k o j i m a ，m e g i d d o ， s a i g a l ，t o d d 和z a n g 都致力于该方法的研究，由此掀起了一股不动点法求解均衡问 题的热潮。七十年代，经济学中的均衡问题被证明和变分不等式的求解有着密切 的联系，其中对许多基础均衡问题的研究都可以转化为变分不等式问题，比如新 古典纯粹交易模型，纳什均衡问题以及网络均衡问题等，可参考文献 8 , 1 3 , 2 2 3 1 , 3 , 1 1 。七 十年代后期，美国能源部提出了关于能源政策研究的项目独立评估系统( p i e s ) ， 这标志着现代有限维变分不等式的开端。该系统是用特殊的迭代求解的一个大规 模变分不等式。a h n i5 0 l 证明了p i e s 算法就是求解非线性等式系统的经典j a c o b i 迭 代法的一般形式；随后，基于r o b i n s o n 的研究， j o s e p h y 通过大量的数值实验确 立了牛顿法求解变分不等式的有效性，同时提供了该方法快速收敛的理论基础。 而r u t h e r f o r d t 5 l 】指出，把牛顿法运用于某些挑战性的经济均衡问题时缺乏健壮性。 基于对牛顿法的健壮性及其全局收敛性要求，p a n g t 2 5 1 提出了线性搜索的b 可微牛 顿法，确立了该方法的全局收敛性和局部收敛性。但是，p a n g 的方法在理论方面 存在缺陷，即该方法的全局收敛性证明必须假设函数在算法产生的序列的极限点 2 变分不等式的算法研究 处是f 可微的。m i f f l i n t 2 8 1 提出的半光滑函数解决了这一问题，而q i 和s u n t 3 8 1 推广 了半光滑函数的应用范围。d i r k s e 和f e r r i s t 5 】替换了p a n g 的线性搜索，代替以路 径搜索算法成功地得到了变分不等式问题的解。九十年代，f i s c h e r 提出的n c p 函 数，被广泛应用于k k t 条件的改写，从而得到了弱于b 可微且具有全局收敛和局 部收敛的半光滑化法。经过几十年的研究，有限维变分不等式的理论和算法已经 得到了极大的发展。但是由于和现实世界的紧密联系，变分不等式将一直是数学 工作者和经济学家研究的热点问题。 下面给出变分不等式问题的一般形式： 定义1 1f ：r ”专r ”是连续可微的向量值函数，x 是尺”上的非空闭子集。变 分不等式问题( v a r i a t i o n a li n e q u a l i t i e sp r o b l e m s ) ，记为v p ( x ，f ) ，是指：求向量 x x ，使对任意x x 有 f ( x ) 7 1 一x ) 0 ， ( 1 1 ) 变分不等式根据约束集x 的不同，可以转化为不同的数学问题。 ( 1 ) 若集合x 表达为 。 x = x r ”lt ( f ) ，薯甜，( f l ) ) ( 1 - 2 ) ，l 是，= 1 ，刀) 的子集( 可能为空) ，此时称v i p ( x ，f ) 为箱约束变分不等式。 特别地，混合互补问题：求x = ( 五，x 2 ) r 仇r 也，使得 e ( _ ，艺) o ，e ( 西，x 2 ) = o ，_ o ，0 e ( 五，x 2 ) = 0 ， ( 1 - 3 ) 其中f i ：r ”一r 啊和e ：r ”jr “，令 x = 钟r “，f = ( 巧，e ) ，玎= 惕+ n 2 ， ( 1 - 4 ) 容易看出，混合互补问题是具有箱约束的变分不等式问题，记为m c p ( i ，u ，f ) 。 ( 2 ) 若x = 趟，则v i p ( x ，) 蜕化为非线性互补问题，记为( ，( f ) ，等价 为：求矿r ”，使得 x 0 ，f ( x 奎) 0 ，f ( x 木) r x + = 0 ： ( 1 - 5 ) 若f 是仿射，即f ( x ) = m x + q ，这里m 为玎阶矩阵，q 为玎维向量，则 c p ( f ) 蜕 化为线性互补问题，记为l c p ( m ，q ) 。 ( 3 ) 若x = r ”，则变分不等式问题v i p ( x ，f ) 蜕化为求解系统f ( x ) = 0 ；若 f = v f 是连续函数f ：r ”一r 的梯度，且x 是非空闭凸集，则v i p ( x ，f ) 等价于约 束优化问题m i n 厂( x ) 的求解。 工e 爿 ( 4 ) 若集合x 为： x = x r ”i ( x ) = 0 ，g ( x ) 0 ) ( 1 - 6 ) 其中h ：r ”寸r p ，g ：r ”专r 册为二次连续可微函数。在一定约束条件下，( 1 1 ) 第一章绪论 的解x 奎和相应的l a g r a n g e 乘子矿r v ，矿r ”满足下列k k t 系统： f ( x ) + v 办( x ) 7 1 y v 奢( x ) r z = 0 ， h ( x ) = 0 ， ( 1 - 7 ) g ( x ) 0 ，z o ，z 7 g ( x ) = 0 ， 在一定条件下，满足k k t 系统( 1 7 ) 的x 宰是( 1 1 ) 的解，因此称( 1 7 ) 是 变分不等式( 1 1 ) 在( 1 - 6 ) 约束下的最优性条件；而满足( 1 7 ) 的三元组 ( 妒，y 木，矿) 尺肘p ”称为k k t 三元组，对应的x 幸称为变分不等式的k k t 点。在不 引起混淆的情况下，简称k k t 三元组为k k t 点。 本文主要研究x 为多面体集形式，不失一般性，设 x = x r ”ig ( x ) 0 其中g ：r ”- - r ”且岛：r ”- - - ) r ( i i = 1 ，所) ) 是凹函数且二阶连续可微。 1 2v i p 的求解方法 目前，v i p ( x ，f ) 在数学规划、对策论、交通运输等领域都具有广泛的应用， 因而受到许多数学工作者，经济学家和工程技术人员的重视。研究人员致力于用 快速、有效、健壮的方法得到变分不等式的解，提出了很多有效地算法，并且完 善与丰富了算法的收敛性理论。本节主要对当前使用广泛的三大类方法进行归纳 整理：投影类算法、非光滑方程组法和光滑化方法。 投影类算法投影算法是求解变分不等式的一类简单算法，其最早由 s i b o n y t ”1 、b a k u s i n s k j i 和p o l y a k l 4 0 在十九世纪七十年代提出。它通常分为基本投 影法【州( b a s i cp r o j e c t i o na l g o r i t h m ) 、外梯度法1 ( e x t r a g r a d i e n tm e t h o d ) 以及平 面投影法 4 4 1 ( h y p e r p l a n ep r o j e c t i o nm e t h o d ) 。这些方法主要依赖于 ，”= 墨( ，一4 ) 的投影迭代，其中g 是包含x 的闭凸集，巩为搜索方向， 0 为步长，( ) 表示向量x 到集合g 上的投影，即 圪( x ) = a r g m i n x - y 1 l y q 。 投影法具有两方面的特征：其一，该方法的实现要求有效地计算闭凸集上的 投影。当约束集x 相对简单使投影易于计算，则算法简单易实现；而当投影计算 比较困难时，该方法的应用将受到限制。其二，算法不涉及函数f 的导数信息和 其它复杂运算，因而也适用于大规模问题。 基本投影法基于b a n a c h 不动点定理，迭代格式为 x 州= f i x , d ( x 。一d 叫f ( x 。) ) 4 变分不等式的算法研究 其中d 为n 阶对称正定矩阵。该方法是其它投影算法的基础，仅当f 强单调时， 算法才具有全局收敛性；且d 未知，需要额外的参数给定d 。因此该方法在实际 中应用并不广泛。 外梯度法由k o r p e l e r i c h 4 1 】在1 9 7 6 年提出，方法名称源于对称变分不等式情况， 每一次迭代需要额外估计f 的函数值与额外的投影，即二次投影： y 。= 昂( x 。一a 女f ( x 。) ) ， x “1 = 最( r - a 女f ( y ) ) 其中a 。 0 为步长，故称外梯度。该算法在映射f 是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 常数未知，i u s e m 和s v a i t e r t 4 5 i 通过引 进一种不带投影的线性搜索技术，提出了改进的求解变分不等式的外梯度法，以 保证f 伪单调时，算法具有全部收敛性。关于该方法的其它改进可参考文献1 4 6 , 4 7 】。 平面投影法由k o n n e v 、i u s e m 和s v a i t e r 提出，它克服了外梯度法依赖f 的 l i p s c h i t z 常数来保证收敛的缺点。其思想是在当前迭代点计算投影点 y = n x ( 一r f ( x ) ) ，用a r m i j o 线性搜索在连接两点x ky 的线段上确定一个点 z ，使超平面 巩= x r ”lf ( z 。) 7o 一矿) = 0 ) 将与变分不等式v i p ( x ，f ) 的解严格分离，然后将投影到超平面凰上，再将 该投影点投影到约束集x 上，得到，”。可以证明+ 1 较x 更接近v i p ( x ，f ) 之解 集。 非光滑方程组法其基本思想是把变分不等式问题或者它的最优性条件转化 为一个与之等价的非光滑方程组，参考p a n g1 2 5 , 2 6 1 ，x i a o 和h a r k e rt 3 6 1 ，d i r k s e 和 f e r r i s l 5 i ，然后通过求解该方程组从而得到原问题的解。非光滑化方法的提出基于 非光滑分析理论的成熟，m i f f l i n 2 8 j 首先给出了关于实值映射的单变量半光滑函数 的定义，q i 和s u n t 3 8 l 将其推广为向量值半光滑函数，并给出了相应的非光滑形式 的牛顿法。q i 给出了非光滑方程组的收敛性分析，在一定正则性条件下得到了超 线性收敛性。f i s c h e r 在1 9 9 2 年引入了一种结构简单的n c p 函数( 又称作 f i s c h e r - b u r m e i s t e r 函数，简称f b 函数) ，f b 函数及其它的n c p 函数 1 4 , 2 0 1 的出现 和半光滑理论的建立，进一步促进了非光滑方程组的发展。 而p a n g t 2 5 , 2 6 l 把一般变分不等式问题转化为非线性互补问题，改进下降牛顿法 为具有全局和局部收敛性的算法。f a c c h i n e i ，f i s c h e r 和k a n z o w t l l 基于f b 函数把 变分不等式转化为非线性方程组( w ) = 0 ，其中：r ”p 州专r 肿p + 卅的非光滑映射， 再引入价值函数 11 甲( w ) = 去( w ) 7 ( w ) = 去( w ) i | 2 ， 第一章绪论 则r t p ( x ，f ) 等价为无约束极小化问题m i n t f ( w ) 的求解。尽管不是连续可微的， 但证明甲连续可微，f a c c h i n e i 提出了半光滑牛顿法，并详细讨论了算法的全局收 敛和局部收敛性所需要的条件。其算法具有下面的特性： 1 和甲的函数值都较容易估计； 2 每一步迭代，仅需求解一个线性系统来得到搜索方向； 3 在合适的假设下，有全局收敛和超线性收敛，特别地，即使是退化问题也能 得到快速局部收敛性。 除了c 尸( f ) 外，把v i p ( x ，f ) 转化为非线性方程组的途径还有：m a r c o t t e 和 d u s s a u l t 2 ”首次使用间隙函数，提出了求解单调变分不等式的全局收敛算法； f u k u s h i m a l l lj 基于优化技巧，提出了快速局部收敛算法。非光滑化方法在实际中应 用非常广泛。 光滑化方法即把变分问题转化为与之等价的光滑方程组求解。它分为j a c o b i 光滑化方法、修正j a c o b i 光滑化方法和完全光滑化法。它的思想在于用一个光滑 函数日。( x ) 近似代替月( x ) ，通过求解光滑函数的解来逼近原问题的解。基于此， 通过引进扰动参数，光滑非光滑函数来构造光滑方程组是常用方法。在求解过程 中，保证扰动参数地专0 ：j a c o b i 光滑化方法中，参数需要严格的迭代规则； 而在修正j a c o b i 光滑化方法中，对于牛顿法而言，在牛顿方向提供满意的下降量 时，肛自动调节，当梯度方向为搜索方向时，需要遵守类似于j a c o b i 光滑化方 法中的迭代规则；而对于完全光滑化方法，则是将p 也看作变量加以迭代。 除此之外，w a n g l 3 2 l 在1 9 9 0 年的博士论文中使用嵌入法，把求解非线性方程 组的方法推广到变分不等式问题的求解，c h e n 和h a r k e r t 3 1 给出了基于四个扰动参 数的求解一般变分不等式的连续法，还有t s e n g t 4 8 】基于一个扰动参数的内点法， 这些方法都可以有效地求解变分不等式问题。 1 3 基本概念 本节给出本文用到的相关概念、记号以及数学背景知识。 函数g ：r “专掣被称为c 函数，如果g 是k 阶连续可微的；称g 是三c 函数， 如果g 是c 函数且第k 阶导数是局部l i p s c h i t z 连续的。如果g ：r ”一r 是c 1 函 数，则用v g 表示g 在x 点的梯度( 即雅克比矩阵的转置) 。全文l | i | 表示欧式范数。 定义1 2 t 7 1 函数f ：x 专r ”，有 ( 1 ) 若v x ，y x ，成立 一y ) r ( f ( x ) 一f ( y ) ) 0 ，则称f 是单调的； ( 2 ) 若v x ，y x ，成立 一y ) r ( 尸( x ) 一f ( y ) ) 1 l x y n 则称f 是关于强单调的。 定理1 31 2 2 1 令xgr ”是非空闭凸集，f ：x 寸r ”是强单调连续映射，则 v z p ( x ，f ) 有唯一解。 6 变分不等式的算法研究 引理1 4 ( r a d e m a c h e r 定理) 设xcr ”是开集，f ：x - - r ”在x 上是局部 l i p s c h i t z 连续，则f 在x 内几乎处处可微。 令g ：r ”- - r 是局部l i p s c h i t z i a n 函数。则由引理1 4 ，g 是几乎处处可微的。 定义1 5 称g 在x 处是半光滑的，如果对每个v r ”，存在 l i mh v ( 1 9 ) h a 0 ( j + 九，1 v - + v t 4 , o 如果g 在x r ”是半光滑的，则它在任意方向v 处都是方向可微的，且g 在工点沿 着方向，的方向导数g x ；v ) 等于极限( 1 9 ) 。 定义1 6 如果g 在x 处是半光滑的，则对任意d - - - ) 0 ，任意h o g ( x + d ) ，成 立 月口一g ( x ；d ) = o ( 1 l d 1 ) 。 ( 1 - 1 0 ) 称g 在x 处是强半光滑的 3 3 , 3 8 1 ，如果g 是半光滑的，且对任意d 专0 ，任意 h c o g ( x 4 - d ) ，成立 h d g ( x ；d ) = o ( t d l l 2 1 。( 1 - 1 1 ) 特别地，任意的c 1 函数都是半光滑的，以及任意的c 1 函数是强半光滑的。 定义1 7 设f ：r ”jr ”局部l i p s c h i t z 连续，如果极限 躲。 r h iv eo f ( x + t h ) ) 对任意的h r ”都存在，则称f ( x ) 在点x r ”处半光滑，如果f ( x ) 在r ”的每一点 都半光滑，则称f ( x ) 在r ”上半光滑。 引理1 8 设f ：r ”一r ”在点x r ”处半光滑，则 i i f ( x + h ) 一f ( x ) 一v h l l = o ( i h l ) ，v v o f ( x + t h ) ，h l 专0 。 定义1 9 设f ：r ”专r ”在点x r “处半光滑，如果 i i f ( x + 厅) 一f ( x ) 一砌8 = o ( h 0 2 ) ，v y o f ( x + t h ) ，i h - 0 ， 则称f ( x ) 在点x 处强半光滑。 定义1 1 0 称向量x x 满足线性无关约束规范( l c q ) ，如果积极不等式约束 的梯度， ) ( f i - f i i g ，( x 。) = o ) 是线性无关的。 为后面定理的证明，全章有下面两个假设成立： 假设1 1 i 假设f 是连续可微的，且在约束集x 上是强单调的。 假设1 1 2 条件三尼q 在x x 时成立，其中x 由( 1 8 ) 定义。 第一章绪论 1 4 本文结构 本文主要研究对象是其约束集x 形式为x = 扛r “ig ( x ) 0 ) 的变分不等式问 题，其中吕：r ”一r ( i i = 1 ，埘) ) 是凹函数r - 阶连续可微。对应的k k t 条件 为 f ( x ) - v g ( x ) 。y = 0 ， g ( x ) 一z = 0 ， ( 1 - 1 2 ) y 0 ，z 0 ，y 。z = 0 因此求解变分不等式转变为求解( x ，y ，z ) 尺舯肿”满足( 1 1 2 ) 的k k t 点。本 文主要基于k k t 条件( 1 1 2 ) ，分别利用光滑和半光滑的n c p 函数，改写k k t 条件，给出了两种求解的算法，从理论和数值上证明了算法的有效性。具体的， 本文的结构和主要研究内容概括如下： 第二章利用两个新的n c p 函数把( 1 1 2 ) 转化为半光滑的非线性等式系统，通 过价值函数的引入，使原问题等价于无约束极小化问题，给出半光滑牛顿算法求 解。证明了算法全局和局部二次收敛性，数值结果表明该算法是有效的。 第三章利用新的光滑函数把( 1 1 2 ) 转化为等价的光滑非线性方程组，提出了非 内点光滑算法求解该方程组，并给出了该算法的适定性和收敛性分析，数值结果 表明算法可以得到较好的解。 最后总结了本文的工作。 第二章半光滑化法 9 第二章半光滑化法 本章引进两个新的半光滑n c p 函数，将变分不等式的k k t 条件转化为半光 滑非线性方程组，进一步又利用价值函数转化为无约束极小化问题，提出了半光 滑化牛顿算法，并分析了算法的全局收敛性和局部超线性收敛，最后给出了数值 实验结果。 2 1n c p 函数及性质 1 9 9 2 年，f i s c h e r 提出了一种n c p 函数( 又称作f i s c h e r - b u r m e i s t e r 函数，简 称f b 函数) ： 驴f s ( a ，6 ) ：a + b 一厮 ( 2 1 ) 把不等式约束优化问题的k k t 条件改写为非光滑等式系统。f b 函数被广泛的应 用于求解各类问题，包括线性互补问题，非线性互补问题以及变分不等式问题。 f a c c h i n e i ，f i s c h e r 和k a n z o w t l l 在1 9 9 5 年将f b 函数用于求解变分不等式问题，他 们考虑变分不等式的约束集x 为x = 扛r ”ih ( x ) = 0 ，g ( x ) 0 ) ，则对应的k k t 条 件为 f ( x ) + v 办( x ) 1y v g ( x ) 7z = 0 ， 办 ) = 0 ， ( 2 2 ) g ( x ) o ，z o ，z 。g ( x ) = 0 ， 利用f b 函数，把( 2 2 ) 转化为非线性方程组 f ，l ( x ，y ，z ) 1 ( w ) = ( x ，y ，z ) - - ih ( x ) i = o 。 ( 2 3 ) i 纰( g ( x ) ，z ) j 再引入价值函数 甲( w ) ：丢西( w ) r ( 川：昙o ( w ) 0 2 ， ( 2 4 ) 则v i p ( x ，f ) 等价为无约束极小化问题m i n q - ( w ) 。f a c c h i n e i ，f i s c h e r 和k a n z o w 提出 了半光滑牛顿法求解该问题，并详细讨论了广义雅克比矩阵的非奇异性条件和价 值函数的稳定点条件。 基于文献川的思想和算法，本文考虑约束集x 为多面体形式，不失一般性， 设 x = x r ”ig ( x ) 0 ) ( 2 5 ) l o 变分不等式的算法研究 其中g ：r ”一r ”是连续函数，且吕：r ”专r ( ii = 1 ，脚) ) 是凹的且二阶连续可 微。 则对应变分不等式的k k t 条件，即求( x ，y ，z ) r ”肿”满足 f ( x ) - v g ( x ) 7y = 0 ， g ( x ) - z = 0 ( 2 6 ) y 0 ，z o ，y 。z = 0 容易验证，当满足一定的约束条件时，变分不等式的解等价于其k k t 条件的解。 为了改写变分不等式的k k t 条件，本章引入两个新的n c p 函数： 一是带参数允的n c p 函数1 7 】： 枞( 口，6 ) = ( a - b ) 2 + a a b 一口一b ( 2 7 ) 二是f b 函数和口+ 以的凸组合函数1 4 1 ： 屯( 口，6 ) = y 掣) f b ( 口，6 ) + ( 1 一y ) 口+ 良 ( 2 - 8 ) 用这两个新的n c p 函数代替f b 函数改写k k t 条件。 式( 2 7 ) 中，a 为固定参数且九( 0 , 4 ) 。由于根号下的表达式总是非负，即 一6 ) 2 + 勉6 0v a ，b r 。因此，九是适定的。特殊情况，当a = 2 时，函数办 为f b 函数；而且当a 一0 时，函数；近似于最小化函数。由此看出妒，涵盖了当前 求解变分不等式最重要的n c p 函数，因此研究；是非常有价值的。 式( 2 8 ) 中，y ( o ，1 ) 是任意固定参数，口+ = m a x ( o ，口) 。由于( 2 - 8 ) 是f b 函数和口+ 良的凸组合，则它不仅具有f b 函数的一切优点，而且q 6 + 的引入，还克 服了f b 的某些缺点。因此，研究屯也是非常有意义的。 引理2 1 ： ( 1 ) 对任意a ( 0 ，4 ) ，成立 屯 ，6 ) = 0 营a 0 ，b 0 ，a b = 0 其中 ( 2 ) 对任意y ( o ，1 ) ，成立 屯( 口，b ) = 0 营a 0 ，b 0 ，a b = 0 由引理2 1 ，则k k t 条件( 2 6 ) 等价的改写成非线性等式方程组： ( w ) = ( x ，y ，z ) = 0 ( 2 9 ) 。叻：，y ，加l ( x 垆, y , z z ， i 妒( y ，z )j 第二章半光滑化法 或者 l ( x ，y ，2 ) = f ( x ) 一v g ( x ) r y ， 爹( y ，z ) = ( 识( 咒，z 。) ，丸( ，z 。) ) ，r ” 妒( y ，z ) = ( 虫( 舅夕，z 1 ) ，虫( ，乙) ) 7 r ” 注意：函数识和函数丸在原点处都不可微，因此( 2 9 ) 是k k t 条件( 2 6 ) 的非 光滑化改写。 引进价值函数： 甲( 、叻= 去$ ( 叻7 ( w ) = 0 。( w ) 1 1 2 = 划尸( x ) 一v g ( x y y 1 2 + i g ( x ) 一z l l 2 + 愀舻) n 容易验证，m 不是处处连续可微的，但甲处处连续可微。因此，求解变分不等式 的k k t 条件( 2 6 ) 就等价于寻找无约束极小化问题 r n i n w ( w ) ( 2 1 1 ) 的全局解。 定理2 2 函数咖满足下面的性质： ( 1 ) 九是局部l i p s c h i t z 连续且处处方向可微的； ( 2 ) 识是强半光滑的； 证明：( 1 ) 显然，证明省略。 只证明( 2 ) ：首先，容易看出 ( a - 6 ) 2 + a a b = 0 营口= b = 0 ( 2 1 2 ) 因此，映射九在任意点( 口，6 ) ( o ，o ) 是三c 1 映射。特别地，戎在任，- 。 1 5 、( 口，6 ) ( o ，0 ) 是强半光滑的。所以，仅考虑在原点的情况。 为此，令d = ( 吃，以) r r 2 是一个任意的非零向量。则也在点0 + d ：d 处是光 滑的，使得h a 九( d ) 是唯一给定的： 日：f 毒堕垂磐生_ l ， 丝丝兰坠一1 ， 2 ( 以一吃) 2 + z a o a 62 ( 吃- d 0 2 + z a o d 6j 因而通过代数运算后，得 h d ：睾兽粤磐一吃一吃 、( 吃一巩) 2 + 旯吃吃 。 = 0 婶n d b ? p + 九d 囊b d n d b = 吼( 吃，以) 另一方面，也在原点沿着方向d 的方向导数为 1 2 变分不等式的算法研究 以( o ；俨躲业等地 = ，1 i m 。+ ( 以一畋) 2 + a 吃吃一吃一吃 = 九( 以，以) 因此，对任意非零向量d r 2 有l i d 一以( o ；d ) = 0 。特别地，在原点处函数九也是 强半光滑的。 定理2 3 1 1 4 1 函数丸：r 2 寸r 满足下面的性质： ( 1 ) 屯在r 2 ( 口，b ) i 口o ，b 0 ，a b = 0 ) 上是连续可微的； ( 2 ) 屯在r 2 上是强半光滑的； ( 3 ) 广义雅克比矩阵a 屯( 口，b ) 等于所有( v 口，) 的集合，( 屹，) 为 ( ) ：”一南卜南 + ( 1 刊( 以甄，q 砒髁妒( o ，o ) ，协 l y ( 1 一善，1 一p ) 如果( 口，b ) = ( o ，o ) ， 其中( 考，p ) 是任意向量，满足( 考，p ) 忙1 ，且 f 1 如果z o ， 昆+ = 【o ，1 】如果z = 0 ， ( 2 - 1 4 ) i o 如果z o ， 0 舯州。1 黄州川书l o , t 刚舻州0 ，l ， 6 ，( w ) = r b , 1 ( w ) + ( 1 一y ) 包2 ( w ) ( 2 - 2 3 ) f 只，如鼽 o ，z i 0 其中6 j ，。( w ) = 1 一下苦，匆，2 ( w ) = t y , z 。， 如瓢 o ，乙= o ，厄【o ，l 】 、”+ 彳 10 ， 否则 当( 只，乙) = ( 0 ，0 ) 时， q ( w ) = r ( 1 - 善，) ，匆( w ) = y ( 1 一n ) ，对任意( 善，n ) r 2 ，使得0 ( 考，p f ) l i i 。 证明：( 1 ) 由于f 是c 1 函数，g 是c 2 函数，因此向量值函数的前n + m 个 元素是连续可微的，于是通过计算直接得到g 的前n + m 行表达式。下面仅考虑g 的后m 行。由( 2 7 ) 的广义雅克比矩阵1 7 ，定理2 5 1 为： c o a x ( y ，z ) a 呶 l ( m ，z 1 ) x a 九，( ，z 。) 其中纵。表示九的第i 个元素。 若i 使得( 只，刁) ( 0 ，0 ) ，则九，是连续可微的，且 a 也，。( 咒，乙) = v 九，( 只，互) j ：(ji：；然-：】e。，c，c，(：ji：ij7i；糍t：)t；， 其中e i 表示第i 个元素为1 ，其余元素为0 的m 阶行向量。 若i 使得( 咒，z i ) = ( 0 ，0 ) ，则 a 九，j ( 只y ，刁) ( ( 专- 1 ) e ，0 ，0 ，( z 。一1 ) q ) 其中( 考，疋) r 2 ，使得0 ( 髻，石) 0 - 刁= 0 时，由定理2 6 的( 2 ) 及口f ，匆的表达式容易得到 q = 0 ，匆 0 ，则由( 2 - 2 6 ) 得g ( 3 ) = 0 ； 情况( 2 ) 若z j 乃= 0 时，由定理2 6 的( 2 ) 及q ，岛的表达式容易得到 a i o ，匆= 0 ，则由( 2 - 2 6 ) 得g ( 2 ) = 0 。 情况( 3 ) 若只 o ，7 , i 0 ，易得a l o ，包 0 ，则有( 2 2 6 ) 得g ：2 g ；3 0 。 情况( 4 ) 若 = 互= 0 ，则有g ；2 g ：3 0 。因而( 彰2 ) 7 谚3 o 。 情况( 1 ) 和( 2 ) 很容易证明结论，下面分析情形( 3 ) 和情形( 4 ) 。 给( 2 2 5 ) 前乘以( g ；2 ) 7 ，得 ( 藓2 ) 7 a q o = ( 酢2 ) q3 0 给( 2 - 2 4 ) 前乘以( 谚1 ) r 得 ( 一) ，n q 1 = ( ) 7 彳r g 2 0 由于假设1 1 l 成立，即f 是强单调的，则雅克比矩阵v f ( x ) 是正定的；又由 约束集定义，所有吕都是凹函数，则其雅克比矩阵驴g ，( x ) ( f ，) 是半正定矩阵。因 此，由h = v f ( x ) - 乃v 2 & ( x ) 得，对v w 尺”xr 7 xr 栅，有h 是正定矩阵。 由于h 是正定酶：因此g ( i ) ：0 。由( 3 1 0 ) 得q ( 3 ) ：0 ，且由( 2 2 4 ) ， o = a r = g ；2 v g ( x 木) 。 f ， 又在情况(