最优化方法及其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≤1<2<1,0<T1<1<2, 0≤E《1.x0∈R”.取定△>0为信赖域半径的上限，初始信赖域 半径△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 若1<Tk<2, (6.4 min{2△k,△，若Tk≥2，ldll=△k. 步5若Tk>1,则令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 < η2 < 1, 0 < τ1 < 1 < τ2, 0 ≤ ε 1. x0 ∈ R n . ½ ∆˜ > 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 < rk < η2, min{τ2∆k, ∆˜ }, e rk ≥ η2, kdkk = ∆k. (6.4) ⁄ 5 e rk > η1, K- xk+1 := xk + dk, ç#› Bk Bk+1, - k := k + 1, =⁄ 1. ƒK xk+1 := xk, - k := k + 1, =⁄ 2