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

1、第五章 拟牛顿法§5.1 拟牛顿法牛顿法具有收敛速度快的优点，但需要计算Hesse矩阵的逆，计算量大。本章介绍的拟牛顿法将用较简单的方式得到Hesse矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速度，这类算法是无约束最优化问题最重要的求解方法。一、拟牛顿条件设在上二次可微，为了获得Hesse矩阵在处的近似，先研究如下问题。考虑在附近的二次近似：.两边求导，有 令，有 再令 ，则有 或 .因此，我们要求构造出的Hesse矩阵的近似或Hesse矩阵逆的近似应分别满足： 或 （5.1）它们均称之为拟牛顿条件。二、一般拟牛顿算法1） 给出初始点，.2） 若，停止；否则，计算（拟

2、牛顿方向）.3） 沿方向进行线性搜索，（可以是精确，也可非精确）.令.4） 校正产生，使拟牛顿条件满足.5） ， 转2）拟牛顿法较之牛顿法有下述优点：1） 仅需梯度（牛顿法需Hesse矩阵）；2） 保持正定，因而方向具有下降性质（而牛顿法中可能不定）；3） 每次迭代需次运算，而牛顿法需次运算。注： 正如牛顿法中牛顿方向是在椭球范数下的最速下降方向一样，也可看成是在椭球范数下的最速下降方向，也就是在空间某种特定度量（尺度）意义下的最速下降方向。由于每次迭代都在变化，因而度量（尺度）也在变化。正因为如此，常称拟牛顿算法为变尺度法。从这个意义上讲，牛顿法本身也是变尺度法。三、对称秩一校正公式（SRI

3、校正）设是第次迭代的Hesse逆的近似，希望对校正得到，即若设是一个秩一矩阵，则 . （5.2）由拟牛顿条件： 得 （取，使） （5.3）将（5.3）代入（5.2）得 （5.4） 称之为一般Broyden秩一校正公式特别地，取时，称为Broyden秩一校正公式。一般地，上述不对称，由于Hesse矩阵是对称的，故希望也对称，因而取从而得 （5.5）称之为对称秩一校正。对称秩一校正法在用于正定二次函数时，不需要进行一维搜索，具有有限终止性质。定理5.1 设线性无关，那么对于正定二次函数，对称秩一校正方法至多步终止，即。证明：首先用归纳法证明拟牛顿条件的遗传性质，即 。当时，直接由（5.5）可知结论

4、成立。若假定结论对成立，现考虑情形，此时1）当时，由归纳法假设，有故当时， 。2）当时，直接由（5.5）可得。再根据以上所得遗传性质，有 ，（） 由线性无关，故有，即。注：1）证明中对除了要求线性无关外，没有其他条件，因而简单取也是可以的。这样完全不用一维搜索，并且由，得到最优解。2）SRI校正的缺点是不能保证的正定性，除非始终保持。当用于一般函数时，由算出的搜索方向不能保证是下降方向，这在一定程度上妨碍了它的应用。四、DFP校正考虑对称秩二校正 由 得 取 ， 即有 ， ，得校正公式： （5.6）称之为DFP公式（由Davidon,Fletcher,Powell提出）。DFP公式是最重要的拟

5、牛顿校正公式，有很多重要性质。对于正定二次函数（若采用精确一维搜索） 1） 具有有限终止性；2） 拟牛顿条件具有遗传性质；3） 当时，产生共轭方向和共轭梯度。对于一般函数4）校正保持正定性，因而算法具有下降性质；5）方法具有超线性收敛速度；6）当采用精确一维搜索时，对于凸函数，算法具有总体收敛性。定理5.2 当且仅当时，DFP校正公式保持正定性。证明：用归纳法。由初始选择，显然正定。设结论对成立，即正定，并记的Cholesky分解为。下面考虑时的情形，设则 由Cauchy不等式知： （*）又由题设，故有由于，而（*）中等式成立当且仅当与平行，亦即当且仅当与平行。而当与平行时，便有。此时因而，对

6、任何，均有，定理于是证毕。注：上面定理中，条件是可以满足的。事实上，由 ，有 （正定）而 。当采用精确一维搜索时，有，从而。而当采用非精确一维搜索（如Wolfe-Powell准则）时，只要适当提高搜索精度，就可使小到所要求的程度，从而有。定理5.3 （DFP方法的二次终止性）设是二次正定函数，若采用精确一维搜索，那么DFP方法具有遗传性质和方向共轭性质，即对于，有， （遗传性质） ， （方向共轭性质）方法在步迭代后终止。若，则。证明： 对两组式子同时用归纳法证明。当时，结论显然成立。设结论对成立，现证明时结论亦成立。注意到，由精确一维搜索及归纳法假设，对于，有由及，得这就证明了定理中的第一组式

7、子。下证第二组式子，即，。由DFP公式立即可得而对于，由有 定理证毕。由此定理可知，DFP拟牛顿法是共轭方向法。若取，则初始方向为负梯度方向，此时方法变成共轭梯度法。DFP算法是一个在理论分析和实际应用中都起重要作用的算法。五、BFGS校正和PSB校正我们知道拟牛顿条件有两个： （Hesse逆近似） （Hesse近似）在上一段中，得到了关于的DFP校正公式： （5.7）若在上式中实行代换：，即可得到关于的校正公式 （5.8）称之为的BFGS（Broyden,Flecther,Goldforb,Shanno）校正公式。对上式应用秩一校正的求逆公式，又得到的BFGS校正公式： （5.9a） (5.

8、9b) (5.9c)再将上式中，得的DFP公式 （5.10a） (5.10b) (5.10c) 以上讨论告诉我们，对一个给定的拟牛顿校正公式，通过交换，可得到关于的对偶校正，再利用秩一求逆公式，又得（对偶校正）。而对再实施上述对偶操作，还可恢复到原来的。从这种观点看是的对偶校正公式。对SRI校正公式 （5.11）进行交换后得： （5.12）再利用秩一求逆公式，得的对偶仍为其自身，因而SRI校正是自对偶的。BFGS校正是迄今为止最好的拟牛顿公式，它不仅具有DFP校正所拥有的各种性质，而且当采用非精确一维搜索时，对于一般函数也具有总体收敛性，但这一结论对DFP校正尚未获得证明。Powell对一般的

9、Broyden秩一校正公式采用对称化改造，得到了PSB公式。其基本思想是：在一般Broyden秩一校正公式的基础上，构造一个不断满足对称性和拟牛顿条件的矩阵序列，然后求出这个矩阵序列的极限，则该极限矩阵是一个满足对称性和拟牛顿条件的矩阵，从而产生出一个校正公式。设是对称矩阵，令 ，一般地， 不一定对称，因而将其对称化，令虽然对称，却不一定满足拟牛顿条件。因而重复以上过程，产生序列： 可证明这个矩阵序列是收敛的，其极限为加上下标，则得到一类秩二校正公式 （5.13）这个校正类包括了很多的校正公式，在（5.13）式中，若令则得到关于的对称秩一校正公式（SR1公式）；若令，则得到关于的DFP校正公式

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

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

12、，这样得到的校正公式必满足拟牛顿条件。这就得到以为参数的一大类校正公式，称之为Broyden族校正公式。，容易看到 （5.15）其中。当时，得DFP校正；时，得BFGS校正；时，得SRI校正；而时，得Hoshino校正。类似地，有关于的Broyden族校正： （5.16）其中。注：由于和，也可以直接验证Broyden族校正对任意的和都满足拟牛顿条件。Broyden族的二次终止性和正定性定理5.4 （Broyden族校正二次终止性定理）设是正定二次函数，是其Hesse矩阵，那么当采用精确线性搜索时，Broyden族校正具有遗传性质和方向共轭性质，即对于，有： ， （遗传性质） ， （方向共轭性质

13、）方法在步迭代后终止。若，则。证明：证明与定理5.3类似，略。定理5.5 （Broyden族校正的正定性）设参数，当且仅当时，Broyden族校正公式保持正定性。 §5.3 Huang族Huang族是比Broyden族更广泛的一类校正公式。在Broyden族中，是对称的且满足拟牛顿条件 。 但在Huang族中取消了对对称的限制，并将拟牛顿条件进一步放松为 （5.17）称之为广义拟牛顿条件，其中是一个参数。为了使Huang族拟牛顿法用于二次正定函数时，所产生的搜索方向共轭，进而具有二次终止性。设Huang族校正公式的形式为（详细分析可参见徐成贤等著近代优化方法或袁亚湘等著最优化理论与方

14、法）：其中,满足： ，在上面的方程组中，含有三个自由参数。特别地，令,，则只含一个自由参数，若取为自由参数，则有： （5.18）其中，正好蜕变为Broyden族校正公式，这表明Broyden族是Huang族的子族。一般地，Huang族中含有三个自由参数，可产生丰富的校正公式。注：1）若采用精确一维搜索，对于正定二次函数，所有Huang族变尺度算法产生相同的迭代点列；对一般函数产生的点列只依赖于。2) 另外，当极小化正定二次函数时，若取，则Huang族校正公式产生的搜索方向与F-R共轭梯度法相同，因而也是共轭方向法。§5.4 拟牛顿法的局部收敛速度一、一般拟牛顿算法超线性收敛的特征假设

15、1：1）设在开凸集中二阶连续可微；2）存在一个严格局部极小点，且正定；3）存在的一个邻域，使得。定理5.6 （不带步长因子的拟牛顿算法超线性收敛的充要条件）设满足假设1中的1）与2），又设为一非奇异矩阵序列。假定对某，迭代序列恒在中且，又设该序列收敛于。则当且仅当时，序列超线性收敛到。定理5.7 （带步长因子的拟牛顿算法超线性收敛的充要条件）设满足定理5.6中的假设，又设为一非奇异矩阵序列。假定对某，迭代序列恒在中且，又设该序列收敛于。如果成立，那么序列超线性收敛到且的充要条件是收敛到1。注：1）要使算法超线性收敛，步长因子必趋近于1；2）拟牛顿算法超线性收敛的几何特征是：其位移在长度与方向上

16、都必趋近于牛顿方向。定理5.8 （基于精确搜索的拟牛顿法的超线性收敛性）设满足假设1中的1）与2），又设为一非奇异矩阵序列。假定对某，迭代序列恒在中且，又设该序列收敛于。由精确线性搜索产生，则当成立时，一定有和，从而序列超线性收敛到。定理5.9 （基于Wolfe-Powell准则的拟牛顿法的超线性收敛条件）设满足假设1中的1）与2），又设为一非奇异矩阵序列。假定对某，迭代序列恒在中且，又设该序列收敛于。由不精确线性搜索的Wolfe-Powell准则产生，则当成立时，一定有和，从而序列超线性收敛到。二、Broyden秩一校正的局部超线性收敛性 定理5.10 （关于Hesse近似）设满足假设1，又

17、设存在正常数，使得 和 则由Broyden秩一方法 产生的迭代序列是有定义的，且超线性收敛到。定理5.11（关于Hesse逆近似）设满足假设1，又设存在正常数，使得 和 则由Hesse逆Broyden秩一方法 产生的迭代序列是有定义的，且超线性收敛到。三、DFP和BFGS算法的局部超线性收敛性定理5.12 设满足假设1，又设在的一个邻域内， 其中， 。于是，存在和 ，使得对于 和，DFP方法 产生的迭代序列是有定义的，且超线性收敛到。类似于Hesse近似形式的DFP方法，可以建立对Hesse拟近似的BFGS方法的局部收敛性定理。定理5.13 设满足假设1，又设在的一个邻域内， 其中， 。于是，

18、存在和 ，使得对于 和，BFGS方法 有定义，产生的序列线性收敛。如果，那么序列超线性收敛到。Byrd，Nocedal，Yuan于证明了Broyden族的超线性收敛性。定理5.14 设在开凸集上二阶连续可微且一致凸，又存在的一个邻域，使得 成立。则对于任何正定矩阵，当线性搜索满足Wolfe-Powell准则时，Broyden族算法（，即不包含DFP算法）所产生的极小化序列，超线性收敛到。定理5.15 设在开凸集上二阶连续可微且一致凸，又存在的一个邻域，使得 成立。则对于任何正定矩阵，当采用精确线性搜索时，Broyden族算法所产生的极小化序列超线性收敛到。§5.5 拟牛顿法的总体收敛性一、精确搜索条件的总体收敛性Powell于1971年证明了当目标函数是二阶连续可微且一致凸函数时，采用精确搜索的DFP方法的全局收敛性及满足Lipschitz条件时的超线性收敛性。1976年，证明了为凸函数时，采用Wolfe-Powell准则的BFGS方法的全局收敛性和超线性收敛性。1987年Byrd，Nocedal，Yuan将Powell的结果推广到除DFP以外的所有限制Broyden族算法（即），证明了全局收敛性及超线性收敛性。定理5