最优化理论与算法.docx

第五章 拟牛顿法§5.1 拟牛顿法牛顿法具有收敛速度快的优点，但需要计算 Hesse 矩阵的逆，计算量大本章介绍的拟牛顿法 将用较简单的方式得到 Hesse 矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速 度，这类算法是无约束最优化问题最重要的求解方法一、拟牛顿条件设f (x)在Rn上二次可微，为了获得Hesse矩阵G(x) = V2f (x)在x 处的近似，先研究如下k +1问题考虑f (x)在x 附近的二次近似:k+11)+ g T (x — x ) + (x — x )T G (x - x )-k +1 k +1 k +1 2 k +1 k +1 k +1两边求导，有g (x)〜g+1+ Gk+1(x — xk+1)x，有k再令s 沁 x — x ， y 沁 g — gk k+1 k k k+1 k则有y q G s 或 G -1 y « s .k k +1 k k + 1 k k因此，我们要求构造出的Hesse矩阵的近似B 或Hesse矩阵逆的近似H 应分别满足:k +1 k +1B s = yk+1 k k5.1)它们均称之为拟牛顿条件二、一般拟牛顿算法1) 给出初始点 x0 e R， H0 = I， £ > 0， k := 0 .2) 若||g ||<£，停止；否则，计算d = — H g (拟牛顿方向).k k k k3)沿方向d进行线性搜索，a > 0 kk(可以是精确，也可非精确)•令x = x +a d .k +1 k k k4) 校正 H 产生 H ，使拟牛顿条件满足.k k + 15) k := k + 1 ， 转 2)拟牛顿法较之牛顿法有下述优点1）仅需梯度（牛顿法需Hesse矩阵）;2） H保持正定，因而方向具有下降性质（而牛顿法中G可能不定）；kk3） 每次迭代需o（n2）次运算，而牛顿法需O（n3）次运算。

注：正如牛顿法中牛顿方向-G-1g是在椭球范数|H|下的最速下降方向一样，-H g也可看成 k k Q k kk是在椭球范数||口||下的最速下降方向，也就是在空间某种特定度量（尺度）意义下的最速下降方向 H-1由于每次迭代 H 都在变化，因而度量（尺度）也在变化正因为如此，常称拟牛顿算法为变尺度k法从这个意义上讲，牛顿法本身也是变尺度法三、对称秩一校正公式（SRI校正）设H是第k次迭代的Hesse逆的近似，希望对H校正得到H ，即k k k +1若设 E 是k个秩一矩阵，则 H = H +uvT.k+1 k5.2)由拟牛顿条件：H y = H y + u (vT y ) = sk+1 k k k k ks — H y卞 k k (取v，使vTy丰0 ) vT y kk5.3)将(5.3)代入(5.2)得 H = H +-^(s — H y )vTk + 1 k v T y k k kk5.4)称之为一般 Broyden 秩一校正公式特别地，取v = y时，称为Broyden秩一校正公式k一般地，上述H 不对称，由于Hesse矩阵是对称的，故希望Hk + 1也对称，因而取从而得(s — H y )(s — H y )TH = H + —k k k k k k —k+1 k (s — H y )T yk k k k5.5)称之为对称秩一校正。

对称秩一校正法在用于正定二次函数时，不需要进行一维搜索，具有有限终 止性质定理5.1设s, s ,…，s线性无关，那么对于正定二次函数，对称秩一校正方法至多n + 1步终止,0 1 n-1即 H = G -1n证明：首先用归纳法证明拟牛顿条件的遗传性质，即H y = s j = 0 , 1•，- i — 0 1i j j当i = 1时，直接由（5.5）可知结论成立若假定结论对i > 1成立，现考虑i + 1情形，此时(s — H y )(s — H y )T yH y = H y + * ** * ** ji+1 j i j (s — H y )T yi i i i1）当j < i时,由归纳法假设，有ji=sT Gsi故当j < i时,H y = H y = i +1 j i2)当j = i时,直接由（ 5.5）可得s — H y )T y = sTy — yTH y = sTy — yTsi i i j i j i i j i j i j— sTGs = 0j i j再根据以上所得遗传性质，有H y = s， Hn j jGsjs ( j = 0,1,…，i — 1 ) j由s线性无关，故有H G = I ,即Hj n n注：1）证明中对s除了要求线性无关外，没有其他条件，因而简单取s =— H g也是可以的。

这样i i i i完全不用一维搜索，并且由s =— H g =— G -1 g，得到最优解n n n n2） SRI校正的缺点是不能保证H的正定性，除非始终保持（s — H y ） Ty > 0当用于一般 k k k k k函数时，由d =— H g算出的搜索方向不能保证是下降方向，这在一定程度上妨碍了它的应用 k k k四、DFP校正考虑对称秩二校正H = H + auu T + bvv T k + 1 k由H y = sk +1 k k得H y +auuTy +bvvTy =s k k k k k即有a uT y = 1，b vTy=， b =-uTyT H y得校正公式：=HH y yTH5.6)yT H y称之为DFP公式（由Davidon,Fletcher,Powell提出）DFP公式是最重要的拟牛顿校正公式，有很多 重要性质对于正定二次函数（若采用精确一维搜索）1） 具有有限终止性；2） 拟牛顿条件具有遗传性质；3） 当H = I时，产生共轭方向和共轭梯度0对于一般函数4） 校正保持正定性，因而算法具有下降性质；5） 方法具有超线性收敛速度；6） 当采用精确一维搜索时，对于凸函数，算法具有总体收敛性 定理5.2当且仅当sTy > 0时，DFP校正公式保持正定性。

ff证明：用归纳法由初始选择，H显然正定设结论对f成立，即H正定，并记H的Cholesky0 f f分解为H = LLt下面考虑f + 1时的情形，设fa=LTz, b=LTyzT H z = zT ( Hf+1 fH y yT H s sT f f f f)z + zT f f y T H y sT yf f f f ffr (aTb )\ (sTz )2z = [aTa - ] + lbTb sT yff由 Cauchy 不等式知：(aTb)2aTa -bTb又由题设sTy > 0，故有ffzT H z > 0f+1由于z丰0，而（*）中等式成立当且仅当a与b平行，亦即当且仅当Z与y平行而当Z与y平行kk时，便有z =卩y，卩工0此时k(STZ )2LsT ykk=0 2sT ykk因而，对任何z丰0，均有zTH z > 0，定理于是证毕k+1注：上面定理中，条件sT y > 0是可以满足的事实上,kk由d=-Hg，s = a dkkkk k k有sTkg = akdTkkg= -a gT Hk k k$ 0kk而s T ykkH 正定)k=ST (g - g ) = sTg - sTg 。

k k +1 k k k +1 k k当采用精确一维搜索时，有gT s = 0，从而sTy > 0k+1 k k k而当采用非精确一维搜索（如Wolfe-Powell准贝I」）时，只要适当提高搜索精度，就可使sTg 小k k+1到所要求的程度，从而有sTy > 0kk定理5.3 （DFP方法的二次终止性）设f （x）是二次正定函数，若采用精确一维搜索，那么DFP方法具有遗传性质和方向共轭性质，即对于i = 0,1,…，m - 1，有H y = s，j = 0,1, ...,i （遗传性质）i +1 j jsTGs = 0， j = 0,1,…,i — 1 （方向共轭性质）ij方法在m < n — 1步迭代后终止若m = n — 1，则H = G -1n证明： 对两组式子同时用归纳法证明当i = 0时，结论显然成立设结论对i成立，现证明i + 1时结论亦成立注意到g工0，由 i+1精确一维搜索及归纳法假设，对于j < i，有gT s = gT s + 乙(g - g )Tsi+1 j j+1 j k +1 k jk 二 j+10 + 工 sTGs = 0=gT s + 工 yTs =j +1 j k j k jk 二 j+1 k 二 j+1由 s = -a d = -a H g 及 Gs = y，得i+1 i+1 i+1 i+1 i+1 i+1 j jsT Gs = -a gT H y = -a gT s = 0 i + 1 j i + 1 i + 1 i + 1 j i + 1 i + 1 j这就证明了定理中的第一组式子。

下证第二组式子，即Hi+2yjs ， j = 0,1, , i + 1j由 DFP 公式立即可得Hi+2yi+1=si+1而对于j < i，由sT y = st Gs = 0 i+1 j i+1 jyT H y — yT s — sT Gs — 0 i+1 i+1 j i+1 j i+1 jHi+2ys sT y H y y T Hi + 1 i 丨 1 j sT yi+1 i+ 1.y.■td t1 = H. y — si + 1 j jy T H yi+ 1 i+ 1i +定理证毕由此定理可知，DFP拟牛顿法是共轭方向法若取H0=I，则初始方向为负梯度方向，此时方法变成共轭梯度法DFP 算法是个在理论分析和实际应用中都起重要作用的算法五、BFGS校正和PSB校正我们知道拟牛顿条件有两个：H y — s （ Hesse 逆近似）k + 1 k kB s — y （ Hesse 近似）k +1 k k在上一段中，得到了关于 H 的 DFP 校正公式：ks st。