最优化理论与算法

1、第五章拟牛顿法§拟牛顿法牛顿法具有收敛速度快的优点，但需要计算Hesse矩阵的逆，计算量大。本章介绍的拟牛顿法将用较简单的方式得到 Hesse矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速 度，这类算法是无约束最优化问题最重要的求解方法。一、拟牛顿条件设f(x)在Rn上二次可微，为了获得Hesse矩阵G(x) 2f(x)在xk 1处的近似，先研究如下 问题。考虑f (x)在xk 1附近的二次近似：1f (x) f(Xki) gT i(x Xk 1)-(x Xki)TGki(x Xki).两边求导，有 g(x) gk 1 Gk i(x Xk 1)令 x Xk，有 gk g

2、k 1 Gk 1 (Xk Xk J再令 Sk Xk 1 Xk，yk gk 1 gk则有yk Gk何或 Gk 1yk sk.因此，我们要求构造出的Hesse矩阵的近似Bk 1或Hesse矩阵逆的近似 Hk “应分别满足：Bk 1 skyk 或 H k 1 yk sk()它们均称之为拟牛顿条件。二、一般拟牛顿算法1) 给出初始点 x0 R， H0 I，0，k: 0.2) 若gk ，停止；否则，计算 dkHkgk (拟牛顿方向)3) 沿方向dk进行线性搜索，k 0 (可以是精确，也可非精确)令xk 1 xkkdk.4) 校正Hk产生Hk，使拟牛顿条件满足5) k: k 1，转 2)拟牛顿法较之牛顿法

3、有下述优点1) 仅需梯度(牛顿法需 Hesse矩阵)；2) H k保持正定，因而方向具有下降性质(而牛顿法中Gk可能不定)；3) 母次迭代需 0(n2) 次运算，而牛顿法需 0(n3)次运算。注：正如牛顿法中牛顿方向Gk1gk是在椭球范数"|Gk下的最速下降方向一样，Hkgk也可看成是在椭球范数 |Hj下的最速下降方向，也就是在空间某种特定度量(尺度)意义下的最速下降方向。由于每次迭代 Hk都在变化，因而度量(尺度)也在变化。正因为如此，常称拟牛顿算法为变尺度 法。从这个意义上讲，牛顿法本身也是变尺度法。三、对称秩一校正公式(SRI校正)设Hk是第k次迭代的Hesse逆的近似，希望对

4、 Hk校正得到Hk，即若设Ek是一个秩一矩阵，则 Hk1 Hk uvT .(5.2 )由拟牛顿条件：Hkk Hkyk u(vTyk) sk得 u % 丿小 (取 V，使 vTyk 0) (5.3)v Yk1将(5.3 )代入(5.2 )得 Hk1 Hk -(sk HkYk)vT (5.4)V Yk称之为一般Broyden秩一校正公式特别地，取v yk时，称为Broyden 秩一校正公式。一般地，上述 Hk1不对称，由于 Hesse矩阵是对称的，故希望Hk 1也对称，因而取从而得 Hk1 Hk (sk Hkyk)(sk THkyk)(5.5 )k(sk HkyQTykn 1步终止,称之为对称秩一

5、校正。对称秩一校正法在用于正定二次函数时，不需要进行一维搜索，具有有限终 止性质。定理5.1设s0,S,-，Sn1线性无关，那么对于正定二次函数，对称秩一校正方法至多即H n G证明：首先用归纳法证明拟牛顿条件的遗传性质，即H i yj Sj j 0,1,，i 1。当i 1时，直接由（5.5 ）可知结论成立。若假定结论对i 1成立，现考虑i 1情形，此时1 ）当j i时，由归纳法假设，有故当j i时，Hi必 HyjSj。2 ）当j i时，直接由（5.5）可得。再根据以上所得遗传性质，有H nyj Sj，HnGSj Sj （ j 0,1，i 1）由Sj线性无关，故有HnG I，即Hn G 1。注

6、：1）证明中对S除了要求线性无关外，没有其他条件，因而简单取SiHigi也是可以的。这样完全不用一维搜索，并且由&HngnG 1gn，得到最优解。2）SRI校正的缺点是不能保证 Hk的正定性，除非始终保持 （Sk Hkyk）Tyk 0。当用于一般 函数时，由dkHkgk算出的搜索方向不能保证是下降方向，这在一定程度上妨碍了它的应用。四、DFP校正考虑对称秩二校正由 H k 1ykSk得 fyk auuT yk bvvT y Sk取 u Sk，v Hkyk即有 auTyk 1，bvT yk1 得校正公式：Hki Hk竺H学ykHk （ 5.6）a 亠亠，bu YkSkYk1Tv yk1y

7、k Hk ykSkykyHyk称之为DFP公式（由Davidon,Fletcher,Powell 提出）。DFP公式是最重要的拟牛顿校正公式，有 很多重要性质。对于正定二次函数（若采用精确一维搜索）1）具有有限终止性；2）拟牛顿条件具有遗传性质；3）当H。 I时，产生共轭方向和共轭梯度。对于一般函数4 ）校正保持正定性，因而算法具有下降性质;5）方法具有超线性收敛速度;6 ）当采用精确一维搜索时，对于凸函数，算法具有总体收敛性。定理5.2当且仅当£yk 0时，DFP校正公式保持正定性。H k正定，并记 H k的Cholesky证明：用归纳法。由初始选择， H。显然正定。设结论对 k成

8、立，即分解为Hk LLt。下面考虑k 1时的情形，设则 zTHkiZ zT(HkHkyky：Hky：Hkyk)z zTTSkSk z zSkykaTa(aTb)2bTb / T 2(SkZ)TSk yk由Cauchy不等式知:又由题设s：yk由于z 0，而时，便有z(aTb)2bTb0,故有(*)（*）中等式成立当且仅当a与b平行，亦即当且仅当z与yk平行。而当z与yk平行yk,0。此时注：上面定理中，条件 £yk 0是可以满足的。事实上，由 dk H kgk , Skkdk有Sk gk kdk gkkgkHkgk 0（ H k 正疋）而Sk ykSk（gk1 gk）Skgk 1 S

9、k gk。当采用精确一维搜索时，有gT 1sk 0 ,从而s：yk 0。而当采用非精确一维搜索（如Wolfe-Powell准则）时，只要适当提高搜索精度，就可使s：gk 1小到所要求的程度，从而有s：yk 0。定理（DFP方法的二次终止性）设 f（x）是二次正定函数，若采用精确一维搜索，那么DFP方法具有遗传性质和方向共轭性质，即对于i 0,1，m 1，有Hi iy j j 0,1，i（遗传性质）sTGsj 0， j 0,1，i 1（方向共轭性质）方法在m n 1步迭代后终止。若 m n 1，则Hn G 1。证明：对两组式子同时用归纳法证明。当i 0时，结论显然成立。设结论对i成立，现证明i

10、1时结论亦成立。注意到 gi 1 0,由精确一维搜索及归纳法假设，对于j i，有由 s 1 i 1di 1 i 1 H i 1 gi 1 及 GSj yj，得0,1，i这就证明了定理中的第一组式子。下证第二组式子，即H i 2yj sj，由DFP公式立即可得Tsi 1si 1 yjs1H i 1yi 1yi 1H i 1yjHijSj而对于j i，由yi 1 H i 1yi 1有Hi 2% Hi定理证毕。由此定理可知，DFP拟牛顿法是共轭方向法。若取 Ho I，则初始方向为负梯度方向，此时方 法变成共轭梯度法。DFP算法是一个在理论分析和实际应用中都起重要作用的算法。五、BFGS校正和PSB校

11、正我们知道拟牛顿条件有两个：Hk 1yk sk（Hesse 逆近似）Bk 1sk yk（ Hesse 近似）在上一段中，得到了关于Hk的DFP校正公式：（DFP）Hkykyk HkHk 1 Hk （5.7）SkykyHyk若在上式中实行代换：HkB.， skyk，即可得到关于Bk的校正公式TT（BFGS）ykykBkSkSkBkBk 1BkTT（ 5.8）ykSks< Bk&称之为 Bk 的 BFGS （ Broyden,Flecther,Goldforb,Shanno）校正公式。对上式应用秩一校正的求逆公式，又得到 Hk的BFGS校正公式:(BFGS)k 1Hk(1yk H k

12、 yk、SkSkTTsk ykSk yk(Sk H k yk)Sk Sk (SkTSk yk(IT響)比(|Sk ykTykSk、)Sk yk再将上式中H kBk ， Sk(DFP) k 1Bk(1BkSkylHk HkykHkyk)TTSkSkTSk yk()yk，得Bk的dfp公式TTSk BkSk)ykykyk Skyk SkykS：BkBkSky：TykSk(yk BkSk)yT yk(yk B.s.)tTyk Sk(a)6 Hkykyk(sWTSkSk (5.9b)(a)(yk BkSk)TSk(yg2Tykyk(5.10b)T(I芈)Bk(lYk SkTSkYkTYkSkTYkYk

13、TYk Sk(c)以上讨论告诉我们，对一个给定的拟牛顿校正公式Hk勺，通过交换Hk Bk , sk yk可得到关于Bk的对偶校正BkD1，再利用秩一求逆公式，又得 HkD1 （对偶校正）。而对HU再实施上述 对偶操作，还可恢复到原来的 Hk “。从这种观点看 H kBFGS）是HkDFP）的对偶校正公式。对SRI校正公式HkSRI） 进行交换后得：弟Bk 5（B：¥：）TB3（ 5-(SRI)k 1Hk(Sk HkYk)(Sk HkYk)T(skHkYk)T Yk(5.11)再利用秩一求逆公式，得 HkT的对偶仍为其自身，因而 SRI校正是自对偶的。BFGS校正是迄今为止最好的拟牛顿

14、公式，它不仅具有DFP校正所拥有的各种性质，而且当采用非精确一维搜索时，对于一般函数也具有总体收敛性，但这一结论对DFP校正尚未获得证明。Powell对一般的Broyden秩一校正公式采用对称化改造，得到了PSB公式。其基本思想是:在一般Broyden秩一校正公式的基础上，构造一个不断满足对称性和拟牛顿条件的矩阵序列，然后求出这个矩阵序列的极限，则该极限矩阵是一个满足对称性和拟牛顿条件的矩阵，从而产生出一个 校正公式。设B Rn n是对称矩阵，令C1 B，c s一般地， G不一定对称，因而将其对称化，令C2虽然对称，却不一定满足拟牛顿条件。因而重复以上过程，产生序列Ck:可证明这个矩阵序列是收

15、敛的，其极限为 加上下标，则得到一类秩二校正公式(yk BkSjc： Ck(yk BkSk)T(yk BkSjs：t、Bk 1 Bktt 2CkCk (5.13 )Ck Sk(ck Sk)这个校正类包括了很多的校正公式，在(5.13 )式中，若令则得到关于Bk的对称秩一校正公式(SR1公式)；若令Ckyk，则得到关于Bk的DFP校正公式;A1wk _右令Ckyk- BkSkwk 1wk 1其中Wk .,y：Sk s-B-E，则得到关于Bk的BFGS校正；若令Ck Sk，则得到PSB校正：(yk BkSk)s- Sk (yk B-s-)(yk B-sOs-tBk 1 BktT 2S-S- (5.

16、14 )s- Sk(Sk Sk)这个校正在理论研究和实际计算中是十分重要的，其缺点是不能保证校正矩阵的正定性。值得指出的是，通过交换 HkBk, yksk，可得到关于 Hk1的类似校正公式。前面介绍了一些拟牛顿校正公式，以及派生新的拟牛顿法校正公式的方法(如对偶方法，对称技术等)。有时候，还可利用一些特殊的附加条件推出校正公式。1 ) BFGS校正是由DFP校正公式经过替换与秩一矩阵求逆得到的校正公式。事实上对其它校正公式也可采用类似方法获得新的校正公式，这些新的派生公式称为原公式的对偶，对偶方法是产生 新校正公式的一种重要方法。若一个校正公式的对偶还等于其自身，则称之为自对偶。2 )将一般的

17、Broyden秩一校正公式反复采用对称化、应用秩一校正使其满足拟牛顿条件，生成一迭代序列，其极限构成一类新的秩一校正公式，而且很多常见的校正公式都含在这个类中，特别 地得到PSB校正公式。3 )有时我们得到的校正公式是一类，在这一类中通常需附加上另外的条件而得到具体的校正公式。这种附加条件有各种提法，若让Hk1 (或Bk 1)最靠近Hk (对应地Bk),由此种条件导出的校正公式称为最小改变割线校正，一些重要的校正公式在适当选取的范数下均具有这种性质。§5.2 Broyden 族上节讨论的DFP校正和BFGS校正都是对称秩二校正，且都是通过y- , s-, H-来获得校正矩阵Hk i。

18、下面考虑DFP与BFGS的加权组合:Hk1 （1 卅肿 HkT（是参数）为参数的一大类校正公式，称之为显然，这样得到的校正公式必满足拟牛顿条件。这就得到以Broyde n族校正公式。，容易看到Hk 1 H：TvM H k3f；GS (1)VkVk其中Vk1（仙朋亢朮。SkHkyk0时，得DFP校正;1时，得BFGS校正;TSk Vkk时，得SRI校正;(Sk Hkyk)T yk11 鼻(ykHkyk/skyQ时，得 Hoshino校正。类似地，有关于Bk的Broyden族校正:Bk 1BkDFP(1)BkBFGSBFGSBk 1TWkWkBDT(1)WkWj 6)1其中W皿汨盒skBkSkBk

19、Q注：由于vTyk0和wkX 0 ,也可以直接验证 Broyden族校正对任意的和都满足拟牛顿条件。Broyden 族的二次终止性和正定性（Broyden族校正二次终止性定理）设 f（x）是正定二次函数，G是其Hesse矩阵，那么当采用精确线性搜索时，Broyden 族校正具有遗传性质和方向共轭性质，即对于i 0,1，m 1，有:H i 1 yjSj，j 0,1，,i（遗传性质）sTGsj0，j 0,1，,i 1（方向共轭性质）方法在m n1步迭代后终止。若1m n 1，则 Hn G证明：证明与类似，略。（Broyden族校正的正定性）设参数0 ,当且仅当ST yk 0时，Broyden族校正

20、公式保持正定性。§ Huang 族Hua ng族是比Broyden族更广泛的一类校正公式。在Broyden族中，H k是对称的且满足拟牛顿条件Hk必 Sk。但在Hua ng族中取消了对 Hk对称的限制，并将拟牛顿条件进一步放松为Hk iykSk（ 5.17）称之为广义拟牛顿条件，其中是一个参数。为了使Hua ng族拟牛顿法用于二次正定函数时，所产生的搜索方向共轭，进而具有二次终止性。设Hua ng 族校正公式的形式为（详细分析可参见徐成贤等著近代优化方法或袁亚湘等著最优化理论与方法）:其中4 ,Vk满足：ukanSk 盹日',u：yka21Ska22H T yk，v在上面的方

21、程组中，含有三个自由参数。特别地，令1 ,a12 a21，则只含一个自由参数， 若取a11为自由参数，则有:Hk1HHkykyHk s：ykyHykTVkVk(5.18)其中Vk加曲或HkykT，正好蜕变为 Broyden 族校正公式，这表明 Broyden族是ykHkykHua ng族的子族。一般地,Hua ng族中含有三个自由参数，可产生丰富的校正公式。注：1）若采用精确一维搜索,对于正定二次函数， 所有Hua ng族变尺度算法产生相同的迭代点列;对一般函数产生的点列只依赖于2）另外，当极小化正定二次函数时，若取H0 I，贝U Hua ng 族校正公式产生的搜索方向与F-R共轭梯度法相同，

22、因而也是共轭方向法。§5.4拟牛顿法的局部收敛速度般拟牛顿算法超线性收敛的特征假设1: 1)设f(x)在开凸集DRn中二阶连续可微；2) f (x)存在一个严格局部极小点 x D，且 2f (x )正定；3) 存在x*的一个邻域N(x*,)，使得II 2f(x) 2f(x)|x x|, x, x N(x*,)。定理(不带步长因子的拟牛顿算法超线性收敛的充要条件)设f(x)满足假设1中的1 )与2)，又设Bk为一非奇异矩阵序列。假定对某x0 D，迭代序列恒在D中且Xk x*( k 0)，又设该序列收敛于 x*。则当且仅当时，序列兀超线性收敛到x*。定理(带步长因子的拟牛顿算法超线性收敛

23、的充要条件)设f (x)满足定理5.6中的假设，又设Bk为一非奇异矩阵序列。假定对某x D，迭代序列恒在D中且xk x*( k 0)，又设该序列收敛于 x*。如果成立，那么序列xk超线性收敛到x*且f (x*) 0的充要条件是 k收敛到1。注：1)要使算法超线性收敛，步长因子k必趋近于1 ；2 )拟牛顿算法超线性收敛的几何特征是：其位移Sk在长度与方向上都必趋近于牛顿方向£。定理(基于精确搜索的拟牛顿法的超线性收敛性)设 f (x)满足假设1中的1 )与2)，又设Bk为 一非奇异矩阵序列。假定对某x0 D，迭代序列恒在D中且Xk x*( k 0)，又设该序列收敛于 x*。k由精确线性

24、搜索产生，则当成立时，一定有k 1和f (x*) 0，从而序列x超线性收敛到x*。定理5.9 (基于 Wolfe-Powell准则的拟牛顿法的超线性收敛条件)设f (x)满足假设1中的1 )与2)，又设Bk为一非奇异矩阵序列。假定对某X。D，迭代序列恒在D中且Xk x*( k 0)，又设该序列收敛于 x*。k由不精确线性搜索的 Wolfe-Powell 准则产生，则当成立时，一定有k 1和f(x*) 0,从而序列xk超线性收敛到x*。二、Broyden 秩一校正的局部超线性收敛性定理0 (关于Hesse近似)设f (x)满足假设1，又设存在正常数，使得Xo x*和 H0 ( 2f(x*)1则由

25、Broyden秩一方法产生的迭代序列xk是有定义的，且超线性收敛到x*。1 (关于Hesse逆近似)设f (x)满足假设1，又设存在正常数 ，使得X。x*和 B°2f (x*)则由Hesse逆Broyden秩一方法产生的迭代序列Xk是有定义的，且超线性收敛到x*。三、DFP和BFGS算法的局部超线性收敛性定理2设f (x)满足假设1，又设在x*的一个邻域内，其中，2f (x*) 1，(Xk,Xk1)max|xk x* , Xk 1 x* 。于是，存在 0和 0，使得对于x。x*|和B。2f(x*)DFp ，DFP方法产生的迭代序列Xk是有定义的，且超线性收敛到x*。类似于Hesse近

26、似形式的DFP方法，可以建立对 Hesse拟近似的BFGS方法的局部收敛性定 理。3设f (X)满足假设1，又设在X*的一个邻域内，其中，2f (X*) 1，(Xk,Xk 1) max|xk x* , Xk 1 x* 。于是，存在 0和 0，使得对于X0 x*|和 H°2f(x*) 1 bfgs ，BFGS 方法有定义，产生的序列xk线性收敛。如果xk x*，那么序列超线性收敛到X*。k 0Byrd , Nocedal , Yuan于1987证明了 Broyden族的超线性收敛性。定理4设f (x)在开凸集D Rn上二阶连续可微且一致凸，又存在 x的一个邻域N(x,)，使得2f (X)2f (x)|x x , x