《自-最优化理论与算法(第五章)》由会员分享,可在线阅读,更多相关《自-最优化理论与算法(第五章)(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族拟牛顿法用于二次正定函数时,所产生的搜索方向共轭,进