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

第五章拟牛顿法§5.1拟牛顿法牛顿法具有收敛速度快的优点，但需要计算Hesse矩阵的逆，计算量大。本章介绍的拟牛顿法将用较简单的方式得到Hesse矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速度，这类算法是无约束最优化问题最重要的求解方法。一、拟牛顿条件设()fx在nR上二次可微，为了获得Hesse矩阵2()()Gxfx在1kx处的近似，先研究如下问题。考虑()fx在1kx附近的二次近似：1111111)()()()2()(TTkkkkkkgxxGxfxfxxxx.两边求导，有111()()kkkgxgGxx令kxx，有111()kkkkkggGxx再令1kkksxx，1kkkygg则有1kkkyGs或11kkkGys.因此，我们要求构造出的Hesse矩阵的近似1kB或Hesse矩阵逆的近似1kH应分别满足：1kkkBsy或1kkkHys（5.1）它们均称之为拟牛顿条件。二、一般拟牛顿算法1）给出初始点0xR，0HI，0，:0k.2）若kg，停止；否则，计算kkkdHg（拟牛顿方向）.3）沿方向kd进行线性搜索，0k（可以是精确，也可非精确）.令1kkkkxxd.4）校正kH产生1kH，使拟牛顿条件满足.5）:1kk，转2）拟牛顿法较之牛顿法有下述优点：1）仅需梯度（牛顿法需Hesse矩阵）；2）kH保持正定，因而方向具有下降性质（而牛顿法中kG可能不定）；3）每次迭代需2()On次运算，而牛顿法需3()On次运算。注：正如牛顿法中牛顿方向1kkgG是在椭球范数kG下的最速下降方向一样，kkHg也可看成是在椭球范数1kH下的最速下降方向，也就是在空间某种特定度量（尺度）意义下的最速下降方向。由于每次迭代kH都在变化，因而度量（尺度）也在变化。正因为如此，常称拟牛顿算法为变尺度法。从这个意义上讲，牛顿法本身也是变尺度法。三、对称秩一校正公式（SRI校正）设kH是第k次迭代的Hesse逆的近似，希望对kH校正得到1kH，即1kkkHHE若设kE是一个秩一矩阵，则1TkkuvHH.（5.2）由拟牛顿条件：1()TkkkkkkHyHyuvys得kkkTksHyuvy（取v，使0Tkvy）（5.3）将（5.3）代入（5.2）得11()TkkkkkTkHHsHyvvy（5.4）称之为一般Broyden秩一校正公式特别地，取kvy时，称为Broyden秩一校正公式。一般地，上述1kH不对称，由于Hesse矩阵是对称的，故希望1kH也对称，因而取()kkkvsHy从而得1()()()TkkkkkkkkTkkkksHysHyHHsHyy（5.5）称之为对称秩一校正。对称秩一校正法在用于正定二次函数时，不需要进行一维搜索，具有有限终止性质。定理5.1设011,,,nsss线性无关，那么对于正定二次函数，对称秩一校正方法至多1n步终止，即1nHG。证明：首先用归纳法证明拟牛顿条件的遗传性质，即ijjHys0,1,,1ji。当1i时，直接由（5.5）可知结论成立。若假定结论对1i成立，现考虑1i情形，此时1()()()TiiiiiijijijTiiiisHysHyyHyHysHyy1）当ji时，由归纳法假设，有()0TTTTTiiijijiijijijTTijijsHyysyyHysyyssGssGs故当ji时，1ijijjHyHys。2）当ji时，直接由（5.5）可得。再根据以上所得遗传性质，有njjHys，njjHGss（0,1,,1ji）由js线性无关，故有nHGI，即1nHG。注：1）证明中对is除了要求线性无关外，没有其他条件，因而简单取iiisHg也是可以的。这样完全不用一维搜索，并且由1nnnnsHgGg，得到最优解。2）SRI校正的缺点是不能保证kH的正定性，除非始终保持()0TkkkksHyy。当用于一般函数时，由kkkdHg算出的搜索方向不能保证是下降方向，这在一定程度上妨碍了它的应用。四、DFP校正考虑对称秩二校正1TTkkHHauubvv由1kkkHys得TTkkkkkHyauuybvvys取kus，kkvHy即有1Tkauy，1Tkbvy11TTkkkauysy，11TTkkkkbvyyHy得校正公式：1TTkkkkkkkkTTkkkkkssHyyHHHsyyHy（5.6）称之为DFP公式（由Davidon,Fletcher,Powell提出）。DFP公式是最重要的拟牛顿校正公式，有很多重要性质。对于正定二次函数（若采用精确一维搜索）1）具有有限终止性；2）拟牛顿条件具有遗传性质；3）当0HI时，产生共轭方向和共轭梯度。对于一般函数4）校正保持正定性，因而算法具有下降性质；5）方法具有超线性收敛速度；6）当采用精确一维搜索时，对于凸函数，算法具有总体收敛性。定理5.2当且仅当0Tkksy时，DFP校正公式保持正定性。证明：用归纳法。由初始选择，0H显然正定。设结论对k成立，即kH正定，并记kH的Cholesky分解为TkHLL。下面考虑1k时的情形，设,TTkaLzbLy则221()()()[]TTTTTTTTkkkkkkkkkTTTTkkkkkkkHyyHssszabzHzzHzzzaayHysybbsy由Cauchy不等式知：2()0TTTabaabb（*）又由题设0Tkksy，故有10TkzHz由于0z，而（*）中等式成立当且仅当a与b平行，亦即当且仅当z与ky平行。而当z与ky平行时，便有,0kzy。此时22()0TTkkkTkkszsysy因而，对任何0z，均有10TkzHz，定理于是证毕。注：上面定理中，条件0Tkksy是可以满足的。事实上，由kkkdHg，kkksd有0TTTkkkkkkkkksgdggHg（kH正定）而11()TTTTkkkkkkkkksysggsgsg。当采用精确一维搜索时，有10Tkkgs，从而0Tkksy。而当采用非精确一维搜索（如Wolfe-Powell准则）时，只要适当提高搜索精度，就可使1Tkksg小到所要求的程度，从而有0Tkksy。定理5.3（DFP方法的二次终止性）设()fx是二次正定函数，若采用精确一维搜索，那么DFP方法具有遗传性质和方向共轭性质，即对于0,1,,1im，有1ijjHys，0,1,,ji（遗传性质）0TijsGs，0,1,,1ji（方向共轭性质）方法在1mn步迭代后终止。若1mn，则1nHG。证明：对两组式子同时用归纳法证明。当0i时，结论显然成立。设结论对i成立，现证明1i时结论亦成立。注意到10ig，由精确一维搜索及归纳法假设，对于ji，有1111111()00iTTTijjjkkjkjiiTTTjjkjkjkjkjgsgsggsgsyssGs由111111iiiiiisdHg及jjGsy，得1111110TTTijiiijiijsGsgHygs这就证明了定理中的第一组式子。下证第二组式子，即2ijjHys，0,1,,1ji。由DFP公式立即可得211iiiHys而对于ji，由110TTijijsysGs11110TTTiijijijyHyyssGs有11111121111111TTiijiiiijijijijjTTiiiiissyHyyHyHyHyHyssyyHy定理证毕。由此定理可知，DFP拟牛顿法是共轭方向法。若取0HI，则初始方向为负梯度方向，此时方法变成共轭梯度法。DFP算法是一个在理论分析和实际应用中都起重要作用的算法。五、BFGS校正和PSB校正我们知道拟牛顿条件有两个：1kkkHys（Hesse逆近似）1kkkBsy（Hesse近似）在上一段中，得到了关于kH的DFP校正公式：()1TTDFPkkkkkkkkTTkkkkkssHyyHHHsyyHy（5.7）若在上式中实行代换：kkHB，kksy，即可得到关于kB的校正公式()1TTBFGSkkkkkkkkTTkkkkkyyBssBBByssBs（5.8）称之为kB的BFGS（Broyden,Flecther,Goldforb,Shanno）校正公式。对上式应用秩一校正的求逆公式，又得到kH的BFGS校正公式：()1(1TTTTBFGSkkkkkkkkkkkkkTTTkkkkkkyHysssyHHysHHsysysy）（5.9a）2()()()()TTTTkkkkkkkkkkkkkkkTTkkkksHysssHysHyyHsssysy(5.9b)()()TTTkkkkkkkTTTkkkkkksyysssIHIsysysy(5.9c)再将上式中kkHB，kksy，得kB的DFP公式()1(1TTTTDFPkkkkkkkkkkkkkTTTkkkkkksBsyyysBBsyBBysysys）（5.10a）2()()()()TTTTkkkkkkkkkkkkkkkTTkkkkyBsyyyBsyBssByyysys(5.10b)()()TTTkkkkkkkTTTkkkkkkyssyyyIBIysysys(5.10c)以上讨论告诉我们，对一个给定的拟牛顿校正公式1kH，通过交换kkHB，kksy可得到关于kB的对偶校正()1DkB，再利用秩一求逆公式，又得()1DkH（对偶校正）。而对()1DkH再实施上述对偶操作，还可恢复到原来的1kH。从这种观点看()1BFGSkH是()1DFPkH的对偶校正公式。对SRI校正公式()1SRIkH()1()()()TSRIkkkkkkkkTkkkksHysHyHHsHyy（5.11）进行交换后得：1()()()TkkkkkkkkTkkkkyBsyBsBByBss（5.12）再利用秩一求逆公式，得()1SRIkH的对偶仍为其自身，因而SRI校正是自对偶的。BFGS校正是迄今为止最好的拟牛顿公式，它不仅具有DFP校正所拥有的各种性质，而且当采用非精确一维搜索时，对于一般函数也具有总体收敛性，但这一结论对DFP校正尚未获得证明。Powell对一般的Broyden秩一校正公式采用对称化改造，得到了PSB公式。其基本思想是：在一般Broyden秩一校正公式的基础上，构造一个不断满足对称性和拟牛顿条件的矩阵序列，然后求出这个矩阵序列的极限，则该极限矩阵是一个满足对称性和拟牛顿条件的矩阵，从而产生出一个校正公式。设nnBR是对称矩阵，令1()TTyBscCBcs，一般地，1C不一定对称，因而将其对称化，令1122TCCC2C虽然对称，却不一定满足拟牛顿条件。因而重复以上过程，产生序列{}kC：2212212122()2TkkkTTkkkyCscCCcsCCC可证明这个矩阵序列是收敛的，其极限为2()()()()TTTTTTyBsccyBsyBssBBcccscs加上下标，则得到一类秩二校正公式12()()()()TTTTkkkkkkkkkkkkkkkkTTkkkkyBsccyBsyBssBBcccscs（5.13）这个校正类包括了很多的校正公式，在（5.13）式中，若令kkkkcyBs则得到关于kB的对称秩一校正公式（SR1公式）；若令kkcy，则得到关于kB的DFP校正公式；若令111kkkkk