（应用数学专业论文）非线性等式约束优化问题的一类既约hessian算法研究.pdf

摘要 对于解决非线性约束最优化问题，罚函数法、可行方向法、逐步二次规触 法( s q p ) 和既约h e s s i a n 法是目前应用比较广泛的几种方法其中，逐步二次 规划法已经成为求解中小规模非线性约束最优化问题的一类最重要的方法，而 既约h e s s i a n 法以每次迭代计算量小且算法所需内存也小等优点更是得到了许 多研究者的青睐既约h e s s i a n 法一般可分为双边既约h e s s i a n 法和单边既约 h e s s i a n 法1 9 7 8 年。w m u r r a y 和m _ h w r i g h t 首先提出双边既约h e s s i a n 的 思想，后来一些学者对此进行了研究并提出一些算法这些算法一般都具有局部 2 步q 卜超线性收敛速度1 9 8 5 年，j n o c e d a l 和m l o v e r t , o n 提出单边既约 h e s s i a n 法，并且证明了此方法具有局部1 步q - 超线性收敛速度本文结合单 边既约h e s s i a n 法较快的收敛速度和双边既约h e s s i a n 法保持正定又较小的存储 的优点。提出一种分别对单边既约h e s s i a n 的近似阵和双边既约h e s s i a n 的近似 阵校正的既约h e s s i a n 算法，在一定条件下证明了算法具有局部1 步q 卜超线 性收敛速度；进一步地，在新算法的基础上又提出一种具有全局收敛性的既约逐 步二次规划法数值实验表明。本文提出的两种新算法是有效的 整篇论文内容安排如下t 在第一章中，首先简要的介绍了最优化问题的提出以及判断最优解常用的最 优性条件，回顾了非线性最优化问题常用的几类方法 在第二章中，就非线性等式约束问题，提出一种既约h e s s i a n 校正算法，此 算法分别对l a g r a n g e 函数的单边既约h e s s i a n 的近似阵和双边既约h e s s i a n 的 近似阵进行校正证明了若每次迭代至少有一者被校正时，算法具有1 步q 一超 线性收敛速度，并给出数值结果 在第三章中，以第二章提出的算法为基础，构建一种解决非线性等式约束问 题的既约s q p 方法为避免m a r a t o s 效应，此方法采用f l e t c h e r 的光滑精确罚 函数的逼近形式作为价值函数，在一定条件下证明了算法的全局收敛性并且给出 数值结果 关键词：约束最优化，既约h e s s i a n ，拟牛顿方法，逐步二次规划，局部超线性 收敛，全局收敛性 a b s t r a c t p e n a l yf u n c t i o nm e t h o d s ，f e a s i b l ed i r e c t i o nm e t h o d ，s e q u e n t i a lq u a d r a t i c p r o g r a m m i n gm e t h o da n dr e d u c e dh e s s i a nm e t h o da r ea p p l i e dm o r ee x t e n s i v e f o rs o l v i n gn o n l i n e a rc o n s t r a i n e do p t i m i z a t i o np r o b l e m s e q u e n t i a lq u a d r a t i c p r o g r a m m i n gm e t h o dh a sb e e nt h em o s ti m p o r t a n tm e t h o df o rs o l v i n gm i d d l e s c a l ea n ds m a l ls c a l en o n l i n e a rc o n s t r a i n e do p t i m i z a t i o n m o r e o v e r ，r e d u c e dh e s - s i a nm e t h o di sl e a so t h e rk i n ( i so fm e t h o 出w h e t h e ri nm e m o r yo re a c hi t e r a t i v e c a l c u l a t i o n s ，s om a n ya u t h o r ss t u d i e dt h em e t h o d sf o rt h e s ea d v a n t a g e s r e - d u c e dh e s s i a nm e t h o dc o n t a i n so n e - s i d e dr e d u c e dh e s s i a nm e t h o da n dt w o - s i d e d r e d u c e dh e s s i a nm e t h o d i n1 9 7 8 ，w m u r r a ya n dm h w r i g h ts u g g e s t e dt h e i d e ao ft w o - s i d e dr e d u c e dh e s s i a nm e t h o d 1 a t e r ，m a n ya u t h o r ss t u d i e da n dp r o - p o s e ds o m ep a r t i c u l a ra l g o r i t h m s t h ec o n v e r g e n c er a t e so ft h e s em e t h o d sa r e l o c a u yt w o - s t e pq - s u p e r l i n e a r i n1 9 8 5 ，j n o c e d a la n dm l o v e r t o np r o p o s e d o n e - s i d e dr e d n c e dh e s s i a nm e t h o da n dp r o v e dt h em e t h o dh a sal o e a lo n e - s t e p q - s u p e r l i n e a rc o n v e r g e n c ep r o p e r t y i nt h i sp a p e r ，t h ef a s t e rc o n v e r g e n c er a t e o fo n e - s i d e dr e d u c e dh e s s i a nm e t h o da n dt h el e s sm e m o f yo ft w o - s i d e dr e d u c e d h e s s i a nm e t h o da r ec o n s i d e d ，w ed e s c r i b ea na k o f i t h mw h i c hu p d a t 髓a na p p r o x - i m a t i o nt oo n e - s i d e dr e d u c e dh e s s i a na n dt w e - s i d e dr e d u c e dh e s s i a ns e p e r a t e l y i ti ss h o w nt h a tt h em e t h o di sl o c a l l yo n e - s t e pq s u p e r l i n e a r l yc o n v e r g e n tu n d e r c e r t a i nc o n d i t i o n b a s eo nt h en e wr e d u c e dh e s s i a nm e t h o d ，w ea l s op r o p o s ea r e d u c e ds e q u e n t i a lq u a d r a t i cp r o g r a m m i n ga l g o r i t h m ，t h ea l g o r i t h mh a sg l o b a l c o n v e r g e n c ep r o p e r t y i nc h a p t e r1 ，w ef i r s ti n t r o d u c et h ed e v e l o p m e n to fo p t i m i z a t i o na n ds o m e e x t e n s i v eo p t i m a l i t yc o n d i t i o n sw h i c ht od e c i d et h eo p t i m u ms o l u t i o n w er e v i e w s e v e r a lm e t h o d so fn o n l i n e a ro p t i m i z a t i o n i nc h a p t e r2 ，t h ep r o b l e mc o n s i d e r e di st h a to fm i n i m i z i n gan o n , n e a rr u n e - t i o ns u b j e c tt oas e to fe q u a l i t yc o n s t r a i n s w ed e s c r i b ea na l g o r i t h mw h i c h u p d a t a p p r o x i m a t i o n st oo n e - s i d e dr e d u c e dh e s s i a na n dt w o - s i d e dr e d u c e dl - e s - s i a ns e p e r a t e l y i ti ss h o w nt h a ti fa tl e a s to n eo ft h eu p d a t e si sp e r f o r m e da t e a c hi t e r a t i o n ，t h em e t h o di sl o c a l l yo n e - s t e pq - s u p e r l i n e a r l yc o n v e r g e n t ，a n d s o m en u m e r i c a lr e s u l t sa r eg i v e n i nc h a p t e r3 ，b a s eo nt h ea l g o r i t h md e s c r i b e di nc h a p t e r2 w ep r o p o s ear e - d u c e ds u c c e s s i v eq u a d r a t i cp r o g r a m m i n g a l g o r i t h mf o rs o l v i n go p t i m i z a t i o np r o b - l e m sw i t hn o n , n e a re q u a l i t yc o n s t r a i n t s i no r d e rt o a v o i dt h em a r a t 0 6 e f f e c t ，t h e m e r i tf u n c t i o n su s e da r ea p p r o x i m a t i o n st of l e t c h e r 8d i f f e r e n t i a b l ee x a c tp e n a l t y f u n c t i o n g l o b a lc o n v e r g e n c ei sp r o v e do l ls o m ec o n d i t i o n s ，a n d8 0 m en u m e r i c a l r e s u l t sa r eg i v e n k e yw o r d s ：c o n s t r a i n e do p t i m i z a t i o n ，r e d u c e dh e s s i a n ，q u a s i - n e w t o nm e t h - o d s ，s u c c e s s i v eq u a d r a t i cp r o g r a m m m i n g ，l o c a u ys u p e r l i n e r l yc o n v e r g e n c e ，g l o b a l c o n v e r g e n c e 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或 集体已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名卫弗 日期，御年f 月j 日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留，使用学位论文的规定，学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将 学位论文用于菲赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将 学位论文的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出 版保密的学位论文在解密后适用本规定 学位论文作者签名。豆移 日期；2 唧年，月f 日 1 非线性优化问题简介 这一章里，将简要介绍非线性最优化问题的发展现状第一节。简要地 阐述最优化问题的提出以及判断最优解常用的最优性条件；第二节。总结 了非线性最优化问题几类常用的方法，重点是约束优化的几类方法；在最 后一节，明确提出构建薪算法的动机和技术手段 1 1 最优化问题的提出及最优性条件 最优化理论与方法是一门应用性很强的年轻学科虽然最优化可以追溯到十 分古老的极值问题，但直到1 9 4 7 年d a n t z i g 提出一般线性规划问题的单纯形法 之后。它才成为- - n 独立的学科，随着现代科技的发展和计算机的广泛应用，进 一步推动了最优化理论和算法的研究今天，最优化理论与方法在经济规划，政 府决策，生产管理、交通运输和军事国防等方面都得到了广泛的应用，已经成为 一门十分活跃的学科 一般来说，最优化问题可归结为求解如下的极小值问题 卿m ) 其中，。d 是决策变量，f ( x ) 为目标函数。d 彤为可行域 根据变量的类型，最优化问题可分为连续型最优化和离散型最优化( 也称组 合优化) 连续型最优化问题又可分为目标函数和约束函数均为线性时的线性规 划问题，以及目标函数和约束函数中至少有个为非线性时的非线性优化问题 本论文研究方向是非线性优化问题非线性优化问题通常有如下形式： 砌r a i n 。m ) 1 ( 1 1 1 ) s t c i ( z ) 0 ，i = 1 ，2 ，一，m 。； g ( z ) = 0 ，t = m 。+ 1 ，m ； ( 1 1 2 ) ( 1 1 3 ) 冗z ) 及q ( ) 0 = 1 ，2 ，m ) 都是定义在形上的函数，其中至少一个为非线 性函数满足( 1 1 2 ) 一( 1 1 3 ) 的点称为可行点。所有可行点所组成的集合被称为 可行域，记为x ，显然 x = x l c i ( x ) = o ， = 1 ，m 。；c d ：功20 ， = m + 1 ，m ) ( 1 1 4 ) 当m = 0 时，问题( 1 1 1 ) 一( 1 1 3 ) 是无约束优化问题，否则，是约束优化问题在 约束优化问题中。如果只有等式约束，即m = m 。 0 ，则称为等式约束问题另 一种特殊情形是所有的约束函数都是线性函数，这时我们称问题( 1 1 ，1 ) 一( 1 1 3 ) 是个线性约束优化问题 下面我们给出非线性优化问题的全局最优解和局部最优解的定义 定义1 1 设矿x ，如果 ，( z ) 2 ，( z + ) ，v x x 成立，则称矿是问题( 1 1 1 ) 一( 1 1 3 ) 的全局极小点，如果对一切z x 且z 矿 有 ，( z ) ( z ) 成立，则称矿是全局严格极小点 定义1 2 设矿x ，如果对某一j 0 有 ，( ) 2 ，( z ) ，0 xnb ( x ，6 )( 1 1 5 ) 成立，则称矿是问题( 1 1 1 ) 一( 1 1 3 ) 的局部极小点，其中b ( x + ，6 ) 是以矿为中 心以j 为半径的广义球z b ( 。+ ，d ) = zj jj 霉一z 0 2s6 ) 2 如果对一切z x n b ( 矿，j ) 且z 矿不等式( i i 5 ) 成立，则称矿是局部严 格极小点 若记g ( z ) = k t f ( x ) 表示，( ) 的梯度，g ( $ ) = v 2 ，( z ) 表示，( z ) 的h e s s i a n 矩 阵对于无约束问题，有以下最优化条件t 定理1 1 【3 3 l ( 无约束优化必要条件) 若矿为问题( 1 1 1 ) 的一个局部极小点， ，( z ) 在矿处可微，则必有 9 ( 矿) = 0 ( 1 1 6 ) 如果，( z ) 在矿处二次可微，则必有 9 ( ，) = 0 ，g ( 矿) 0( 1 1 7 ) 满足( 1 1 6 ) 的点称为函数，( z ) 的稳定点从上述可知，只要目标函数可微，局 部极小点必是稳定点 定理1 2 3 3 】( 无约束优化充分条件) 假设，( 功在矿处二次连续可微，如果矿 是f ( x ) 的稳定点且对任何非零向量d j 妒有 d r c ( x ) d 0 ， ( 1 1 8 ) 则矿是无约束问题( 1 1 1 ) 的局部严格极小点 现在我们考虑约束优化问题显然，可行域上的一个点是否为局部极小点取 决于目标函数在这一点以及该点附近的可行点的值所以我们有必要给出可行方 向的定义 定义1 3 引入记号e = l ，2 ，m 。) ，= m e + 1 ，m ) ，i ( x ) = 纠臼( z ) 0 ，i ) ，对矿舻，我们称集合 a ( x ) = e u ，( z ) 是在z 点的积极集合( 或有效集合) ，g ( z ) a a ( z ) ) 是在z 点的积极约束( 或有 效约束) ，q ( z ) “簪a ( z ) ) 是在点的非积极约束( 或非有效约束) 3 定义1 4 设矿x ，0 d 舻，如果存在6 0 使得 z + t d x ，【0 ，司，( 1 1 9 ) 则称d 是x 在矿处的可行方向x 在矿处的所有可行方向的集合记为 f d ( x + ，x ) 定义1 5 设矿x ，d 舻，如果 d r v c i ( z ) = 0 ，i e ，( 1 1 1 0 ) d t v e i ( x + ) = 0 ，i j ( 矿) ，( 1 1 1 1 ) 则称d 是x 在矿处的线性化可行方向x 在矿处的所有线性化可行方向的 集合记为l f d ( x + ，x ) 定义1 6 设，x ，d 肝，如果存在序列血= 1 ，2 ，) 和以 0 ( k = 1 ，2 ，) 使碍 矿+ 以d k x ，v k ( 1 1 1 2 ) 且有如一d 和如一0 ，则称d 是x 在矿处的序列可行方向x 在矿处的所 有序列可行方向的集合记为s f d ( x ，x ) 引理1 1 如果所有的约束函数都在矿x 处可微，则有 f d ( x ，x ) s f d ( x + ，x ) l f d ( x 。，x ) 定理1 3 设矿是( 1 1 1 ) 一( 1 1 3 ) 的一个局部极小点，如果 s f d ( x ，x ) = l f d ( x ，x ) 则存在越a = 1 ，2 ，m ) 使得 v ( z ) = x v g ( 矿) ， i = l a 0 ，a ：岛( z + ) = 0 ， i 4 埘 均 1 1 0 0 定义1 7 如果矿x 且存在”= ( 姆，螺) r m 满足( 1 1 1 3 ) 一( 1 1 1 4 ) ，则 称矿是问题( 1 1 1 ) ( 1 1 3 ) 的k u h n - t u c k e r 点( 简称k - t 点) ，称”是在z 处 的乘子 假定我们已知问题( 1 1 1 ) ( 1 1 3 ) 在解处的积极约束a ( x ) 我们只需求解如下 的等式约束优化问题 砌m i n ，m ) ( 1 1 i s ) 3 t c f ( z ) = 0 ，l a ( x + )( 1 1 1 6 ) 由( 1 1 1 3 ) 可得，( z ) 的l a g r a n g e 函数，即 l ( x ，a ) = m ) 一f c ( z ) = 他) 一地( z ) ( 1 1 1 7 ) i = l 其中a = ( a l ，k 。) 7 妒，以及c ( z ) = ( c 1 ( z ) ，c 南( ) ) 7 定义1 8 设矿是( 1 1 1 ) 一( 1 1 3 ) 的k - t 点。”是一相应的l a g r a n g e 乘子 如果d 是x 在矿处的线性化可行方向且有智矿v c i ( 矿) = o ，v i j ( 矿) ，则 称d 是在矿处的线性化零约束方向在矿处的所有线性化零约束方向的集合 记为g ( 矿，”) 如果在矿处的l a g r a n g e 乘子是唯一的，我们用g ( x 。) 来表示 g ( 矿，”) 定义1 9 设矿是( 1 1 1 ) 一( 1 1 3 ) 的k - t 点，a 是一相应的l a g r a n g e 乘子如 果存在序列以= 1 ，2 ，) 和缸 0 ( k = 1 ，2 ，) 使得 矿+ 以d k x ， ( 1 1 1 8 ) ：q ( + 以d k ) = 0 ， ( 1 1 1 9 ) = l 且有以一d 和以一0 ，则称d 是在矿处的序列零约束方向在矿处的所有序 列零约束方向的集合记为s ( 矿，”) 5 下面给出约束问题的优化条件r 定理1 4 【3 2 】( 约束优化一阶必要条件) 设矿是问题( 1 i 1 ) 。( 1 1 3 ) 的一个局部 极小点，如果v c ( x + ) “e u ，( 矿) ) 线性无关，则必存在智“= 1 ，2 ，m ) 使 得( 1 i 1 3 ) 一( 1 i 1 4 ) 成立 定理1 5 【32 】( 约束优化一阶充分条件) 设矿x 如果，( 功和岛( z ) 0 = i ，m ) 都在矿处可微且 矿v ，( 矿) o ，v o d s f d ( x * , x ) ，( i i 2 0 ) 则矿是闻题( 1 1 ，1 ) 一( 1 1 3 ) 的局部严格极小点 定理1 6 【3 2 】( 约束优化二阶必要条件) 设矿是问题( 1 1 1 ) ( 1 1 3 ) 的个局部 极小点，是a 相应的l a g r a n g e 乘子，则必有 d 7 吃l ( z ，a ) d o ，v d s ( x + ，a ) ，( 1 1 2 1 ) 其中l ( x ，a ) 是由( 1 1 1 7 ) 定义的函数 定理1 7 【32 】( 约束优化二阶充分条件) 设矿是( 1 1 1 ) 一( 1 i 3 ) 的个k - t 点，” 是相应的l a g r a n g e 乘子如果 v 乞l ( x + ，a ) d o ，v o d c ( x ，a ) ，( 1 1 2 2 ) 则矿是局部严格极小点 1 2 非线性优化问题的常用方法 本文主要研究约束优化问题，由于约束优化问题的解法很多基本思想来自无 约束优化问题的解法，且约束优化问题往往可以转化为无约束优化问题的求解， 所以有必要先介绍一些常见的无约束问题的解法和理论根据 无约束优化问题的算法大致分为两类：其中之一，在计算过程中要用到目标 函数的解析性质( 包括一阶导数和二阶导数) ，一般称这些方法为解析法；另一类 只用到目标函数值，不涉及目标函数导数的计算，通常成为直接方法 6 首先我们简要介绍一下解析法它是求解无约束优化问题； 。m w i nf ( x ) ( 1 2 1 ) 常用的一类算法，它的基本思想是t 对于当前的迭代点瓤，首先确定个搜索方 向靠，使得目标函数f ( x ) 的值沿该方向是下降的，然后确定沿靠方向行进的 步长k 并得到下一个迭代点。“1 = 巩+ k d k 在这里，我们要确定的搜索方向应满足z v ，( 。i ) 7 d k 0 ，啦 0 ，n 0 ，v 2 0 s t e p 2 计算o ，g o ，c o ， s t e p 3 分解山= y o 磊】 o ，令= o s t e l m 如果o 【砌 ! i m 工则停止，否则解 l 硗w = 一c 【b k p z = 一z g k d k y k p y s t e p 5 计算z 女+ 1 = 矾+ y + z k p z s t e p 6 计算厶+ 1 ，g k + 1 ，c k + l ，a i + 1 s t e p 7 分解a t + = 【k + - 五+ - 】【1 】 s t e p 8 若( 2 2 7 ) 成立时用( 2 1 9 ) 校正d 得d k + 1 ，否则d k + 1 = d k ；若( 2 2 8 ) 成立时用( 2 1 1 0 ) 或( 2 1 1 1 ) 校正k 得仇+ l ，否则与k + l = f k s t e p 0 k = k + 1 ，转s t e p 4 2 3 主要结果 此节我们分析算法1 的局部收敛性 假设( h 1 ) ( 1 ) 。是( 2 1 1 ) 的局部最小值点，a = a ( 缸) 列满秩。k 满足g ( z ) = a , a ， 既约h e s s i a n z ( x 。) 7 ( ，a 。) z ( z ) 是正定的 ( 2 ) y ( z ) ，z ( z ) 在z 的附近邻域l i p s c h i t z 连续v 2 ，和 v 2 c i ，i 1m ，是 l i p s c h i t z 连续的矩阵函数 ( 3 ) z ( z 。) 7 ( z 。，k ) 有界，且z ( z 。) 7 ( ，k ) 满秩 本文定义e 女= z i x g = 刃w ，风= z y h i 五当0 e k l e + 1 0 足够小时， n o c e d a l 和o v e r t o n 在文献【9 】中给出如下不等式t 0 霹( 鲰+ l a k + l 扎+ 1 ) 一琢m 一霹w i ( z i + 1 一z k ) l l g 0 孤+ l 一孤n ( 2 3 1 ) l i z g k 一霹w ；| i e o e k 俨( 2 3 2 ) 由算法1 可以得到如下等式总是成立， 瑁( 钆+ l z 女) = 一r c k ， 刃( z 川一瓢) = 一巧1 刃吼一巧1 d k k 何7 c k ( 2 3 3 ) ( 2 3 4 ) 下面我们给出几个相关的引理和定理 引理2 1 彻假定对给定的k ，i i “l | 和l i e k 一10 充分小，则存在常数岛( 与k 无关) 使得， ( i )i i 瑁8 0 c o 蚓1 2 ， ( i i ) 0 谬| j 曼c o ( 1 l e k l l 2 + f l e k l 旧， ( i i i ) 0 y ( z + 1 一z ) 0 c o ( 1 l 钆1 1 2 + 0 e 女一l 2 ) 定理2 1 假设( h 1 ) 成立。元为一给定常数，若存在l 0 ，对慨有l i b 2 。0s 元，| | 占1 10s 元，i i d k l0 i ，i i d o l is 元，0 e k 1 0 曼l 则存在常数c 1 0 使得算法 1 生成的序列 k 满足 ( i )l | e 0 c 10 e 一10 ， ( i i )0 e k + l l lsc l ( 1 1 钆1 1 2 + i i ( b k 一日，) z 善e 女8 + l ic d k g ，) k 瑁e 1 1 ) ， ( n i ) 0 e l0 c 1 ( 1 1 1 1 2 + i ic b k 一l ) 刀( 瓢+ 1 一孤) i | + i i ( d k g 。) 妖昭 k + l 一 钆) 旺 证明t 由假设( h 1 ) 可知c ( z ) 和矛( z ) g ( z ) 在z 。附近邻域l i p s c h i t z 连续， i 点程l i d k 1 0 有界又因为c ( 文) = 0 ，z 7 ( z 。) 9 ( z ) = 0 ，故由( 2 3 3 ) ( 2 3 4 ) 知 存在常数a 0 使得 i 陬0s0 巩一。一l i i + i l e t l0 = i i 一圪一l r 矗强一1 一z i l p 芒l ( z l l g k 一1 + d k l k l r t c - t _ l c k 1 ) 1 1 + | | e 一li i 0 k l i ! 晶i i i i “一l c 0 + 0 磊一l 硭。1 1 1 1 耀_ 。g k 一1 一刀舢0 + 0 么一l b 矗l d k l k l 瞄“一l c i l + i l e i l i | sc 10 8 i 一1 叭 所以( i ) 成立 由( 2 3 2 ) 和【k 磊】的正交性可得 1 1 名t 船一瑶w k ( z k z 吾+ y k 埋) | l e | | 0 2 则由假设( h 1 ) 的( z ) ，z ( z ) ，y ( x ) 在z 。附近邻域的l i p s c h i t z 连续性可得 i i z g i 一( 刃帆磊一h 。) 露一风刃一( 霹帆磊一g ) k 埒g ，y k 蹬i i c 慨i t 2 即 0 名t 肌一峨霹e k g 。y k 记“0s 臼1 1 e k 0 2 ( 2 3 5 ) a 凌一h 。凌+ 忸k 硪e k b k z t x k + b k 玩z 0 一t 魄磁e m b k 玩巩+ 1 + b k 壤z 0 一g 。k 昭靠+ ( 仇k 蹬e i d k y t x k + d k 圪昭。) ( d k k 昭e l 一仇k 昭瓢+ l + d k k 啦。) 0 西j h n 故有 i l 刃鳜一( 风一凤) 刀一b k 刃( e k + 1 一( z 一瓢) ) 一( g 一d k ) y 辨钆 一d 圪昭( e k + l 一( 劫讳t 一k ) ) i is 西0 e k 酽 因为 取霹( z 一) = 一刃鲰一仇k 昭( z 川一) e 斤以 鼠刀e l + d k y k 谬e 州一( 最一风) 露e 一( d k g 。) k 瑁e 0s 臼l l e k l l 2 ， 0 最耀e 川+ d k y k y $ e 卜0 ( 取一风) 耀e k + ( d k g 。) k 昭e k 峪臼l l e k u 2 ， i i 展刀e 州+ d k k 昭e k + l i i 臼慨0 2 + 0 ( 取一1 - i ) 耀e + ( d k g 。) k 昭e i l ， 由引理2 1 0 ) 和0 仇0 有界可得 i i 瞰耀e 峪岛( 1 i e 1 1 2 + 0 ( 风一i - i ) 耀e i + 慨一g 。) k 昭吼胁 因为晚正定，巧1 有界可知i i 爹 i i 非奇异且其逆有界故有 慨+ l | l 剑 蟹 临州叫i 2 删( 凤一矾) 刃+ ( d t - g ) k 曙“i t ) ， 所以存在常数g 0 使得 j j p + l | | sc l ( 1 i e k | | 2 + i i ( b i h + ) 霹e k + ( i 九一g 。) 圪曙e k l l ) 成立，即( i i ) 成立 由( 2 3 5 ) 可得 i i 刁鲰一h 。耀e 川+ ( 以一b k ) 耀( z k + 1 一) + 玩霉( 1 一乳) 一g 。k 培e m + ( g + 一d ) k 昭( z i + l z k ) + d i k ，( z + l x k ) l i 0 l i i e 0 2 ， 又因为 取刃( 靠+ l 一瓢) = 一刃瓤一仇圪曙( x k + l 一巩) ， 故由以上两式可得 i l j l 霹e i + l + g 。k 埋e + l l l 西0 e 1 1 2 + | i ( 晚一f l ) 霉( 孤+ 1 - - 巩) + ( d 一g 。) k 昭( 巩+ 1 - - z k ) 0 由引理2 1 和假设( h 1 ) 可知存在常数a 0 使得 慨+ l0 c , ( i f “u 2 + 0 ( 取一皿) 霹( 。川一瓢) 忡8 ( 仇一g 。) k 昭( z 州一巩) 眇 成立，即( n i ) 成立 口 由于定理2 1 根据0 e 1 8 给出了0 。1 0 的界，我们可以得到算法1 的1 步( 卜超 线性收敛特征，见如下推论 推论2 1 假设( h 1 ) 成立，若瓢一z 。，且对任意k ，有l | 夙0 元，0 b f l 0 元，l i 圾| l 元，成立，且 = 墼攀等型一。 蝴= 监罨辔茅趔硼 则。i 一巩的收敛速度为1 步( 卜超线性 证明：由定理2 1 ( i i i ) 可知；当k 足够大时有 8 e + 1j le i ( 1 1 1 1 2 + u l 女i i z 女+ l z j | + u 2 | + l z 0 ) sa ( 1 l e d 2 + u l 女l l e k + l 一8 l + 心0 8 i + 1 一e k 0 ) c , ( 1 l e d 2 + u l | 1 8 + 1 + e k i + 峨k l | e k + l + “l ) 由定理2 1 ( i ) 以及上式可推出 0 e k + l s a ( 0 靠0 2 + ( 1 + a ) ( u l k + 忱k ) 0 “) 所以 坐掣：g 幽卫型睁型必业。0 口 | i e 詹l l i i e l 0 2 4 定理2 28 k ，y k 由( 2 2 2 ) ( 2 2 3 ) 定义，则存在2 4 0 使得若0 e k 0 5 知，i h + l0s e ，则存在与k 无关的常数c k 使得 l l y k - - g * s k l i c m a x ( 1 l e k l l ，l i e i + z 1 1 ) l l z i + l x d + ( 1 l h i i + l l a 1 1 1 1 t 刃( x k + l x i ) 1 1 ( 2 3 6 ) 靠，吼由( 2 2 5 ) ( 2 2 6 ) 定义，则存在e 妨 0 使得若i i e k i l c 2 b ，i l e i + l0 站，则 存在与k 无关的常数c 如使得 0 鲰一z ，氟0s m “( 8 e l e k + z 1 1 ) l l x k + z - - x k l l + i i g - - d k l 川巩+ 1 一z k m ( 2 3 7 ) 证明：由( 2 3 1 ) 知 0 i z k w d x + 1 一x k ) l i g 0 z + l x k l l 2 ， 由陬玩】的正交性可得 故有 0 口一z k 妖( 玩霹+ k 昭) ( z k + l z ) se i | z k + l x k i 2 ， 0 一( b 一皿) 巧( z + 1 一瓢) 一风露( z 女+ 1 一。) 一( d 女一g ) 圪记( z k + l z k ) 一g 。k 培扛i + l x k ) l i c l i x 女+ l x k 0 2 ， 由日k ，仇的l i p s c h i t z 连续性可得 l | 女一风z f ( z + l - - x k ) 一g 。k y ( 巩+ l x k ) l l e ( 1 i z k + l z k ) 1 1 2 + l i e 女i l l l x 女+ l z i i ) ( 2 3 8 ) 由于 z k + 1 一x k = k 昭x t + l z 女) + z k z 吾( z i + l 一七) ， 故由( 2 3 8 ) 可得 0 一g 。8 k 一风z 暑( z i + l 一口k ) + g 。磊刃( z + l z i ) 1 1s0 ( j | z + i - - z 1 1 2 + u e k i i i i x k + l z i i ) 2 5 故 0 挑一g 。船i l伤。m “( 1 l e k lr ，0 e k + 10 ) 0 z 女+ l z k 9 + i j 宵。刀( x k + 1 一善k ) - g 玩刃( z + 1 一x k ) l l c km a x ( 1 l e k l l ，i l e k 4 1 1 1 ) l l x k + l 一茁1 0 + i i h i l l l z 蚕( 孤+ l z 女) 0 + i i g 圳琢( 。州一x k ) f f ( k m a x ( i i e 0 ，j | e 1 1 1 ) l i z k + l z k i l + ( 1 风0 + l g 。0 ) i i 召( z t + l x k ) i j 又由( 2 3 8 ) 可知 l l y k - d 觑昭( 。一巩) 一风霹( 。l 一现) 一g 。k 培( z m z k ) + 仇坎昭( + l z k ) 0 d ( i i z k + l 一瓤) 酽+ i l 州z + l z k 0 ) ， 故有 i | 蟊一月。靠ls0 ( 1 f 卧l 一磊1 1 2 + i i 靠l l l l x k + i 一钆0 ) + ”( g 。一d k ) y 谬( 巩+ i z i ) h sc m a x ( 1 e k ，i l e k + 1 1 1 ) l l x + l z k 0 + 0 g + 一d k f | 0 z + 1 一z 难伦2 2 看透代弟k 步7 菏足【2 2 ，即d k 设校正，足义 一掣， 则若m a x ( 1 l e k l l ，0 e + 1 0 ) h ( 由定理2 2 定义) ，有 7 ，t m 舣( 忙川川川) + ( t j h t l + i i g 帅黼 若迭代第k 步满足( 2 2 8 ) ，即鼠被校正，定义 一铲， 设m e 月f 1 2 ，则若m a x ( ir e 恢+ l i i ) 5 站( 5 2 6 由定理2 2 定义) 有 蔫尹s i i m i l 2 m - 1 氟0 一 “” 目 仫m a x ( 1 l 叫h + l | i ) 黼圳g 。一驯黼 d 动 j 1 l l l 2 0 0 矗 a ( 2 2 2 2 ( ( (v 证明：由定理2 2 可得此推论成立 引理2 21 1 0 1村如( 2 1 1 3 ) 中定义，设m 是任意非奇异对称矩阵使得 峰高产岛1 3 靠o ( 2 3 1 4 ) 0 m 。靠0 一。 。7 若迭代第步用( 2 1 1 0 ) 校正展则露靠 0 且 i l b - + t 一见8 吖s ( ( 一a 口) 1 胆+ ! 兰；i ；：；j ；：字型川日- 一日川m + ! ! m j 云i 剑 ( 2 。3 1 5 ， 其中o ( o ，l l ，a l ，o t 2 是与无关的常数且 ：卷黼，bk#h1 0 1 k i i 。, i i m ， = 0 鼠一反 一1 氟0 l0 ，风= 皿 叭1 1 f ( 2 ，1 1 2 ) 中定义，若迭代第步用( 2 1 9 ) 校正d - 则 l i 仇+ 1 - a 1 l ，( ( 1 一n 3 0 h ) l 2 i i 仇一g 川，+ 掣，( 2 3 1 f i ) 其中( 0 ，1 1 ，且 1 独。：f 糕，仇