《自-最优化理论与算法(第五章)》由会员分享，可在线阅读，更多相关《自-最优化理论与算法(第五章)（15页珍藏版）》请在金锄头文库上搜索。
1、第五章 拟牛顿法51 拟牛顿法牛顿法具有收敛速度快的优点，但需要计算Hes矩阵的逆,计算量大。本章介绍的拟牛顿法将用较简单的方式得到se矩阵或其逆的近似,一方面计算量不大,另一方面具有较快的收敛速度,这类算法是无约束最优化问题最重要的求解方法。一、拟牛顿条件设在上二次可微，为了获得se矩阵在处的近似,先研究如下问题。考虑在附近的二次近似：.两边求导,有 令，有 再令 ,则有 或 .因此,我们要求构造出的esse矩阵的近似或Hese矩阵逆的近似应分别满足: 或 （.1)它们均称之为拟牛顿条件。二、一般拟牛顿算法1） 给出初始点,，.2） 若,停止;否则,计算（拟牛顿方向）.3） 沿方向进行线性搜
2、索,(可以是精确，也可非精确）.令.4） 校正产生，使拟牛顿条件满足5） ，转)拟牛顿法较之牛顿法有下述优点：1） 仅需梯度(牛顿法需Hee矩阵);2） 保持正定,因而方向具有下降性质（而牛顿法中可能不定);3） 每次迭代需次运算,而牛顿法需次运算。注:正如牛顿法中牛顿方向是在椭球范数下的最速下降方向一样，也可看成是在椭球范数下的最速下降方向，也就是在空间某种特定度量（尺度）意义下的最速下降方向。由于每次迭代都在变化,因而度量(尺度)也在变化。正因为如此,常称拟牛顿算法为变尺度法。从这个意义上讲，牛顿法本身也是变尺度法。三、对称秩一校正公式(RI校正)设是第次迭代的Hese逆的近似,希望对校正
3、得到，即若设是一个秩一矩阵,则 (.2）由拟牛顿条件: 得 (取,使) （5.3）将(5.3）代入(5.2)得 （5.4) 称之为一般Boyn秩一校正公式特别地，取时，称为Broyde秩一校正公式。一般地,上述不对称,由于ese矩阵是对称的，故希望也对称，因而取从而得 (5.5）称之为对称秩一校正。对称秩一校正法在用于正定二次函数时，不需要进行一维搜索，具有有限终止性质。定理.1 设线性无关,那么对于正定二次函数,对称秩一校正方法至多步终止,即。证明：首先用归纳法证明拟牛顿条件的遗传性质,即 。当时，直接由（5.5）可知结论成立。若假定结论对成立，现考虑情形，此时1)当时，由归纳法假设,有故当
4、时, 。)当时,直接由(.5)可得。再根据以上所得遗传性质，有 ,（） 由线性无关,故有,即。注：1)证明中对除了要求线性无关外，没有其他条件,因而简单取也是可以的。这样完全不用一维搜索，并且由，得到最优解。2）RI校正的缺点是不能保证的正定性，除非始终保持。当用于一般函数时，由算出的搜索方向不能保证是下降方向,这在一定程度上妨碍了它的应用。四、DF校正考虑对称秩二校正 由 得 取 , 即有 , ,得校正公式： (5)称之为DP公式（由Davido,Fletchr,Poel提出）。P公式是最重要的拟牛顿校正公式，有很多重要性质。对于正定二次函数(若采用精确一维搜索)1） 具有有限终止性；2）
5、拟牛顿条件具有遗传性质;3） 当时,产生共轭方向和共轭梯度。对于一般函数4)校正保持正定性，因而算法具有下降性质;5)方法具有超线性收敛速度;)当采用精确一维搜索时，对于凸函数，算法具有总体收敛性。定理.2 当且仅当时，DFP校正公式保持正定性。证明：用归纳法。由初始选择，显然正定。设结论对成立，即正定，并记的Chlesky分解为。下面考虑时的情形，设则 由Cacy不等式知: (*）又由题设,故有由于，而（*)中等式成立当且仅当与平行,亦即当且仅当与平行。而当与平行时，便有。此时因而，对任何，均有,定理于是证毕。注:上面定理中，条件是可以满足的。事实上,由 ,有 (正定）而 。当采用精确一维搜
6、索时，有，从而。而当采用非精确一维搜索（如WolfePoe准则）时,只要适当提高搜索精度,就可使小到所要求的程度，从而有。定理.3（DFP方法的二次终止性)设是二次正定函数,若采用精确一维搜索,那么FP方法具有遗传性质和方向共轭性质,即对于，有， (遗传性质) ， （方向共轭性质）方法在步迭代后终止。若,则。证明: 对两组式子同时用归纳法证明。当时，结论显然成立。设结论对成立，现证明时结论亦成立。注意到，由精确一维搜索及归纳法假设,对于,有由及，得这就证明了定理中的第一组式子。下证第二组式子,即，。由D公式立即可得而对于,由有 定理证毕。由此定理可知,DFP拟牛顿法是共轭方向法。若取，则初始方
7、向为负梯度方向,此时方法变成共轭梯度法。DFP算法是一个在理论分析和实际应用中都起重要作用的算法。五、BGS校正和PSB校正我们知道拟牛顿条件有两个： (ese逆近似) (ee近似)在上一段中,得到了关于的DFP校正公式： (5.）若在上式中实行代换：,即可得到关于的校正公式 （5.8)称之为的BS（Brde，Fher,Gldfob,Shano)校正公式。对上式应用秩一校正的求逆公式,又得到的BFGS校正公式: (.9a） (.b) （5.9c)再将上式中，,得的P公式 (10a） (510) (5.0c） 以上讨论告诉我们，对一个给定的拟牛顿校正公式,通过交换,可得到关于的对偶校正，再利用秩
8、一求逆公式,又得(对偶校正)。而对再实施上述对偶操作，还可恢复到原来的。从这种观点看是的对偶校正公式。对SRI校正公式 （5.11)进行交换后得： (5.2)再利用秩一求逆公式，得的对偶仍为其自身，因而SRI校正是自对偶的。BFS校正是迄今为止最好的拟牛顿公式,它不仅具有DF校正所拥有的各种性质,而且当采用非精确一维搜索时,对于一般函数也具有总体收敛性,但这一结论对FP校正尚未获得证明。Pwll对一般的Boyden秩一校正公式采用对称化改造，得到了P公式。其基本思想是:在一般Bryden秩一校正公式的基础上,构造一个不断满足对称性和拟牛顿条件的矩阵序列,然后求出这个矩阵序列的极限,则该极限矩阵
9、是一个满足对称性和拟牛顿条件的矩阵,从而产生出一个校正公式。设是对称矩阵，令 ,一般地,不一定对称,因而将其对称化,令虽然对称,却不一定满足拟牛顿条件。因而重复以上过程，产生序列: 可证明这个矩阵序列是收敛的,其极限为加上下标,则得到一类秩二校正公式 （5.3）这个校正类包括了很多的校正公式，在(13）式中,若令则得到关于的对称秩一校正公式(S1公式);若令，则得到关于的DFP校正公式;若令 其中，则得到关于的FGS校正；若令,则得到SB校正： (.4)这个校正在理论研究和实际计算中是十分重要的,其缺点是不能保证校正矩阵的正定性。值得指出的是，通过交换,可得到关于的类似校正公式。前面介绍了一些
10、拟牛顿校正公式，以及派生新的拟牛顿法校正公式的方法（如对偶方法，对称技术等）。有时候，还可利用一些特殊的附加条件推出校正公式。）BGS校正是由DFP校正公式经过替换与秩一矩阵求逆得到的校正公式。事实上对其它校正公式也可采用类似方法获得新的校正公式,这些新的派生公式称为原公式的对偶,对偶方法是产生新校正公式的一种重要方法。若一个校正公式的对偶还等于其自身,则称之为自对偶。)将一般的rye秩一校正公式反复采用对称化、应用秩一校正使其满足拟牛顿条件,生成一迭代序列，其极限构成一类新的秩一校正公式,而且很多常见的校正公式都含在这个类中,特别地得到PB校正公式。3)有时我们得到的校正公式是一类，在这一类
11、中通常需附加上另外的条件而得到具体的校正公式。这种附加条件有各种提法，若让(或)最靠近（对应地)，由此种条件导出的校正公式称为最小改变割线校正，一些重要的校正公式在适当选取的范数下均具有这种性质。5. Broyde族上节讨论的DP校正和BFGS校正都是对称秩二校正,且都是通过，来获得校正矩阵。下面考虑DP与S的加权组合:（是参数)显然,这样得到的校正公式必满足拟牛顿条件。这就得到以为参数的一大类校正公式，称之为Boyden族校正公式。,容易看到 (.15)其中。当时,得P校正;时，得BS校正;时，得SRI校正；而时,得Hshino校正。类似地,有关于的Broyde族校正： (516）其中。注:
12、由于和，也可以直接验证oyden族校正对任意的和都满足拟牛顿条件。rode族的二次终止性和正定性定理.4 （Broy族校正二次终止性定理)设是正定二次函数，是其esse矩阵，那么当采用精确线性搜索时,Brod族校正具有遗传性质和方向共轭性质,即对于,有: , (遗传性质） ， （方向共轭性质）方法在步迭代后终止。若,则。证明：证明与定理53类似，略。定理5(Brden族校正的正定性)设参数，当且仅当时，Boyde族校正公式保持正定性。 5.3 Hun族uag族是比oyden族更广泛的一类校正公式。在Broyen族中，是对称的且满足拟牛顿条件 。 但在Huan族中取消了对对称的限制，并将拟牛顿条件进一步放松为 (5.17)称之为广义拟牛顿条件,其中是一个参数。为了使Huang族拟牛顿法用于二次正定函数时,所产生的搜索方向共轭,进
