（应用数学专业论文）求解非线性互补问题的光滑牛顿法.pdf

摘要 非线性互补问题是一类非常重要的优化问题，它在工程、经济与交通平衡等 领域有着广泛的应用。因此，对非线性互补问题的研究具有重要意义。目前己产 生了很多求解方法，也得到了全局和局部收敛结果。近年来多采用互补函数把非 线性互补问题转化为方程组的形式来求解。 本文首先基于陈小红等2 0 0 6 年提出的光滑函数，根据现有的各种光滑牛顿法 思想和半光滑理论，得到了求解尸o 函数非线性互补问题的完全光滑牛顿法，并证 明了算法的适定性，通过控制函数的引入，得到了算法的全局收敛性。然后介绍 了一种求解非线性互补问题的修正光滑牛顿法，它将光滑因子看成是参数，其选 择形式和迭代格式简单，并在适当的假设条件下，证明了该算法具有全局收敛性。 关键字：非线性互补问题互补函数光滑牛顿法全局收敛性 a b s t r a c t n o n l i n e a rc o m p l 锄e n t 撕t ) ，p r o b l e mi sa i l i m p o r t a n t c l a s so fm a t h 锄a t i c a l o p t i m i z a t i o np r o b l 锄，w h i c hh a sw i d e 印p l i c a t i o n si nm a n yf i e l d ss u c ha se n g i n e 嘶n g ， e c o n o m i c sa l l dt r a m ce q u i l i b r i u mp r o b l 啪t h e r e f o r e ，i “ss i 印i f i c a n tt os t u d ym e a l g o r i t h n l sf o rs 0 1 v i n gn o n l i n e a rc o m p l e m e n t 撕t yp r o b l e m s u pt on o wt h e r eh a v e d e v e l o p e dm a n ym e t h o d st os 0 1 v ei ta n dg l o b a la n d1 0 c a lc o l e r g e n c er e s u l t sh a v ea l s o b e a no b t a i n e d i nr e c e n ty e a r sm o r ea t t e n t i o nh a sb e e l ld e v o t e dt o r e f b n n u l a t i n gt h e n o n l i n e a rc o m p l e m e n t a r i t yp r o b l e ma sas y s t e mo fn o n - s m o o t he q u a t i o n sb yu s i n gs o m e n c p 如n c t i o n i nt h i sp a p b a s e do nt h es m o o t h 如n c t i o n 酉v e nb yc h e l lx i a o h o n gi n2 0 0 6 ，m e c o n c 印to ft h es m o o m i n gn e w t o nm e t h o d st h a te x i s ta i l dt h es e m i - s m o o t ht h e o 以 w er e c e i v ea s m o o t h i n gn e w t o n m e t h o df o r s o l v i n gr 一向n c t i o n n o n l i n e a r c o m p l e i l l e n t 州t yp r o b l e l n t 1 1 ea l g o 枷珊h a sb e e i lp r o v e dt ob ew e l l - d e f i n e d a tm e s a m et i m e ，w ea l s op r o v em ea l g o r i t i s 酉o b a lc o n v e r g e i l c eu n d e rac o n t r o lm n c t i o n t h a th a se x i s t e d t h e nam o d i f i e d s m o o t h i n g n e w t o nf o r s 0 1 v i n g n o n l i n e a r c o m p l e m m t a r i t yp r o b l e mi sp r o p o s e d t h es m o o m i n gf a c t o ri ss e e n 嬲ap a r 锄e t e ri n o u rp a p e r t h ef o m 锄di t e r a t i o ns c h e m eo ft h es m o o t h i n gp a r 锄e t e ra r es i m p l e i ti s p r o v e dt h a tm em e m o dh a s 酉o b a lc o n v e r g e n c ei np r o p e rc o n d i t i o n s k e y w o r d ： n o n k n e a rc o m p l e m e n t a r i 够p r o b l e m c o m p l e m e n t a r i 坶f u n c t i o n s m o o t h i n g n e w t o nm e t h o d g l o b a lc o n v e r g e n c e 西安电子科技大学 学位论文创新性声明 秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导 师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注 和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果； 也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明 并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切的法律责任。 本人签名：j 隆扯 日期呻弓j 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。学校有权保 留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内 容，可以允许采用影印、缩印或其它复制手段保存论文。同时本人保证，毕业后 结合学位论文研究课题再撰写的文章一律署名单位为西安电子科技大学。 日期型型! 第一章绪论 第一章绪论弟一早 三百t 匕 1 1 互补问题的提出 互补l 司题是一类重要的优化i 司题，是从线性规划和非线性规划推广而采的。 它在力学、交通、经济、金融等领域有着广泛的应用【1 捌。 互补问题的标准形式是：给定向量函数，( 工) ：尺”一r ”，求一向量x 尺”，使 其满足下列关系： 石o ，f ( 力o ，z r ，( 力= o( 1 - 1 ) 其中，是连续可微的。 当f ( 工) 是线性函数( 即f ( 石) = 尬+ g ，m r “，g 尺”) 时，称( 1 - 1 ) 为线性互补 问题，记为三c p ( m ，g ) ；否则称为非线性互补问题，记为i c p ( 尸) 。 互补问题广泛的存在于最优化问题中，最优化中的许多问题都可以转化为互 补问题求解，下面分别给出说明。 1 考虑线性规划问题【3 】： c 幽 警絮嚣。 i s j 爿x 6 ，工o 其中彳r ，6 尺”，c r ”。( 三尸) 的对偶问题是： ( d p ) 懈g ? 卜j ， 【s j 么1y c ，y o 设而，分别是( 三p ) 和( d p ) 的可行解，由【3 1 知而，同为最优解的充要条件是： c t x o = b l y o 设z = ； 尺”+ m ，定义厅：r 4 + m 争r ”+ ”女口下： 坼，= 搿h 荆z 1 妣九斗v ) z y 卜阳w 朋k y k c k 咖 2求解非线性互补问题的光滑牛顿法 这样求解( p ) 就等价于： 求z 。r 肿”使得： z o 0 ，j l l ( z o ) o ，z o 了五( z o ) = 0 显然这是一个线性互补问题。 2 考虑二次规划( q p p ) 【4 】： 耐n + 胁 j f 彳r z 易z 0 不难求的( 1 2 ) 的k t 条件为： g + 月x = 彳允+ “，彳r z = 6 + ， a o ，”o ，o ，x o 再定义m = ；了 ，g = 三 ，w = ： ，z = 三 ， 则由( 1 3 ) 得到： w 一 勿= g ，w o ，z o ，z = o 显然，( 1 4 ) 为线性互补问题。 3 考虑非线性规化( 舭p ) ： m i n 厂( x ) s f g f ( x ) o ，f = 1 ，l ，x o 其中，连续可微，f = 1 ，聊令 肘 ( 石，“) = 厂( x ) + 蜀( x ) f 聋l 则由约束最优化的k - t 条件： 将上面的式子展开写成： 夥( x ) + 吩( x ) 一五= o f = l x o ，“= 【”i ，“。】r ，工r 五= o “r g ( 力= o ，g ( x ) = 【g 。( z ) ，g 。( x ) 】r ( 1 - 2 ) ( 1 - 3 ) ( 1 4 ) 第一章绪论 3 望生窒生尘：j i l l ( x ，“) ，皇墨宝生尘：吃+ ，( x ，“) ， c “ 皇拿窒生堕：吃( 五“) ，皇笔窒蔓堕：吃+ 。( x ，“) ， 吼咖。 若令z = 习， ( z ) = h ( 五“) 一，吃+ 。( 五“澎，则k t 条件等价于求： 这正是互补问题。 z 群”，使得 ( z ) 群棚且z r j i l ( z ) = o ， 1 2 互补问题模型 由式( 1 - 1 ) 定义的互补问题为标准的线性互补问题或非线性互补问题，是互补 问题中最简单的形式，也是研究最广泛的。但在实际应用中，常常会遇到与互补 问题相关的更复杂的问题【5 】，下面简要的给出一些互补问题推广的模型。 1 混合线性互补问题( 尬c p ) 其一般形式是：给定彳r n x ”，曰r “，c 尺”， d 尺”。”，厂尺”和6 r “，求z 尺”，j ，r ”，s 尺“且满足： f 砂+ 黜+ c = o 印+ 既+ 厂= o( 1 5 ) i x o ，j o ，x r s = o 在式( 1 5 ) 中，若彳为非奇异矩阵，则y = 一4 一( m + c ) ，( 1 - 5 ) 式可进一步表述为线 性互补问题三c p ( e d 爿- 1 召，一d _ - 1 c ) 。 2 水平线性互补问题( 肌c p ( m ，g ) ) 其一般形式是：给定r “，g r “，和 必尺椰，求x r “j 尺“且满足： 竺+ ，篡羔。 m 6 ， l 石o ，j 0 ，石7 j = 0 、 若= ，时，( 1 6 ) 式即为标准的线性互补问题；若为非奇异矩阵，则上式等价于 线性互补问题三c p ( 一- 1 肘，一- 1 9 ) 。 3 竖直线性互补问题( 兕c p ( m ，g ) ) 令m 。，鸠，心和g t ，9 2 ，口8 分别为一列矩阵 4求解非线性互补问题的光滑牛顿法 和一列矢量，其中m ，r ”，g 尺“，定义竖直矩阵m 和矢量g 为： m 蚓舻 ；i ， 即m 是一所，l 矩阵，g 是一m 矢量。竖直线性互补问题是：寻求矢量工尺”，满 足： m 石o ，m j x + g o ，蕾已( m f x + g ) ，2 o ，f = l ，2 ，以 显然如果他= 1 ，( 待1 ，2 ，1 ) ，则兕c p ( m ，g ) 化为普通的线性互补问题。 4 混合互补问题即给定函数 厂：r 1 一r ”， 尺u ) ”，“ 尺u + ”，且， ”， 求x 尺“，w 尺“，r ”满足下式： 厂( x ) 一w + y = o x 一，o ，w 0 ，( x 一，) r w = o “一x o ，o ，( “一x ) 7 y = o 当，= 埘，“= 佃时，上式就是方程组厂( x ) = o 。 当，= o ，“= o o 混合互补问题就转化为了标准非线性互补问题。 将非线性互补问题以及混合互补问题做更进一步的推广，可得到变分不等式， 即：给定函数厂：彤一尺“，矽足g 尺”，且满足： v 夕k ，( y z ) 7 厂( x ) o 当k = 工ix o 时，上式退化为标准非线性互补问题； 当尺为矩形即k = 兀 ，吩】，( 一 o 为步长。然而它的收敛性需要f 是强单调的映射为此，k o 印e l e v i c h ( 1 9 7 6 ) 提出了外梯度法，即 + l = 【以一口f ( 一口，( ) 】+ ) 】+ 它的收敛性仅要求f ( x ) 单调且解集x + 非空。s u n 【3 6 3 7 】应用a 姗i j o 搜索技术得到， 在f ( x ) 伪单调且x + 非空的假设下，迭代点列收敛到x 。 最近，s o l o d o v 和t s e n g 【3 8 】给出了一个g l p 投影法的一般迭代格式： + 1 = ，卟p 1 毛( 一口f ( ) + ) 这里， o 是步长，= ，一口f ( 当f ( x ) = 胁+ g 时，死= j + 口m r ) ，口 0 使得艺 强单调，p 是选定的正定矩阵。 投影类算法的优点是格式简单、存储最小、保稀疏性、易于计算机实现。另 外，因为这种方法在迭代中不用去解线性方程组，所以每步的计算t 都非常小。但 它的不足是至多只有线性收敛速度，所以k a n z o 给出建议当互补问题的规模很大或 f ( x ) 的雅可比矩阵不存在或不易求时再考虑使用这类方法。 5 无约束优化法 这种方法就是把互补问题转化为一个与之等价的可微无约束优化问题，然后 用某种大范围或n e 叭o n 类型的算法求解。由于无约束优化的求解方法比较成熟， 因此，对这类方法的研究重心在于如何转化上。m a n g a s 撕觚和s 0 1 0 d o v 【3 9 】先于他人 第二章基础知识 1 3 给出了一个可微的势函数： 椰( x ) = x ，( x ) + - 去 | i ( 一口f ( 工) + 石) + 1 1 2 一1 2 z c ri ” ” + f | ( _ 纵+ ，( 功) + l ，( 琊 ，口 o 实际上，埘( z ) 可以由可微的c p 函数： 腓( 口，6 ) = 口6 + 去( m a x 2 o ，口一口6 ) 一日2 + m a x 2 。，6 一口口 - 一6 2 ) 按下式生成： 埘( x ) = ( ，( 誓) ) ( 2 4 ) f = l 文【删研究了上式与互补问题( 1 1 ) 之间的关系，如果f ( 工) 是可微的且 ( ，) 正定， 那么( 2 - 4 ) 的稳定性与( 1 1 ) 的解是等价的。 近年来，对可微无约束优化法的研究兴趣转向增加非负约束，因为实际计算 表明，仅用无约束优化求出的互补问题的解并不理想。为此m o r e 【4 1 1 给出了一个可 行的信赖域方法，w a n g m o n t e i m p a n 一2 8 】提出了一个降势内点法，这方面的方法也 逐渐增多，如文献【4 2 4 3 1 6 磨光方程与非内点法 前面的光滑牛顿法存在一个弱点，即方程的h ( x ) = 0 的j a c o b i a n 矩阵v 日( 功 难于计算。自然地，可以考虑用一个光滑函数日( x ，口) 近似代替日( z ) ( 这里日( x ，口) 称为磨光函数，口称为磨光参数，日( 工，o ) = 日( x ) ) ，这样可以转而求解日( x ，口) = o ， 如果在迭代过程中能自动调整口到0 ，则称之为连续磨光方程；进一步，如果连续 不断地压缩口到0 ，则称为非内点法。后者具有路径跟踪法的主要特征，但它能取 任何初始点及充分选取步长，这恰好能克服内点法的弱点，所以自它由 c h e n h a r k e r h 钉于1 9 9 3 年提出来以后，吸引了众多学者的注意，并取得了迅速发展。 2 2 互补问题解的存在性 迄今为止关于互补问题的解的存在性、唯一性、解集的有界性误差性以及其 他相关问题等，大量综合性文献中已有广泛研究，这一节我们将叙述这些基本的 理论结果，具体可参见文献【6 ，4 5 ，4 6 ，4 7 】。 1 4求解1 线性互补问题的光滑牛顿法 定义2 2 1 【6 】若存在向量x 尺”，使得石+ 0 ，( z ) 0 成立，则称互补问题是 可行的；进一步若有x f ( x ) = 0 成立，则称x 是互补问题的一个解。 定义2 2 2 【6 】设矩阵m r ，如果对任意的x r ”，x 0 有x r 尬0 ，则称 m 是半正定矩阵；若，欣 o ，则称m 是正定矩阵。 定义2 2 3 【6 1 设矩阵m 尺，如果它的元素都是正数，则称m 是正矩阵。 定义2 2 4 【6 】设矩阵m r 删，如果对任意给定的向量x ，o x o 都有 工r 尬0 ，则称m 为协正定矩阵；若，施 0 ，称m 为严格协正定矩阵。 定义2 2 5 【6 】设矩阵m r 脚，如果对任意给定的向量x ，o _ ) c o ，存在 七，使得而 o ，( 胍) i o ，则称m 为半单调矩阵；若五 0 ，( 施) t o ，则称m 为严格半单调矩阵。 定义2 2 6 【6 】设矩阵m 尺，如果对任意的向量x o ，存在正对角矩阵人， 使得，( m ) x o ，则称m 是尸矩阵。 定义2 2 7 【6 】设矩阵m r 脚，若它的非对角元都是非正的，则称m 是z 矩阵。 在介绍了这些基本定义的基础上，我们介绍互补问题解的存在性定理。 引理2 2 1 【4 5 1 若m r 棚为正定矩阵，则对任意g r “，三凹( m ，g ) 有唯一解。 引理2 2 2 【4 5 】设m 尺为半正定矩阵，若三c p ( m ，g ) 可行，则其解存在。 引理2 2 3 【4 5 】设m r 舢正矩阵，则对任意给定的g 彤，c p ( 膨，q ) 有解。 引理2 2 4 【4 5 1 设必r 棚为协正定矩阵，则对任意的g 彤，c 尸( m ，g ) 有解。 引理2 2 5 4 5 1 设m r 嗍为严格协正定矩阵，则对任意g 尺”，三c p ( 肘，g ) 有 解。 引理2 2 6 4 5 】若二次函数厂( 曲= ，( 尬+ g ) 对任意的x o 有下界，则对任意 的m r “，g r “，g o ，三c p ( m ，g ) 有解。 引理2 2 7 h 刀设m 尺嗍为半单调矩阵，则对任意g 尺”，g o ，c p ( m ，g ) 有 第二章基础知识1 5 解。 引理2 2 8 f 4 刀设m 尺删为严格半单调矩阵，则对任意的g r ”，g 0 ， 三c p ( m ，g ) 有解。 引理2 2 9 【4 7 】设m r 是尸矩阵的充分必要条件是：对任意的给定的 g 尺“，c 尸( m ，g ) 有解。 引理2 2 1 0 【4 7 】设m 尺蝴是z 矩阵，对任意给定的g 尺“，若三c p ( m ，g ) 可 行，则解存在。 引理2 2 1 l 【4 7 】设膨r 棚是具有正对角元的矩阵，对任意给定的g ， 三c 尸( 必，g ) 有唯一解。 定义2 2 8 6 1令cc 尺”是一非空集，f ：c r “是一映射，= ( z ，五，z ) r ， 如果存在常数口 o ，对任意的五y c ，x y ，存在下标七= 七( z ，j ，) ，l 七刀，使得 儿，( 一以) ( 以( x ) 一五( y ) ) 口忙一圳2 ，则称f 是c 的一致尸映射。 引理2 2 1 2 6 1 若f ：掣一r 4 是连续的一致尸映射，则互补问题( 1 1 ) 有唯一解。 引理2 2 1 3 【6 1 若，：群一尺”是一连续映射，如果f 不存在关于磁的例外簇， 则互补问题( 1 1 ) 有唯一解。 引理2 2 1 4 【6 】若m 尺脚是严格共正矩阵，则对任意给定的g 彤，则 三c p ( m ，g ) 有解，且解集有界。 2 3 基本概念和定理 我们考虑非线性互补c p ( f ) 问题，为了以后的方便，便在这一节中，首先给 出一些定义、引理以及定理，它们大都出现在文献【5 m 5 3 1 。 定义2 3 1 【5 0 】若矩阵膨尺帅的每个主子式都非负，即对任意的x o ，x r 一， 存在f ，使得五0 且再( 膨吐o ，则称m 是届矩阵。 定义2 3 2 例若矩阵m r 棚的每个主子式都为正，即对任意的x 0 ，工尺一， 1 6 求解1 仁线性互补问题的光滑牛顿法 存在f ，使得五0 且薯( 旅) ， o ，则称m 是p 矩阵。 显然p 矩阵一定是昂矩阵。 定义2 3 3 5 0 1 设函数f ：尺”专尺4 ，如果对比，y r 一，x y ，存在一个指标 乇，使气，且( 气一“) ( 气( 工) 一。( y ) ) o ，则称f 是异函数。 定义2 3 4 【5 0 】设，：月”专月一，如果： 理磐( 薯一m ) ( 曩( x ) 一只( y ) ) o 成立，其中工，y 尺“，工y ，那么称，是p 函数。 定义2 3 5 【5 川设，：月”哼月一，如果： 恐警( 薯一咒) ( 巧( x ) 一e ( y ) ) 忙一y 0 2 ， 成立，其中x ，y 彤， o 为常数，那么称f 是一致p 函数。 注 如果f ( x ) 是线性函数，即f ( 石) = 尬+ g ，那么，是p 函数，当且仅当 即( x ) = 肘r 是p 一矩阵，当时当f 是非线性函数时，如果v ，( 工) 是p 函数，只有f 是一致p 一函数时，才有v f ( x ) 是p 一矩阵。 关于层函数和昂矩阵有如下引理： 引理2 3 1 5 田 映射f ：尺”专月“连续可微，则f 为昂函数当且仅当对任意的 z r “，在x 处的j a c o b i a i l 矩阵v f ( x ) 为只矩阵。 借助朋凹函数，可以将式( 1 1 ) 描述的非线性互补问题删f ) 转化为与之等 价的非线性方程组。所谓的凹函数是这样描述的：设函数也尺z 专r ，若 ( 口，6 ) = o 等价于口0 ，6 0 ，口6 = 0 ，则称函数是一个c p 函数。下面是几个常 用的脚函数： ( 口) 丸i 。( 口，功= n l i n ( 口，6 ) ( 6 ) 矽髓( 口，6 ) = 口2 + 6 2 一口一6 ( c ) 加，功= 铂+ 圭m i n 2 o ，口+ 6 ) 第二章基础知识 1 7 ( d )矽( 口，6 ) = ( 口一6 ) 2 一口i 口i 一6 1 6 l 其中( a ) 叫最小化( m i n ) 函数，是最简单的( 函数；( b ) 是f i s c h 盯- b l 舢e i s t e r 函划3 4 1 ， 在口= 6 = 0 处不可微( 非光滑) ；( c ) 和( d ) 是在整个尺2 空间可微( 光滑) 的函数，其中( d ) 来自于m a n g a s 撕a n 【5 0 1 。 对于任意给定的c 尸函数，定义映射：尺“专尺”如下： 吣，慑黝 则显然石+ 是非线性互补问题i 凹( f ) 解的充要条件是x 是非线性方程组m ( x ) = 0 定理2 3 1 【5 2 】设p ( f ) 是严格增加的函数，并且矽( f ) = 0 ，则： ( 口，6 ) = 口( 1 口一6 i ) 一口( 口) 一口( 6 ) 妒( o ，6 ) = 臼( 1 6 i ) 一目( o ) 一矽( 6 ) = 口( 6 ) 一矽( 6 ) = o 反之，设( 口，6 ) = o ，即 口( i 口一6 1 ) 一汐( 口) 一秒( 6 ) = o o 秒( i 口一6 i ) = 护( 口) + 9 ( 6 ) o ，l 口一6 l = a 一6 秒( 1 口一6 i ) = 口( 口一6 ) o ，6 o ，不妨设口6 ，则 秒( i 口一6 i ) = 目( 6 一口) 口( 口) + 伙b ) 此时有：( 口，6 ) o 是常数，则称f ：尺”专r ”在工点局部l i p s c h i t z 连续。 定义2 3 7 嘲设g ：尺“j r ”局部l i p s c h i t z 连续， 如果l i m f y “对任何 p e a g ( + 咖) 、 7 | l i 尺”都存在，则g 在z 处半光滑。 注根据定义2 3 7 ，有： 牌坐等型= ，。船0 j l l ) ( 2 - 6 ) 斗fy e a g ( j + 曲) 、 ， 半光滑的概念在三c 1 规划的算法收敛性分析中起着重要的作用。实际上，许多 类函数，比如光滑函数，分片光滑函数，凸函数和拟凸函数都是半光滑函数。此 外，半光滑函数的和、查、数乘和复合函数也是半光滑函数。 定理2 3 4 【5 3 】 设函数f ：尺一寸r 一局部l i p s c h i t z 连续，以下陈述等价： 1 ) f 在石处半光滑； 2 ) ( 3 3 ) 式右边对所有矗依范数一致收敛； 3 ) 对任何y a f + j 1 1 ) ，i i lj 0 有： 妇一尸( z ， ) = p ( ) ( 2 7 ) 4 ) ：黔堕铲2 。 ( 2 8 ) 定理2 3 5 【5 3 】 设函数f ：尺“专r 4 局部l i p s c h i t z 连续，其中曩是f 的分量函 数，如果墨在点x 处半光滑，那么f 在点x 处半光滑。 证明：对x + i l d f ， 一o ，有 i l ， + j l ；j 1 ) 一，( 石五) 0 窆i 互o + 乃；j j i ) 一巧( 五五) i 2 0求解1 f 线性互补问题的光滑牛顿法 对f 利用式( 2 - 7 ) ，有 f ( x + j l z ；j i l ) 一曩( x ；j 1 1 ) = d ( 0 矗0 ) ， v f 根据定理2 3 4 有f 在点x 处半光滑。 定义2 3 8 【5 2 】对任何y 卯 + j j i ) ，乃专o ，如果： y j j l 一，( x ，j 1 1 ) = d ( p ) 就称f 在点x 处p 一阶半光滑，其中o o 【- ( “，吒，e ( x ) ) j h u a n gz h e n 哥h a i ，h a nj i y e 和c h e nz h o n 争w e n 对于m i n 函数提出了另一种光 滑函【5 6 】： ( 邺，6 ) ：( 1 + “) ( 以+ 6 ) 一而i 而j 汀石“ o 由光滑函数九舵( “，口，6 ) 得到的光滑逼近方程： l ( “，五，e ( x ) ) i ( “，功= i ； l = o “ o l ( “，c ( x ) ) j c k a n z o w 对f i s c h e r - b u n l l i s t e r 函数给出了一种光滑函划5 6 】： 矽( “，口，6 ) = 口2 + 6 2 + “2 一a 一6 “ o 利用上式也得到了互补问题的一种光滑逼近方程。 3 2 新的光滑函数及其性质 矽阳( 口，6 ) = 口2 + 6 2 一日一6 c p 函数给出了一种新的求解层函数非线性互补问题的光滑牛顿法，该算法具有 l 纸( 五互( x ) ) i il 似垆l ； l - 0 【- ( ，e ( x ) ) j 第三章光滑牛顿法的构造和收敛性分析 2 3 由于函数如在零点不可微，导致传统求解方程组的方法不能直接应用到纰，为 此，陈小红等给出了它的光滑形式【5 7 】： f 口+ 6 一而，而 烈从功2 h 一掣一等，厮 o 为光滑参数这个函数具有的性质如下： 引理3 1对任意的 0 ，( 以，6 ) r 2 ，有： ! 姆矽( ，口，6 ) = 九( 口，6 ) 训 一 这个引理的证明很简单，在此不加说明。 引理3 2 对任意的m 0 ，鸬 o ，( 口，6 ) r 2 i ( 以，口，6 ) 一矽( 鸬，口，6 ) l i “一心i 证明 如果“= 鸬 o ，结论自然成立。所以只需考虑“鸬的情形，不妨假设 “ 鸬，下面分三种情况讨论： ( i ) 若“ 鸬口2 + 6 2 ，则矽( h ，口，6 ) = ( 鸬，口，6 ) ，结论显然成立。 ( i i ) 若l 口2 + 6 2 2 。 贝i j 矽( 一，口，6 ) = 口+ 6 一口2 + 6 2 ， 矽厶功6 一等一譬 因为 窖堡+ 譬厮 2 鸬 2 所以 地以旷舭a 圳- l 筹+ 譬一 = 警+ 譬一厮 = 一+ 二_ 三一、，履+ ， 2 鸬 2 等+ 等一以= i 鸬一“i 22 “ ”“。 ( i i i ) 若厮 o ) 为日的光滑逼近函数，如果r 不依赖于z ， 则称饥( ) 为日的一致光滑逼近函数。 为了以后叙述方便，首先给出如下的定义。 令：z = ( ，x ) r + r 1 ，定义： i 矽( 而，互( z ) ) i ( z ) = i ； l ( 3 2 ) l 矽( 吒，c ( 力) j 一 p 3 ， i 痧( ，五，正( 砌i 其中 芦( z ) = i ； i ( 3 4 ) 【矽( ，吒，e ( x ) ) j 引理3 3 如果及为分别由式( 4 - 2 ) 和( 4 - 4 ) 所定义，则“为的一致光滑 ( 工) 一( x ) f l ；_ 懋i ( ，而，( 薯) ) 一( 五，( ) ) i 现 根据一致光滑逼近函数定义知o 。为的一致光滑逼近函数。 啪忍驴巨三嚣三： 口 肿忍垆仁罗l 卜昙 咖以垆眵l 卜云 厮 厮 0 ，吼，纯，都是连续的，且有 0 纯( ，口，6 ) 2 ， o 纯( ，口，6 ) 2 引理3 4 5 7 1 ：设何：足+ r ”j 足川由式( 4 3 ) 定义，那么 ( 1 ) h 在r + 尺”连续可微，且其j a c o b i a i l 矩阵为： 其中 及 哟讹，+ 品m v ( z ) = w c 纥( ，薯，( 玉) ) d l ( z ) = 硪昭k ( z ) ) d 2 ( z ) = 抛 包( z ) ) 姒护仁字= 2 6 求解1 e 线性互补问题的光滑牛顿法 驰，：卜燕劬( z ) 1 1 一型f 口( z ) 这里，指标集口( z ) = f ：0 了了丽 o ，令i = ( 觞，o ) 及+ r ”，z 。是彤 中任意一点。置z 。= ( 觞，石。) ，选择( o ，1 ) 使得8 日( z 。) 8 o ； ( 2 ) 对任意的七0 ，有z q ； ( 3 ) 段) 是一个单调下降序列。 证明根据上述定理的证明知( 1 ) 成立 ( 2 )根据初始点的选取知z o q ，假设对某个七，有z q ，下证z n l q 即证 以+ ，0 日( z 川) i f ( z “1 ) 使用归纳法证明分两种情况证明。 如果1 1 日( z ) l l 1 ，那么p ( z ) = ，进而 以+ ，一风0 日( z “1 ) l l 夕( z “1 ) = + 兄一风l ( z “1 ) 0 p ( z 1 ) = ( 1 一) + 见风0 ( z ) 8 p ( z ) 一觞0 h ( z “1 ) 0 p ( z 1 ) ( 1 一名) + a 。l i h ( z 。) 0 p ( z ) 一触。1 1 日( z 。) 0 ( 1 一名) 0 日( z ) 0 p ( z ) + 力风0 日( z ) 4 户( z ) 一鳓0 日( z ) 0 p ( z ) = 0 如果0 日( z ) | l o ，因为z q ，所以z q 一方面由算法3 1 步骤3 知： 0 ( z + 万一心) j l ( 1 一盯( 1 一屈) 万肌1 ) 日( z 。) 0 ( 3 - 6 ) 两边求极限得 日( z ) r 日( z ) z 一( 1 一纸) 1 1 日( z + ) l j 2 另一方面对( 3 5 ) 式两边求极限后变形得 日o ) r 日( z + ) ，= 一j p ( z ) l j 2 + 肛日( z ) rj 1 日( z + ) 0 五 = 一1 1 日( z ) 0 2 + 肛熊0 日( z + ) 0 2 ( 3 7 ) 有( 3 6 ) 和( 3 7 ) 得： 肛风0 日( z ) 1 1 2 ( 1 一仃( 1 一钒) ) 0 日( z ) 0 2 又根据反的定义知反s 3 0求解非线性互补问题的光滑牛顿法 所以“o ( 1 一盯( 1 一芦k ) ) ，即( 1 一盯) ( 1 一芦) o 。 这与盯 。都成立。 其中( 1 ) 使得日( ，x ) 半光滑，并且保证有定义；( 2 ) 使得h ( ，z ) = 0 必然有= 0 ， 从而h ( ，x ) = o 对应的x 是c p ( f ) 的解；( 3 ) 意味着 o ，即使得迭代点列 段) 保持为正，并不断下降。 算法4 1 【删 步骤o ( 初始步) ：选取x 。，取p ，刁( o ，1 ) ，盯( o ，丢) ，口 。，适当选取正整数。，令 成= l | ( ，) l l ，c = i ，风= 乏风，z 。= ( ，p ) ，尼= o 步骤l ( 终止条件判断) ：如果v 甲( ) = o ，则停止 步骤2 ( 牛顿步) ：求解如下的线性方程组得& 尺叶1 ： 日( z ) & = 一何( z ) ( 4 - 4 ) 设聊。是 o ，1 ，2 乙。) 中满足下式的最小非负整数，l ： 厂( z + p 臃z 七) ( 1 2 叩胛) 厂( z ) ( 4 - 5 ) 计算五= p ，z = z 。+ 五z ，展+ ，= 展令七= 后+ 1 ，转步骤1 步骤3 ( 梯度步) ：如果方程组( 4 - 4 ) 不可解或者 o ，1 ，2 乙。 中没有正整数满足( 4 5 ) ， 那么取： 第四章修正的光滑牛顿法 3 3 缸= 一v 甲( )( 4 6 ) 同时在 o ，l ，2 中找到最小的正整数聊。满足下式： 甲( z 女+ p 血) 甲( z ) 一印仉0 敏8 2 ( 4 7 ) 令五= p ，+ 1 = + 磊血，转下一步； 步骤4 ( 梯度步继续) ：如果下式成立 川) 陋a x 椴，扣( 一段( 1 1 ) ( 4 - 8 ) 则令展+ 。= 0 ( x “1 ) i i 并取以+ 。： 。 剑n 件9 ， 如果( 4 - 8 ) 式不成立，那么令展+ 。= 履，并取以+ 。： 。 。+ 。二n 业竺垒掣，譬 c 4 一。， 令z “1 = ( 川+ 1 ) ，七= 七+ 1 ，转步骤1 算法4 1 的几点说明： 1 在步骤2 中，搜索技巧( 4 5 ) 与标准的加m i j o 技巧略有不同( 给定了聊。的上限 。) ，这主要是为了保证迭代的步长不会过小( 步长以不会小于p k ) ，这一技巧 使得算法不仅全局收敛，还具有很快的局部收敛率。如果( 4 5 ) 成立，则段+ 。也在z 1 中自动产生，并有厂( z 川) 刁( z ) ，其中孑= 1 2 0 p k 一心，所以以+ - = 以+ 以从 ( 1 - 以) 以，另一方面，明显以 0 故以+ 。以；另外，当执行步骤4 时，有o o 。 4 2 新提出的修正光滑牛顿法 在本小节中，我们将光滑因子看作是一个参数来构造新的修正光滑牛顿法。 4 2 1 算法的构造 算法4 2 ( 修正的光滑n e w t o n 法) ： 步骤o ( 初始化) 选取初始点石。尺”，0 盯，p ，心，氏，成，展 0 ；后= o 步骤1 ( 终止条件) 若忙以( ) l l & ( 4 1 4 ) = 引聋主 件均 后= 后+ 1 ，转步骤1 算法的几点说明： 1 如果牛顿方程( ) + ：( 矿) 缸= o 有解，设为血，那么 v 甲( ) r 缸= ：( ) ! ( ) 缸 = ：( x ) ( 一p ( z 。) ) = 一慨( ) 卜。 即血是甲“( x ) 在处的一个下降方向。 2 在步骤2 中，若牛顿方程有解，则线搜索( 4 1 2 ) 一定有解，这时算法退