最优化理论与算法(第三章)

1、第三章牛顿法 3.1最速下降法一、最速下降法产生的算法称为最速下降法,在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向, 它是无约束最优化算法中最简单、最基本的算法。算法描述：1)给出初始点X0 R，允许误差0, k 0 ；2)计算dkgk，若 gk*,Stop 令 xXk ；3)由维搜索确疋步长因子k，使得f (Xkkdk)min f (Xkdk)4)令 Xk 1 Xk kdk，k k 1，go to 2).、最速下降算法的收敛性定理3.1 设f C1，则最速下降算法产生的点列xk的每个聚点均为驻点。证明：设x是Xk的一个聚点，则存在子序列Xk K，使得K1lim xk Xk K1令

2、dkf(Xk)，由 f C1 ，知f(Xk) &是收敛序列，故dk K有界，且f(X)由定理2.6有f(X)T(f(X)f(X)2 0定理3.2 设f(x)二次连续可微，且故有f(X) 0。2f (x) M，则对任何给定的初始点X0Rn，最速下降算法或有限终止，或lim f (Xk) ，或lim f (Xk)0。kk证明：不妨设 k ,f(xk) 0。由定理2.5有于是f(Xk)f(Xk 1)1制 f(Xk)lkf(Xo) f (Xk)f (Xi) f (Xi i)i 012Mf (Xi) 2令k ，由 f(Xk)为单调下降序列，则要么kim f (Xk)，要么 严| f(Xj| 0。最速下降

3、算法若采用不精确一维搜索，仍有下列总体收敛性定理。定理3.3 设f C1，则采用不精确一维搜索得到的点列Xk的每个聚点均为驻点。证明：直接由定理2.14可得。注：1)最速下降算法的收敛性也可由前述关于模式算法收敛性结果定理2.7直接获得;2)最速下降算法的主要优点是方法简单、直观，有好的总体收敛性，但收敛很慢。三、最速下降算法的收敛速度 1.先考虑二次函数情形1定理3.4 对极小化问题 minf(x)xtGx，其中G为n n对称正定矩阵，1， n分别为G的最大与最小特征值。设 x*是最优解，则最速下降算法的收敛速度至少是线性的，且下面的界成立：f(Xk 1)*f(x)(1)2 (1n)21Xk

4、 1 x*|f (Xk)*f(x)(1)2 (1n)2 |xkx*|其中1/n |G|G1|(为矩阵G的条件数)。证明：由f (x) Gx，有f(xQ GXk。故Xk 1Xkkdkxkkf(Xk) XkkGXk其中k使f(IkG)Xk)f (IG)Xk)，0若设P(t)1kt，Q(t)ut其中,uR。则有(IkG)Xk(1)Q(G) I uG，而 Q(0)利用这些，可知f(Xk 1) f(lkG)xJf(Q)Xk),(要求 U 0 )Q(0)令Xk对 Q(t)事实上,2(鵲 xkgQGh)2,L , n是G的特征值，而Ui（i2Q2(0)(Q(G)xk)TG(Q(G)xk)1,L , n）是对

5、应得标准特征向量 （两两正交的单位向量）。a（k）ui ,则上式可进一步表示为:n2Q2(0)(i1a(k)Q(G)Ui)TG(na(k)Q(G)Uj)j 1n硕(i1a Q(n詁0)(严(122Q2(0) in2a(k)1ut ,可适当选取只须令Q( 1) 1Q( n)1i)Ui)TG(a(k)Q( j)Uj)1（将G作用到内每一项）即可求得从而Q(t)显然Q（t）单调上升。f (Xkni)Ui)T(a(k)Q(j 12Q ( i) i,U，使 Q(1 n,U1 n2t 1由 Q( 1) 1,Q(1)1,Q(j)n)jUj)（由ui是标准正交向量组）n)2丄，n ,即得Q( i)1,L ,

6、n)。ak) 2Q2(i) i22Q (0) i 1i a(k)2nn1 /(k). T(k)f(xk)(ai Ui) G( aj Uj)2 i 1j 1n(k)、T1 、.、，.(ai Ui)(2 i 1n(k)、ajjUj)j 1a(k) 2 i即得f(Xk 1)f (Xk)2Q (0)再由最后得Q2(0)f(Xk 1)f (Xk)k 0.由0 -一- 1,并注意到f(x)是正定二次函数(f(x) 0),则有f(xk)0 (k )。1 n再由f (X)为严格凸二次函数(正定二次型)，故当且仅当X 0时，f(X)0,由此可推得必有Xk 0再注意到f(x)0,则有f(Xk 1)f(x )f(X

7、k 1)f(Xk) f (X*)f (Xk)从而定理第一式得证。由G是对称正定的，故有T nQ ekejGekT1ek Q*T _T.2f(Xk)由X 0，则ek GekXk GXk故有T nQ ek2f(Xk)T16 ekF面再证定理第二式，记ekXk21 n注意到:f (Xk 1)f (Xk)因而有xx*2Tf (xk 1 )2Xk 1 xek 1 ek 1n11n1nn 1 nf (Xk)1* 2Xk X最后得Xk 1Xxk x-(1)(1)(其中这表明：最速下降算法至少具有线性收敛速度1和n分别为其最大和最小特征值，则定理3.5 (Kantorovich不等式)设G是n阶对称正定矩阵,

8、Rn，有(xTx)2TT 1(x Gx)(x G x)证明：参见袁亚湘等最优化理论与方法第三章附录，略。1以上对特殊形式的二次函数f (x) - xT Gx的收敛速度进行讨论，对一般的二次函数f (x)- xT Gx bT x2利用Kantorovich不等式可得类似的结论，其证明思路如下：设x是极小点，则x满足Gx* b 01 1且 f (x)可表示为f(x)(xx )TG(xx )x TGx1* t*记E(x)(xx ) G(xx)，则E(x)与f (x)仅相差一个常数，它们有相同的最优解，且使用最速下降算法时，每次迭代方向产生的迭代序列均完全相同。现在考察对E(x)的极小化，这时最速下降

9、算法的迭代公式为:Tgkgk gkgkGgkT(这里k -业为最优步长因子)gkGgk其中gk GXk b。直接计算可得:E(xQ E(Xk J(gb)2E(Xk)TT 1(gkGgk)(gkG gk)41 n 2 (由 Kantorovich 不等式) (1 n)2(2)E(xJ 0 (或 E(xJ由(1)有:注意到：故有：2E(XkJ1( 4 1 n)2E(Xk)1nE(Xk)( 1)(1n)1n由(1)即得:E(x*)。由G正定，当且仅当x x*时,I* T*E(x) (x x )TG(x x )02利用E(x) 一致凸性，可证必有：Xk X。这表明：算法产生的点列 Xk是整体收敛到X的

10、。* 2f(Xk 1) f (x ) E(Xk 1)1 n*f (Xk) f (x ) E(Xk)1 nf (x ) x TGx 0，222由（2）有f (Xk 1)f (Xk)11 n*、f (X)1n1n2-n f(Xk)（3）1n*再令ekXkx （ k），则GekT注意到QGek2E(xQ即有:XkX2E(Xk)iXk从而有:X*2Xk 1* 2XkX2E(Xk 1)nE(Xk)1iE(Xk JnE(Xk),(令最后得：llxk xj 口 1），定理证毕。Xk收敛于X*，则收敛当目标函数为非二次函数时，最速下降算法的收敛速度依然是线性的。定理3.6 设f （X）满足定理2.8的假设条件

11、，若最速下降算法产生的点列速度至少是线性的。 3.2 牛顿法一、牛顿算法的基本思路牛顿算法的基本思路是：利用目标函数在当前迭代点Xk处的二次近似的极小点作为f（x）的近2似极小点。设Xk是当前迭代点，f（Xk）正定，则f(x)f (Xk)f (Xk)T (XXk)：(x Xk)T 2f (Xk)(X Xk)2记q（k）（s）f (Xk)f (Xk)Ts1 s2T 2f (Xk)s，其中 s X Xk，极小化q（k）（s）得Sk(2f(Xk)1 f(Xk)Gk1gk进而得牛顿算法的迭代公式：Xk 1 Xk Gk1gk.关于牛顿算法的若干评注 牛顿算法可视为椭球范数 gG下的最速下降算法。事实上，

12、欧氏空间 Rn中一般范数|g下的方向导数定义为:(它显然与范数 g有关)sdf lim f (Xks) f(Xk)f(xJTs g：sds 叫T显然，min餐 的最优解就是函数f (x)在Xk处对应于范数II g的最速下降方向。容易理解，这个解 s Rn制与所取的范数有关。a)当取欧氏范数(2范数)时，可证Skgk是最速下降方向;b)若取椭球范数 gGk，最速下降方向则为 sk1Gk gk。事实上,TgksgkAGs(Ggk,s)GkGk1gk GksGkGk1gksksGk|s|GksGkGkTs Rn，有 gkss|GkGk1gk(意味着Gk1gk厂为方向导数下界)Gk另一方面，若取s1G

13、k gk 时gk s _gkGk_gk sL sgsGks(Gk1gk)TGk( GGk1gkGk方向导数达到下界Gklk G，故sk Ggk是对于椭球范数gG的最速下降方向。k 牛顿算法实际上就是非线性方程组的牛顿迭代法。由于min f (x)等价于求解非线性方程组X Rnf (X)0设Xk是当前迭代点，若f(Xk) 0,则Xk是方程组的解，否则将f (X)在Xk处线性化，得f (X)f (Xk)2 f (Xk)(X Xk) 0将上述线性方程组的解作为f (x)0的近似解，得2 1x xkf (xk) f (xk)故有xk 1 Xk2 f (xk) 1 f (xk)，这恰好就是牛顿迭代公式。

14、二、牛顿法的收敛性定理3.7 设f C，xk充分靠近极小点X,而f(x) 0，2f(x )正定，若进一步假设Hessian矩阵G(x)满足Lipschitz条件。则由牛顿法产生的序列xk收敛于x*，且具有二阶的收敛速度。证明：由 g(x*) g(Xk)1dg(xk(xxk)d1 * *G(Xk(x* Xk)(Xk x*)d0d0及G(x)满足Lipschitz条件，可得* * 1g(x*) g(xk) G(Xk)(x* Xk)0G(Xk(X* Xk) G(Xk)(Xk x*)dg(Xk) G(Xk)(x* Xk) o(x*Xk21)故有0 g(Xk) G(Xk)(Xk X*) o( Xk X*

15、2)(*)由于f C，G*2f (x*)正定，故当xk充分靠近x*时，Gk正定，且Gk1有上界。事实上，设1(k),L , nk)是Gk的特征值，且1最大，nk)最小，则Gk1的特征值为7k) ,L , (k?，且 | Gkn11(k)，Gk1殆(这里矩阵范数取谱范数)。又特征值是特征多项式系n数的连续函数(参见蒋尔雄线性代数P39定理10)，故当时，存在m, M使得n(G(x)1(G(x)M，(相当于特征值一致有界)因而当xk x*n(Gk)佝)M(这里n(Gk ) 1 (Gk )分别表示Gk的最小、最大特征值)。由以上分析及(*)式，则有20 Gk1gk (Xk X*) 0( Xk x*

16、)*I*2Xk 1 X 0( Xk X )02 Xk 1X* c Xk X*(* )只要c Xkx* r1,则有Xk 1 x*0 ,即XkX*，迭代点列收敛，且由(*)式知，算法具有二阶收敛的速度。关于算法的评价1) 优点：当初始点 Xo离最优解X*很近时，收敛速度快；算法简单；不需要用一维搜索。2) 缺点：局部收敛，Gk不正定时，不能保证牛顿方向是下降方向。事实上，当Gk为正定时，牛顿1tT 1方向SkGk gk满足：gkSgkGk gk 0 (下降方向)，但若Gk非正定，则不能保证 Sk是下降方向。由以上分析可知，固定的步长因子不能保证目标函数有合理的改善，甚至不能保证算法下降，因此有必要

17、对牛顿算法作一些改进，一个最直接的改进是：在牛顿算法中加入一维搜索。三、带步长因子的牛顿法一一阻尼牛顿法1 算法1 )取初始点X0 R，允许误差0，置k : 0 ；2) 计算gk，若|gk ，停止迭代，X*Xk ；否则go to 3);3) 构造牛顿方向：从 Gkd gk求出dk ；4) 沿dk进行一维搜索，使得k满足：f(Xkkdk) minf(Xkdj ；05) 令 Xk 1 Xkkdk , k : k 1 转 2)。2.总体收敛性定理3.8 设f : RnR二阶连续可微，且对任意的X0 Rn，存在常数m 0，使得f(x)在水平集 L(X0)x f (x) f (X0)上满足，uk 2 f

18、 (x)u m u2 , u Rn , x L(x)Xk满足:则在精确一维搜索条件下，带步长因子的牛顿法产生的迭代点列1)当Xk为有穷点列时，对某个k，有gk 0 ；2)当Xk为无穷点列时，Xk收敛到f的唯一极小点证明：由定理条件知，f (x)在L(Xo)上一致凸。故f (x)在L(Xo)中若有极小点，则必唯一，且f(x)在L(x。)中的稳定点必是f(x)的极小点。下证 xk收敛到f(x)的稳定点。由f (X)在L(Xo)上一致凸，知L(Xo)是有界闭凸集，再由f (Xk)单调下降,可知XkL(xo)，故xk是有界点列，于是存在极限点X L(Xo)及子列xk Ki使limXkx.k ,k Ki

19、再由f(xk)单调有界(有界性是由于：L(Xo)闭有界，且f (x)在L(Xo)上连续)可知:kim f (Xk) f (X)(这里是指整个序列)叽f(Xk)f(X)(这里是子序列)由精确一维搜索的极小化算法的收敛定理2.7，有从而f (Xk) gk(整个序列)(*)lim f (Xk)kf(X)即x是f (X)的稳定点，它也是极小点。现在实际上还只证明了Xk的子序列xk K收敛到X，下证xk整体收敛到K1X。事实上，若XkXkX Io ( kK2，o是给定的正数)注意到xk 是有界点列，故存在收敛子列Xk K3(K3 K2)，使limXk?L(Xo)(由L(xo)闭有界)k,kK3从而lim

20、k Kqf (Xk)f(X)Xk K2 使由(*)式进一步得不收敛到X，则存在一个子序列f(Xk)f (?) 0从而X也是f (x)的平稳点，也是极小点，但显然 X X，这与f (x)的极小点唯一矛盾,Xk故必有在上面证明过程中，直接引用了精确一维搜索的极小化算法的收敛定理2.7，因此必须指出定理2.7的条件是满足的。事实上，1)2)由L(x0)有界闭，故f (x)在L(x0)上一致连续，且 G(x)m dkP2M,(x L(xo)；由 COS kg：dkd：Gkdkdbdk得：kIlgJIlldkll.m arcs in Mgk dkGkdJ|dkM dk 3.3 修正的牛顿法上面带步长因子

21、的牛顿法实际上还不能克服牛顿算法的全部缺陷，因为还有可能出现：1) Gk1不存在；2)Gk不正定，故dkGk1gk可能不是下降方向。为此人们对牛顿法提出了多种方式的修改。一、Goldstein Price 修正方案当Gk非正定时，采用最速下降方向gk替代牛顿方向。若进一步将搜索方向与负梯度方向的角度准则结合起来，则有dN 若cos(dN, gj(这里 d,Gk1gk)dkgk否则这样搜索方向dk总满足cos：dk, gk 注：按照这种方法选取搜索方向，再加上一维搜索(精确或非精确)可以保证算法的总体收敛性，但也可能失去牛顿法快速收敛的特点。二、Goldfeld修正方案若Gk不正定，则用Gk G

22、k VkI来修正Gk。通过适当选取Vk 0 ,可以使Gk正定。事实上,只要将Vk取得稍大于Gk的最小特征值的模即可。利用特征值的圆盘定理可以求得最小特征值的模:minimiinn (Gk)ii(Gjj i注：用此方法可求出Vk，但通常得到的Vk远大于最小特征值的模，导致 Gk与Gk相差甚远，这是个缺陷。而实际求出 Gk的全部特征值计算量又太大，因此，这个方法更多的是理论的价值。三、基于Gk的Cholesky分解的方案先作Gk的Cholesky分解GkLDLt然后令Gk LDLt，其中 D diag (dii,L ,dnn)而& max dii ,，dii为D中对角元，为给定的小正数。注：这种处

23、理方法简单，但有下列缺陷:1）当Gk不可逆或Gk的主子式为零时，Gk的Cholesky分解不存在（分解过程将进行不下去）。如GkCholesky分解不存在。2）即使Gk的分解存在，其计算过程也可能数值不稳定。如当 0时，l与d均无界，计算过程中小的误差会导致结果的巨大差别。因而数值不稳定，同时还可能出现Gk与Gk的差别很大。如112Gk1110 203231Gk的Cholesky分解为100100L110 ， D010 20021020100(3 1020)由di, max山,的处理方式得100D010 2000031020可见D与D (从而Gk与Gk)相差甚远。四、Gill和Murray修正

24、方案Gill Murray修正法也称为强迫矩阵正定的Cholesky分解法，它在Gk的分解过程中进行适当修正，使*总为正，从而分解过程可以持续下去，但最终得到的分解式LDkL不是真正的Gk，而是Gk的近似Gk。其要点在于：1) 在分解过程中，增加了保证分解得到的因子矩阵元素一致有界的措施。在过程完成时，得到：TGk LDLGk E (其中E是非负对角阵)2) 在整个计算过程中，为了保证dii及因子矩阵元素一致有界，必须对 Gk的元素进行调整，否则算法进行不下去，但必须指出的是，所有调整都只涉及Gk的对角元(通常是将其增大)，这就保证了：Gk Gk E，即Gk与Gk仅差一个对角阵。3) 可以证明

25、，当Gk充分正定时，有 Gk Gk。可参阅席少霖著非线性最优化P80,或徐成贤等 著近代优化方法 P62。定理3.9 设f(x)在Rn上二阶连续可微，且存在X。使L(x)x f(x)f(X0)为有界闭凸集，若初始点 论 L(x0)，则由Gill Murray修正牛顿法产生的点列xk满足：1) 若xk是有限点列时，它的最后一个点必为f (x)的平稳点；2) 若xk是无穷点列时，它必有聚点，且任一聚点均为f(x)的平稳点。证明：参阅邓乃扬著无约束最优化计算方法注：一般.用到的Gill Murray修改牛顿法除了强迫正定的Cholesky分解法外，在鞍点处还用到负曲率方向，因而它是一个对牛顿法改造的

26、最彻底、最具有实用价值的方法。 3.4 负曲率方向法一、负曲率方向负曲率方向法是修正牛顿法的又一种形式。当2f(xk)不正定时，利用负曲率方向可找到下降方向，尤其在鞍点处，即：2f (Xk) 0,而f(Xk)不是半正定时(当然也不是正定的)此时若采用负曲率方向作为搜索方向，可以使目标函数下降。定义3.10 设f (X)在开集D上二阶连续可微,1)2)若2f (x)至少有一个负特征值，则 x D称为不定点;设x是一个不定点，若方向 d满足：dT 2 f (x)d 0，则称d为f (x)在x处的负曲率方向;(若d是负曲率方向，显然d也是)3)如果 sT f (x)0，dT f (x)T 20， d

27、 f(x)d0,则称向量对 s,d为不定点x处的下降对;若x不是一个不定点,则称满足:sT f (x)0dT f (x)0，dT 2f(x)d0的向量对(s, d)为点X处的下降对。下降对的例子令 s f (x)，sign(uT f (x)u若 2f (x)0否则其中u是对应于 2 f (x)的负特征值的特征向量。注：1)由定义可见：当且仅当f(x) 0，2f(x) 0时，x处不存在下降对。因此，一旦在该点不存在下降对，那么该点必满足极小点的二阶必要条件(但仍不一定是极小点)。2)若x是鞍点，则负曲率方向必为下降方向。事实上，设 d为负曲率方向，由f(x*d) f(x*)f(x*)T d 2

28、2dT 2f(x*)d( d)容易看出：当很小时，f (x d) f (x )。3）若x为一般点，且负曲率方向d满足dT f（x） 0,则d与 d均为下降方向。4 ）若dT f （x）0,则d是下降方向；若dT f （x）0,贝U d是下降方向。由上述分析,一旦找到负曲率方向,则总存在一个下降方向。而唯一难找到下降方向的情形是：f （ x） 0 且 2 f （ x） 0 时。二、 Gill-Murray 稳定牛顿法基本思想：将修改 Cholesky分解与负曲率方向相结合。当Gk不正定时，采用修改 Cholesky分解强迫矩阵正定；而当 gk0 时,采用负曲率方向使函数值下降。1） 负曲率方向的

29、求法（与修改的Cholesky 分解相联系,计算相对容易）2）Gill-Murray 稳定牛顿法算法步骤（参阅袁亚湘等著最优化理论与方法 ）。3） 收敛性定理（证明参阅邓乃扬著无约束最优化计算方法）。三、 Fiacco-Mccormick 方法Fiacco-Mccormick 是最早利用负曲率方向修正牛顿法的学者,他们利用精确一维搜索以及Cholesky 分解 Gk LDLT。11） 当 Gk 正定时,产生下降方向dkGk gk （牛顿方向） ；2） 当 Gk 不定时,通过求解 LTt,其中1 dii 0获得 t ,然后令0 dii 0t gkTt 0,dkT,t gk Tt 0得负曲率方向

30、dk （也是下降方向） 。该方法的主要缺陷是：Gk LDL T 可能存在数值不稳定,甚至分解不存在。四、二阶 Armijo 步长准则 Mccormick 方法设Xk是当前迭代点，(Sk,dk)是下降方向对，迭代格式为:Xk 1 Xk i( )Sk 2( )dk这不是沿一个方向进行线搜索，也不是S,与dk的组合方向，而是一种曲线搜索策略。算法终止：不存在下降方向对时，算法终止。此时，意味着f (Xk)20 且f (Xk)0，故 Xk是一个满足二阶必要条件的点。右产生无穷点列xk，则在对下降方向对(Sk,dk)附加较强条件时，算法总体收敛。在该方法中使用的非精确步长准则实际上属于简单步长准则，但不

31、是Armijo 一阶准则，而是Armijo二阶步长准则。令iyk(i)XkSk2 idk2 2求i。，它是使下式满足的最小整数。令5仏)f (Xk)2iSkT f (Xk)2f (Xk)dkXk 1 yk(i)XkSk2i0 2dk 2。五、二阶 Armijo 步长准则 一Goldfarb 方法设Xk是当前迭代点，(Sk,dk)是Xk处的下降方向对。令2x( ) XkSkdk,(0,1)这实际上是Mccormick方法的一种特殊形式。仍然采用Armijo简单步长准则，选择最小的正整数i,使得1 .f (Xk( i) f(Xk)( iSkgk 1 4idkTGkdk),(0,1)其中， 与是预先

32、给定的常数。六、二阶 Wolfe-Powell 步长准则一More-Sorensen 方法形式：x( ) x2sd。采用非精确搜索确定步长，步长准则采用 Wolfe-Powell准则的推广形式，即所谓二阶 Wolfe-Powell准则。关于上述内容的详细讨论可参阅袁亚湘等著最优化理论与方法的相应章节。 3.6 信赖域方法一、信赖域算法1 牛顿法的基本思想在当前迭代点 xk附近用二次函数q(k)(s)f (Xk)gkTssTGkS,(s x Xk)逼近f (x)，并以q(k)(s)地极小点Sk修正Xk，得Xk !XkSk。如果不限定s的范围，实际上是用 q(k)(s)在全空间逼近f (X)，而用

33、q(k)(s)的极小点代替f(X)地极小点。容易理解，这样得到的迭代点Xk !往往不能使f (X)有较大的改进，有时不仅不能得到改进，反而变得更糟。2 信赖域方法的基本思想信赖域方法是上世纪 70年代提出的一种重要的优化方法，它针对上面提及的牛顿方法的缺陷，在子问题中，明确要求 X必须位于当前迭代点Xk的邻域(信赖域)内。在算法每次迭代中，求解下述信赖域子问题：minq(k)(s) f (xj gjssts n注：1)由于从信赖域子问题求出的Sk必须满足skhk，故称为有限步长方法；2) 范数没有特别限制，可根据需要随意选取，但多数情形用g2或g两种范数；3) Gk可用有限差分近似，也可用后面

34、即将介绍的拟牛顿方法构造其近似。在信赖域算法中，信赖域半径hk采用自适应方式调整，若 q(k)(s)与f(xk s)近似程度好，则hk尽可能取大，否则将其缩小。而通常采用下述方式评价q(k)(s)与f (xk s)的逼近程度：在算法迭代的第k步，定义fk f (Xk) f (Xk sk)称实际下降量q(k) f (Xk) q(sQ称预估下降量定义比值:| kq(k)rk越接近1，表明近似程度好，应加大 hk，否则相反。3.信赖域算法（算法模式）1)初始步：给出初始点X。，令hogo2)第k步：10给出Xk和hk，计算gk和Gk20解信赖域模型（子问题），求出Sk30求f (Xk Sk)和rk的

35、值40 如果 rk 0.25，令 hki（缩减信赖域半径）如果 rk 0.75 且 |Skhk，令 hk2hk（增大信赖域半径）否则，置hk 1 hk（信赖域半径不变）sk 求出的试探步最后是否移动，取决rk是否rk(0) 50 若 rk0 ,置 Xk 1Xk;否则置 Xk 1 Xk注：求解信赖域子问题得到的 sk称为试探步。由50可见,大于0在有些信赖域算法中，将50中的rk 0替换成了二、信赖域算法的收敛性定理3.11设B是Rn中的一个有界集，信赖域算法产生的点列XkB。若进一步假设f C2且在B上满足：|G（x） M （M 0）。则Xk存在一个满足一阶和二阶必要条件的聚点x 证明：由算法

36、分析可知，算法产生的点列必存在一个子序列，要么满足：1）rk0.25 ,hk 10（因而 |sj| 0）;要么满足2）rk0.25 ,glb（hj0 （glb（hj表示相应子列hk的下确界）。设x是这样子序列的任一聚点，并设xk K X，下面证明X就是满足定理要求的点。a）若此序列满足条件 1）用反证法，设g f （x ）0，对Xk K中的任何Xk，考虑该点的最速下降方向，有q(k)(告)f(Xk)|gk|(k)gk2gk Gkgkgk1) 当 gkTGkgk 0时，注意到Sk|gk是信赖域子问题的可行解，因而有gk注意到k从而有故有(k)q(k)k q且k K时,2 M 2gkl2)当 gk

37、TGkgk0 时，由故当k(Sk)fk q(k)(Sk21|Sk| gkTGkgkgk2-（*）2|s.|2m1|s|gk|(2（*）式仍然有:Sk gk1 Sk 2II gkgk且k K时（此时| sj0）,Sk2再由Taylor展开式进而得:这与k K时,sjgk(k)qkq(k)0.25矛盾，从而有0 (由 gk(Sk2)0 （即一阶必要条件满足）再证G G（x ）半正定。若不然，设是G的最小特征值，则0 设其对应的单位特征向量为v ,且满足vTgk 0 （否则可取 v） o显然Sk v是信赖域子问题的可行解，故q（k）(k)fkq(k)(Sk) fk q(k)( Sk v)Sk vTg

38、k2 Sk PGkV从而有(闻Iq（k）(叮)1 SkGkV0 (注意 vTGkV vTG v vT v )1,又与rk0.25矛盾。从而G是半正定的，即x满足极小点的一阶和二阶必要条件。再由 Taylor 公式，fkq(k)( Sk 2)得到 b）若子序列是第二种情形注意到下降算法的特点，有f1ffkk K0.25q(k)k K故级数收敛。因而qk0（* ）对应于x ，定义qsfsTg2金并设h满足0h129呱）又设S是下述信赖域子问题min q(S)s.tSh的解。注意到k,k K时，XkX，因而X Xs满足xXkhk（k）。从而(k),q(xXk)q(k)6)fk(k) q()取k，注意

39、xXkxsXks，以及fkf ,gkg ,GkG ，因而有q(S)fq (0)。（由（*）式，q（k）0）这说明S 0也是min q (s)s.t s h的最优解。注意到 h 0,此时约束不起作用。因而 s 0相当于无约束问题min q （s）2的极值。因而有q （0） 0， q （0）半正定，由此即知g 0，G半正定。即在x处满足一、二阶必要条件。定理证毕。关于定理3.11中两类子序列必出现一类的补充证明设算法产生的点列为xk，相应的有序列rk与h 。1） 若k充分大时，均有rk 0.25，则显然存在满足第一类条件的子列；2） 若k充分大时，均有rk 0.25，则显然存在满足第二类条件的子列

40、；因而下面仅考虑rk 0.25与rk 0.25总是相间出现的情形。这种情形下，必存在一个子序列Xk k K，当k 心时，有rk 0.25 （这里心可取为使rk 0.25成立的指标的全体）。若k 心时，glb（hQ不大于零，则存在 h K的一个子列 心，心 &使得lim hi 0 。k心k再从hk心中如下构造子列：先选出 hk心的首项，设为h% ;由于rk 0.25与rk 0.25总是相间 出现。故必有k &，使rk 0.25，又一定有k2K2使得k2k，对应得到hk2，仿此得到R心的一个子序列 入心。hk心显然具有如下特点：1）k K3，有 rk 0.25 且 lim hk 0 ；2） hk

41、K中任两个相邻项之间，必定存在一个指标k，使rk 0.25。3设hk1与hk2是hk心中相邻两项。K, k2是两项对应的下标。 设k是从k2出发回溯得到的第一个使rk 0.25的下标，由信赖域半径的自适应调整规则，显然有hk1 hk2（见下图），图中箭头表示hk的升降趋势。0.25由hk 1hk2及lim hk0，立即可得hk 10。这恰好表明由这样的k K3k构成的子列满足:0.25 且 lim hk 10即若k K1时，glb(hk)不大于零，则可构造出一个子序列使得rk0.25且lim hk i 0。这正好是第一种情形，故两种情形至少会出现一种。若进一步加上较强的条件，可得到信赖域算法的

42、二阶收敛结果。定理3.11若进一步假定在定理 3.10中的聚点x处，有G 正定，那么算法产生的序列 xk整体有：rk1,Xkx ,glb(hk) 0，对充分大的k，总有Skhk ；并且收敛速度是二阶的。证明：假设算法产生的子序列 xkx属于第一种情形，即0.25, hk 10 ( Sk0) (kKi)考虑牛顿方向dkGk 1gk。由G正定，因此当k充分大时，dk有定义且为下降方向。1)若dk，则sk dk (即牛顿步为信赖域子问题的最优解)q(k)(k)T1 Tk q(sk )gk sk sk Gksk2T 1 T1 T1Sk(GkSj skSk GkSkQ GkSkk2 2 2其中,k是Gk

43、的最小特征值。2)若dkdk是信赖域子问题的可行解。dkq(k)fkq(k)(Sk)fk q气sj倍)SkdkgklldklldkTGkdkdkSk|2 dkTGkdkdk2 dkTGkdkdk21| dkTGkdk2阁丽r12剛kiid（由 shkdk ）（k是Gk的最小特征值）综合1）与2）可知，在任何情况下，都有(k)2又由fkq(k)o(Sk )吩1 q(。（闾2）(k)q(（*）故而对整个序列有Xk X。注意到:Xk 1Xk 0这与rk 0.25矛盾，从而子序列不属于第一种情形，而属于第二种情形。故k K1, glb（hj 0（注：到现在为止，结论还仅限于子序列）若对子序列中的某个充

44、分大的k，有1Xk xmin2glb（hk）, 0这里0由牛顿收敛定理中要求初始点Xk充分靠近X的条件：人 X0所确定。注意到牛顿法由于Xk 1XkGk gk满足Xk 1X|xk x |（由牛顿收敛定理的证明）而且由Xk 1Xk|xk 1 xXkx Ihk收敛定理的条件现在全部满足，xk为初始点。知xk 1在信赖域Qk中，因而此时信赖域算法蜕变为牛顿算法。k充分大时，始终有 hk单调增，故有及（*）式知rk1。由信赖域半径的自适应调整规则，当glb（hQ 0（注意这里是对整个序列，而不仅指子序列）。而且k充分大时，总有 shk。此时，信赖域算法完全蜕变为牛顿算法，故有二阶收敛速度。注：这个定理

45、的证明过程知，信赖域算法在迭代后期，将自动转化为牛顿算法，因而具有二阶收敛 速度；而在算法的开始阶段，对初始点无特殊要求，因而具有全局收敛性质。三、关于信赖域子问题最优解的条件在下面的讨论中，均采用|2范数。定理3.12 考虑二次函数qg fk g：s sTGkS其中Gk为n n对称矩阵。则(1) qk(s)有极小点当且仅当Gk为半正定，且gk属于矩阵Gk的值空间，即gk GkS|s Rn；(2) qk(s)有惟一极小点当且仅当 Gk正定；(3)若Gk为半正定，则方程 GkSgk的每个解均为q/s)的全局极小点。证明：(1)假定Gk为半正定，且gk属于Gk的值空间。即存在s Rn，使得gk则有

46、GkSGkSgk。显然，w Rnqk(sw)qk(s*)*t1 tGs gk) w qwGkW故s是qk(s)的(全局)qk(s ) GkSqk(s)1 t*尹 GkW qk(s )(*)极小点。反之若s是qk(s)的极小点，则满足极小点的二阶必要条件:2 *gk 0,且 qk(s ) Gk半正定，(1)得证。(2)注意到：当且仅当 Gk正定时，(*)对一切w 0,成为严格不等式。故qk(s)有惟一极小点当且仅当Gk正定。(3再注意到(*)当Gk? gk 0及Gk半正定时总成立，故当？满足Gk?gk时，也是qk s的极小点。定理3.13 考虑信赖域问题:min qk (s)kgkTs sTGk

47、Sst | sihk(1)*n则s R为该问题解的充要条件是hk，且存在v 0,使得:(Gk v*l)s*gk , v*(hk |s* ) 0,且Gk v*l半正定。证明：充分性：设有s | hk及v 0，使得(Gk v*l)s*gk, v*(hk s* ) 0,且GkvI半正定。由前一定理，可知s是二次函数qoTk gk ssT (Gk v2l)s的极小点。因此，对一切sRn，有从而有qg(?k(s*)Tk gk sT gk s*T* v *t *Gks (s s2sT s)(2)v (hks* ) 0v*(h；0,由（2）知，当shk时，有Qk(s)qk(s )。为信赖域问题的解，充分性得证;必要性：设S是（1）的解,hk，则s是qk（s）的无约束极小,故Gk半正定。取v 0，即知s满足所有条件;(b)若 sh,，则s也是等式约束问题mi nq k(s) fk gjs1 Ts Gs2s.tsT s的解。因此，由条件极值的拉格朗日乘子法，存在v，使得Lagrange 函数v T 2L(s) qk(s)2(ss 九)的梯度在s处为0，即:(3)L(s