（应用数学专业论文）修正broyden族拟牛顿算法及其应用.pdf

博士学位沧文 摘要 鬣优化问题及其理论和算法米源予经济，管理，工程等许多重谣领域，同时和 计算数学中瓣微分方程数僮解法，菲线性方程组数基黪洼等分支寄着密甥酶联系 和应用传统的b r o y d e n 族拟牛顿算法因为其良好的数值效果和快速收敛速度已 成为求解最优化问题颇受欢迎的一类算法自上世纪6 0 年代以来，传统的b r o y d e n 族拟牛顿募法的璎论受到了广泛戆重视并且墨经取得了事磋静残聚当銎标瓣数 是凸磷数时、该类算法的局部收敛性和全局收敛性理论融得到很好的解决 当目标丽数鼹菲凸函数时，d a i 构造了一个反例说明了使用非精确搜索的b f g s 算洼对非凸涵数不是全局收敛戆寒爨王稷中游许多实躲鞫题往经整是非凸魏。研 究求解非凸的优化问题的拟牛顿算法的全局收敛性具有现实的理论意义和实际意 义 本文首先研究求黪裴凸的无约束拢恁闻题戆修正b f g s 算法以及b r o y d e n 族拟牛顿算法的全局收敛性及其趣线性收敛性在此基础上我们研究求勰非线性 疆，j 、二乘问题的结构化拟牛顿法及其收敛惶理论最后，我们研究求解变分不等 式耀题鲍模单调下降鲍b f g s 葵法及冀全局收敛渡分枣子 首先，在第二章到第四嚣，我们研究求解下面无约荣优化问题的算法， 其中，：舻一瓣是一光滑函数最近，z h a n g ，d e n g 和c h e n 以及w c i ，y n 和 a n 等分舅提出了满怒薪的撅牛顿方程酶瓠牛顿算法，希望提高传统损牛顿算法 的效攀- 他髓对厨提出的叛牛顿篓法的局部收敛性进行了分掇。但是，当基标灏数 ，是非凸函数时，这些算法的全局收敛性尚不清楚我们在l i 和f u k u s h i m a 全局 纯m b f g s 和c b f g s 算法的基础上，分别掇出蘩于z h a n g ，d e n g 和c h e n 以及 w e i ：y n 和y u a n 簿的拟牛顿方程鼹修燕的b f g s 葵法秘保守修正的b f g s 葵法。 在较弱的条件下，我们证明邋两种方法用于求解非凸函数的无约束优化问题时，具 宥全局收敛住及萁超线往i | 5 c 敛往进而，在第舀章，我们研究修正的b r o y d e n 族 拟牛顿算法及其全局收毁嚏我】涯明冤论是基予传统鲍接牛顿方程还楚z h a n g ， d e n g 和c h e n 以及w e i ，y u 和y u a n 簿的拟牛顿方程的修正的b r o y d e n 族拟牛 顿算汝在适警的条件下，不识是局部超缭往收敛的，而且具有全局收敛健， 求鼹菲线性最小二黎闯题的缨擒 l ：擞牛顿法熬全局收敛。陡闻题是人钢关淡的 研究难点课题研究该问题的主要困难在于结构化拟牛顿法产生的矩阵不能保证 对称芷定性。本文第五章致力子谈问题酌研究我们在对y a b e 和t a k a h a s h i 及 u b e 秘y a m a k i 提出的分鼹结擒他攫牛顿雾泼进行 子绷分板的基皴上，结合簿睡 章的思想，提出了一种满秩分解的结构化的b r o y d e n 族算法该算法的特点是，无 i i 修b r o y d c n 族稼串顿葬法殛其寝用 论迭代点是否在解。的附近，都越保 嚣算法产生的迭代矩黪是正定的。我# 】透明， 采用w o l f e 线性搜索的这种结构化b r o y d e n 族拟牛顿法具有全局收敛性和超线性 收敛性此外，利用该算法与g 哪s n e w t o n 算法杂交使用，我们证明杂交算法对 零残差问题是= 次收敛的， 在第六章，通过q r 正交分解，我们对y a b e 和t a k a h a s h i 的结构仡分解形式 懿b f g s 冀法逆行改进改遂后的分解形式静结 每纯b f g s 算法总篌缮逡代矩阵 是正定的焱运避的基伴下，我口】证明这釉分黪形式的结梅化b f g s 算法鲍髑部 超线性收敛性 第七章，我们研究求解对称变分不等式的k k q 、系统的具有单调下降性的 b f g s 莽泫我们酋先将对称变分不等式的k k t 系统转化为等价的非光滑方 程组然后考察餍叛牛颟算法求解该菲光滑方程组我# 对“和f u k u s h i m a 提 出毂 攀调线瞧攫索烟以改遴，在姥基罄羔搀造一个捷方程维搂函数荜璃递城的 b f g s 算法，在遗当的条件下我妇建立獒法的金局收毁瞧及熊超线牲收敛性定理 关键词：无约束优化问题； # 线性最小二乘问题；变分不等式；b r o y d e n 族拟粤顿 算法；b f g s 算法；全局收敛性；超线性收敛性 篓兰兰j 薹翌茎 a b s t r a c t o p t i m i z a t i o nh a saw i d er a n g eo fp r a c t i c a lb a c k g r o t m di ne c o n o n l i c s ，m a n + a g c m e n t ，e n g i n e c r i n ga n d s oo n 。i ti sa l s oc l o s e l yr e l a t e dt ot h en u m e r i c a lm e t h o d s i l lc o m p u t a t i o n a lm a t h e m a t i c ss u c ha st h ed i f f e r e n t i a le q u a t i o na n dt h en o n l i m e a re q u a t i o n sd u et ot h ee f f i c i e n tn u m e r i c dp e r f o r m a n c ea r i at i l ef a q tt h e o r e t i c c o n v e i * g e n c ep r o p e r 镪t h eb r o y d e n sc l a s so fq u a s i n e w t o nm e t h o d sh a v eb e c o m e w e l c o m el n l m e r i c a lm e t h o d sf 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 s s i n c ee a r l y1 9 6 0 s ， n n l c ha t t e t g i o nh a sb e e np a i dt ot h et h e o wo fb r o v d e n 8c l a s so fq u a s i - n e w t o n m e t h o d s t h e r eh a st a k e ng o o dp r o g r e s si nt h es t u d yo fg l o b a la n ds u p e l l i m e a rc o n v e r g e n c ep r o p e r t i e sf o rt h e s em e t h o d s i np a r t i c u l a r ，t h eg l o b a la n dl o c a l s u p e r l i n e a rc o n v e r g e n c eo fb r q v d e n sc l a s so fq u a s i - n e w t o nm e t h o d sf o rc o n v e x m i n i r a i z a t i o n sh a v eb e e nw e l le s t a b l i s h e d o nt h eo t h e rh a n d ，h o w e v e r 、t h es t u d yo nt h eg l o b a lb e h a v i o ro fb r o y d e n s c h e s so f q u a s i - n e w t o nm e t h o d sf o rn o n e o n v e xp r o b l e u li sr e l a t i v e l yf e w e r r e e e n t l y d a ic o n s t r u c t e dac o u n t e r e x a m p l et os h o wt h en o n e o n v c r g e n e eo fb f g sm e t h o d w i t hw o l f el i n es e a r c hi ft h eo b j e c t i v ei sn o tc o n v e x a sm a n yp r a c t i c a lp r o b l e m s a r i s i n gf r o n le n g i n e e r i n ga r en o n e o n v e x ，i ti si m p o r t a n tt od e v e l o pq u a s i - n e w t o n m e t h o d st h a ta r eg l o b a l l ya n ds u p e r l i n e r a l yc o n v e r g e n tf o rn o n e o n v e xn f i n i m i z a - l i o n t i l ep u r p o s eo ft h i st h e s i si st os t u d yt h i st o p i c i nt h i st h e s i s w ef i r s td e v e l o pam o d i f i e db f c sa n dac a u t i o u s 露f g sm e t h o d a ，n ds h o wt h e i rg l o b a la n ds u p e r l i n e a rc o n v e r g e n c ef o rn o n c o l l v e xm i n i m i z a t i o n s 晒t h e np r o p o s eas t r u c t u r e dq u a s i n e w t o nm e t h o df o rs o l v i n gt h en o n l i n e a rl e a s t s q u a r e sp r o b l e m s a tl a s t w ep r o p o s ea1 2 0 1 1 1 1d e s c e n tq u a s i n e w t o nm e t h o df o r s o l v i n gan o n s m o o t he q u a t i o nr e f o r m u l a t i o no ft h es y m m e t r i cv a r i a t i o n a li n e q u m n i t yp r o b l e l n u n d e ra p p r o p r i a t ec o n d i t i o n s w ee z t a b l i s hi t sg l o b a la n ds u p e r l i n e a r c o n v e r g e n c e ， f i r s t ，w ec o n s i d e rt h ef o l l o w i n gu n c 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 m i n ，( z ) ，菠” w h e r e ，：渺_ 鞋i sas m o o t hf u n c t i o n ，歉；e e e n t l ga i m i n ga te n h a n c i n gt h ec f l i - c i e n c yo fq u a s i n e w t o nm e t h o d s ，z h a n g ，d e n ga n dc h e n ，w e i ，y ua n dy u a ne ta 1 p r o p o s e ds o m en e w q u a s i - n e w t o nm e t h o d sb a s e do ns o m en e ws e c a n te q u a t i o n s ， t h e i rn u m e r i c a le x p e r i m e n t ss h o wt h a tt h e s em e t h o d sd oh a v es o m ea d v a n t a g e s t h e ya l s oe s t a b l i s h e dt 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 eo ft h em e t h o d s t t o w e v e r ， i v 修证b r 州d e n 嘏拟牛顿算法段其或甩 8 0f a r ，w ed i dn o ts e ea n yt h e o r ya b o u tt i l eg l o b a lc o n v e r g e n c eo ft h ep l o p o s e d m e t h o d si ft h eo b e c t i v ef u n c t i o ni sn o tc o n v e xi nt h i st h e s i s b a s e do nt h e m b f g sm e t h o da n dc b f g s “l e t h o dp r o p o s e db yl ia n df h l k u s h i m a ，w ew i l l p r o p o s eam o d i f i e da n dac a u t i o u sb f g $ m e t h o d st h a ts a r i s “t i l es e c a n te q u a - t i o n sp r o p o s e db yz h a n g jd e n ga n dc h e n ? a n df f 趣y ua n d 鳓a 薛越u n d e r m i l dc o n d i t i o n s ，w ep r o v et h eg l o b a la n ds u p e r l i n e a re n v e r g e n c eo ft h e s et w o v e r s i o n so fb f g sm e t h o d s f u r t h e r m o r e 。i nc h a p t e r4 ，w ep r o p o s eam o d i f i e d b r w d e n sc l a s so fq u a s i - n e w t o nm e h o d sa n de s t a b l i s ht h e i rg l o b a la n ds u p e r t i n c a rc o n v e r g e n c e i nc h a p t e r5 ，w es t u d yt h eg l o b a lc o n v e r g e n c eo ft h es t r u c t u r e db f g sm e t h o d f o rs o l v i n gt h en o n | i n e a rl e a s ts q u a r e sp r o b l e m s t h i si sad i f f i c u l tr e s e a r c ht o p i c t h ei n a i o rd i f f i c u l tt og l o b a l i z et h es t r u c t u r e db f g sm e t h o di st h a t ，u n l i k eo r d i n a r yb f g sm e t h o d ，t h em a t r i xg e n e r a t e db yas t r u c t m e db f g sm e t h o dm a y n o t b ep o s i t i v ed e f i n i t e 。c o n s e q u e n t l y ，t h eq u a s i - n e a r , o nd i r e c t i o nm a yn o tb ead e s c e n td i r e c t i o nf o rt h eo b j e c t i v ef i l n c t i o n t od e v e l o pag l o b a l l yc o n v e r g e n ts t r u e - t r e e db f g 8m e t h o d w ef i r s tt a k eam o d i f i c a t i a nt ot h ef a c t o r i z e db f g sm e t h o d p r o p o s e db yy a b ea n dt a k a h a s h i ，a n dy a b ea n dy m n a k i ，w et h e np r o p o s e m o d i f i e df u l l - r a n kf a c t o r i z e db f g sm e t h o da n db r o y d e n sc l a s so fq u a s i n e w t o n m e t h o d sa na t t r a c t i v ep r o p e r t yo ft h ep r o p o s e dm e t h o d si st h a tt h eg e n e r a t e d q u a s i - n e w t o nm a t r i c e sa r ep o s i t i v ed e f i n i t e 删埘li ft h ei t e r a t 觚e a w a yf r o m t h es o l u t i o nz 4o ft h ep r o b l e m u n d e ra p p r o p r i a t ec o n d i t i o n s ，w ep r o v et h eg l o b a l a n ds u p e r l i n e e a c o n v e r g e n c eo ft h em e t h o d s b yc o m b i n i n gt h ep r o p o s e ds t r u e - t u r e db r o y d e n sc l a s so fq n a s i - n e w t o nm e t h o d sw i t hg a l l s s n e w t o nm e t h o d ，w e p r o p o s eah y b r i dm e t h o df o rs o l v i n gt h en o n l i n e a rl e a s ts q u a r e sp r o b l e n m t h e a d v a n t a g eo ft h eh y b r i dm e t h o dl i e si nt h a ti t i s n o to n l yg l o b a l l yc o n v e r g e n t f o rn o n z e r or e s i d u a lp r o b l e m sb u ta l s oq u a d r a t i c a l l yc o n v e r g e n tf o rs o l v i n gz e r o r e s i d u a lp r o b l e m s ， a tl a s t w ew i l ls t u d yt h en o r i nd e s c e n tb f g sm e t h o df o rs o l v i n gt h ek k t s y s t e m so ft h es y m m e t r i cv a r i a t i o n a li n e q u a l i t yp r o b l e m b a s e o i 2an o n s m o o t h e q u a t i o nr e f o r m u l a t i o no ft h ek k ts y s t e mo ft h ep r o b l e n l ，w ed e v e l o pab f g s m e t h o d b yt a k i n gad e e pa n a l y s i st ot h en o n n l o n o t o n ol i n es e a r c hp r o p o s e db y l ia n df u k u s h i m a w ec o n s t r u c tad e s c e n tq u a s i - n e w t o nd i r e c t i o nf o rt h en o l m f u n c t i o no ft h ee q u a t i o n 。u n d e ra p p r o p r i a t ec o n d i t i o n s ，w es h o wt h a tt h en o r m d e s c e n tb f g sm e t h o di sg l o b a l l ya n ds u p e r l i n e a r l yc o n v e r g e n t v 博士学谊论文 k e y w o r d s ：u n c 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 ；n o n l i n e a rl e a s t , s q u a r e sp r o b l e m ；v a r i a t i o n a li n e q u a l i t yp r o b l e m ；b r o y d e n 8c l m $ so fq u a s i n e w t o nm e t h o d s ； b f g s m e t h o d ；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 v l 器蓬b r o y d e n 藏攒串赣算涟照其寰_ 秘l 附表索引 表2 1 小规模问题的数值结果 表2 , 2 中等援谈耀题酶数蠖缝果， 表2 3 大规模问题的数值结果 表3 1 初始点为o 使用a r m i j o 搜索的数值结果 表3 2 耱络点为g o 捷蘧w o l f e 搜索静数擅结爰 表3 3 使用a r m i j o 搜索的综合数值结果 表3 4 使用w o l f e 搜索的综合数值结粜。 表3 5 葭薅w o l f e 援索# 一1 0 0 鼗蠖终聚： 表3 6 使用w o l f e 搜索7 1 , = 3 0 0 数值结果 表3 7 使用a r m i j o 搜索n 一1 0 0 数值结果 表4 1 秘始矩羚b o = i 酶数骧结果 表4 2 翩始矩阵玩= 螺 的数值结果 表4 3 初始矩阵b o = ，的综合数值结果 表4 。4 穰始篷薄弱= i 懿缘会鼗穰绩聚 表4 5 初始矩阵b o = 罐1 而的综合数值结果 表4 6 韧始矩阵b o = 嚣而的综合数德结果 表4 7 翔始篷箨b o = 南耪不淹戆妒的数毽结皋 表4 8 初始矩阵b 0 = 靠而和不同的的数值结果 表4 9 d f p 算法的数值结果 表5 。1 甥始点o o 时i 羹! | 渡耀越集1 黪数蕊结暴 表5 26 个不同初始点的测试问题集1 的综合数德结果 表5 3 韧始点o o 时测试问题集2 的数值结果 表5 46 令甭霹镯始豢妈溺渡阕题集2 的缘台数爨结皋 表7 1 问题1 - 3 的数值结粜 表7 2 问题4 - 6 的数值结果 弘瑟弱弘弱；号w鹅蹁毒骚缸船础斛弱挺s8雒泓m n 博士学位论文 基本符号和数值实验的说明 我幻纷出一些从第一蜜到第六章所缝用的蒸本符号， 基本符号： 咿 维欧氏空趣 g p “ m n 阶矩阵集合 f ( x )匿标缀数 9 ( z ) ，v ，( z )目标函数，如) 的梯度向量 g 。) ，v 2 f ( x )目标霸数f ( x ) 的h a ；s i a n 筑阵 z + 所考虑问题的解 z 磐矿妁第次近似 乳 g k = 口( z k ) = v f ( x k ) g g k = g ( x ) 一v 2 ，( # a ) b k g 女的拟牛顿近似 h 秘k = b ：l a 7 向量n 的转鬣 a 7 矩阵a 的转缎 j 单位矩阵 。g 抄 表示g p 中向量 1 1向量或矩阵的欧几羹德范数 t a i i f矩阵a 趣f r o b e n i u s 范数 1 i a i i ，f i i a l l f ，f = f i m a m i i f 数值实验的说明： 掰有静诗葵怒在联想疆| 霹e 3 2 0 ( p e n t i u mi v ，2 0g h z 游个人骨簿祝数双精 度格式进行的所肖的程序是用m a t l a b6 5 语宙自行编写的 对于茏终柬傀纯润聪，溺试瓣蔻选自于下瓣懿两藏： f t p ：f t p m a t h w o r k s c o m p u b c o n t r i b v 4 o p t i m u n c p r o b s 对于菲线洼簸，j 、二秉阕题，我# j 还逡取了以下问搿： h t t p ：w w w c sc a s c z l u k s a a t e s t h t m l 。 第二章至g 第纛章酶数德实验秘中虫穗粥翔下： 1 ，l f 歹( 瓢) | | 1 0 “；或蠢 2 1 i l a x l z + l 一4 1 m = l + l k l s 掬1 。；或毒 x 修】eb r o y d e n 族拟牛顿弹法及其应用 3 ， ，( 。 一1 ) 一f ( x ) ) m a x t ，0 ) ) 1 0 。5 ；或者 4 。迭代次数超过5 0 0 第四章和辩五章还增加一个中止准则： ，( ) 0 不一定成立，扶露导致 h e s s i a n 瓶阵的拟牛顿近似有可能是不定的或奇异的。此时线性搜索可能失败；而 且，萼兰霹巍会镪意姆大，致嚣玻嚣攒牛顿箕法静全慰牧敛挂，珏穰f u k u s h i m 8 在 啦 拟牛顿算法的全墒收敛性理论上做了创新陛研究。他们在文【5 9 ，6 0 分别提出了修 正豹b f g s 篓法帮绦守缪歪静b f g s 算法，势锺汪疆了当誓栎鑫数獒有l i p s e h i t z 连续的导数，水平集有界的情况下，采用w o l f e 或a r m i j o 线性搜索的相应算法足 全羁毂簸静。并髓在与褥统援牛赣算法耱磊静摄设条释下，运两帮箨法茯然具有 3 修i i ：b r o y d e n 旗拟牛顿算法及其应用 怒线蛙收敛性。l 矗帮f 、。u k u s h i m a 韵垒局收敛襁结采能否推广韵b r o y d e n 族上是 值褥礤突鳃同题、也是本文的研究王露之一。 l 。1 2 求解# 线桎最d ：- 乘问越的络构他拟牛顿冀法 本文考虑的舄一个问题怒下面的非线性最小二乘问题： 一 m m i ，l 施) = 扣( z ) 2 1 只( z ) 一；， ( 1 7 ) 一 。1 其中茕( z ) 一( n ( z ) ，r 2 ( ) ，r ，。( 。) ) 7 ，f i ：舻一瓣( i = 1 ，7 f t ) 二次连续可 镦，本交考虑m n 静情形。 对于非缝篷最小二藜闻题( 1 ，7 ) ，锺标添致静梯窿藕h e s s i a n 矩辫分剿其有下 西特别的形式： 和 v 2 ，( 芏) = j ( 譬) t j ( 茗) + 芝二( 嚣) v 2 毪( 茁) 器( 。) t ( z ) + s l 嚣) ， ( 1 9 ) l = i 其中j ( x ) 箍r ( x ) 的j a c o b i a n 矩阵。显然，当m 比较大时，用n e w t o n 算法来 求解饕线性疑小二秉阉题( 1 7 ) 嚣要计算n 扛) f i 一1 ，m ) 静一4 - 阶导数，计算 量比较大，瞍藤鼹不遥宣粒，g a u s s - n e w t o n 算法及l e v e n b e r g - m a r q u a r t 算法莽用 丁h e s s i a , n 矩阵的特殊结构，其迭代矩阵只利用了h e s s i a n 嫩阵( 1 , 9 ) 的一盼譬数 信息，而忽略了( 1 9 ) 中的第= 部分s ( x ) 。所以，当f ( x ) 在鹪处很小或者鲻数 n ( ) 近似予线性函数时，g a u s s n e w t o n 算法及l e v e n b e r g - m a r q u a r t 算法的收敛 速度 琵侠，甚至怒二阶收敛的* 瑚$ j 。但是滔f ( x 1 在解x + 处很大或者函数，t ( z ) 线性程度狠大对，g a u s s - n e w t o n 算法及l e v e n b e r g - m a r q u a r t 葬法的收敛速度 可减低至线性。我蛔称潆是，囊+ ) ：= 0 鲍阉遂( 1 7 ) 为零残差耀鼷；否剩称鸯j 零 残蓑问题。 考察用拟牛顿算法求解( 1 7 ) 、由( 1 8 ) 和( 1 9 ) 可以看出，( z ) 的h e s s i a n 矩 阵靓含有已经计算出的一阶信息l ，( z ) 7 j ( x ) 。在一般的拟牛顿算法中，迭代矩阵 琉没有充分桶嗣v 2 ，( z ) 的结构，而楚遥近整个h e s s i e a l 矩阵。为克服这一缺陷， d e n n i s ，m a r t i n e z 帮t a p i a 提癌了下瑟缩褊亿藤猁酬：令 b k = j ( x k 厂。，( ) 十a ，( 1 1 0 ) 其中爿是h e s s i a n 矩阵v 2 f ( x ) 的第二部分s ( x ) 的近似。根据此结构化原则 d e n n i s 。m a r t i n e z 和t a p i a 提出了下面的结构化拟牛顿算法： f j ( x ) t ，( 带) + a 】p 女 + ，( 并女) r r ( x k ) = 0 ，( 1 1 1 ) 博士学佗论文 其中足s ( z k ) 的近似，并且满足下面的拟牛顿方程 a l 岛= y 拳( i 1 2 ) 上式中s k = z k + l z 自，y 榉是s ( 。) 龇的近似。b r w d e n 族结构化拟牛顿算法中， 奄按照下面蛉公发进行修正： + 1 = a k + ( 轧，孑，4 ，) ，( 1 1 3 ) 葵孛， ( 壤，窘，a e ，) = 史生二二生璺尘叠麦若j 巡一盟警”：蝶壤l o i j f 1 1 4 ) 无论是零残差问蹶还是非零残差问题，d e n n i s ，m a r t i n e z 和t a p i a 证明了结构 侄b f g 8 算法戆竭帮超线性壤敛穗。e n g e l s 秘m a r t i n e z 耱逮一缝聚接广餮采 用b r o y d e n 族修雁公式的结构化拟牛顿算汰 “。d e n n i s ，g 州和w e l s c h 提出了 结姆化d f p 算法，并且采用了偿赣蛾技术保证垒届牧敛性6 4 l 。遵獯这个愿剥， b a r t h o l o m e w o b i g g s 提出了对称秩一修正酌结构化拟牛顿算法。上述结构仡拟 牛顿算法对零残熬问题不能保证其像g a u s s - n e w t o n 算法那榉具有二次收敛眭。闲 魏，m - b a a l i 稔f l e t c h e r 致f l e t c h e r 和x u 提出_ 将结秘纯b f g s 算滚与g a l l s s n e w t o n 算法杂交的算法叫；h u s e h e n s 对d e n n i s ，m a r t i n e z 和t a p i a 的结构化 缀剿进褥了改遴，挺出了蘩积形式鳇结橡化糖 譬顿算法嘲。茏沦是鸯滚算法还是 乘积形式的结构化拟牛顿薄法对予非零残麓问题是髑部超线性收敛的，而对于零 残差问题，算法逐具有二次收敛速度。 上瑟提到静结构 ：叛牛顿算法在线往攘索豹稚黎下，只有局部收敛性速度的 分析，缺乏相应的给局收敛睫研究。罄实上，研究基于d e n n i s ，m a r t i n e z 和t a p i a 结 梅毽派剿豹结稳纯攒牛顿葵法懿全蜀牧鼓豫瓣最大瓣难之一是螽餐修疰鱼使褥 遮代矩阵缘是正定的。对于非结构化的拟牛顿算法，条件【v ，( k + 1 ) 一v f ( x ) 】7 8 k 0 程鼠是正定的矩阵就熊像涯对鼹有数，b k 正定。然露，黠按照d e n n i s ，m a r t i r m z 和t a p i a 的结构化原刚构造的迭代矩阵玩在此条件下不能保诋鼠正定 性。为解决这一问题，y a b e 和t a k a h a s h i 掇出了分勰形式的结构化b f g s 算法 秘d f p 簿法 y a b e 帮y a m a k i 将这一嚣想推广弼垒俸b r o y d e n 族摈牟赣算 法【，并且证明了分解形斌算法的局部超线性收敛性。然而，这类分解形式的结 褥诧熬牛顿葵法哭褰在鳃$ 约辫_ i 琏才能缳谖滚分蘩楚瀵疆瓣，挖对襞僚涯壤是 正定的。幽迭代点远离解时，该算法不能保诚b k 的姬定性。另外，z h s a _ l g ，c h e n 和 d e n g 结食分鳃的恩想和h u s c h e n s 莱积技术，提出了黎积形式的分解黪结槐诧搬 牛顿算法明该簿法对于a # 零残蓑闻题是商部超线性收敛的，对于零残差问题是 二次收敛的 修正b r o y d e a 挟拟牛顿算法及荩应用 最近，w a n g ，l i 秘q i 挺鑫了一个耨鹤结构亿惑懋 7 2 1 ： 令成= b 一j ( 髫+ 1 ) 7 j ( x k + 1 ) 。选代矩阵风按照下面的公式计獒 a l = a + ( # 薯，a t ，t ) ， 岛+ l = j ( x k + 1 ) 7 。l ( x e + 1 ) 一- t - a k + l 其中，a ( s k ，g 警，a t ，v k ) 如式( 1 1 4 ) 所定义。根据新的结构化原则，w a n g ，l i 期q i 提出了一种修正的结构化b f g s 算法同。该修正的结构化b f g s 算法最大的特 点屉这代键菸换对骈鸯静k 都蹙正定静、扶蓊搜索方窝是下降翡。德们溽对证 明r 该算法的全局收敛性。据作卷所知，这是迄今为止唯一的关于结构化拟牛顿 算法肄有垒局收敛性的结果。 上嚣摄到研究结梅铯搬牛壤赛法全局牧敛经懿最夫嚣难在于按然掺正公式 ( 1 1 0 ) ，( 1 1 3 ) 和( 11 4 ) 得到的遮代矩阵圾不是正寇的，从而导致w o l f e 类或 a r m i j o 类线性搜索的失败。y a b e 和t a k a h a s h i 及y a b e 和y a m a k i 的思想已经保 涯迭代矩黪是半曩定蜂，妇侮在越基础皇敞遂一一步褥究，徒簿改遘麓静分解形痰的 结构化拟牛顿算法能够保证迭代矩阵是正定的，进而证明算法的全局收敛性 屉一件有意义的工作，这也怒本文的另一个冀要工作。 1 1 3 求解对称变分不等式k k t 系统的模下降b f g s 算法 本文考虑的最后一个问题是求解下面变分不等式融题：设f ：舻一即悬连 续可微粒避数，求矿毫x 爱褥 ( y 一。) f ( z 8 ) 0 ，v y x ，( 1 1 5 ) 其中，x = z 吼( z ) 0 ，h j ( x ) 一0 ，= 1 ，m 、j 一1 ：，r ，吼( z ) ，b ( z ) 是 渺一羚二次连续可欺静丞数。 本文，我们将变分不等式问题( 1 1 5 ) 记为v k x ，f ) 。显然，如果x = 渺，贝i ( 1 1 5 ) 退化为非线性方程组 f ( 。) = 0 。 溺藏，菲线往方程组可作为v i ( x ，f ) 的一种特殊簿况。v i ( x ，f ) 另外一种特殊 情况鼹x 一豫! 一囊渺：g20 。这时，v i ( x ，f ) 退睨成嚣线性麓 阉题 ( n c p ( f ) ) ：求z 铲，使得 z o ，p ( 正) o ，z ，f ( 。) 嚣0 众所属翔，攥一定瓣约寒晶蠼下( 】+ 1 5 ) 鹭鳃，3 连弱耀发黪l a g r a n g e 乘予超 量a 一( a l ，m 严彤“和弘= ( 肛h ，) 7 彤满足下列k k t 系统 f 1 1 反之，湔足k k t 系统( 1 _ 1 6 ) 的_ ：4 在一定的条件下是v i ( x ，f ) 的解。因此通过 求铸燮分不等式k k t 系统是求解原闻题v i ( x ，f ) 的一种重要手段。 求辩k k t 系缭f 1 1 6 ) 鹃方法之一是将冀转讹为等价懿j 澎滑方程组+ 邋1 0 余年来，求解非光滑方程组的广义牛顿法和光滑化牛顿法及其收敛性理论的研究 受到了相当大的重视，并且取得了很大的发展呱“4 ，7 “”】。q i 和q i s u n 提出了 求髂一般的j 光滑盼方程组广义牛顿法嗡8 “。考虑如下非线髅方程组： ( 。) = 0 其中，h 是酽_ 彬的局部l i p s c h i t i z i a n 函数。q i 和q i _ s u n 掇出了利用c l a r k e 广义静数钱营毙潦媾澎黪f r 6 c h e t 浮鼗懿争顿汝鼢龉l 。其子瓣鼹是 k p + 科( ) = 0 ，k o h ( z k ) 其中，a h ( z 女1 为曩谯稚处的c l a r k e 广义导数【9 4 j 。如果在鳞矿处日是c d 一噩 翔酌秘半光蒲静或强薯主毙潼稳，瓣凌广义n e w t o n 法产生魏滓巅聚趣缓经牧敛域 二次收敛的有关广义牛顿法的全局收敛性研究在过去的2 0 年中取得了重要的 结果，可参见文1 7 8 ，8 9 l 然瓣求锯菲光滑方程组的拟牛顿法的研究檬对较少。其主要困难在于即嫒对 予惫辫弱菲线往方程缢，羧牛羲法产生静方惫一黻不貔绦涯是效兹露羧薛下耩方 向。常用的线性搜索( 如a r m i j o 搜索) 此时已不邋甩。因此，为了研究拟牛顿法的 全局收敛性，必须使用新的线性搜索技巧。 g r i e w a n k 首先掇蹬了求解光滑 # 线性方程缀的具有全局收敛性的拟牛顿泼 1 2 s 。箕蒜塞是在辑掇囊的b r o y d e n 秩1 箕法审罨i 入一释无导数线谴援索，捷葵 法成为下降算法。然而，该算法在装魉情形下，线性搜索可能失败。求解非线性方 程组的首个适定的嶷有全局收敛性的拟牛顿法由l i - f u k u s h i m a 提出刚l l 和 h l k u s h i m a 提出了一肆薪的非单测茏导数线性搜索。剥用此线性搜索，l i 秘 f u k u s h i m a 搀出了密勰光涛菲缓魏方程组薛一个其毒垒局毅敛靛的b r o y d e n 秩 1 算法。这种非单谢线性搜索设_ 崴用于求解非线性互补问题和变分不等式问蹶 “蚓。在适当的条件下，这些算法都具有全局收敛性和超线性收敛性。对于光滑 的对称非线性方程缀，l i 秘f u k u s h i m a 程g u ，矗裙毯等分另撼蹦了非单调下海 圳趣 辫。篓坷蕊部 器 修正b r o y d e n 旌拟牛顿算法及其应用 帮罄调下降盼b f g s 算法 3 8 t “。在l i 和f 、：k u s h i m a 的基磷上，l i 。y a m a s h i t a 强h ：k u s h i m a 掇出了一个求黪约束挠化同鞭k k t 系统熬j 单调b f g s 葵法【“。 到目前为止，还没有人讨论求解k k t 系统( 1 1 6 ) 躲单调下降数牛顿法。本 文将在【3 5 ，3 8 】基础上提出一种求解k k t 系统( 1 1 6 ) 模下晦拟牛顿算法。 1 2 本文韵工作和结构 本文包括三个主要部分。第一部分从第二章到第四章研究求解无约束问题的 修正的羧牛镢算法。第二都分包括第蠢章藕第六章研究求