（运筹学与控制论专业论文）具有非单调线搜索的半光滑牛顿法.pdf

具有非单调线搜索的半光滑牛顿法 s e m i s m o o t hn e w t o n a l g o r i t h mf o rn c p w i t han o n m o n o t o n el i n es e a r c h 学科专业：运筹学与控制论 研究生：栗婉茹 指导教师：黄正海教授 天津大学理学院学院 二零零八年五月 摘要 半光滑牛顿法开始于2 0 世纪9 0 年代早期，随着人们对半光滑问题研究的不 断深入，该方法的研究得到迅速发展，并成为当时最优化领域中极为活跃的研究 方向之一。在以往的半光滑化算法中，通常采取的是单调线搜索，而在实际问题 中，非单调线搜索能改进数值计算的结果和找到数值最优解的可能性。非单调线 搜索可以绕过某些极小点得到问题更好的解；对一些性态不好的函数的优化问 题，非单调线搜索也非常有效。 本文结合非单调线搜索，提出了一个新的求解互补问题的半光滑牛顿算法， 并对算法进行了收敛性分析，在一定的假设下，理论上得到了算法的全局收敛性 和局部超线性收敛性，而且本文对这个算法进行了数值实现。 关键词： 非单调线搜索；半光滑牛顿法；全局收敛性；局部超线性收敛性 a b s t r a c t t h er e s e a r c ho ft h es e m i - s m o o t hn e w t o na l g o r i t h mb e g a ni nt h ee a r l y19 9 0 s i t r a p i d l yd e v e l o p e dw i t ht h ef u r t h e rs t u d yo ns e m i - s m o o t hp r o b l e m sa n db e c a m eo n eo f t h ee x t r e m e l ya c t i v em e t h o d si nt h eo p t i m i z a t i o nf i e l d t h em o n o t o n o u sl i n es e a r c h w a st a k e ni nt h e p a s ts e m i - s m o o t ha l g o r i t h m h o w e v e r ，i np r a c t i c a lp r o b l e m s ， n o n - m o n o t o n el i n es e a r c hc a ni m p r o v et h en u m e r i c a lr e s u l t sa n dp o s s i b i l i t i e so f f m d i n gt h en u m e r i c a lo p t i m i z a t i o ns o l u t i o n n o n - m o n o t o n el i n es e a r c hc a nb y p a s s s o m em i n i m a lp o i n t sa n d g e tb e t t e rs o l u t i o n sa n di th a sb e e nh i g h l ye f f e c t i v ef o rs o m e b a df u n c t i o ni nt h eo p t i m i z a t i o n i nt h i sp a p e r , w ep r o p o s ean e ws e m i - s m o o t hn e w t o na l g o r i t h mw i t hn o n - m o n o t o n el i n es e a r c hf o rc o m p l e m e n t a r l i t yp r o b l e m sa n da n a l y z ei t s c o n v e r g e n c e b e h a v i o r i ti sg l o b a l l yc o n v e r g e n ta n dl o c a l l ys u p e r - l i n e a r l yc o n v e r g e n tu n d e rs o m e a s s u m p t i o n s w ed os o m en u m e r i c a li m p l e m e n t a t i o n sf o rt h i sa l g o r i t h m k e yw o r d s ：n o n m o n o t o n el i n es e a r c h ，s e m i s m o o t hn e w t o na l g o r i t h m ， g l o b a lc o n v e r g e n c e ，l o c a ls u p e r - l i n e a rc o n v e r g e n c e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丕洼盘鲎或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：熏漉菡 签字日期：切 0 年，月弓。日 学位论文版权使用授权书 本学位论文作者完全了解吞盗盘堂有关保留、使用学位论文的规定。 特授权苤注盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 导师签名：薹矾 签字日期：钆劫年s月3p 日签字日期：潲年6 月日 第一章背景介绍 1 1 互补问题 1 1 1 互补问题简介 第一章背景介绍 互补问题是运筹学与计算数学的一个跨领域交叉研究的学科，3 0 多年以来， 互补问题己经发展成为许多领域非常受欢迎的工具。互补问题在数学规划、经济、 工程及其它学科具有非常广泛的应用，在经济领域中的应用主要有w a l r a s i a n 平 衡、空间价格平衡和对策论模型等；在工程中的应用有接触力学问题、断裂力学 问题、障碍和自由边界问题、流体弹性动态润滑问题、最优控制问题及交通平衡 问题等。也就是说，上述这些问题都可以模型化为互补问题，从而最终归结为互 补问题的求解。这使得互补问题成为数学规划中的一个十分热门的研究课题。 追溯互补条件的起源，1 9 6 3 年，著名运筹学家、数学规划的创始人 g b d a n t z i n g 和他的学生r w c o t t l e 首先提出了互补问题。第二年，c o t t l e 在他的 博士论文中第一次提出求解它的非线性规划算法。于是，互补问题很快引起了当 时运筹学界和应用数学界的广泛关注和浓厚兴趣。经过2 0 余年的努力，也就是到 2 0 世纪8 0 年代中后期，互补问题在理论和算法两方面已取得了比较丰硕的成果， 关于1 9 9 0 年以前的工作，可见于h a r k e r 和p a n g 的综述文章以及该时期的优秀专著 【1 。因为在经济和工程领域里的大量关于平衡问题的研究，会自然地涉及到互 补条件，其重要性日益明显，激励人们对其理论和算法的进一步研究，出现了2 0 世纪9 0 年代以来的研究高潮。在这十余年的时间里，不仅改进与丰富了互补问题 的理论研究，而且还提出多种有效算法。 19 6 4 年美国r w c o t t l e 在其博士学位论3 乏 n o n l i n e a rp r o g r a m sw i t hp o s i t i v e l y b o u n d e dj a c o b i a n s ”首先提出了“互补问题”这一类新的数学模型。c o t t l e 的导 师是著名的运筹学家、“线性规划之父 gb d a n t z i g 教授。这一数学问题在初 期曾被称为“拼合问题 ( c o m p o s i t ep r o b l e m ) 、“基本问题 ( f u n d a m e n t a lp r o b l e m ) 或“互补转轴问题( c o m p l e m e n t a r i t yp i v o tp r o b l e m ) 等。c o t t l e 在1 9 6 4 年的文 献 2 中和d a n t z i g c o t t l e1 9 6 7 年的文献 3 】中都曾指出：线性规划与二次规划是线 性互补问题的特例。在d a n t z i g c o t t l e1 9 6 8 年的文献 4 】中更指出：双矩阵对策 ( b i m a t r i xg a m e ) 问题也是线性互补问题的一个特例。线性互补问题还包括了最 优停止问题和市场均衡问题等。非线性互补问题、混合互补问题和隐互补问题包 第一章背景介绍 括了更多的数学问题，如一般非线性规划的k k t 条件是隐互补问题的一特例。 互补问题是从线性规划和非线性规划的推广而形成的，所以它的算法研究和可解 性研究一样，受到了研究者的重视。互补问题的研究还包括：可解性、阶级的拓 扑性质、稳定性、误差界以及不同类型的互补问题的算法研究等。互补问题与数 学规划、变分不等式、不动点问题、广义方程及对策论等有着密切联系，在它的 研究中使用了非线性分析与拓扑学中的不少理论，故它可被视为应用数学、计算 机数学与基础数学的一个交叉。关于互补问题的综述性文章可参阅文献 5 8 。 1 1 2 互补问题的模型 互补问题是指这样的问题，它包含的两组决策变量之间满足一种“互补关 系。互补关系反映了广泛存在的一种基本关系。根据问题中变量所满足的条件 的不同，以及互补关系的不同形式，互补问题被区分为若干类型，包括线性互补 问题( t h el 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 ev e r t i c a ll i n e a r c o m p l e m e n t a r i t yp r o b l e m ) ，广义竖直线性互补问题( t h ee x t e n d e dv e r t i c a ll i n e a r c o m p l e m e n t a r i t yp r o b l e m ) ，水平线性互补问题( t h eh o r i z o n t a ll 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 ) ，广义水平线性互补问题( t h ee x t e n d e dh o r i z o n t a ll 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 ) ，广义线性互补问题( t h ee x t e n d e dl 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 eg e n e r a le x t e n d e dh o r i z o n t a ll 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 ) ，非线性互补问题( t h en 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 ee x t e n d e dn 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 em i x e dn 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 ei m p l i c i t c o m p l e m e n t a r i t yp r o b l e m ) ，竖直互补问题( t h ev e r t i c a lc o m p l e m e n t a r i t yp r o b l e m ) ， 半定互补问题( t h es e m i d e f i n i t ec o m p l e m e n t a r i t yp r o b l e m ) ，隐混合半定互补问题( t h e i m p l i c i tm i x e ds e m i d e f m i t ec o m p l e m e n t a r i t yp r o b l e m ) ，非线性微分互补问题( t h e n o n l i n e a rd i f f e r e n t i a lc o m p l e m e n t a r i t yp r o b l e m ) ，集值互补问题( t h es e t v a l u e d c o m p l e m e n t a r i t yp r o b l e m ) 等。 1 1 3 非线性互补问题及其求解方法 非线性互补问题( t h en 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 ) ： 令f ：吼“一吼“是由吼“到孵“的一映射，相应的非线性互补问题是：求解矢 量x 孵“，满足 x 0 ，f ( x ) 0 ，x t f ( x ) = 0 ， ( 1 1 ) 2 第一章背景介绍 非线性互补问题被记为n c p ( f ) 。当映射f 是线性映射时，即f ( x ) = m x + q ，则 非线性互补问题化为线性互补问题l c p ( m ，q ) 。 i h 题n c p ( f ) 的解，即有又o ，f ( 丈) o ，- - x i tf i ( 叉) = 0 ，i = 1 , 2 ，n ，显然这等价于 又满足m i n ( 叉i ，f j ( - ) ) = 0 ，i = 1 , 2 ，n 。这一组等式可记为i i l i n ( _ ，f ( _ ) ) = 0 ，这 里m i i l ( _ ，f ( 叉) ) 是一矢量，其分量是疵( 趸i ，f i ( 叉) ) ，i = 1 , 2 ，n 。所以互补问题 n c p ( f ) 等价于求解方程组m i n ( x ，f ( x ) ) = 0 。函数m i n ( a ，b ) 被称为“m i n 函数”。 定义1 1 函数弘吼2j 锨1 被称为一“n c p 函数”，如对任意( a ，b ) t 吼2 ， 显然m i l l 函数是一n c p 函数，它被记为。对于任- - n c p 函数矽，互补 r ，( x 。，f l ( x ) ) 、1 似曲k 孟，j = 0 l 矽( x 。，f n ( x ) ) 丸访( a ，b ) ：昙( a + b 一而) 。 ( a ，b ) = a 2 + b 2 一( a + b ) ， ( 1 - 2 ) x - i j - - t n c p 函数，如和其他一些常见的n c p 函数 1 1 】，上面给出的互补 问题n c p ( f ) 的等价方程组( x ) = 0 是非光滑方程组，求解这类非光滑方程组可 第一章背景介绍 以有两种途经，一是用非光滑牛顿方法，一是对非光滑牛顿方法引进光滑逼近方 程( x ) = 0 ，并给出光滑化方法，其中西( x ) 是( x ) 的一光滑逼近函数，是 一参数。具体求解方法有价值函数法 1 2 - 1 8 ，非光滑牛顿法 1 9 2 2 ，非内点连续 法 2 3 2 5 1 ，光滑化牛顿法 2 6 - 3 1 和半光滑化牛顿法 3 2 等。 1 2 半光滑牛顿法 本文主要研究用半光滑牛顿法求解互补问题，它的基本思想是把一个互补问 题转化为一个与之等价的半光滑牛顿方程组，然后用广义牛顿类型法求解该方程 组，从而得到原问题的解。该方法开始于2 0 世纪9 0 年代早期，随着人们对半光 滑问题的研究不断深入，该方法的研究得到迅速发展，并成为当时最优化领域中 极为活跃的研究方向之一。 本文中的函数f 是连续可微的p o 函数，即对于所有的x ，y 孵“，x y 有 m 姬a 。x ( x i y i x f i ( x ) 一f i ( y ) ) - 0 。这样的非线性互补问题叫做p 0 一n c p 。 利用n c p 函数，互补问题可等价的转化为方程组 r ，矽( x 。，f l ( x ) ) 、 x 2 l 。x 。，i 。x ，j 2 。， y ( x ) ：丢o ( x ) 0 2 = 昙窆矽2 ( x ；，f j ( x ) ) 。 那么，求解方程( 1 1 ) 就等价于求解方程( x ) = 0 。也就等价于寻找沙( x ) 的全 局极小点。众所周知标准逼近方法是用来解决不适定问题的，也用于解决非线性 互补问题。这个方法存在于一系列互补问题中：找到x 孵“使得 x o ，f ：( x ) o ，x t f ：( x ) = 0 ， 其中s 0 是一个趋于零的参数，函数e 定义为e ( x ) ：= f ( x ) + 镊。令只i ( x ) 表示 e ( x ) 的第i 个分量，y ：= ( 占，x ) 吼+ 吼。定义 4 第一章背景介绍 d ( y ) ：= s 矽( x 。，t 。( x ) ) 矽( x 。，l 。( x ) ) ( 1 3 ) 咐卜扣= 如+ 喜玖x c x ，) o ( 4 ， 很容易知道如果y ：= ( g ，x ) 是d ( ”= 0 的解，那么x 是( 1 1 ) 的解。 1 3 非单调线搜索 非单调线性搜索方法是求解无约束最优化问题的一种较为有效的一维搜索 方法，其搜索的基本思想是在保持目标函数总体趋势下降的基础上，允许目标函 数在迭代过程中按一定的原则有时有所上升。 非单调线性搜索的方法最早是在文献 3 3 】中被提出的并且在无约束优化和 约束优化中得到成功运用与发展。例如：文献 3 4 3 6 。以无约束优化问题为例： m i n f ( x ) ，x r 4 ， ( 1 - 5 ) 其中是光滑函数并且它的梯度g = v f ( x ) 是可行的。假设( 1 5 ) 的近似解为魂。 如果g 。= v f ( 劝0 ，那么线性搜索定义为某个搜索方向d 。，通过线性搜索方向 d 。找到步长，并计算下一个近似解以+ 。： x 女+ l2x k + 口 d i 。 ( 1 6 ) 在选取步长中，传统的线性搜索要求函数值在每步中都是单调下降的，即： f ( x 州) f ( x 女) 。 ( 1 7 ) 例如a r m i j o 线性搜索 3 7 和w o l f e 线性搜索 3 8 。而非单调线性搜索是不满 足条件( 1 - 7 ) 的，对于一些优化问题目标函数不是线性收敛的，但是有收敛的 趋势，非单调线性搜索就是用来解决这类函数的问题，因为它们不用保证在每一 步目标函数都是下降的。例如下面的连续二次规划方法，也被叫做二阶超线性收 敛。 令0 如，盯( o ，1 ) ，万( o ，1 ) ，取正整数m ，假设到第k 次搜索，优先选取 第一章背景介绍 的步长瓦a ，五) 是给定的。非单调线性搜索就是选取第一个非负整数h 。使得 步长 吼= 瓦仃， 满足 厂( 以+ 畋) 麟j f ( x k _ j ) + 施t g t t 畋， 其中m ( o ) = o _ r o m ( k ) m i n m ( k 一1 ) + 1 ，m 一1 】，k 1 。 如果m ( k ) 三0 ，上面的单调搜索就还原为a r m i j o 线性搜索。 基于函数d 和p ，c h e n 和p a n 3 9 发现了一种求解n c p ( 1 1 ) 的半光滑牛 顿算法，是由s u n 3 2 给出的标准半光滑牛顿算法的推广。他们证明了在通常假 设条件下算法是全局收敛和局部超线性收敛的。在以往半光滑化算法中，通常采 取的是单调线搜索，而在实际问题中，非单调线搜索能帮助我们解决一些问题。 例如非单调线搜索可以绕过某些极小点得到问题更好的解；对一些不好的函数的 优化问题非单调线搜索也非常有效，因此为了改进数字计算的结果，在前面的算 法中，单调线搜索被z h a n g 和h a n g e r 4 0 非单调线搜索取代。当他们运用这个算 法时，报告出令人欣喜的数字结果。然而，所有 3 9 中给出的单调线搜索算法的 理论分析已经过时了。一个本质的问题是当单调线搜索被非单调线搜索取代时相 应的收敛结果是否成立。 在本文中，将研究非单调线搜索半光滑牛顿算法，给出它的定义和全局收敛 及局部超线性收敛性。 在本文中将采用以下符号：假设所有向量为列向量。角标t 表示转置。吼：( 个 别地，吼) 表示非负( 个别地，i e ) 孵“中的正规矩阵。对于任意向量，l ，吼“， 把( t ，y t ) t 简写为( ty t ) 。对于任意函数f ：吼“_ 吼”，如果f 在x 处是收敛 的，那么f ( x ) 表示f 在点x 处的j a c o b i a n 矩阵， f ( x ) = ( v f ( x ) ) t = ( v f i ( x ) 9o ，v f m ( x ) ) t ， 其中v f i ( x ) 表示f i 在x 点的梯度；如果f 在x 周围是局部l i p s c h i t z 连续的，那么 o f ( x ) 表示f 在x 点的c l a r k ej a c o b i a n 。对于任意，i ，孵+ ，= o ( v ) ( 或 = d ( y ) ) 也就是l i m 竺 嘞，或a 。专佃且 b 。哼佃，那么有当k 专佃时，i 声( a k ，b 。) 卜佃。 运用命题2 1 ( c ) ，很容易得到下面的结论。 命题2 2 映射d ：吼孵“_ 锨“的形式如下： r ， 占 1 一卜r | ， ( x 。，e ，。( x ) ) j 那么，d 是半光滑的。而且，如果f 7 是全局l i p c h i t z 连续时，是强半光滑的。 证明：因为一个函数是半光滑的当且仅当它的分量是半光滑的，所以为了证 明d 是半光滑的，仅需要证明d i ，i = 1 , 2 ，n + 1 是半光滑的。因为d ；：s ，所 以它是强半光滑的。 第二章基本结论 对于d i ，i = 2 , 3 ，n + l ，由命题2 1 ( c ) 知函数是半光滑的，而由 4 1 ， 结论1 9 知两个半光滑函数的复合函数是半光滑的，于是得到d i ，i = 1 , 2 ，n + l 是半光滑的。这样就证明了d 是半光滑的。 当p 是全局l i p c h i t z 连续的时，e 是强半光滑的，那么d i ，i 窑1 , 2 ，n + 1 是 强半光滑的。因为一个函数是强半光滑的当且仅当它的分量是强半光滑的，所以， d 是强半光滑的。 运用命题2 1 ( d ) ，d 的j a c o b i a n 矩阵如f ： 命题2 3 对任意的y ：= ( 占，x ) 9 1 + x9 t “有 c a d ( y ) ) tc ( 三。g 叫+ 。鬻删炉。，) ， 其中g ( y ) 和h ( y ) 是多值l l x n 对角矩阵，第i 个对角元素为 g 捌2 丽x i ， 、x i + 鬈j ( x ) ，、 e ，i ( x ) 巩又力2 蒴 如果( x i e i ( x ) ) ( 0 ，o ) ；否则g i i ( y ) = 参，h i i ( y ) = 硗对任意的( 毒，r i ) 使得 i 磊1 2 + i ，7 i1 2 1 。 证明：由求j a c o b i a n 矩阵的方法知 ( c o d ( y ) ) t a d l ( y ) x a d 2 ( y ) x a d 。+ l ( y ) ， 其中右边表示第i 列属于扣i ( y ) 的矩阵的集合，d ；是d 的第i 个分量。显然 酬加( 扣叫， 对于j = 2 ，3 ，n + l ，a 令- i = j 1 ，运用命题2 1 ( d ) 如果( x ；，e ，；( x ) ) ( o ，0 ) 则 喇= ( 鬲蠢 9 第二章基本结论 一 7 3 螭) ( 孝蠹一 ， 酬炉捌+ h 3 二；卜1 ) ， l 毒1 2 + l 硗1 2 l ，其中e i 表示第i 个元素是0 其它元素是1 的向量，由这些等式 结论易得。 由命题2 1 ( e ) ，可得f 面结论。 命题2 4 假设f 是p o 函数，吾，可是两个给定的正数，且舌 0 使得劈 0 。 证明：由等式( 3 2 ) 知 s k + l = 占k + z k a 6 k = ( 1 一z k ) 占k + zk 厂k 万 0 ， ( 3 7 ) 这就证明了s “1 0 。另一方面， 占。州一九+ l 虿( 1 - 粤k ) s k + 粤k 7 k 云一厂k + l 云 ( 1 一z k ) 九云+ z k 九万一九+ l 手 = ( 7 k 一九+ l 谬 0 ， 第一个不等式由( 3 - 7 ) 得出，第二个不等式由假设y 。t 得出，最后一个不等 式由命题3 5 得出。这就证明了y 。+ 1 t 。 命题3 7 对于任意的k 3 ，吼 0 ，序列 气) 是单调下降的。 证明：由式( 3 7 ) 很容易知道对于任意k s ，吼 0 ，另一方面，由式( 3 7 ) 和命题3 6 知 氛+ j = 气+ z k a s k = ( 1 一z k ) 氏+ z k 九享。 第三章算法描述 所以，命题3 7 结论成立。 ( 1 一z k ) o k + z k 气 2 气 命题3 8 算法3 1 是适定的。 证明：由命题3 4 和3 7 知线搜索( 3 3 ) 有限步终止，由命题2 3 和 4 3 ，命 题2 知等式( 3 2 ) 式对于所有k s 是可解的。那么，算法3 1 是适定的。 第四章算法3 1 的收敛性 第四章算法3 1 的收敛性 在这章，将讨论算法3 1 的收敛性性质。 引理4 1 假设f 是p o 函数，厂是由( 3 1 ) 式定义的。那么算法3 1 不是有限 步终止的，产生序列 y 。) 满足 1 i my ( y 。) = 0 。 k 特别地， y 。) 的任意收敛点y + 是d ( y ) = 0 的解，其中d 如( 1 3 ) 式定义。 证明：由命题3 6 知序列 y ( y 。) ) 是单调下降的，因为对于任意的k s ，有 ，( y 。) 0 ，那么存在，0 使得当k 专佃时y ( y 。) - - - ，。由命题3 2 和2 知对 于任意的k 3 ， 0 p ( y 。+ 1 ) a k + l a k 5a o = p ( y o ) ， ( 4 1 ) 这就证明了序列 p ( y 。) ) 是非负有上界的。那么假设存在p 0 使得 1 i mp ( y 。n ) = p ， k n _ 峋 其中 k 。) 是3 的一个子集。由厂的定义知7 = 0 当且仅当p = 0 。如果p = 0 ， 所求得证。假设p 0 ，那么，由命题3 6 和3 7 及命题2 4 ，运用 3 2 ，定理4 1 的类似方法，得到对于充分大的k 。，存在一个非负整数z 使得 p ( y 。“+ 国2 y 。“) 1 - 2 u ( 1 - 露) 缈。 a k 。， 那么，对于每一个充分大的k 。，都有z k 。z ，国h 缈。所以对于所有充分大 的k 。， p ( y k + 1 ) 1 - 2 0 ( 1 一t 露 ) ( 0 t k n 】a k 1 2 0 ( 1 一贸) 仞 a k ， 与假设p 0 相反，所以 1 6 第四章算法3 1 的收敛性 1 i mr ( y 。) = 0 。 k - - - t - 因此，由p 的定义知 y k ) 的任意收敛点y 是d ( y ) - 0 的解。 引理4 1 证明的是如果 y 。) 的收敛点y 存在，那么它是d ( y ) = 0 的解。这不 意味着 y 。) - 一定有收敛点，下面的定理给出了算法3 1 的全局收敛性。 定理4 2 假设f 是p o 函数，n c p 函数的解集s 是非空有界的，那么由算法 3 1 定义的无限序列 y 。) 是有界的，且 y 。) 的任意收敛点y = ( 占，x 。) 是d ( y ) = 0 的解，s = 0 ，x 是n c p 的一个解。 证明：由引理4 1 ， 1 i mr ( y 。) = 0 ， k - - 由7 的定义( 3 - 1 ) 式( 4 1 ) 知 1 i mp ( y 。) = 0 ， k 那么，当k - - 0 时，占。- - - 0 ， 矽2 ( x ；，f i t , i ( x 。) ) - - - 0 。 i = l 另外，由命题3 7 知对于任意的k s ，吼 0 ，因此，运用命题2 5 即得所求。 下面，考察算法3 1 的局部超线性收敛性。由y 的定义知对于所有算法3 1 中定义的y 。有r ( y 。) 万( p ( y 。) ) ，由这个事实和命题2 2 ，运用 3 2 ，定理5 1 的 相似方法，得到下面关于算法3 1 的超线性收敛性。 定理4 3 假设f 是p o 函数，n c p 函数的解集s 是非空有界的，y = p + ，x ) 是 由算法3 1 定义的无限序列 y 。) 的一个收敛点，所有的v a d ( y ) 是非奇异的。 那么，序列 y 。) 以下面的方式收敛于y i l y h l 一y i i = o ( 1 y 。一y | | ) ， 第四章算法3 1 的收敛性 而且，如果f 在x 周围是全局l i p s c h i t z 连续的，那么 i y 一y i i - - o ( 1 y 。一y 1 1 2 ) ， 占。州= o ( e 。) 2 。 假设中的充分条件v a d ( y ) 是非奇异的在 3 9 ，命题3 3 中给出。 证明：百先，由定理4 2 点y = 。，x ) 是d ( y ) = 0 的解， 由 4 4 】，对于所有 的y 收敛于y 和对于所有的v a d ( y ) ， l i v i | = 0 0 ) 。 f h 假设和命题2 2 知d 在y 点是半光滑的，那么由定理4 2y 。的收敛于y ，得 l iy 。+ y 。一y i i = 旷+ 1 - d ( y 。+ 几歹) 卜y 0 = o ( 慨y 。) - d ( y ) - - v k ( y 。一y ) | l + 九功 = 。( 0 y 。一y 0 ) + o ( f ( y 。) ) ( = o ( 0 y k y 1 1 2 ) + o ( f ( y 。) ) ) 。 ( 4 2 ) 那么，因为d 在y 周围是l i p s c h i t z 连续的，对于所有的y0 l 殳敛于y f ( y 。) = 1 1d ( y 。) 1 1 2 - - o ( 1 l y 。一y 1 1 2 ) ，( 4 - 3 ) 因此由( 4 2 ) 和( 4 - 3 ) ，因为知d 在y 点是半光滑的，对于所有的y 收敛于y ， 所以 l l y k + y 。一y + i i = o ( 1 l y 。一y 咖( = o ( 1 l y 。一y 。i j 2 ) ) 。( 4 - 4 ) 由 4 5 定理3 1 的证明，对于所有的y 0 & 敛于y ，有 ! iy ：一y 睁o ( i l d ( y 。) - d ( y ) j i ) 。 ( 4 5 ) 那么，因为d 在y 是半光滑的，对于所有的y 收敛于y ，有 f ( y 。一y ) - - i i d ( y 。一y ) 1 1 2 第四章算法3 1 的收敛性 = o ( i iy 。+ y 。一y | 1 2 ) = 。( | l y k y 1 1 2 ) ( = o ( 妒一y 1 1 4 ) ) = 。( i i d ( y 。) 一d ( y + ) 1 1 2 ) ( = o ( d ( y 。) 一( d y ) 1 1 4 ) ) = o ( f ( y 。) ) ( = o ( f ( y 。) 2 ) ) 。 ( 4 6 ) 因此，对于所有的y 收敛于y ，有 y “1 = y 。+ y 。， 由此式和( 4 4 ) 证明了 l y “1 一y + 0 = 。( 妒一y | j ) ， 如果f 在x 周围是全局l i p s c h i t z 连续的，那么 旷y1 一y i i - - o ( 1 y 。一y 1 1 2 ) o 下面，由y k 的定义和当k 一0 时，y 。专y + 的结论，对于所有充分大的k ， 7 。= 目f ( y 。) = 刚d ( y 。) n 又因为对于所有充分大的k ，有 y 。州= y 。+ y 。， 所以， 因此， 由( 4 3 ) ( 4 - 5 ) 得 占。+ 1 = 扩+ a e 。= 以云。 占“1 = 刚d ( y 。) 1 1 2 石， 憋字= 熙黔 ：l i l l l ：里! 兰：! 二里! 兰：业：；：o 。 h ”| | d ( y 卜1 ) 一d ( y ) l | 2 这就证明了占“1 = - - o ( 6 。) ，如果f 在x 。周围是全局l i p s c h i t z 连续的，通过上面的 1 9 第四章算法3 1 的收敛性 讨论很容易得到扩+ 1 = o ( e 。) 2 。 通过这一章的讨论我们知道，在以往的半光滑牛顿法中的单调线搜索被非单 调线搜索所取代时，在与文献 3 9 中给出的假设条件相同的情况下，算法是全局 和局部超线性收敛的。 第五章数值计算结果分析 第五章数值计算结果分析 下面，将给出一些算例并将对其结果进行分析。 对于算法中的参数，令万= o 0 2 ，虿= 1 0 ，缈= 0 5 ，d ：0 0 0 1 ， 个算例： 算例1 ： 算例2 ： 算例3 ： 算例4 ： m = ( 妻主三 ，q = 三 ，f = m t m k + q ，初始点x 。 计算下面几 辄 l 1 j m = 一防t 初始枫= ( ： - m = m = 算例5 ：m = 三 ，q = 三 ，f = m t m x + q ，初始点x 。= ( i 。 室訇，q = 虱，f = m t m x + q ，初始点x 。= 三至 ，q = 三 ，f = m t m 恢+ q ，初始点x 。= ； 子 。 使用m a t l a b 计算以上算例，取不同的，分别将迭代次数，d 的范数，函数值， 函数调用次数，c p u 时间列于下表中。 不同的运算结果如下： r o = 0 5 表5 1 2 1 2 2 o 2 1 2 3 2 l 0 2 迭代次数函数调用次数c p u 时间 算例1 1 3 35 4 11 5 6 e 0 0 1 算例2 7 82 8 56 2 0 e 0 0 2 算例3 1 2 55 1 21 2 5 e 0 0 1 第五章数值计算结果分析 l 算例4 1 1 54 5 41 1 0 e 一0 0 1 i 算例5 1 0 84 3 6 6 2 5 e 0 0 2 r o = 0 2 5 表5 - 2 迭代次数 函数调用次数c p u 时间 算例1 1 3 3 4 9 11 0 9 e o o l 算例27 82 7 77 8 0 e 0 0 2 算例3 1 2 55 0 91 2 5 e 0 0 1 算例4 1 0 64 2 51 3 4 e 0 0 1 算例5 9 34 4 5 6 2 5 e 0 0 2 = o 0 5 表5 - 3 迭代次数函数调用次数c p u 时间 算例1 1 0 44 1 39 4 0 e 0 0 2 算例2 6 8 2 4 36 3 0 e 0 0 2 算例31 0 34 0 71 0 9 e 0 0 1 算例41 0 23 9 51 5 6 e 0 0 1 算例5 8 93 8 44 6 9 e 一0 0 2 r o = 0 0 0 5 表5 4 迭代次数函数调用次数c p u 时间 算例19 43 6 89 4 0 e 0 0 2 算例26 92 5 46 2 0 e 0 0 2 算例3 9 53 7 51 1 0 e 0 0 1 算例4 9 13 7 65 6 4 e 0 0 1 算例5 7 42 5 34 6 9 e 0 0 2 由此可见，数值运算的迭代次数与函数的形式和r 。的取值有关。 第六章总结与展望 第六章总结与展望 互补问题是一类非常重要的数学规划问题，它的研究一般分为理论和算法两 个方面，在设计算法时，通常要考虑到如下两个方面：算法的理论性质以及算法 的实际计算效果。而在以往的算法中，半光滑化牛顿算法是一类比较常用的算法， 但是，在以往光滑化算法中，通常采取的是单调线搜索，而在实际问题中，非单 调线搜索能改进数值计算的结果和找到数值最优解的可能性。因此是否能把非单 调线搜索引入到半光滑牛顿算法中就是本文要考虑的问题。 本文主要是将以往的半光滑牛顿算法中的单调线搜索改为非单调线搜索，证 明了非单调算法的适定性，并给出了算法是全局和局部超线性收敛的。但是非单 调线搜索还有其他的形式，本文只是选择了一种引入半光滑牛顿算法，因此，在 求解n c p 函数的其它数值算法中引入非单调线搜索的其他形式应该也可以得到 相似的结论，这有待进一步进行研究。 参考文献 2 】 3 【4 】 【5 6 7 】 8 9 参考文献 h a r k e re t ，p a n gj s ，f 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 li n e q u a l i t ya n dn o n l i n e a r c o m p l e m e n t a r i t yp r o b l e m s ：as u r v e yo ft h e o r y , a l g o r i t h m sa n da p p l i c a t i o n s m a t hp r o g r a m m i n g ，19 9 0 ，161 - 2 0 9 c o t t l er w ：，n o t eo naf u n d a m e n t a lt h e o r e mi nq u a d r a t i cp r o g r a m m i n g