最优化方法及其Matlab程序设计 第五章拟牛顿法 Back Close
1/52 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1 Ÿ [⁄Ó{
第3章所介绍的牛顿法的优点是具有二阶收敛速度，但当Hesse 阵G(x)=Vf(x)不正定时，不能保证所产生的方向是目标函数在 xk处的下降方向.特别地，当G(x)奇异时，算法就无法继续进行下 去.尽管修正牛顿法可以克服这一缺陷，但其中的修正参数的选取 很难把握，过大或过小都会影响到收敛速度.此外，牛顿法的每一迭代 步都需要目标函数的二阶导数，即Hesee阵，对于大规模问题其计算 量是惊人的 本章即将介绍的拟牛顿法克服了这些缺点，并且在一定条件下这 类算法仍然具有较快的收敛速度一超线性收敛速度， S5.1拟牛顿法及其性质 拟牛顿法的基本思想是在基本牛顿法的步2中用Hesee阵G= Vf(xk)的某个近似矩阵Bk取代Gk.通常，Bk应具有下面的三个特 Back Close
2/52 JJ II J I Back Close 1 3 Ÿ§0 ⁄Ó{`:¥‰k ¬ÒÑ›, Hesse G(xk) = ∇2 f(xk) ÿ½û, ÿUy§)êï¥8IºÍ3 xk ?e¸êï. AO/, G(xk) ¤.û, é{“Ã{UY?1e . ¶+?⁄Ó{å±é—˘ò"Ä, Ÿ•?ÎÍ µk ¿ ÈJrº, Lå½L—¨Kè¬ÒÑ›. d , ⁄Ó{zòSì ⁄—Iá8IºÍ Í, = Hesee , Èuå5 ØKŸOé ˛¥Ø<. Ÿ=Ú0 [⁄Ó{é— ˘ ":, øÖ3ò½^áe˘ aé{E,‰kجÒÑ›—áÇ5¬ÒÑ›. §5.1 [⁄Ó{9Ÿ5ü [⁄Ó{ƒ gé¥3ƒ ⁄Ó{⁄ 2 •^ Hesee Gk = ∇2 f(xk) ,áCq› Bk ì Gk. œ~, Bk A‰ke°náA
点 (1)在某种意义下有B≈Gk,使相应的算法产生的方向近似于 牛顿方向，以确保算法具有较快的收敛速度 (2)对所有的k,B是对称正定的，从而使得算法所产生的方向 是函数∫在xk处下降方向 (3)矩阵B更新规则相对比较简单，即通常采用一个秩1或秩 2矩阵进行校正 下面介绍满足这三个特点的矩阵Bk的构造.设∫：R”→R在开 集DCR”上二次连续可微.那么，∫在xk+1处的二次近似模型为 fa)≈f(+1)+9眼+1(c-xk+H)+)-k+1)PGk+1(-k+1). 对上式求导数得 g(c)≈9k+1+Gk+1(x-ck+1): Back Close
3/52 JJ II J I Back Close :: (1) 3,´ø¬ek Bk ≈ Gk, ¶ÉAé{)êïCqu ⁄Óêï, ±(é{‰kجÒÑ›. (2) ȧk k, Bk ¥È°½, l ¶é{§)êï ¥ºÍ f 3 xk ?e¸êï. (3) › Bk ç#5KÉÈ'{¸, =œ~Ê^òáù 1 ½ù 2 › ?1. e°0 ˜v˘náA:› Bk E. f : R n → R 3m 8 D ⊂ R n ˛gÎYåá. @o, f 3 xk+1 ?gCq .è f(x) ≈ f(xk+1) + g T k+1(x − xk+1) + 1 2 (x − xk+1) TGk+1(x − xk+1). È˛™¶Í g(x) ≈ gk+1 + Gk+1(x − xk+1).
令x=xk,位移Sk=xk+1一xk,梯度差y=g张+1一9k,则有 G+15k≈h. 注意到，对于二次函数∫，上式是精确成立的.现在，我们要求在拟牛 顿法中构造出Hesse阵的近似矩阵Bk满足这种关系式，即 Bk+1sk=Yk (5.1) 上式通常称作拟牛顿方程或拟牛顿条件.令Hk+1=B1,则得到拟 牛顿方程的另一个形式： Hk+1yk=Sk (5.2) 其中Hk+1是Hesse阵逆的近似.搜索方向由dk=一Hkgk或Bkdk= 一9k确定.根据Bk(或H)的第三个特点，可令 Bk+1=Bk+Ek:Hk+1=Hk+Dk; (5.3) Back Close
4/52 JJ II J I Back Close - x = xk, †£ sk = xk+1 − xk, F› yk = gk+1 − gk, Kk Gk+1sk ≈ yk. 5ø, ÈugºÍ f, ˛™¥°(§·. y3, ·Çá¶3[⁄ Ó{•E— Hesse Cq› Bk ˜v˘´'X™, = Bk+1sk = yk. (5.1) ˛™œ~°ä[⁄Óêß½[⁄Ó^á. - Hk+1 = B −1 k+1, K[ ⁄Óêß,òá/™: Hk+1yk = sk, (5.2) Ÿ• Hk+1 ¥ Hesse _Cq. |¢êïd dk = −Hkgk ½ Bkdk = −gk (½. ä‚ Bk(½ Hk) 1náA:, å- Bk+1 = Bk + Ek, Hk+1 = Hk + Dk, (5.3)
其中E,Dk是秩1或秩2矩阵.通常将由拟牛顿方程(5.1)（或(5.2）) 和校正规则(5.3)所确立的方法称为拟牛顿法， 下面我们介绍一个对称秩1校正公式.在(5.3)中取E=au以（秩 1矩阵)，其中a∈R,uk∈Rm.由拟牛顿方程(5.1)得 (Bi+aukur)5k=Vk, 即有 a(uk sk)uk =yk -BiSk. (5.4) 上式表明向量平行于(-Bksk),即存在常数B使得=B(y一 Bks).因此有 Ek:aB2(Uk:-BkSk)(Uk:-Bk.Sk)T. 于是，由(5.4)得 aB2[(V1:-Bi.Sk)Tsk](Uk:-BiSk)=(Uk:-BkSk). Back Close
5/52 JJ II J I Back Close Ÿ• Ek, Dk ¥ù 1 ½ù 2 › . œ~Úd[⁄Óêß (5.1) (½ (5.2)) ⁄5K (5.3) §(·ê{°è[⁄Ó{. e°·Ç0 òáÈ°ù 1 ˙™. 3 (5.3) • Ek = αuku T k (ù 1 › ), Ÿ• α ∈ R, uk ∈ R n . d[⁄Óêß (5.1) (Bk + αuku T k )sk = yk, =k α(u T k sk)uk = yk − Bksk. (5.4) ˛™L²ï˛ uk ²1u (yk − Bksk), =3~Í β ¶ uk = β(yk − Bksk). œdk Ek = αβ2 (yk − Bksk)(yk − Bksk) T . u¥, d (5.4) αβ2 [(yk − Bksk) T sk](yk − Bksk) = (yk − Bksk)