（计算数学专业论文）带二次约束的最小二乘问题及一类矩阵方程的数值解法.pdf

摘要 在本文中，我们首先讨论了带二次不等式约束的最小二乘问题( l s q i ) ： 。m i ni i a = 一b l l 2 向量z 满足 i i c = 一d l l 2 q ， 其中a r m n ( m n ) ，c r p 肌，b r m ，d r p ，实数q 0 我们论述了l s q i 问题有解的条件以及有解时的各种不同情形之后，我们详细 讨论了带二次等式约束的最小二乘问题( l s q e ) ： m ，。i n 。i l a x 一6 1 1 2 向量z 满足 i i c x 一刮2 = o z 对l s q e 问题，我们利用l a g r a n g e 乘子法建立法方程，通过法方程的解与l s q e 问题的解之间的关系，我们提出了求解l s q e 问题的投影方法我们证明了由 投影方法得到的迭代序列是有界的，并且如果满足一定的初始条件则由投影方 法得到的迭代序列单调收敛于l s q e 问题的解另外我们在文中还讨论了投 影方法的收敛阶数，理论结果表明投影方法至少是二次收敛的此外我们还对 l s q e 问题进行了扰动分析并且给出了相应的结果数值例子表明投影方法比 牛顿迭代方法更有效 最后，在文中第三章我们还对一类不相容的矩阵方程对( a x b ，c x d ) = ( e ，f ) ( x 为实矩阵) 最小f r o b e n i u s 范数问题给出了一种迭代算法在没有舍 入误差的情况下，对任意( 特定) 的初始迭代矩阵，运用此算法能在有限步 内得到问题的( 最小f r o b e n i u s 范数) 解数值例子表明我们所提出算法的有效 性 关键词：最小二乘；二次等式约束；投影方法；g s v d ；迭代算法；k r o n e c k e r 积； 矩阵方程对 a b s t r a c t i nt h i sp a p e r ，w ef i r s td i s c u s st h el e a s ts q u a r e sp r o b l e mw i t haq u a d r a t i c i n e q u a l i t yc o n s t r a i n t ( l s q i ) ： 。r a r i n 。f l a x 一6 i | 2 s u b j e c tt o f f 仇一d l l 2 口， w h e r e a r m 竹m n ) ，c r 尸n ，b 乏m ，d r p ，a n dn 0 眦d i s c u s st h ec o n d i t i o n st h a tg u a r a n t e et h el s q ip r 。b l e mh a sa s o l u t i o n ，a n d v 舭i o 惦c a s e so ft h es o l u t i o n s t h e nw ed i s c u s st h o r o u g h l yt h el e a s t s q u a r e s p r o b l e mw i t haq u a d r a t i ce q u a l i t yc o n s t r a i n t ( l s q e ) ： 七r a r i n 。i i a x 一6 f f 2 s u b j e c tt o i l c x d i f 2 = q u s i n gt h em e t h o do fl a g r a n g em u l t i p l i e r ，w eo b t a i nt h en o r m a le q u a t i o i l s o f t h el s q ep r o b l e m b yt h er e l a t i o no fs o l u t i o n sb e t w e e nt h ei l o r m a le q u a t i o l l s a n dt h el s q ep r o b l e m ，w ep r e s e n ta p r o j e c t i o nm e t h o df o rs o l v i n gn u m e r i c a l l y t h el s q ep r o b l e m w ep r o v et h eb o u n d e d n e s so ft h e s e q u e n c eg e r l e r a t e db v t h ep r o j e c t i o nm e t h o d ，a n di ft h ei n i t i a lv a l u e s a t i s f i e ss o m ec o n d i t i o nt h e nt h e s e q u e n c eg e n e r a t e db yt h ep r o j e c t i o nm e t h o dc o n v e r g e sm o n o t o n i c a i l yt o t h e s o l u t i o no ft h el s q e p r o b l e m i na d d i t i o n ，w ed i s c u s st h ec o n v e r g e n c er a t eo f t h ep r o j e c t i o nm e t h o d ，t h e o r e t i c a lr e s u l t s s h o wt h ep r o j e c t i o nm e t h o dh a 8a t 1 e a s tq u a d r a t i cc o n v e r g e n c e w ea l s og i v e ad i s t u r b a n c ea n a l y s i so ft h el s q e p r o b l e m ，a n dc o r r e s p o n d i n gr e s u l t sa r eo b t a i n e d n u m e r i c a le x a m p l ei n d i c a t e 8 t h a tt h ep r o j e c t i o nm e t h o di sm o r ee f f i c i e n tt h a nn e w t o n ，sm e t h o d 8 上1 n a l l y ，i nc h a p t e rt h r e ew ep r e s e n ta ni t e r a t i v ea l g o r i t h mf o rs o l v i n gt h e 1 e a s tf r o b e n i u sn o r mp r o b l e mo fa ni n c o n s i s t e n tm a t r i x e q u a t i o np a i r ( a x b ，c x d ) 2 ( e ，f ) w i t har e a lm a t r i xx b yt h i sa l g o r i t h m ，f o ra n y ( s p e c i a l ) i n i t i a lm a t r i ) ( ) c o ，as o l u t i o n ( t h em i n i m a lf r o b e n i u sn o r m s o l u t i o n ) c a nb eo b t a i n e dw i t h i nf i n l t ei t e r a t i o ns t e p si nt h ea b s e n c eo fr o u n d o f fe r r o r s t h en u m e r i c a le x 锄p l e s v e r i f yt h ee f f i c i e n c yo ft h ea l g o r i t h m 。 一 a b s t r a c t 1 1 1 k e y w o r d s ：l e a s ts q u a r e s ；q u a d r a t i ce q u a l i t yc o n s t r a i n t s ；p r o j e c t i o nm e t h o d ； g s v d ；i t e r a t i v ea l g o r i t h m ；k r o n e c k e rp r o d u c t ；m a t r i xe q u a t i o np a i r 学位论文独创性声明 本人所呈交的学位论文是我在导师的指导下进行的研究工作 及取得的研究成果据我所知，除文中已经注明引用的内容外，本 论文不包含其他个人已经发表或撰写过的研究成果对本文的研 究做出重要贡献的个人和集体，均已在文中作了明确说明并表示 谢意 作者签名：垂全麟日期：2 旦星4 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定， 学校有权保留学位论文并向国家主管部门或其指定机构送交论文 的电子版和纸质版。有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆被查阅有权将学位论文的内容编入 有关数据库进行检索有权将学位论文的标题和摘要汇编出版。保 密的学位论文在解密后适用本规定 ) ， 学位论文作者签名：微导师签名：茬b 香电 日期：皇塑基。左i 日期：墨呈翌壁：堑：l 第一章引言 带约束的最小二乘问题是指在满足一定约束条件下的向量集合中求最小二 乘问题的解约束条件不同，则得到不同的带约束的最小二乘问题例如，求下 面的最小二乘问题， 王m 豫i n 。 1 a x b l l 2 向量z 满足 c x = d ， ( 1 1 ) 其中a r m x n ( m 佗) ，c 珉甲n ，b r ”，d 船， 这里的向量x 所要满足的条件：c x = d 即为问题( 1 1 ) 的约束条件，由于此约 束为线性的等式约束，因此，我们也可以称之为带线性等式约束的最d 、- - - 乘问 题此类问题的解集以及相应的等价性问题在文献f 1 2 】中有着详细的讨论，感兴 趣的读者可以查阅文献【1 2 】如果将约束条件改为：i i x l l 2 q ，其中口为某正实 数则问题( 1 1 ) 相应变为： 婴器i | a z b l l 2 向量z 满足 i l x l l 。q ( 1 2 ) 这里的约束条件不再是线性的了，我们将问题( 1 2 ) 称之为带二次不等式约束的 最小二乘问题文献【3 】提出了一种投影方法解决了如下问题： z m 肛i n 0 a z 一6 i f 2向量z 满足l z l l 22a 在本文的第二章中，我们将问题( 1 2 ) 的约束条件进一步推广为：l i c z 一刚2 a ，则我们得到如下的带二次不等式约束的最小二乘问题： z r a r i n 。l l a z b l l 2 向量z 满足 i | 一训2 a ( 1 3 ) 通过对问题( 1 3 ) 各种不同情形的讨论，我们最终将问题( 1 3 ) 归结为求解下面 的带二次等式约束的最小二乘问题： z m r i n 。i i a z 一6 j 1 2 向量z 满足 i i c z d 1 2 = a ( 1 4 ) 运用文献【3 】的思想，我们同样也提出了投影方法，并且对我们所提出的投影方 法进行了收敛分析，证明了该方法具有二次收敛性数值例子表明我们所提出 第一章 引言 2 的投影方法是有效的，特别是在条件i i c a t b d i l 2 0 记 b = ( c a ) ，r = r a n k ( c ) ，s = r a n k ( b ) 首先我们简要的讨论一下保证( 2 1 ) 有解的条件及有解时的各种情形 1 如果z 是( 2 1 ) 的一个解，则对任意的向量y = z + ( i b t b ) z ( z r “) ， 我们注意到 a 秒一b l l 2 = i l a x + a ( i b t b ) z 一6 | 1 2 = 0 如一6 1 1 2 ， c 剪一r i l l 2 = 0 c z + c ( i b t b ) z d l l 2 = f i c x d 1 1 2 o l ， 因此y 也是( 2 1 ) 的一个解，因为r ( a t ) r ( b r ) 并且r ( c r ) r ( b t ) 2 由于 c x d l l ；= i i c z c c t d 一( i c c t ) d l l ； = i i c x c c t d l l ；+ l i ( i c c t ) d l l ； l i ( i c c t ) d l l ；， 如果l s q i 问题( 2 1 ) 有解，则必然有 i i ( 1 一c c + ) d l l 2 o t 如果i i ( i c c t ) d l l 2 = q ，则l s q i 问题( 2 1 ) 转化为下面带线性等式约束的 最小二乘问题： 婴器i i a z b l l 2 向量z 满足 c z = c c d 第二章带二次约束的最d , - 乘问题的投影方法 4 3 如果z 是。m r i n 。i i a x 一圳2 的任最小二乘解，则z = a t b + l a z ，其中 l a 全i a t a ，名r n ，且 c z d 幢= l i c a t b + c l a z d l l l = i i ( 一c l ( c l a ) ) ( c a t 6 一d ) 幢 + l i c l a ( ( c l a ) ( c a t 6 一d ) + z ) l l ； i i ( z c a ( c l a ) + ) ( d a t 6 一d ) l t ； 如果0 ( j c l a ( c l a ) t ) ( c a t 6 一d ) 1 1 2 q ，令名= 一( c l a ) t ( c a t b d ) ，则 正= a t b l a ( c l a ) i ( c a t b d ) 是( 2 1 ) 的一个解 如果 l i ( 一c c ) r i l l 2 q ，( 2 3 ) 可以证明l s q i 问题( 2 1 ) 有解，并且所有的解位于边界0 c z 一刮2 = q 上，也 就是说，l s q i 问题( 2 1 ) 转化为如下带二次等式约束的最小二乘问题( l s q e ) ： m 舭i n l i a z 一6 1 1 2 向量z 满足 i l c x 一训22 q ( 2 4 ) 为了确定性我们作如下假定： 假定1 ( 2 2 ) 成立并且r a n k ( b ) = n 注意到当0 ( ，一c l a ( c l a ) t ) ( c a t 6 一d ) 1 1 2 q 在下文中我们通过推广【3 】的理论和方法来研究l s q e 问题( 2 4 ) 第二章带二次约束的最小二乘问题的投影方法 5 2 2 标记和预备结果 为了更深入的讨论，我们需要下面的关于矩阵a 和c 的广义奇异值分解 假设假定1 中的条件成立，则有 a = u d a x ，d a = d i a g ( a l ，口2 ，q n ) ， c = y d c x ，d c 2 d i a g ( 尻，伤，岛) ， ( 2 5 ) 0 o t l a 2 口r i ， 。 岛尾岛0 ，q = m i n ( p ，佗) ， 其中u r m m 和v r p p 是正交阵并且x r 似n 是非奇异的 不失一般性，令( 2 4 ) 中o t = 1 我们注意到( 2 4 ) 的解是下面l a g r a n g e 函 数l 的一个不动点， l ( x ，入) = 去j i a z bj l ；+ 害( j j c z d jj ；一1 ) 其中入是l a g r a n g e 乘子令筹= 0 ，丽o l = 0 ，因此，我们有下面的法方程： ( a t a + a c t c ) z = a t 6 + 入c t d ， ( 2 6 ) i i c z d 1 ；= l - 、7 如果矩阵a t a + a 伊c 是非奇异的，则对应的向量z 由l a g r a n g e 乘子a 唯 一决定；即， z ( 入) = ( a + a c t c ) 一1 ( a t 6 + a c t d ) ( 2 7 ) 定义 ，( a ) = | i c z ( 入) 一d 0 ；( 2 8 ) 如果入满足特征方程 ，( a ) = 1 ，( 2 9 ) 从而，( a ，x ) 是法方程的一个解我们感兴趣的是解( 入，z + ) ，其中a 是最大的 l a g r a n g e 乘子： a = m a x 入i ( 入，z ) 是( 2 6 ) 的一个解) ( 2 1 0 ) 我们可以证明a 一p 1 ，其中肛1 是广义特征值问题a t a x = p c r c x 的最 小广义特征值我们以定理的形式陈述如下并且给出相应的证明 第二章带二次约束的最小二乘问题的投影方法 6 定理2 1 若p 1 是广义特征值问题a t a x = # c t c z 的最小广义特征值， 和z 。如上文中所定义考虑线性系统 ( a t a p 1 c t c ) x = a t b 一# i c r d ， ( 2 1 1 ) 1 如果( 2 1 1 ) 无解，则a + 一p 1 并且有x + = ( a t a + 入+ c t c ) 一1 ( a t b + 入+ c t d ) 2 如果( 2 1 1 ) 至少有一个解金，并且圣是所有解当中使i c x d l 2 达到极小 值的解，则 f ，砂若| i c 岔一d l l 2 1 ，则入+ 一p 1 并且有x + = ( ，a + ”c r c ) 一1 ( a t 6 + 入+ c t d ) 阳) 若l i c 仝一d l l 2 = 1 ，则”= - - # l 并且有x + = 圣 俐若0 c 金一d l l 2 屏+ l = = 岛= 0 因此，p l = 筹线性系统( 2 1 1 ) 有如下形式： 其中 因此， ( a ；一p l 辟) 俄= q t q 一# l 届i h i ， i = 1 ，r ，( a ) a t 2 仇= a i c i ，i = r + 1 ，n ， g = ( g t ，9 n ) t = x 一1 z ， c = ( c 1 ，c m ) t = u t b ， h = ( h i ，k ) t = v t d = 暑槲+ 暑黼+ 熹。砖 全朋) + 暑错+ ；量p 。砰， ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 第二章带二次约束的最4 , - 乘问题的投影方法 7 其中 j = di 结合假定1 和g s v d ( 2 5 ) ，有 1 拇，毒2 砷卜 p 净忡一c c + ) d i l l 0 由 于在区间( 一z 1 ，+ o 。) 上有，7 ( a ) 一p l ，使得，( ”) = 1 和矿= ( a t a + ”伊c ) _ 1 ( a 。r b + a 伊c f l 2 如果线性系统( 2 1 1 ) 有解，则对所有的i j 有q ；( 觑q a t 玩) 2 三0 ，并 且，( a ) ：，( 入) + p 研因此，( 2 1 2 ) 的任一解有如下形式： i f f i r + l 9 t2 t 囊i p 1 侥 。a 2 一p 1 辟l i i c x r i l l ；= i i v t c x x 一1 z v t d l l ；= i i d c g h l l ； = 暑槲+ i e j ( e 仇吐) ；p 。墙 如果i j ，我们可以选取俄= 侥，使得向量g 极小化i i c x d l l ；我们将这 里特定选取的向量g 表示为多，则岔= x 雪 ( a ) 如果i i c 金一d i | 2 1 ，则 p f ( - p ) = ，( 一p ) + 砖= i i e 圣一d i l 2 1 + = 0+ p 一 ，j - # 1 有， 因此，”= 一p l ，并且( ”，圣) 是( 2 6 ) 的解 ( c ) 如果i i c 圣一r i l l 2 1 ，则 i 一d 1 1 2 一p 1 从而l s q e 问题( 2 4 ) 的解由矿= ( a t a + a + c t c ) 一1 ( a t b + ”c r d ) 给出 且 2 3投影方法 设z ( 入) 如( 2 7 ) 中所定义且，( a ) 由( 2 8 ) 给出记 y ( 入) = c ( a t a + a c t c ) 一1 ( a t b + ) _ c t d ) 一d = c x ( a ) 一d ， ( 2 1 6 ) z ( a ) = c ( a r a + 入c t c ) 一1 c t y ( a ) ( 2 1 7 ) l = d肛 一 ，一一砖 p 卅 + p 一 砖 p 卅 +入 i i 入 f ， = 危 p 叫 + p 一 ， i i p 一 ， 第二章带二次约束的最小二乘问题的投影方法 9 则有y 7 ( 入) = 一c ( 俨a + a d r c ) 一1 矿y ( a ) ，z ( a ) = - i f ( a ) 联系到f ( a ) = i i c x ( a ) 一刚；，因此 ，7 ( 入) = 一2 y r ( a ) z ( 入) ，( 入) = 6 | i z ( a ) 0 ；( 2 1 8 ) 我们首先给出关于运用牛顿方法和投影方法的三个算法如下记 z 七= z ( a 七) ，y k = ( a 七) ，z k = z ( a 七) 算法2 1 ( n e w t o n1 ) 对方程f ( a ) = 1 应用n e w t o n 方法给定初值a o ，计 算z o ，y o ，z o 对尼= 0 ，1 ，计算 直到收敛为此 k t 孔+ 紫隅扎肌彬， 算法2 2 ( n e w t o n2 ) 对方程，( 入) _ 1 2 = 1 应用n e w t o n 方法给定初值a o ， 计算z o ，y o ，z o 对k = 0 ，1 ，计算 沁。：入七+ 业屿型址，吣。，帅，撕， 直到收敛为此 下面我们提出关于解l s q e 问题的投影方法 算法2 3 ( 投影方法) 给定初值知，计算z o ，y o ，z o 对k = 0 ，1 ，计算 a k + = k + l 一( v 鳍伍钆7 - i | f f 钆旧z t ! ，) 川k 训层兰：三主 ( 2 1 9 ) z k + 1 ，y k + 1 ，锹+ 1 直到收敛为此，其中。 七= ( 可吾魂) 2 + ( i l y t ! l l ；一1 ) 愀悖 ( 2 2 0 ) 众所周知，n e w t o n 迭代方法只是局部二次收敛，正如文献 3 1 中所提到，为 此文献【3 】提出了一种投影方法，它的基本思想是将向量v t 可( a ) 投影到由 向量u ( 入) 所张成的一维子空间中，其中近似向量u ( a ) 应该没有极点注 第二章 带二次约束的最小二乘问题的投影方法1 0 意到正交投影兄( a ) y t 3 ，( 入) 是关于v t 矽( a ) 在子空问s p a n ( w ( a ) ) 上的最佳逼 近；i e ，0 兄( a ) y t 可( 入) 一v t 秒( 入) 1 1 2 = ，m i ，n ，、i i x v t 可( a ) | 1 2 这里两个函数 z 8 d a r t ( u 【a i l ，( a ) = l i v t ! ，( 入) 旧与0 兄( a ) y t u ( x ) l l ；之间的间隙为： 川矿t 剪幢一i | 兄y t 秒幔i = i i ( x 一兄) y t 可幢， 其中兄= t i | u 慨旷! ，r p ，u r p 运用g s v d ，向量秒( a ) 表示如下： 鼬) = 喜鬻州， 其中q ，h i 如( 2 1 3 ) 中所定义，并且仇是正交矩阵v 的第i 列，则，( 入) 有如下 形式： m m 眩刮n 幢= 喜谢+ ；三p 。坛2 记胁= a ；群，i = 1 ，n 我们可以看到函数f 是关于a 的有理函数，并且它 的极点是集合【一地ii = 1 ，r ) 的子集此外， v t y ( 入) =，v t z ( a ) = 嘶群( 屏白一o ，k ) 下药瓦葫r 一 0 下面我们引入关于入的两个函数u 南( a ) 和机( a ) ， 纨( a ) = v 丁讥+ ( a 一扎) y t 魂= 罐剃t a i + 入所) 弋蒂瓦万矿 十 p 1j ； 罐搿( a ；+ 入辟)鬲石口i 矿l “r 十 p rj h r + 1 群 竺 第二章带二次约束的最小二乘问题的投影方法 机q 三黧一 仁2 2 ， 2 丽面面f 两菇荔西夏孑蕊。 注意到蛾( a ) 没有极点，并且 纵妒( y r 鼬) ) = 壹i = 1 渊+ ；塾彤训i 耋= i i 训巨 下面的定理表明函数机( a ) 是对f ( a ) 的二次逼近 定理2 3 设f ( a ) 和机( a ) 分别如( 2 8 ) 和( 2 2 2 ) 中所定义如果对t = 1 ，r 有a 七一地，则 j 七( a 七) = f ( a k ) 且戤( 入七) = ，7 ( a k ) 2 对任意的a 一地有机( 入) ，( a ) 证明：1 由( 2 1 8 ) 和( 2 2 2 ) ， 州= 燃训硎m = 警= - 2 y 彳) 2 由( 2 2 2 ) ，注意到兄。( a ) 是正交投影， 七( a ) = 0 j 气氇( a ) y t 3 ，( a ) 0 ；i | y t 可( a ) 0 ；= ，( a ) 口 类似于文献【3 】，我们选取方程妣( a ) = 1 最大的解取代方程f ( a ) = 1 的 解来作为对最优解a 的更好的逼近利用定理2 3 中的公式和机( 入) 的性质， 我们上文提出的投影方法的迭代公式( 2 1 9 ) 可以考虑用来解方程c k ( a ) = 1 ， k = 1 ，2 ， 定理2 4 在算法2 3 中， f 如果k 20 ，贝1 南( 入七+ 1 ) = 1 且i | 七+ 1 1 1 5 1 2 如果k 0 ，则| | 弧1 1 2 1 且l i 鲰+ l i l 2 i i 玑1 1 2 第二章带二次约束的最小二乘问题的投影方法 1 2 证明：1 当七0 ，则由算法2 3 ，定理2 3 和( 2 2 2 ) ， 九( k + ) = 丽隔硒雨露剖黜警而同巧函而 = 硼盘渤 = 佩獗瑞渊措硼 y k + l i i ；= ，( a 七+ 1 ) 七( 入七+ 1 ) = 1 2 当七 0 ，同样由算法2 3 ，定理2 3 和( 2 2 2 ) ，我们有i 帆0 2 o ( i = 1 ，r ) ，则t t l i = 1 r i - - - - 1詈 - 澍et u t r ，因此t 1 妒( k ) 婢 焉髀 ，汹黼，谢 第二章 带二次约束的最d - 乘问题的投影方法 1 3 r ( 2 ) 如果t i o ( i = 1 ，7 ) ，这表明五 o ( i = 1 ，7 ) ，则t i t l i - - - - 1 因此t l 妒( a 七) t ， ( 3 ) 如果t l t 2 t 。 0 o 饥t 。并且i r - - - - 1 互t l2 蚤丑t i + ；。鲁5 蚤丑- - t i + ；。吾 因此， 正 t = l t 1 一正 i = 1 - - t i 由( 2 2 5 ) 和( 2 2 6 ) ，我们有 则 8 正 兰!- l t l t 乃 i = 8 + 1 t r 正 阜+ t l 正 = + l t r r ( a ) 如果正 一r r 丑 二“ t = l 正 竺! 生 一r 吾 t = ：l 粤j 一正正 = 1t = l - f t2 t 。a ， 墨 登 t i 一以+ 1 矗 正 ! 三!l f p a t 正 i = s + 1 t a + 1 正 ! 萼一+ r 正 t = 1 噩 t = 0 + 1 “+ l 孔 上! 三! ! “+ 1 孔 上：三! ! t 。+ l t 1 ( 2 2 5 ) ( 2 2 6 ) ra正 ，斟 一丑缸 ，澍 一 生吨 j 斟 。 整。 一 丑一如 r 汹 正 ，澍 冠 ，：l 噩 ，汹 塾下酗下 第二章带二次约束的最4 , - 乘问题的投影方法 1 4 i 因此t l 矽( a 七) 0i e a 七十p 1 矽( a 七) a 七十肛r 现在我们证明( 2 2 4 ) 对任意的k 之0 ，结合迭代公式( 2 1 9 ) ，我们得到 入七十1 a 七一妒( a 七) 一乒b 如1 果a 七 ”都有f ( a ) 逦磊产 龇 ( 喜等猎+ ；萎p 。孵) 壹i = 1 鱼篙鬻 ( 喜黼) ( 壹i = 1 黼磋w ) 2m i n i 地+ 入七i = - - ( t i o + 入七) 因此， 入七+ 1 - - # i o = 入 这与上文矛盾，因此a 不是f ( a ) 的极点，玑_ 歹三可( 入) 并且_ 虿三 z ( 入) ，这里( a ) 和z ( 入) 均为有限元素组成的向量由( 2 2 7 ) ，我们有 、( 矿刁2 + ( 1 1 歹1 1 ；一1 ) | i 歹旧i i 芽旧一矿z = 0 因此，7 ( 入) = 一2 俨z 0 ，并且f ( a ) = 0 训；= 1 口 注2 1 由定理2 6 ，如果存在使得l l b i l 2 = i i c x k 。- d l l 2 1 ，则序列 a 七) 必定收敛并且0 弧1 1 2 _ l ( k _ + o 。) 如果对所有的k 都有i l y k l l 2 1 ，则我们有 下面的定理 定理2 7 若对所有的k 都有l l y k l l 2 1 ，则钏弧0 2 ) 是单调增加的并且存 在某使得对任意的k k o 有， a 七= a k o - - # 1 且，7 ( 入七) = 0 ( 2 2 8 ) 证明：由定理中条件对所有k 都有i l y k l l 2 0 ，使得对所有的a ( 爻一点爻+ 6 ) 都有，( 爻) f ( a ) 成立由于 a 。一天( 后_ o 。) ，则存在某个k o 使得入幻( 支一6 ，爻+ 6 ) 利用序列 l l y k i l 2 ) 的 单调性，对任意的k ，我们有 引1 2 | l 鲰。i 2 1 1 纵1 1 2 | | 引1 2 因此i l y k l l 2 = l l 引1 2 ( k k o ) 由( 2 2 3 ) 和( 2 1 9 ) ，对任意的毛k o ，我们有 y t z k = 0 和儿= 入_ | c o ，因此对任意的k 有，7 ( k ) = 一2 y t z 七= 0 因为当 a - # 1 时有，7 ( 入) 1 设 = m a x l ，( 1 且厂7 ( 勤= o ) ，( 2 2 9 ) 如果不存在这样的，则令= 一o o 对任意满足( 2 2 9 ) 的，我们可以证明 f ( a + ) = 1 ，i e ，i l y o l l 2 1 由定理2 6 可知结论成立 如果k ( ，- - p 1 ) ，由定理2 6 ，我们需要证明存在k 使得j j 纨j j 2 1 如果= 一，定理2 7 表明要证的结论是正确的因此我们假设是一个有 第二章 带二次约束的最d , - - 乘问题的投影方法 1 7 限的值由的定义，对任意的入( 色- # 1 ) ，我们有，7 ( a ) = 一2 y t ( 入) z ( a ) ，( ) = 0 ，因为，( 入) = 6 1 1 z ( a ) l l ； 0 ，所以函数，( a ) 是单调增加的因此 z o 入o 如果a 1 一肛1 ，我们同样有y t z l a 1 ，如此 反复继续下去由定理2 7 ，下列情形中必有一种情形成立： ( 1 ) 存在某个k ，使得a 七 0 并且l i 玑+ l0 2 1 因此无论出现上述两种情形中的哪一种情形都存在某个整数k ，使得 i l y , 。1 1 2 1 ，并且由定理2 6 ，当k _ 时，有儿_ a + 口 下面的定理表明我们所提出的投影方法至少是二次收敛的 定理2 9 设当k _ o o 时，k a 如果，7 ( 入) 0 ，则 。咂l i r a 嵩鲫矿兰3 锱，一七一( a 一入七) 2 一。、7，7 ( a ) 7 其中面表示上极限 证明：由微分中值定理，存在依赖于尼的某个 1 ( a 七+ 1 ，入) ，使得 f ( a ) 一f ( a k + 1 ) = ，骶1 ) ( a a k + 1 ) ( 2 3 0 ) 另一方面，只要k 充分大总有机一1 ( 入l i c ) = k ( a k + 1 ) = 1 = ，( a ) 将 c k ( a k + 1 ) 一f ( a k + 1 ) 在k 点展开至二阶，并联系定理2 3 我们有 ，( 入) 一f ( a k + 1 ) 。? 七( a 知+ 1 ) 一，( a 七+ 1 ( 2 3 1 ) = ( 蝶( 2 ) 一，( 已) ) ( a 后+ l a k ) 2 ， 、7 其中( a 七，入+ 1 ) 由( 2 3 0 ) ，( 2 3 1 ) 和不等式九入七+ 1 - t , l ( t ) 由z 和a 的定义， z + ( t ) = z ( a ) ) ，z + = z + ( o ) ，入。= 入+ ( o ) ，岔= 。( 1 ) 和a = a ( 1 ) 记 r ( t ) = b ( t ) 一a ( t ) x ( ) ，e 1 ( t ) = 5 b 一5 a x + ( t ) ，e 2 ( t ) = 5 d 一5 c x ( ) ， 3 ( t ) = 5 a t r ( t ) 一a + ( ) 6 c t 可( ) ，e 4 ( t ) = a ( t ) t s l ( t ) + 入( ) c ( t ) t 2 ( t ) ， m ( t ) = a ( ) r a ( t ) - 4 - a + ( t ) c ( ) r c ( ) ， 则我们有下面的定理： 定理2 1 1 假设( ，z ) 和( 爻， ) 是分别相应于( a ，c ，b ，d ) 和( a + 5 a ，c + 5 c ，b - i - 5 b ，d - i - 5 d ) 的最优解则 t 、1 胁( 剑i e ( f ) 0 2 + 弦( 制恢( ) 0 2 一ai _ = = = = = = = = = = = = = = = = = _ _ 一+ ( 1 ) + p l ( 刮i m ( 1 ) 。1 7 2 c ( 1 ) 丁可( 洲2 f 2 3 7 ) 1 i m ( ) 。2 e 3 ( 1 ) 1 1 2慨( ) 1 1 2 、 。| l m ( 1 ) 一2 c ( 1 ) t y + ( - ) 1 1 2 。i l m ( ) - 1 2 c ( - ) r y + ( - ) 吲 岔一z + 1 1 2 1 。e ( 。) i l 。+ i a ( 已) l i i e 2 ( 已) 1 1 2 + 2 1 1 m ( 5 2 ) 2 6 3 ( 2 ) 1 1 2 + i i m ( 2 ) 2 e 4 ( f 2 ) 1 1 2 ( 2 3 8 ) + 丽拱瓷丽) 、一m i i y t q 2 1 z ， l i m ( 巳) 。2 c ( 2 ) t + ) | j 2 ” 矿一! ，+ i i 。f 、厕忙( 岛) 1 1 2 + i a + ( 6 ) 川z ( 矗) | | 。 - i - 2 1 1 m ( 3 ) 一1 2 3 ( 6 ) 1 1 2 + 0 m ( 3 ) 一1 2 4 ( f 3 ) 1 1 2 + 丽刮糍) 忪( 锄m ( 盯m i i 。+ i i 以姗， ( 2 3 9 ) 其中1 ，已和6 为区间( 0 ，1 ) 上的某常数 第二章带二次约束的最小二乘问题的投影方法 证明：为简便起见，将a ( t ) ，z ( 亡) ，矿( ) 和z ( t ) 分别写为a ( t ) ，z ( ) ，y ( t ) 和名( ) 将等式( 2 3 3 ) 和( 2 3 4 ) 两边分别对t 取微分我们得到 一 卜翟揣罢桨5 c 卵) ) + 5 a 啊卅卸厅m ) ) ( 2 4 。) + a ( t ) ( c )