（计算数学专业论文）求解非光滑方程组的newtonkrylov子空间迭代法.pdf

2 0 0 4 年上海大学硕士学位论文 摘要 本文针对非光滑方程组求解问题，提出了求解该类问题的 n e w t o n k r y l o v 子空间迭代法，该类算法不需要计算广义j a c o b i 矩阵，因此非常适用。在一定条件下我们证明了该类算法的局 部超线性收敛性，并分析了其全局收敛性。同时将此类算法应 用于非线性互补问题，非线性优化问题及变分不等式。我们进 行了大量的数值试验。数值结果表明我们提出的算法是有效 的。 全文安排如下：第一章、引言；第二章、非光滑映射及其 性质；第三章、求解非光滑方程组的牛顿法和不精确牛顿法； 第四章、n e w t o n k r y l o v 子空间迭代法及其局部收敛性分析； 第五章、全局收敛性分析。 关键词非光滑映射，n e w t o n 法，拟n e w t o n 法，n e w t o n k r y l o v 子空间迭代法，非线性互补问题，变分不等式 2 0 0 4 年上海大学硕士学位论文 i i a b s t r a c t i nt h i s t h e s i s ，w ep r o p o s eac l a s s o fn e w t o n k r y l o vs u b s p a c e m e t h o d sf o rs o l v i n gn o n s m o o t hs y s t e m so fe q u a t i o n s t h em e t h o d s n e e dn o te v a l u a t et h eg e n e r a l i z e dj a c o b i ，t h e r e f o r et h e ya r e p r a c t i c a l w 色p r o v et h el o c a ls u p e r l i n e a rc o n v e r g e n c ef o rt h en e w t o n k r y l o v s u b s p a c em e t h o d su n d e rs o m ec o n d i t i o n s w 色a l s oc o n s i d e rt h eg l o b a l i z a t i o nf o rt h e s em e t h o d sa n di t s c o n v e r g e n c e a1 0 to fn u m e r i c a l e x p e r i m e n t ss h o wt h ee f f e c t i v e n e s so ft h ea l g o r i t h m s t h et h e s i si s o r g a n i z e da sf o l l o w s ：c h a p t e r1 t h ei n t r o d u c t i o n c h a p t e r2 ，n o n s m o o t hm a p p i n ga n di t sp r o p e r t i e s ，c h a p t e r3 ，n e w t o n m e t h o da n di n e x a c t n e w t o nm e t h o df o rs o l v i n gt h en o n s m o o t h s y s t e m so fe q u a t i o n s ，c h a p t e r4 ，n e w t o n - k r y l o vs u b s p a c em e t h o d sa n d t h el o c a lc o n v e r g e n c e ，c h a p t e r5 ，t h eg l o b a lc o n v e r g e n c e k e y w o r d s ：n o n s m o o t h m a p p i n g ，n e w t o nm e t h o d ，n e w t o n - k r y l o v s u b s p a c em e t h o d ，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 s ，q u a s i n e w t o n m e t h o d ，v a r i a t i o n a li n e q u a l i t y 原创性、声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰 写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：童鎏丝日期竺生主：兰2 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校 有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：童逢鱼导师签名：噬嗍型 2 0 0 4 年上海大学硕士学位论文 第一章引言 哟，仨 = ( ：黑 s ， l 蚱m 卵i n m 2 0 0 4 年上海大学硕士学位论文 2 g 。，= ( i ；誊：! ? 们t u + + v ( 9 ) t 。 = 。 c ，e ， i 叭1 - 瓠托 ( 1 9 ) 2 0 0 4 年上海大学硕士学位论文 3 其中( y k ，。k ) 是f ( y ) 在y k 沿x k 的方向导数 另一种方法是由q i 和s u n 3 5 提出的，我们称之为广义n e w t o n 法 算法2 ： 眦1 = 抓托( 1 1 0 ) 【k 。 + f ( 弛) = 0 其中坛o f ( y k ) ，o f ( y k ) 是f ( y ) 在y k 处的广义j a c o b i 1 1 ，即 0 f ( 弧) 2 c o l i m ，。v f ( 鼽) ) “d f 其中d f 表示f 的f 可微点集 易知，算法1 中，每迭代一步需求解一个非线性方程组，而算法2 每迭代一 步需确定广义j a o b i 矩阵k 在实际应用中，利用( 1 ，1 0 ) 求解非光滑问题，k 特 别难于估计，尤其对于大型问题更是如此，这在实际应用中是非常不方便的此 外，如何有效地求锯广义n e w t o n 方程组 k 。+ f ( 珊) = 0 也是值得深入研究的问题。 注意到，对于求解线性方程组( 1 1 1 ) 的f o m 算法，g m r e s 算法及其他的 k r y l o v 子空间迭代法，只需要矩阵k 与向量“的乘积，不需直接计算k 。因此， 在非光滑情形下，可用 f ，( 鲰，“) f ( y k + , _ 了u ) - - f 一( y k ) ( 1 1 2 ) 近似代替y k u ，结合f o m 算法或g m r e s 算法等k r y l o v 子空间迭代法可得到一种 求解( 1 1 ) 的嵌套算法：非光滑方程组的n e w t o n - k r y l o v 子空间迭代法该算法一 方面克服了计算k 的困难，另一方面有效地求解了( 1 1 1 ) ，因此特别适用已有 很多作者考虑了非线性方程组的n e w t o n - k r y l o v 子空间迭代法 1 2 3 【4 ，但是他 们只是把问题局限在光滑的情况本文，我们考虑了非光滑的情形，实际上是对 光滑情形的推广鉴于算法1 和算法2 中的困难，所以这种非光滑的n e w t o n - f o m 算法和n e w t o n - g m r e s 算法非常适用 2 0 0 4 年上海大学硕士学位论文 4 此外，我们证明了利用n e w t o n - g m r e s 算法求得的g 是函数9 ( ) = f ( ) t f ( ) 在讥处的一个下降方向，由此，我们构造了一个全局的n e w t o n g m r e s 算法，我 们证明了n e w t o n - g m r e s 算法的全局收敛性 全文安排如下：第一章、引言；第二章，我们介绍了非光滑映射及其性质，这 些知识是我们研究问题的基础；第三章，我们介绍了求解非光滑方程组的牛顿法 和不精确牛顿法；第四章提出求解非光滑方程组的n e w t o n - k r y l o v 子空间迭代法： n e w t o n - f o m 算法及n e w t o n g m r e s 算法，并证明了算法的局部超线性收敛性； 第五章、构造了具有全局收敛性的n e w t o n - g m r e s 算法，并证明了算法的全局收 敛性 2 0 0 4 年上海大学硕士学位论文 5 第二章非光滑映射的性质 为了考虑非光滑方程组f ( y ) = 0 的求解，我们首先引进有关非光滑问题的一 些定义和性质这些定义和性质是研究非光滑方程组算法的基础 定义2 1 1 1 1 】假设f ：r n _ + r n 是局部l i p s c h i t z 映射，f 的可微点集表示为 d f ，则 o f ( y ) 2 c o i i m ，j f ( y i ) ) ( 2 1 ) ，z e d f 称为f 在y 处的广义j a c o b i 定义2 2 假如o f ( y ) 中的所有元素是非奇异的，则称f 在点y 处是正则的 若f 在y 的邻域内的任意一点都是正则的，则称f 在y 的邻域内是正则的 性质2 1 1 1 对任意的。，y r n f ( y ) 一f ( x ) c oo f ( i x ，j ) ( y z ) ( 2 2 ) 性质2 2 1 1 设f ：r n - 酽是局部l i p s c h i t z 映射，且对任意h r n ，极限 。l i r a 。 y ) 存在则方向导数 耿咖) = l m i m 盟掣 ( 2 3 ) 存在，而且成立下面的等式： f i ( ； ) 2 ，。占m + y ) ( 2 4 ) 定义2 3 1 3 5 称局部l i p s c h i t z 映射f ：r n _ r n 在点g 处是半光滑的，如果对 任意的h r “ 。l ，i ( m 。+ 。，) v h ) ( 2 5 ) 存在 2 0 0 4 年上海大学硕士学位论文 6 半光滑定义最早在1 9 7 7 年由m i f f l i n 2 5 引入，并由q i 和s u n 3 5 推广到向量 值函数凸函数，分片光滑函数都是半光滑函数，对于半光滑函数的应用和其他 非光滑性质见6 7 1 2 【1 3 】 2 5 2 6 3 4 a 9 4 0 。 很明显，函数f 在点y 处半光滑强于条件。船 矿 ) 存在，并且能推得 h a d a m a r d 方向导数满足 。lira。盟掣=，。li器thi)vhto f ( ) ( 2 6 ) 矿一 y + 。 引理2 1 【1 2 假设f ：舻_ r n 是局部l i p s c h i t z 映射，即存在工及d ，使得当 6 时，有l i f ( y + 。) 一f ( ) l | i t l z l ，且在g 处对vh ，f ( g ；h ) 存在，那么 ( i ) f ；) 是l i p s c h i t z 连续的； ( i i ) 对vh 存在一个v o f ( y ) 使得 f ( g ；h ) = v h( 2 7 ) 弓l 理2 2 1 3 5 假设f ：r n _ 形是局部l i p s c h i t z 映射。下列命题是等价的 ( i ) 尸在点y 处是半光滑的； ( i i ) 对任意的h 且| i h l i = l ，( 2 4 ) 式右端的极限一致收敛； ( i i i ) 对任意的h 且l i h l i = 1 ，( 2 6 ) 式右端的极限一致收敛； ( i v ) 对任意的v o f ( y + h ) ，h _ + 0 ，有 v h f 7 ( ；h ) = o ( 1 l h l t )( 2 8 ) ( v ) ，协盟铲”嵩? ， 推论2 3 假设f ：r ”_ r “是局部l i p s c h i t z 映射，如果f 的每一分量在点y 处半光滑，则f 在点y 处半光滑。 证明对y + h d f ，h - 0 ， m t t f 7 ( v + ； ) 一f b ； ) | 【s l 爿b + ； ) 一( v ； ) l = 1 对只应用( 2 9 ) ，对每一个i 我们有 耳白+ ；h ) 一群( g ；h ) = o ( 1 l h l l ) 2 0 0 4 年上海大学硕士学位论文 7 这样，对f 就有( 2 9 ) 定义2 4 1 3 0 1f ( g ) 在点= 处的f 一导数v f ( z ) 称为强的，如果 l i m 坐型掣墨掣：o ( 2 1 0 ) 。，i ) 一( “)l i x 一l i 定义2 5 3 5 设f 在点y 处是半光滑的我们称f 在y 处是1 一阶半光滑的 如果对于任意的v o f ( y + ) ，h _ 0 ，有 v h f ( ，h ) l l = o ( 1 l h l l 2 ) 若f 在y 的邻域内的任意一点都是1 阶半光滑的，则称f 在y 的邻域内1 一阶半 光滑 如果f 在点y 处是半光滑的，那么对vh _ 0 ，见【3 3 f ( y + h ) 一f ( y ) 一f 7 ( ；h ) = o ( 1 l h l l )( 2 1 1 ) 如果f 在y 处是1 阶半光滑的，则对vh - 0 ，见 3 5 】 i i f ( y + h ) f ( g ) 一f ( ，h ) l l = o ( 1 l h l l 2 ) ( 2 1 2 ) 引理2 3 2 3 1 假如f 在y 处是正则的，则存在m 0 使得m = m n z l l v x l l ： v 卯7 ( ) ，。并且对于任意给定的e 0 ，存在y 的一个邻域n ( y ) ，使得f 在 n ( y ) 内是正则的，且对任意v o f ( x ) ，z en ( u ) ，有0 y _ 1 | | m + e 2 0 0 4 年上海大学硕士学位论文 8 第三章求解非光滑方程组的牛顿法和不精确牛顿法 3 1 求解非光滑方程组的牛顿法 由于非光滑方程组的理论价值和实际应用背景，非光滑方程组的求解引起了 很大关注，并且已提出许多求解非光滑方程组( 1 1 ) 的方法，其中最重要的有两种 方法一种方法是由p a n g 3 0 】提出的 算法1 ： 肌1 _ 鲰札( 3 1 ) lf ( 弧，x k ) + f ( u k ) = 0 其中f ( y k ，t ) 是f ( y ) 在玑沿x k 的方向导数。 p a n g 在文献【3 0 】给出了其收敛性定理， 定理3 1 1 3 0 设f ：r n _ 舻在y 的邻域内是b 可微的，其中f ( y + ) = 0 假 设f ( y ) 在y + 处有强f 导数v f ( y + ) 存在，且非奇异，则存在圹的邻域n ，对任 意的初始估计y o n ，由算法1 产生的序列 讹) cn 收敛于y 此外，如果方 向导数在矿处是l i p s c m t z 连续的，则序列 y k 平方收敛于y + 另一种方法是由q i 和s u n 3 5 提出的，我们称之为广义n e w t o n 法 算法2 ； 可。+ 1 = 掣+ z 。( 3 2 ) ib k + f ( 可k ) = o 其中y k o f ( y k ) ，o f ( y k ) 是f ( y ) 在y k 处的广义j a c o b i 1 l 】，即 0 f ( y k ) = c o ，j 甄v f ( y d “e d f 其中d f 表示f 的f 可微点集 算法2 的收敛性定理如下， 2 0 0 4 年上海大学硕士学位论文9 定理3 2 1 3 5 设局部l i p s c h i t z 连续映射f ( y ) 在旷处半光滑，且所有的v o f ( y + ) 都非奇异，其中f ( y + ) = 0 ，则由算法2 有意义，且由算法2 得到的序列 t 玑) 收敛于y + 此外，如果f ( ) 在y + 处是p _ 阶半光滑的，则收敛阶为l + p 。 3 2 不精确牛顿法 在广义n e w t o n 法的每步迭代中，我们都需要求解广义n e w t o n 方程 k 巩+ f ( y k ) = 0 ( 3 3 ) 当该线性方程组的维数较高时，计算其精确解的开销就会很大相应地，广义n e w t o n 法的计算量也就会很大对于大型问题，一些计算系统的存储也可能受到限制， 为此我们利用某种迭代法来近似的求解( 3 3 ) ，由此即得求解非光滑方程组的不精 确n e w t o n 法 肌严珊札t( 。4 ) 【k z = 一f ( 女) + n 这里y k a f ( y k ) ，n 称为残向量 下面考虑解非光滑方程组的不精确n e w t o n 法的收敛性： 定理3 3f ：d 舻_ + 且“是开凸集d r n 上的局部l i p s c h i t z 映射设f 在 y 4 d 处是1 一阶半光滑的和正则的，其中f ( y + ) = 0 若由( 3 4 ) 产生的迭代序列 弧) ，= 0 ，1 ，2 ，满足下述不等式： l i k z k + f ( 瓠) | | sa l i f ( y k ) 1 1 2( 3 5 ) 其中v k o f ( y k ) ，a 0 ，则不精确n e w t o n 法( 3 4 ) 局部平方收敛 证明因为f 在y + 处是正则的，且是局部l i p s c h i t z 映射，故对任意的 0 ， 存在0 1 0 ，m 0 和l 0 ，使得当l l y y + | | 0 ，当y ( 旷) i 剖岫一+ | | 田且v o f ( y ) 时，有 l l y ( g y + ) 一f ( g ，g g + ) 1 1 ；| i 一g + | | 2( 3 6 ) 2 0 0 4 年上海大学硕士学位论文 1 0 i i f ( y ) 一f ( v + ) 一f b + ，一+ ) 忪；i l y - g + 1 1 2 ( 3 7 ) 利用( 3 6 ) ，( 3 7 ) 可得： l i f ( y ) 一f ( v + ) 一v ( v 一圹) | | = i i f ( y ) 一f ( v + ) 一f ( 4 ，y y + ) 一( v ( y y + ) 一( 矿，y 一) ) l 茎i i f ( y ) 一f ( v + ) 一f ( 扩，y 一矿) | | + i i v ( y y + ) 一f ( 圹，y y 4 ) 曼；i l y - g m i i + 扣一“i i = o i l y 一旷1 1 2 于是，当y n ( v + ) 时， y k + l y + | | = i l t y + + 。女| | i i v 1 l i l i v k ( y 一y + ) + y k x k i l i i 盯1 l i l i v k ( y k y + ) 4 - v k r c k + f ( y k ) 一f ( v k ) e i l i 盯1 l i 1 l v k z k + f ( y k ) i l + l i f ( y k ) 一f ( v + ) 一v k ( v k 一+ ) 扪 m o i i f ( y d i l 2 + c l l v 一玑1 1 2 sm ( , a l 2 + c ) 【i g 女一g + 1 1 2 = 劁弧一圹1 1 2 因此，利用归纳法可得不精确牛顿法局部平方收敛 2 0 0 4 年上海大学硕士学位论文 第四章n e w t o n - k r y l o v 子空间迭代法及其收敛性分析 4 1n e w t o n - f o m 算法 设f ：dc r “_ + r “是局部l i p s c h i t z 映射，我们考虑非光滑方程组 f ( y ) = 0( 4 1 ) 的求解一种求解( 4 1 ) 的比较经典的算法是广义n e w t o n 法 y k + l = 州y k + x k ：。 z ， 其中，k o f ( 9 k ) 可见，算法( 4 2 ) 每迭代一步需确定广义j a c o b l 矩阵k ，在 实际应用中，k 特别难于估计，尤其对于大型问题更是如此，这在实际应用中是 非常不方便的此外，如何有效地求解广义n e w t o n 方程组 y k x k + f ( y k ) = 0( 4 3 ) 也是值得深入研究的问题 首先考虑线性方程组 a x = b ( 4 4 ) 的求解，其中 4 = v k ，k o f ( y k ) ，b = - - f ( y k )( 4 5 ) 对于任意的初始近似x 0 ，求解( 4 4 ) 的f o m 算法如下： 算法4 i ( f o m 算法) s t e p1 计算r 0 = b a x o ，令u 1 = 7 0 l l r o l l 2 s t e p2 对于j = 1 ，2 ，m 计算： 2 0 0 4 年上海大学硕士学位论文1 2 h i jz ( a u j ，“1 ) ，( i = 1 ，j ) 嘶+ l = a u i 一h i j u i h j + t j = i t w j + tt 2 u j + l = q 十1 h j + i j s t e p3 计算t m = x 0 + 娠1 u m t r 0 ，其中= u l ，“。】，日m 是非零元为 的m m 上h e s s e n b e r g 矩阵 由于在算法4 1 中不需要直接计算k ，而是需要k u ，于是可以利用下式 f ( y + 口“) 一f ( 口) 。 来近似代替k u ，结合( 4 2 ) ，可得求解非线性方程组( 4 1 ) 的n e w t o n f o m 算法 算法4 2 ( n e w t o n - f o m 算法) s t e p l 给定e 0 ，a 0 选择初始近似g o r 竹，女= o s t e p2 令q o = ( f ( y k + 口o o ) 一f ( 弧) ) 口o ，口o 0 ，其中岔。是线性方程组( 4 4 ) 的解的初始近似而= 一f ( 珊) 一q o ，声= 怖1 1 2 ，也1 = 膳，g l ：也1 ， j = 0 s t e p3 j = j + 1 q j + l = ( f ( y k + q 奶) 一f ( v k ) ) 。j ， 0 ， l j = ( 劬+ 1 ，啦) ，i = 1 ，一，j 叫j + 1 = q j + 1 而+ l ，j = i i q 十1 1 1 2 ， f i j + i = 奶+ 1 岛扎j 令岛是非零元为 巧的j j 的上h e s s e n b e r g 矩阵，岛：陋1 ，吗】 计算= 如+ 白亏1 凹而 乃21 1 吩1 1 2 = h f ( y k ) + ( f ( k + o j 量j ) 一f ( y 女) ) a 3 1 1 2 s t e p4 若乃s a 归( 讥) 惦或j = n ，则令m = 且做下一步，否则转s t e p3 弘 h ，汹 2 0 0 4 年上海大学硕士学位论文 1 3 s t e p5 令g k + 1 = 9 k + 。m s t e p6 若i i f ( y k + i ) 1 1 2 墨e ，结束否则，k = + 1 转s t e p2 4 2 收敛性分析 为了书写方便，省去下标k 以下仍记a = v o f ( y ) ，b = 一f ( y ) 下面分 析n e w t o n - f o m 方法的收敛性令 岛= 口f + 1 一a 啦，i = 1 ，一，m 定义n n 矩阵， e 。= e m 霹，e ”= p 1 ，一，s m 】r n “ 于是有 ( a + b 。) 也= a f t i + e “醒啦 = a ( t i + 晶 = q i + t ( i = 1 ，一，m ) 引理4 1 设f ：d 舻_ 且“是局部l i p s c h i t z 映射。设f ( y ) 在y 处1 阶半 光滑则存在 0 ，6 0 ，使得当l 口o o l 2 0 ，当1 2 0 ，他 0 使得 i l y h f b ，h ) 1 1 2s 酗h 惦( 4 9 ) 2 0 0 4 年上海大学硕士学位论文 1 4 i i f ( y + h ) 一f ( ) 一f b ，h ) 1 1 2 到圳； ( 4 1 0 ) 因此由( 4 9 ) ( 4 1 0 ) ，有 l i f ( y + h ) 一f ( y ) 一v h l l 2 兰i i f ( y + h ) 一f ( ) 一f b ，h ) l f 2 + i i y h f ( ，h ) 1 1 2 ( 4 1 1 ) 取7 = m a x 7 l ，加) ，当l i h l h d 时，由( 4 1 1 ) h f ( y + h ) 一f ( ) 一y h l l 2 ；i l l l ； ( 4 1 2 ) 令6 0 = q o a 岔o 因为i 印奎o i l 2 d ，所以由( 4 1 2 ) 有 1 1 e o l l 。= i l q o a 岔。1 1 2 j 记 三m = 如1 螺确= 声崴1 e ， 其中卢= 怖1 1 2 则由算法4 2 可得 k , m = 童o + 皇m 于是， = b a 。= b a ( 仝o + l 。) = ( ( 6 一a 仝o ) 一户o ) 4 - ( 而一( a + e 仉) 童m ) + 舀k 童m = o 4 - ( f o 一( a 4 - e r n ) j 。) + e m m 因此， 加= i i i 2 s l l e o l h 十1 1 f o 一( a + e 。) 2 。1 1 2 + 1 1 e 。o 。1 1 2 ；| 印川2 。鸭+ l l 确一( a + e 。) 1 1 2 + 1 1 e 矗钿i j 2 因为f 是一阶半光滑的，所以由( 4 1 2 ) ，当们i f f _ 干而汗 0 ，选卢，d 足够小，使得： a v l l a - 11 1 2 1( 4 1 3 ) 锄硼+ 驯一( 1 i b 一腧+ 钧钏) ；a i i f ( y 川；( 4 1 4 ) y + v d ，v v r “，l i v 1 2 6( 4 1 5 ) 选矿= ( ( 7 1 ，口。) t ，使l i o “1 1 2 d ，1 0 - 0 1 卢，1 0 - 0 1 1 1 i 0 1 1 2 d ，则存在m 0 ，n ) 使得 加= i i b a 岔。1 1 2 a l l f ( y ) l l ； 2 0 0 4 年上海大学硕士学位论文1 6 证明由假设条件( 4 1 3 ) 怕_ 1 e 训2 茎i i a _ 1 蚓l 五k l l 2 曼l i a “i h l i s “i h s i i a i i 。娑 l 一2 所以，a + e m = a ( i + a 。) 非奇异，且 i i ( a + 时1 i i 。s 两矸烩s 剖斜赢剑旷1 i i 。 记f o = b q o ，贝0 由弓理4 1 l l f o i l 2 = 8 b q o l l 2 = “( 6 一a 童o ) 一o i l 2 s i i b a o 1 1 2 + l i e o l l 2 l l b - 舭。i i z + ；h i i i ：。幢 设赢为+ 晶，) z = f o 的解，则 j i z ：, 1 1 2 = i i ( a + 日。) 一1 9 0 1 1 2 2 1 1 a 一1 1 1 2 i i # o l l m j 。一碥= ( a + e m ) 一1 ( 直+ e 。) 三m 一粕】 因此 l l 毛钆i f 2i l z 三1 1 2 + | | ( a + e m ) 一1 1 1 2 声k s2 1 1 a 一1 1 1 2 l l f o i l 2 + 2 1 1 a 一1 1 1 2 p 。 = 2 1 1 a 一1 以l i f o i | 2 + | 舀。) 其中卢。= 一( a + 上k ) 三m | | 2 所以由引理4 1 ， j ；+ 赫+ 割a ”i i 。i i j m i f 。 ；h 蚓睦+ 两+ 导炉- 1 州划l 。+ 两) 譬忪。1 1 2 + n i i a - 。1 1 2 ( 1 i b a 卸1 1 2 + 譬忪川；) + 芦m ( 1 + 酬a 1 1 2 ) s ；a i i f ( y ) i i ；+ 。( 1 + 6 7 l | a 一1 舱) 2 0 0 4 年上海大学硕士学位论文 1 7 下证 赫( 1 + 洲旷z ) s ；n i ( f ( v ) l l l ( 4 1 6 ) 我们分两种情况讨论 ( 1 ) 若f o = 0 ，即6 = q o 则 加= l i b a x o l l 2 = f i q o a o l l 2 = 1 1 0 1 1 2 ；h o l l l 川；勃钏 ；a i i f ( 洲 结论成立 ( 2 ) 若f o 0 ，此时钒= p o t t f o tl 2 ，e t = 1 n ，目= q 2 一a f t l ，由以上证明可知 a + e l 非奇异所以q 2 = ( a4 - e 1 ) o l 0 ，于是得到西2 ( a ) 若曲2 = 0 ，则 2 l = 0 ，于是由引理4 2 自l = o ( a + e 1 ) m = l l 0 且2 l = 怖1 1 2 舟也1 是( a + e 1 ) z = f o 的精确解即芦l = 怖一( a + e 1 ) j t l l 2 = 0 所以( 4 1 6 ) 成立 ( b ) 若西2 0 ，则算法可继续下去，得吐2 0 ，此时得到x l ，若z 1 满足算法 4 2 的s t e p 4 ，则定理结论成立，否贝定义e 2 = e 2 仍，这里2 = h ，e 2 】，2 = q 3 一a f t 2 ，同理可得a + 岛非奇异，因此q 3 = ( a + 玩) 矗2 0 ，得到西3 。 一般地，若由算法4 2 得到= 陋h ，也。 及曲。+ l ，则可类似地得到a + 非奇异 若曲。+ 1 = 0 ，则宜i 1 存在，且是精确解，这样知= 0 。 若蛾0 ，t = 1 ，n ，且存在某个i 满足算法4 2 中s t e p 4 ，则定理结论成立； 否则l 。是( a + 玩) z = p o 的精确解。所以磊= 0 综上所述，定理结论成立 定理4 2 设f ：r ”_ r “是开集d 形上局部l i p s c h i t z 映射，设f 在矿的 邻域内1 阶半光滑，且是正则的，其中f ( y + ) = 0 。则由n e w t o n - f o m 算法产生的 序列 弧) 局部平方收敛于y + 2 0 0 4 年上海大学硕士学位论文 1 8 证明用数学归纳法证明 k = 0 时，选扩= ( 口l ，) r n ，使得l l 一“l 2 0 ，使得 5 0 训a - 1 1 1 2 0 ，口 0 选择初始近似y o r “，令k = 0 s t e p2 令口o ：( f ( 蛳+ a o k o ) 一f ( 弧) ) o o ，o 0 0 ，其中卸是线性方程组( 4 4 ) 的解的初始近似f o = 一f ( 靴) 一q o ，序= l l f 0 0 2 ，m = f o l b ，q 1 2 缸l ， = 0 s t e p3 j = j + 1 2 0 0 4 年上海大学硕士学位论文 q j + l = ( f ( y k + q 奶) 一f ( 纨) ) 勺，q 0 h i j = ( q j + l ，也) ，i = 1 ，一，j j e j + 1 = q j + x 一r ，j 砒 t = 1 屯+ l ，j = l i 奶+ 1 | | 2 q + l = w j + l h j + l , j 定义( j + 1 ) jh e s s e n b e r g 矩阵彤，其非零元为硝，岛= 矗1 ，也2 ，奶】 求解极小化问题 d m i 刚n 廖8 1 一q 吼 ( 4 2 0 1 ) 其中e l = ( 1 ，0 ，o ) r 是j + l 维单位向景，记奶为( 4 2 0 ) 的解 计算q = 。o + 白d j 岛= 1 1 0 1 1 2 = i i f ( 纨) + ( f ( 弧+ q 劫) 一f ( y k ) ) a y 1 2 s t e p4 若力a t l f ( y k ) i i ；或j = n ，则令m = j 且做下一步，否则转s t e p3 。 s t e p5 令y k + l = y + z m 。 s t e p6 若l i f ( y 女+ i ) 1 1 2 e ，结束。否则，k = k + 1 ，转s t e p2 可以利用类似于定理4 1 的证明方法证明下述定理 定理4 3 假设定理4 1 的条件成立，则存在m l ，n ) ，使得 两= 1 1 6 一a 童。1 1 2 o i i f ( y ) i i ； 成立，其中士。是由算法4 4 得到的线性方程组的近似解 类似于n e w t o n - f o m 方法，由算法4 4 得到的序列 y t ) 是平方收敛的 定理4 4 设f ：舻- r “是开集d r “上局部l i p s c h i t z 映射，设f 在y + 的 邻域内1 一阶半光滑，且是正则的，其中f ( y + ) = 0 则由n e w t o n - g m r e s 算法产生 的序列 靴) 局部平方收敛于圹 2 0 0 4 年上海大学硕士学位论文2 1 4 4 n e w t o n - k r y l o v 子空问迭代法在非线性规划问题上的应用 f c 们= ( 三 ：) = ( 竺! 二：) = 。 c a z q = r ”l g ；+ ( ( g ) ) 2 o ，i = l ，n 下面我们分析f 在r “上的广义j a c o b i 矩阵对y q ，有 其中 v f ( y ) = d i a g ( 4 i ( y ) ) v f ( y ) + d i a g ( p i ( y ) ) m b ) = ，l ( ) ( 芹( y ) + ? ) 一 一1 p t ( g ) = 9 i ( ，? ( g ) + g ；) 一 一1 2 0 0 4 年上海大学硕士学位论文 很明显，( 7 i ( y ) + 1 ) 2 + ( m ( y ) + 1 ) 2 = l ，i = 1 ，一，n 当隹n 时，对任意的v o f ( y ) ，可表示为 v = d i a g ( 一i ) v f ( y ) 十d i a g ( # i )( 4 2 5 ) 其中 ( m + 1 ) 2 + ( 地+ 1 ) 2s 1 ，i = 1 ，一，n( 4 2 6 ) 但是一般情况下，上述结论反过来不一定成立 定义4 1 映射，称为一致p 映射，如果存在o 0 满足 l 0 ，即得引理结论 命题4 1 假设，：r ”_ 舻是连续可微的，如果，是一致p 映射， 的v o f ( y ) ，y 础，v 是非奇异的 证明对任意的v o f ( y ) ，y r n ，设d 是方程组v d = 0 的解 奇异，只要证明d = 0 即可。由( 4 2 5 ) ( 4 2 6 ) ，存在常数m ，h ，肛h _ 即 d i a g ( 7 i ) v f ( y ) d 4 d i a g ( # i ) d = 0 p l d l + m v ，l ( y ) d = 0 胁d 竹十h v 厶( g ) d = 0 对第i 个方程两边同乘以d i ，我们有 , u l d 十d 1 7 l v k ( u ) d = 0 肛。d ：+ d n v f n ( y ) d = 0 则对任意 要证矿非 ，“。使得 2 0 0 4 年上海大学硕士学位论文 由( 4 2 6 ) ，若m = 0 ，则啦= 0 若m o ，m 地异号，有 l m a x 。d i v f i ( y ) d 然一等d 2 o 又因为，是p - 映射，所以d = 0 ，结论成立 命题4 2 假设，：r “一r “是两次连续可微的，则由( 4 2 4 ) 定义的f 在舻上 是1 阶半光滑的 证明我们只要证明f 在f 不可微的点处是l 一阶半光滑的即可，为此只需 考虑y 芒q f 在处是1 一阶半光滑的当且仅当对所有的i ，f 在处是1 阶 半光滑的。不失