注在算法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 >