（运筹学与控制论专业论文）p0函数非线性互补问题的光滑化拟牛顿法.pdf

局函数非线性互补问题的光滑化拟牛顿法 摘要 互补问题是一类重要的优化问题，它在工程、经济和交通平衡等领域都有 重要应用关于互补问题的研究一直是非线性科学和计算科学的热点问题，求 解互补问题算法的研究也取得了很多成果本文研究r 函数非线性互补问题 的数值方法 本文给出了求解p o 函数非线性互补问题的光滑化拟牛顿算法此算法基 于光滑对称扰动f i s c h e r - b u r m e i s t e r 函数并且利用了无导数线搜索在r 函数非 线性互补问题有非空有界解集且f ，是l i p s c h i t z 连续的条件下，证明了算法的全 局收敛性全局收敛性的主要特征是不需要提前假设水平集是有界的这一 假设在文献中被广泛使用于证明全局收敛性 关键词：非线性互补问题，拟牛顿，全局收敛，超线性收敛，光滑逼 近，f i s c h e r - b u r m e i s t e r 函数 s m o o t h i n gq u a s i - n e w t o nf o r p o f u n c t i o nn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m a b s t r a c t t h ec o m p l e m e n t a r i t yp r o b l e mi sac l a s so fi m p o r t a n to p t i m i z a t i o np r o b l e m s ，w h i c h h a v ei m p o r t a n ta p p l i c a t i o n si ne n g i n e e r i n g ，e c o n o m i c sa n dt r a f f i ce q u i l i b r i u m t h er e - s e a r c ho ni ti sa l w a y st h eh o ts p o t si nn o n l i n e a ra n dc o m p u t a t i o n a ls c i e n c e m a n yr e s u l t s h a v eb e e na c h i e v e d n u m e r i c a lm e t h o d so ft h ep 0f u n c t i o nn o n l i n e a rc o m p l e m e n t a r i t y p r o b l e ma r es t u d i e di nt h i st h e s i s i nt h i st h e s i s ，w ep r o p o s eas m o o t h i n gq u a s i n e w t o nm e t h o df o rs o l v i n gp of u n c - t i o nn 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 m t h ea l g o r i t h mc o n s i d e r e dh e r ei sb a s e do n t h es m o o t h i n gs y m m e t r i cp e r t u r b e df i s c h e r - b u r m e i s t e rf u n c t i o na n dm a k e su s eo ft h e d e r i v a t i v e - f r e el i n es e a r c hr u l e i t sg l o b a lc o n v e r g e n c ei sp r o v e dw h e nt h es o l u t i o ns e to f 氏f u n c t i o nn 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 mi sn o n - e m p t y 。b o u n d e da n df li sl i p s - c h i t zc o n t i n u o u s t h em a i nf e a t u r eo fo u rg l o b a lc o n v e r g e n c er e s u l t si st h a tw ed on o t a s s u m eap r i o r it h el e v e ls e ti sb o u n d e d k e y v c o r d s - 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 m ，q u a s i n e w t o n ，g l o b a lc o n v e r - g e n c e ，s u p e r l i n e a rc o n v e r g e n c e ，s m o o t h i n ga p p r o x i m a t i o n ，f i s c h e r - b u r m e i s t e rf u n c t i o n 原创性声明 本人声明：所呈交的学位论文是本人在导师的指导下进行的研究工作及取得的研究成 果。除本文已经注明引用的内容外，论文中不包含其他人已经发表或撰写过的研究成果，也 不包含为获得凼苤古太堂及其他教育机构的学位或证书而使用过的材料。与我一同工作的同 志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：硅；蠡蓟 日 飙域辋拿目 指导教师签名：至垒【叠丞 日 期：迎星经s 巨l2 旦 在学期间研究成果使用承诺书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：内蒙古大学有权将 学位论文的全部内容或部分保留并向国家有关机构、部门送交学位论文的复印件和磁盘，允 许编人有关数据库进行检索，也可以采用影印、缩印或其他复制手段保存、汇编学位论文。 为保护学院和导师的知识产权，作者在学期问取得的研究成果属于内蒙古大学。作者今后 使用涉及在学期间主要研究内容或研究成果，须征得内蒙古大学就读期间导师的同意；若用 于发表论文，版权单位必须署名为内蒙古大学方可投稿或公开发表。 学位论文作者签名：生器萤 i e i 期：堑翌蚴缒 指导教师签名墅盘! 旦蛰 日 期：血翌2 晕三团旱曰 第一章绪论 设f ：研一衍是一非线性映射，非线性互补问题( n o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m ，简记为n c p ( f ) ) 是指：求一个向量z 册，使得 z 0 ，f ( x ) 0 ，z r f ( z ) = 0 ( 1 1 ) 如果( 1 1 ) 中的f ( z ) 是线性函数，耳p f ( z ) = m x + g ，其中m 为礼n 矩阵，g 为死维向 量，则非线性互补问题蜕化为线性互补问题( 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 m ，简记 为l c p ( m ，口) ) 1 1 d e r i v a t i v e - f r e el i n es e a r c h 非线性互补问题在很多领域都有重要应用【6 8 】，其理论和算法的研究在近些年来得 到了长足发展【6 】很多求解n c p ( f ) 的有效算法已被提出【8 】，其中比较流行的方法之一是 首先把n c p ( f ) 转化成一个非线性方程组h ( x ) = 0 ，然后利用求解方程组的相关方法【9 】间 接求解得到n c p ( f ) 的解牛顿型方法是求解非线性互补问题的一类重要的数值迭代算 法，其局部收敛性的研究取得了很好的成果【引近些年来，此类算法的全局收敛性研究也 得到了诸多进展 3 9 _ 4 3 i 然而对于计算上更为实用的拟牛顿算法的研究相对较少其主要 困难在于即使对于光滑的非线性方程组，拟牛顿法产生的方向不能保证是某个度量函数 的下降方向，常用的线搜索( 如a r m i j o 型线搜索) 此时已不适用( 参见文献【4 4 ) 另外对 拟牛顿法来说，那些需要计算导数的线搜索是不适合的因此，为了得到求解非线性方程 组的拟牛顿法的全局收敛性，需要一个无导数线搜索( d e r i v a t i v e - f r e el i n es e a r c h ) 1 9 8 6 年，g r i w a n k 在文献【4 5 】中首先提出了一种无导数线搜索，并证明了求解非线性 方程组的b r o y d e n 秩一校正方法在该线搜索下的全局收敛性，但此线搜索在某些情况下， 可能不能实现( 文献【5 1 中给出了例子) l i 和f u k u s h i m a 在文献【5 】中，针对文献【4 5 】 中无导数线搜索的不足，提出了一个新的易于实现的无导数线搜索 i i h ( x 七+ a d 七) l ls 1 日( z 七) i l 一0 1 i i , x d k l l 2 + r l k l l h ( x 七) 1 1 ，( 1 2 ) 其中o 1 0 是常数，r k 0 ，( 1 2 ) 式成立事实上，当a _ 0 k = 0 时，( 1 2 ) 式的左边趋于i i g ( x 七) i i ，而右边趋于( 1 + r 七) l l h ( x 七) 1 1 因为对每个k 有 h ( x 七- 1 - a d k ) l i ( 1 + v k ) l l h ( x 七) 1 1 ， 故线搜索( 1 2 ) 是近似范数下降的利用此线搜索l i 和f u l m s h i m a 提出了求解光滑非缚性 方程组的一个具有全局收敛性的b r o y d e n - l i k e 算法 内蒙古大学硕士学位论文 除了无导数线搜索( 1 2 ) ，l i 和n k u s h i m a 在文献【4 ，4 6 】中还给出了其他形式的无导 数线搜索，它们分别是 i i h ( x 七+ a d k ) l i 一0 日( z 七) | i 一口l i i g ( x 七+ a d k ) 一h ( x 七) i j 一仍i i 入矿| 1 2 + 仉， ( 1 3 ) o o 其中o 1 ， 7 2 是常数，啦 一 甄 苣昌 p = 碑 阵 觚咄 对 ， 的 一 忍 一 = 1 彩仉飙驴禄矶 第二章预备知识 本章第一节给出了互补问题的算法概述，第二节给出了后面将要用到的一些基本概 念和重要结论 2 1 互补问题的算法 c o t t l e 等人于1 9 6 3 年首次提出互补问题次年，c o t t l e 便在他的博士论文中第一次提 出求解互补问题的数学规划算法互补问题的出现引起了人们的浓厚兴趣，特别是8 0 年 代中后期，随着科学与技术的发展，互补问题变得越来越重要，成为了数学规划中的热点 问题，同时也涌现出了许多求解互补问题的算法这里简单的作如下介绍： l 非线性方程组法 这类方法就是首先把非线性互补问题转化成一个非线性方程组圣( z ) = 0 ，然后利用 求解方程组的相关方法【9 l 间接求解得到n c p ( f ) 的解，这类方法通常需要一个n c p 函 数来完成如果函数西：刀铲_ 皿满足条件 圣c z ，：= ( 三三：三：三：) = 。 c 2 2 ， 现在已有了许多n c p 函数【1 3 1 7 1 ，m a n g a s a r i a n 在文献 1 7 】中首先构造了一族 内蒙古大学硕士学位论文 1 9 8 7 年，r o b i n s o n 1 8 】最早利用日一导数来研究非光滑方程组的牛顿法1 9 9 0 年，基于 非光滑方程组( 2 3 ) ，p a n g 1 9 】利用b 一导数提出了一种广义牛顿法，并在一定条件下证明 了算法的全局收敛性之后，p a n g 和g a b r i e l 【2 0 】提出了他们自己称作n e s q p 的方法，在 某些( 解的) 正则条件下，证明了其算法产生的点列的任意聚点是互补问题的解，同时得到 了局部超线性- 次收敛性不过，该方法中每次迭代的下降方向是通过求解二次规划子 问题得到基于非光滑方程组 西( z ) = f ( x + ) + z 一= 0 ( 2 4 ) h a r k e r 和x i a o 2 1 j 利用b 一导数提出了一类广义牛顿法，并在f ( z ) 为一致p 一函数的假设条 件下，证明了其算法的全局收敛性 1 9 9 2 年，f i s c h e f i j f 入了一种结构简单的n c p 函数( 又称作f i s c h e r - b u r m e i s t e r 函 数) f i s c h e r - b u r m e i s t e r 函数及其它n c p 函数的出现和半光滑理论的建立，进一步促进 了非光滑方程组的发展，这类算法的全局收敛性好局部超线性收敛性在适当条件下得到 证明其中d el u c a ，f a c c h i n e i 和k a n z o w 5 3 】对基于极小值函数和基于f i s c h e r - b u r m e i s t e r 函 数的各种广义牛顿类算法( 包括精确、不精确和l e v e n b e r g - m a r q u a r d t 型不精确广义牛顿 法) 进行了从理论到数值结果的比较、评价，详细讨论了这些算法全局和局部收敛性所需 要的条件指出基于f i s c h e r - b u r m e i s t e r 函数的算法可在较弱条件下也能确定下降方向 2 内点法 内点法是求解线性规划问题的十分有效的算法，它具有多项式复杂性内点法的思 想最早可追溯到2 0 世纪5 0 年代，2 0 世纪6 0 年代也曾有人进行过研究但是，第一个具有多 项式复杂性和实用性的内点法是由k a r m a r k a r 于1 9 8 4 年首先提出的此后2 0 年，经过众多 优化专家的共同努力，对内点法的研究取得了丰硕成果：不仅建立了完善的理论体系，而 且开发出高效的数值软件此外，受内点法刺激，对单纯形法的研究也有了不同程度的改 进，其数值软件的计算效率明显提高如今，内点法被推广到求解单调互补问题、凸或非 凸规划问题等，详见近期综述文献【5 2 1 3 磨光方程与非内点法 前面的非光滑方程组法存在一个弱点，即方程组西( o ) = o 的j a c o b i a n 矩阵v 西( o ) 难 于计算自然的，可以考虑用一个光化函数雪( z ，q ) 近似代替西( z ) ( 这里面( z ，q ) 成为磨光函 数，q 称为磨光参数，西( z ，0 ) = 圣( z ) ) ，这样可以转而求解西( z ，口) = 0 如果在迭代过程 中能自动调整q 到0 ，则称之为连续磨光方程；进一步，连续不断地压缩a 到0 ，则称为非 内点法后者具有路径跟踪法的主要特征，但它能取任何初始点及充分选取步长，这恰好 能克服内点法的弱点，所以自它由c h e n h a r k e r 3 0 l 于1 9 9 3 年提出以来，吸引了众多学者 的注意，并取得了迅速发展1 9 9 6 年，k a n z o w 3 5 j 对线性互补问题构造了与3 0 1 不同的磨 光函数，并在m 为局+ 凡一矩阵的假设下，证明了其算法的全局收敛性有些学者把这 类磨光函数称作c h k s ( c h e n h a r k e r - k a n z o w - s m a l e ) i 函数近年，用磨光方程组法解互补 7 内蒙古大学硕士学位论文 问题的文章有很多，h u a n g 3 6 】利用扰动的极小化函数给出了磨光函数 ( p ，口，6 ) = ( 1 + p ) ( 口+ 6 ) 一x ( 1 - # ) 2 ( a - b ) 2 + 4 # 2 基于这一磨光函数构造了再估计- 再校正( p r e d i c t o r - c o r r e c t o r ) 磨光牛顿法，对于岛一函数， 在适当条件下证明了算法的全局收敛性和局部超线性收敛性z h a n g 1 1 给出了称为光滑对 称扰动f i s c h e r i 蚕数( s s p f ) ( p ，口，6 ) = ( 1 + p ) ( n + 6 ) 一、i i 干i 万f 葺弋石i ；丐所 ( 2 5 ) 构造算法迭代的每一步只需要解一个线性方程组和一次线搜索，因此称为一步光滑牛顿 法，这一算法的主要特点是不需要提前假设聚点的存在而达到全局收敛 4 可微的无约束优化法 这一方法就是把互补问题转化为一个与之等价的可微无约束优化问题，然后用广 义n e w t o n 类型法求解由于无约束优化法较为成熟，因此对这类方法的研究重心在于如 何转化上文 3 1 】引进一个光滑函数，使得以该函数为目标函数的无约束最优化问题的全 局最优解为n c p ( f ) 的解文【3 2 】证明了当f 在衍中强单调时，文 3 2 】中的无约束优化问 题的任一稳定点均为n c p ( f ) 的解文【3 3 】提出了几种将n c p ( f ) 转化为无约束优化问题 的新方法在设法构造n c p 函数的同时，也带动了其误差界的研究，误差界是一个特殊 的n c p 函数近来，对可微无约束最优化再生的研究兴趣转向增加非负约束因为实际 计算表明，仅用无约束优化问题求出的解并不理想为此文 3 4 】给出了一个可行的信赖域 方法 5 投影法 投影法是求解互补问题的一类基本而又重要的计算方法它源于g o l d s t e i n l e v i t i n - p o l y a k 的求解凸约束优化问题的梯度投影法，包括著名的外梯度法、逐点逼近法、矩阵分 裂法等其基本迭代格式为 z 1 = p r x i x 七一a f ( z 知) 】， 这里q 0 为给定的常数，对于非线性互补问题，上述迭代格式简化为 矿+ 1 = p a f ( z ) 十 由b a n a c h 不动点定理可以证明，当f 为强单调，全) 蜀l i p s c h i t z 连续的函数且q 充分小时 具有全局收敛性虽然这类方法最多只有线性收敛速度，但它的运算量小、存储量小、 保稀疏性，因此也一直受到人们关注，特别是对计算大型互补问题投影法的文献也很 多，x i u 和z h a n g 给出了最新的综述报告f 3 7 i 8 内蒙古大学硕士学位论文 2 2 基本概念和结论 定义2 2 1 设m 为礼n 矩阵，称m 为 ( i ) p - 矩阵，如果m 的所有主子式皆为正实数； ( i i ) 局一矩阵，如果m 的所有主子式皆为非负数； ( i i i ) 正定矩阵，如果z t m x 0 ，对任意0 z 丑妒成立； ( i v ) 半正定矩阵，如果x t m z 0 ，对任意z 五p 成立； ( v ) 凡矩阵，如果线性互补问题l c p ( m o ) 只有零解 半正定矩阵必为岛矩阵，正定矩阵必为尸- 矩阵，p 矩阵既是r 一矩阵又是凰矩 命题2 2 1 设m 皿n 加( 不必对称) ，则如下叙述等价 ( i ) m 为岛一矩阵； ( i i ) 1 。m 0 ，m + e i 为p - 矩阵 定义2 2 2 设f ：衍_ 衍，称为f 为 ( i ) p o 函数，若对任意z ，y 衍，z y ，存在i n 使得( 戤一y i ) ( r ( z ) 一只( 可) ) o 且鼢玑； ( i i ) p - 函数，若对任意z ，y 衍，z y ，存在i n 使得( 一玑) ( 只( z ) 一只( 耖) ) o ； ( i i i ) 一致p 一函数，若存在g - 数口 0 ，使得理譬( 毛一玑) ( 只( z ) 一只( ) ) a l l x 一引1 2 ， 对任意z ，y 舒； ( i v ) 单调函数，若( z 一箩) t f ( z ) 一f ( ) 】o 对任意z ，y 衍成立； ( v ) 严格单调函数，若( z 一) t f ( z ) 一f ( 秒) 】 o 对任意z ，y 衍成立； ( v ) 强单调函数，若存在常数q 0 ，使得( z y ) t 旷( z ) 一f ( ! ，) 】d 忪一训2 对任 意z ，y 衍成立 单调函数必为r 函数，严格单调函数必为p 函数，强单调函数必为一致p 函数 命题2 2 2 设f 为连续可微函数，那么f 为岛函数当且仅当f 的j a c o b i a n 矩 阵在任意点处均为局矩阵：若f 为一致p - 函数，则f 的j a c o b i a n 矩阵在任意点处 均为p 矩阵 非线性互补问题n c p ( f ) ，当f 为一致尸函数时，n c p ( f ) f f 勺解存在且唯一对线性 互补问题l c p ( q ，m ) ，当m 为p 矩阵时，l c p ( q ，m ) 的解存在唯一 9 内蒙古大学硕士学位论文 定义2 2 3 设0 ：衍_ 衍，若e ( x ) 满足 ( i ) 8 ( x ) 0 对任意z 衍成立； ( i i ) 口( z ) = 0 当且仅当z 是非线性互补问题( 1 1 ) 的解，则称e ( x ) 为非线性互补问 题的价值函数 定义2 2 4 设f ：丑弘_ 卫妒，则称f 在x 丑铲强制，若存在z o x 使得 s e x 警一 ，忙0 一 i l z 对于n c p ( f ) 的价值函数p ( z ) ，若l i m l l 训一o ( x ) = + o o ，则称价值函数e ( x ) 是强 制的，这就保证了水平集 z 丑哥：o ( x ) 口) 对任意正数a 都有界 设向量函数h ：衍_ 衍在点z 卿局部l i p s c h i t z 连续，即存在g 0 ，l 0 ， 使得 j i h ( x 1 ) 一h ( x 2 ) j i i i z l 一x 2 l l ，比1 ，z 2 b ( x ，e ) ， 其中b ( x ，e ) 表示z 的邻域b ( x ，e ) = ( 可厨：恬一z i | 0 ，h 5 ( ) 光滑且 。i 。l i 护m 霉日8 ( y ) = 日( z ) ，比砑 定义2 2 9 设函数日8 为日的光滑化函数，若对任意紧集dc 衍和任意手 0 ， 存在常数工 0 使得 0 日5 ( z ) 一h ( x ) i i l ，v d ，垤( 0 ，司， 则称函数日5 为日的正则化光滑化函数 定义2 2 1 0 假设h ：衍_ 衍是上局部l i p s c h i t z 连续，则日在z 衍处的 d 次微分定义为： o c h ( x ) ? ：= a 玩( z ) a a 2 ( z ) a 月n ( z ) 1 1 内蒙古大学硕士学位论文 d 次微分与c l a r k e 广义j a c o b i a no h 有如下关系a h ( x ) 如日( z ) 定义2 2 1 1 假设h ：衍_ 衍是上局部l i p s c h i t z 连续，如果它的光滑逼近函数 日p ( ) 满足下述条件：对任意z 五妒，有 l 川i r ad i s t ( h ：( x ) ，如何( z ) ) = 0 ， 则称光滑逼近函数日p ( ) 与日( ) 满足j a c o b i a n 相容性 j a c o b i a n 相容性定义了日p 对日一阶意义上的逼近 定义2 2 1 2 称矿为n c p ( f ) ( 1 1 ) 的严格互补解，如果z 是( 1 1 ) 的解且满足 z ：+ 只( 矿) 0 定理2 2 1 ( 山路定理 4 9 】) 设f ：衍_ 皿是连续可微函数且强制，c 衍是非空 紧集，m 是y ( x ) 在c 的边界a c 上的最小值m ：= r a i n 王o cf ( x ) ，若存在q c _ ；f i l bgc 使 得，( 口) m r f ( b ) m ，则存在一个c 衍，使得v f ( c ) = o 且f ( c ) 仇 1 2 第三章求解局函数非线性互补问题的光滑化拟牛顿法 3 1光滑对称扰动f i s c h e r b u r m e i s t e r 函数及其性质 日( z ) ：= 日( p ，z ) ：= ( 圣( 差z ) ) ， ( 3 3 ) 圣c z ，：= 圣c p ，z ，：= ( 三三二；三三：) c 3 4 ， 日c z ，= ( 口之，v z 三z ，t ) ， c 3 5 ， 内蒙古大学硕士学位论文 兵中 u ( z ) = v e c 【仇( z ) = 以( p ，甄，r ( z ) ) ，i ) ， v z 西( z ) t ：= 眦d 1 ( z ) + d 2 ( z ) 1 + d l ( z ) + p d 2 ( z ) 】f ( z ) ， ( 3 6 ) 且 d 1z ) ：= d i a g a l ( z ) ，( z ) ) ，( 3 7 ) d 2 ( z ) ：= d i a g b l ( z ) ，k ( z ) ) ， ( 3 8 ) 抖卅一而乖稀蒜特丽雨， ( 3 9 ) 6 i ( 小= 1 一而雨蒜群等雨雨， ( 3 1 0 ) u t ( z ) ：2 砚( z ) z t + 6 t ( z ) 只( z ) 一= 了彳i i 盂i i i 亏i ；亏孬亏乏i 芎专乏乏i = ；i i 丽 ( 3 1 1 ) 、i p z i 十，l l o 十【十p ，i l z j 厂十p 易知对所有i = 1 ，2 ，礼有 0 a i ( z ) 2 ，0 b i ( z ) 0 ，定义水平集 l p ( c ) ：= z 皿p ：i i 圣( 弘，x ) l l c ) ( 3 1 3 ) 则对任意p 2 p l 0 和c 0 ，集合 l ( c ) y - - u “( c ) ( 3 1 4 ) p 1 s 弘p 2 是有界的特别地，对任意p o 和c 0 ，集合“( c ) 是有界的 推论3 1 1 假设f 是连续可微的r 函数且圣( p ，z ) 由( 3 4 ) 定义则对任意p 0 ，函 数西( p ，z ) 是强制的，即 。珊恻舭) 忙 1 4 内蒙古大学硕士学位论文 具有强制性的光滑函数用于设计互补问题的算法时，对算法的全局收敛性有明显的 特点一不需要提前假设聚点的存在( 即不需要提前假设水平集有界) ，这一假设在文献 中被广泛使用于证明全局收敛性 4 , 4 6 - 4 8 】除具有强制性的光滑函数( 3 2 ) 外，文献 3 6 】 中提出了另一个具有强制性的光滑函数： ( p ，口，b ) = ( 1 + p ) ( d + b ) 一、( 1 一p ) 2 ( n 一6 ) 2 + 4 p 2 ( 3 1 5 ) 它是通过光滑化扰动极小化函数： m i n a + 肋，p a + 6 】 而得到的对于上面提到的光滑函数( 3 2 ) 的所有性质，光滑函数( 3 1 5 ) 也成立另外， 使用文献 1 1 ，1 2 ，4 9 】中的正则化方法也可得到类似于推论3 1 1 的强制性结果使用光滑 函数( 3 1 5 ) 和正则化方法，本章的所有结果也是成立的 3 2 光滑化拟牛顿算法 设，y ( 0 ，1 ) 定义函数p ：衍+ 1 _ 毋为 p ( z ) = tm i n 1 ，1 1 日( z ) 1 1 2 ) 算法3 2 1 步0 选择常数q ，6 ，百( 0 ，1 ) ，仃1 ，c r 2 0 ，伽珥+ 设口= ( p o ，0 ) 取+ 衍， 任取初始点x o 衍设z o = ( p o ，x o ) 选择7 ( 0 ，1 ) 使得7 # o o 是一给定 常数并选择一正数列【仉) 满足 孤7 7 p k # o ，解下面的方程得 z k = ( 纵，一) ， h ( z 七) + g k a z k = m 口( 3 1 7 ) 否则，令a z 七= ( 肌，a z 七) ：= ( 0 ，) ，并解如下方程组得一， 垂( z 七) + b k a x 七= 0 ( 3 1 8 ) 其中g 七皿( 叶1 ) ( n + 1 ) 定义为 g 七= 1 ，三) 内蒙古大学硕士学位论文 且瞰是v z 垂( 驴) t 的一个近似 步2 若 i i h ( z 七+ a z 七) l i a l l h ( z 七) i l 一0 1 i i a z 七0 2 ，( 3 2 0 ) 则设a 七：= 1 ，转步4 步3 设儿是取自集合 1 ，6 ，铲】使得a = 满足如下线搜索的最大数 i i h ( z 七+ a a z 七) | | l i h ( z 七) i l 0 2 1 a a z 七1 1 2 + 7 7 k l i h ( z 七) 1 1 ( 3 2 1 ) 步4z 七+ 1 = ( p 七+ 1 ，z 七+ 1 ) = z k + a k a z 七 步5 用如下b r o y d e n - l i k e 校正公式修正鼠得b k + l ： b k + t = b k + 以生笳掣， 其中8 k = k a x 七= z 七+ 1 一矿，y 七= 圣( 地，z 七+ 1 ) 一圣( 胀，矿) ，参数以满足i 以一l i 殂 b k + a 非奇异 步6 令七：= 七+ l ，转步1 对算法的几点说明： ( 1 ) 由方程( 3 1 7 ) 求分两步：首先由下面的方程求纵 a u k = - - u k + p k # o ，( 3 2 2 ) 然后解如下线性方程组求a z 七 b 七a z k = 一圣( z 七) 一a u 七v ( z 七) ( 3 2 3 ) ( 2 ) 算法3 2 1 与 2 】中算法1 1 的区别不仅在于光滑函数咖( p ，o ，b ) 选取不同，还在 于肌的选取方法可证明算法3 2 1 中 触) 是单调非增序列( 见下面定理3 2 1 ) 然而 2 】 中算法1 1 并不能保证 鲰) 是单调非增的 ( 3 ) 在算法3 2 1 步1 中引入m 口的好处：它保证了肌是正的( 见下面定理3 2 1 的证 明) 由引理3 1 2 和引理3 1 3 可知这又保证了日7 ( z 七) 非奇异以及l p 。( c ) 有界不引入m 口， 贝0 ( 3 1 7 ) 式变为h ( z 七) + g k a z 七= 0 ，此时a i t k = 一p 七，p 七+ 1 = p 七十a k a i t k = ( 1 一a 七) 肛七 当儿= 1 时，p 七+ 1 = 0 定理3 2 1 算法3 2 1 是有定义的，且产成一无穷序列 = ( 触，矿) ) 满足 纵) c r + + 是单调非增的 证明由鼠非奇异知g 七+ 1 非奇异，因此线性方程组( 3 1 7 ) 和( 3 1 8 ) 唯一可解易知对 充分小的入 0 ，不等式( 3 2 1 ) 成立事实上，当入_ o 时，( 3 2 1 ) 的左边趋于i i h ( z 七) i i ， 但右边趋于( 1 + 班) i | 日( ) 1 1 因此算法3 2 1 是有定义的 1 6 内蒙古大学硕士学位论文 下面用归纳法证明 纵) c r + + 因为p o 0 ，假设鲰 0 ，则1 1 日( ) | l 0 ，从而 m = m i n 1 ，1 1 日( ) 1 1 2 ) 0 如果p 七 p k p o ，贝0 由( 3 2 2 ) j f f l 入七( 0 ，1 】知 p 七+ 1 = p 七+ a 七p 七= ( 1 一a 七) p 七+ a k p k l , 0 0 如果m p k # o ，由算法3 2 1 步1 可知此时肌= 0 ，从而 “七+ 1 = p 七 0 所以 m ) c 研+ 故算法3 2 1 产生一无穷序列 下面证明算法3 2 1 中 舰) 是单调非增序列事实上，如果肌 p k # o ，由( 3 2 2 ) 知 鲰 0 ，如果对所有的七o 有肌皿且0 矿0 _ o o ( 七一o o ) ，那么 。l i r a 旧( ) i | = + o 。 证明由定理3 2 1 知 纵) 单调非增，从而对任意k 0 ，有皿脚5 肋用反证法证 明，假设存在一无界序列 扩) ，使得| i ( 肌，x k ) 1 1 有界因为序列 矿】是无界的，所以指 标集i ：= i n ： z ) 是无界的) 是非空的不失一般性，可假设【i 苟l 】_ + o o ，i 定义序列 铲) 为 ， 牟 一j 0 ， i i i 研k igi 1 7 内蒙古大学硕士学位论文 则显然 妒) 是有界的因为f 是岛函数，所以 0 m 劁a x 、( x 七, 一童：) 峨( z 七) 一只( 瑚 = m 叫a xz ( 矿) 一r ( 硼 ( 3 2 5 ) = 苟【b ( ) 一乃( 扩) 】， 其中歹是取得m a x 的指标之一，不失一般性，假设j 与七是互相独立的因j ，所以 l 苟i 一+ o 。 ( 3 2 6 ) 现考虑如下两种情况： ( 1 ) 如果砖_ + o o ，则由弓的连续性知乃( 妒) 是有界的，由( 3 2 5 ) 可知乃( ) 唧 一o 。因为0 豇鲰p o ，所以 鲰苟+ 弓( 扩) 一+ o 。，苟+ 胀弓( 扩) _ + o o 由( 3 2 ) ，( 3 4 ) 和引理3 3 1 可得 i 奶( 脚，x k ) i _ + o o ( 3 2 7 ) ( 2 ) 如果弓_ 一o 。，则由乃的连续性知乃( 矿) 是有界的，由( 3 2 5 ) o - t 失：1 1 马( ) 乃( 鲈) 因为0 豇纵脚，所以 胀苟+ 乃( 矿) _ 一o o ，苟+ m b ( 矿) _ 一。o m ( 3 2 ) ，( 3 4 ) 和引理3 3 1 可得 f 奶( 触，x k ) l _ + o o ( 3 2 8 ) 综上可知忙( ) | l 一+ 。o ，从而l l h c z 七) i l = + 。o ，这与1 1 日( 砂) | l 有界矛盾 引理3 3 3 设【= ( 肌，扩) ) 由算法3 2 1 产生，c = , l l h ( z o ) 1 1 ，则矿l p 。( c ) ，其 中l l 。( c ) 由( 3 1 3 ) 定义 证明由( 3 2 0 ) ，( 3 2 1 ) 可知对所有k ，0 日( z 七十1 ) i f ( 1 + 仉) l i h ( z 七) f j ，从而 j j 圣( 名七+ 1 ) j j j i h ( z 七+ 1 ) l | ( 1 + 矶) j | 日( ) j i k ， k i 旧 0 ) | i 娶( 1 州 i 旧 0 ) i i ( 熹薹( 1 州广1 - i l 聊0 ) i ( 1 + 上l + k 篆剑酢0 ) l i ( 1 + 熹广1 se 叶1 1 日( z o ) l l ， 所以矿十1 l m l ( c ) 18 内蒙古大学硕士学位论文 引理3 3 4 设 驴) 由算法3 2 1 产生，则 i i a k a z 1 1 2 o 。 k = o 证明由( 3 2 0 ) ，( 3 2 1 ) 可知对所有七有 c r o l l a k a z 七0 2 = 盯o l l z 七+ 1 一z 七| | 2 i i h ( z 七) 0 一i i h ( z 七+ 1 ) 0 + 7 7 k 1 1 日( z 七) 1 1 ， 其中o 0 = m a x a l ，c r 2 ) ，所以 j ， 钆z k l l 2 i i h ( z 。) 1 1 一i i h ( z j + 1 ) 1 1 + 7 7 k l l h ( z k ) l l k = ok = 0 j i i h ( z o ) 1 1 + 仉z 七) 1 1 由引理3 3 3 证明过程知对所有七，| 1 日( ) i i e l l h ( z o ) 1 1 ，从而 jj o o i i , 入k a z m i i 剑日( z 。) i i + e 叩i i h ( z 。) 1 1 r k k = 0k - - 0 令歹_ 。o 且由( 3 1 6 ) 口- j 得 即 且 o o i i , x k x , 矿1 1 2 i i h ( z o ) 1 1 + e q l h ( z 。) 1 1 , 7 o o k = o o 。 i i a k a z 七1 1 2 。o k = 0 z j l 理3 3 5 【5 】设 a 七) ，_ 【如 是满足如下条件的正数列 鲰+ 1 ( 1 + t k ) a k + t k 则 口知) 收敛 引理3 3 6 设 ) 由算法3 2 1 产生，则序列 1 1 日( ) 1 1 ) 收敛 证明由( 3 2 0 ) ，( 3 2 1 ) 知 1 1 日( z 1 ) i i ( 1 + 仉) 0 日( ) 1 1 ( 14 - 啦) 1 1 日( ) i i + r k 1 9 ( 3 2 9 ) 0 ，使得 l i v e 西( z ) 一v 霉圣( 7 ) 1 1 f2i i v z 圣( p ，z ) 一v z 西( p 7 ，) i l f ( 3 3 0 ) 丽i p p 7 i + t i i x z 川2 ，比，z l ( c ) 、。 证明由( 3 6 ) 知 i i v z 圣( z ) 一v 圣( z 7 ) i i f = i i p d lc z ) + d 2 ( z ) 】+ d l ( z ) + p d 2 ( z ) 】f 7 ( z ) 一 p d ( 名7 ) + d 2 ( 7 ) 】一【d l ( z 7 ) + i , t 7 d 2 ( z 7 ) if 7 ( z 7 ) i if i i p d l ( z ) 一p d x ( z ) i i f