《数值最优化方法》课程教学课件（讲稿，打印版）信赖域方法

最优化方法及其atlab程序设计 第六章信赖域方法 Back Close

1/28 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 18Ÿ &6çê{

信赖域方法与线搜索技术一样，也是优化算法中的一种保证全局 收敛的重要技术.它们的功能都是在优化算法中求出每次迭代的位 移，从而确定新的迭代点.所不同的是：线搜索技术是先产生位移方 向（亦称为搜索方向），然后确定位移的长度（亦称为搜索步长）：而信 赖域技术则是直接确定位移，产生新的迭代点 信赖域方法的基本思想是：首先给定一个所谓的“信赖域半径” 作为位移长度的上界，并以当前迭代点为中心以此“上界”为半径“画 地为牢”确定一个称之为“信赖域”的闭球区域.然后，通过求解这个 区域内的“信赖域子问题”（目标函数的二次近似模型）的最优点来确 定“候选位移”.若候选位移能使目标函数值有充分的下降量，则接 受该候选位移作为新的位移，并保持或扩大信赖域半径，继续新的迭 代；否则，说明二次模型与目标函数的近似度不够理想，需要缩小信赖 域半径，再通过求解新的信赖域内的子问题得到新的候选位移.如此 Back Close

2/28 JJ II J I Back Close &6çê{ÜÇ|¢E‚ò, è¥`zé{•ò´y¤ ¬Ò­áE‚. ßÇıU—¥3`zé{•¶—zgSì† £, l (½#Sì:. §ÿ”¥: Ç|¢E‚¥k)†£ê ï (½°è|¢êï), ,￾(½†£› (½°è|¢⁄); & 6çE‚K¥Ü(½†£, )#Sì:. &6çê{ƒgé¥: ƒkâ½ò᧢/&6çåª0 ä膣›˛., ø±cSì:è•%±d/˛.0èåª/x /èO0(½òá°Éè/&6ç04•´ç. ,￾, œL¶)˘á ´çS/&6çfØK0(8IºÍgCq.) Å`:5( ½/ˇ¿†£0. eˇ¿†£U¶8IºÍäkø©e¸˛, K .Tˇ¿†£äè#†£, ø±½*å&6çåª, UY#S ì; ƒK, `²g.Ü8IºÍCq›ÿ né, Iá†&6 çåª, 2œL¶)#&6çSfØK#ˇ¿†£. Xd

重复下去，直到满足迭代终止条件， §6.1信赖域方法的基本结构 现在我们来讨论用信赖域方法求解无约束优化问题 min f(x) (6.1) x∈Rn 的基本算法结构.设xk是第k次迭代点.记=f(xk),9=Vf(xk), B.是Hesse阵V2f(xk)的第k次近似，则第k次迭代步的信赖域子 问题具有如下形式： min ma国=9d+d (6.2) s.t.d≤△k, 其中△k是信赖域半径，‖·‖是任一种向量范数，通常取2范数或○-范 数.设子问题(61)的最优解为d,定义△f.为f在第k步的实际下 Back Close

3/28 JJ II J I Back Close ­Ee, ܘvSì™é^á. §6.1 &6çê{ƒ( y3·Ç5?ÿ^&6çê{¶)ÃÂ`zØK min x∈Rn f(x) (6.1) ƒé{(.  xk ¥1 k gSì:. P fk = f(xk), gk = ∇f(xk), Bk ¥ Hesse ∇2 f(xk) 1 k gCq, K1 k gSì⁄&6çf ØK‰kXe/™: min qk(d) = g T k d + 1 2 d TBkd, s.t. kdk ≤ ∆k, (6.2) Ÿ• ∆k ¥&6çåª, k·k ¥?ò´ï˛âÍ, œ~ 2-âͽ ∞-â Í. fØK (6.1) Å`)è dk, ½¬ ∆fk è f 31 k ⁄¢Se

降量： △f=f-f(xk+d), △q为对应的预测下降量： △qk=qk(O)-qk(d): 再定义它们的比值为 △f Tk二 (6.3) △qk 一般地，我们有△qk>0.因此，若Tk<0,则△f<0,xk+d 不能作为下一个迭代点，需要缩小信赖域半径重新求解子问题.若Tk 比较接近1，说明二次模型与目标函数在信赖域范围内有很好的近似， 此时xk+1:=xk+d,可以作为新的迭代点，同时下一次迭代时可以增 大信赖域半径.对于其他情况，信赖域半径可以保持不变.下面给出求 解无约束优化问题信赖域方法的一般框架 Back Close

4/28 JJ II J I Back Close ¸˛: ∆fk = fk − f(xk + dk), ∆qk èÈA˝ˇe¸˛: ∆qk = qk(0) − qk(dk). 2½¬ßÇ'äè rk = ∆fk ∆qk . (6.3) òÑ/, ·Çk ∆qk > 0. œd, e rk < 0, K ∆fk < 0, xk + dk ÿUäèeòáSì:, Iá†&6ç媭#¶)fØK. e rk 'C 1, `²g.Ü8IºÍ3&6çâåSkÈ–Cq, dû xk+1 := xk + dk å±äè#Sì:, ”ûeògSìûå±O å&6çåª. ÈuŸ¶ú¹, &6çåªå±±ÿC. e°â—¶ )ÃÂ`zØK&6çê{òѵe.

算法6.1（信赖域方法） 步0选取初始参数0≤10为信赖域半径的上限，初始信赖域 半径△0∈(0，△].令k=0. 步1计算9=Vf(c).若g‖≤e,停止选代. 步2求解子问题(6.2)的解d. 步3按(6.3)式计算rk的值. 步4校正信赖域半径. T1△k, 若Tk≤1， △k+1= △k 若11,则令xk+1:=ck十dk,更新矩阵Bk到Bk+1,令 Back k=k十1，转步1.否则xk+1=xk,令k=k+1,转步2. Close

5/28 JJ II J I Back Close é{ 6.1 (&6çê{) ⁄ 0 ¿–©ÎÍ 0 ≤ η1 0 è&6çåª˛Å, –©&6ç åª ∆0 ∈ (0, ∆] ˜ . - k := 0. ⁄ 1 Oé gk = ∇f(xk). e kgkk ≤ ε, éSì. ⁄ 2 ¶)fØK (6.2) ) dk. ⁄ 3 U (6.3) ™Oé rk ä. ⁄ 4 &6çåª. ∆k+1 :=    τ1∆k, e rk ≤ η1, ∆k, e η1 η1, K- xk+1 := xk + dk, ç#› Bk  Bk+1, - k := k + 1, =⁄ 1. ƒK xk+1 := xk, - k := k + 1, =⁄ 2

注在算法6.1中一组推荐的参数值为 m1=0.05,2=0.75,T1=0.5,2=2.0,△0=1或△0= 在实际计算中可以对上述参数进行调整，以达到最佳计算效果 由于子问题(6.2)的可行域是有界闭集，因此算法6.1中步2的d4 存在，即子问题(6.2)是可解的.下面的定理说明xk不是问题(6.1)的 稳定点，则预估下降量△qk>0.因此算法是适定的 定理6.1设d是子问题(6.2)的解.若9纵=Vf(xk)卡0，则 △qk=qk(0)-qk(d)>0. 证易知0是子问题(6.2)的可行点，因此q(d)≤q张(0)，即 △qk≥0.下面只需证明△qk卡0.如若不然，△qk=q(0)-qk(d)=0, 则q(d)=q(0).故0是子问题(6.2)的最优解.但0是可行域的内 点，故有7q(O)=0,即Vf(xk)=0,这与定理的假设矛盾.证毕. Back Close

6/28 JJ II J I Back Close 5 3é{ 6.1 •ò|ÌÎÍäè η1 = 0.05, η2 = 0.75, τ1 = 0.5, τ2 = 2.0, ∆0 = 1 ½ ∆0 = 1 10 kg(x0)k. 3¢SOé•å±È˛„ÎÍ?1N, ±àÅZOéJ. dufØK (6.2) å1ç¥k.48, œdé{ 6.1 •⁄ 2  dk 3, =fØK (6.2) ¥å). e°½n`² xk ÿ¥ØK (6.1)  ­½:, K˝e¸˛ ∆qk > 0. œdé{¥·½. ½n 6.1  dk ¥fØK (6.2) ). e gk = ∇f(xk) 6= 0, K ∆qk = qk(0) − qk(dk) > 0. y ¥ 0 ¥fØK (6.2) å1:, œd qk(dk) ≤ qk(0), = ∆qk ≥ 0. e°êIy² ∆qk 6= 0. Xeÿ, ∆qk = qk(0) − qk(dk) = 0, K qk(dk) = qk(0).  0 ¥fØK (6.2) Å`). 0 ¥å1çS :, k ∇qk(0) = 0, = ∇f(xk) = 0, ˘Ü½nbgÒ. y.

利用上述定理可以证明由算法6.1产生的序列{f(xk)}是单调非 增的.我们有 推论6.1设{xk}是由算法6.1产生的迭代序列，则序列{f(x)} 是单调非增的， 证由算法结构可知，对任意k≥0，若Tk≤1，则xk+1=xk,此 时有f(xk+1)=f(xk).若rk>1,由定理6.1以及Tk的定义可知 f(xk)-f(k+1)=f(xk)-f(ck +dk)=TkAqk>0, 即f(xk+1)<f(xk).证毕 §6.2信赖域方法的收敛性 为了分析信赖域方法的收敛性，我们首先在迭代点x处，引入所 Back Close

7/28 JJ II J I Back Close |^˛„½nå±y²dé{ 6.1 )S {f(xk)} ¥¸Nö O. ·Çk Ìÿ 6.1  {xk} ¥dé{ 6.1 )SìS, KS {f(xk)} ¥¸NöO. y dé{(å, È?ø k ≥ 0, e rk ≤ η1, K xk+1 := xk, d ûk f(xk+1) = f(xk). e rk > η1, d½n 6.1 ±9 rk ½¬å f(xk) − f(xk+1) = f(xk) − f(xk + dk) = rk∆qk > 0, = f(xk+1) < f(xk). y. §6.2 &6çê{¬Ò5 è ©¤&6çê{¬Ò5, ·Çƒk3Sì: xk ?, ⁄\§

谓的“柯西点”(Cauchy point)d5的定义： △k di=-TkTgkok, (6.5) 其中 1 9kB9k≤0， Tk三 (6.6) 容易证明 ‖d‖=Tk△k≤△k, 即柯西点是可行点，且平行于f(x)在xk处的负梯度方向（最速下降 方向).下面的引理说明柯西点诉可以带来二次模型一定量的下降 引理6.1由(6.5)定义的柯西点d满足 a0-se≥nm{a圆} (6.7） Back Close

8/28 JJ II J I Back Close ¢/Ö‹:0(Cauchy point) d c k ½¬: d c k = −τk ∆k kgkk gk, (6.5) Ÿ• τk =    1, gT k Bkgk ≤ 0, min  kgkk 3 ∆kg T k Bkgk , 1  , gT k Bkgk > 0. (6.6) N¥y² kd c kk = τk∆k ≤ ∆k, =Ö‹:¥å1:, Ö²1u f(x) 3 xk ?KF›êï (ÅÑe¸ êï). e°⁄n`²Ö‹: d c k å±ë5g.ò½˛e¸. ⁄n 6.1 d (6.5) ½¬Ö‹: d c k ˜v qk(0) − qk(d c k ) ≥ 1 2 kgkk min  ∆k, kgkk kBkk  . (6.7)

证（①）若gFBx9张≤0，则由(6.5)-(6.6)有= △ g79.此时有 0-喝=0-公（←高 =(六-高'a(六 aar-2aa ☆-A(注藏到-层B≥0) m{al} z (2)若9Bg>0且 s1,则=-a △kgBk9R g Bigk 一9，从而 Back Close

9/28 JJ II J I Back Close y (1) e g T k Bkgk ≤ 0, Kd (6.5)-(6.6) k d c k = − ∆k kgkk gk. dûk qk(0) − qk(d c k ) = 0 − qk  − ∆k kgkk gk  = −g T k  − ∆k kgkk gk  − 1 2  − ∆k kgkk gk T Bk  − ∆k kgkk gk  = ∆k kgkk kgkk 2 − 1 2 ∆2 k kgkk 2 g T k Bkgk ≥ ∆k kgkk kgkk 2 = ∆kkgkk ( 5ø − g T k Bkgk ≥ 0) ≥ 1 2 kgkk min  ∆k, kgkk kBkk  . (2) e g T k Bkgk > 0 Ö kgkk 3 ∆kg T k Bkgk ≤ 1, K d c k = − kgkk 2 g T k Bkgk gk, l

有 a-a(-设 -(-a6）-a(刘 -器≥≥m{A-》 2gf Bkgk 书8>0里>1则成-奇e及 Back Close

10/28 JJ II J I Back Close k qk(0) − qk(d c k ) = 0 − qk  − kgkk 2 g T k Bkgk gk  = −g T k  − kgkk 2 g T k Bkgk gk  − 1 2  − kgkk 2 g T k Bkgk gk T Bk  − kgkk 2 g T k Bkgk gk  = 1 2 kgkk 4 g T k Bkgk ≥ 1 2 kgkk 2 kBkk ≥ 1 2 kgkk min  ∆k, kgkk kBkk  . e g T k Bkgk > 0 Ö kgkk 3 ∆kg T k Bkgk > 1, K d c k = − ∆k kgkk gk 9 kgkk 3 >