拟牛顿法type
status
date
slug
summary
tags
category
icon
password
Property
牛顿法是一种具有较高实用性的优化问题求解方法，如果收敛，则收敛阶数至少是2。但是，当目标函数为一般性的非线性函数时，牛顿法不能保证能从任意起始点收敛到函数的极小点。如果初始点 不足够接近极小点，那么牛顿法可能不具有下降特性，即对于某些 ，
牛顿法的基本思路：在每次迭代中， 利用二次型函数来局部近似目标函数，并求解近似函数的极小点作为下一个迭代点，迭代公式为：
对上式进行适当修正，可以保证牛顿法具有下降特性：
为步长，合理地确定步长，使得
比如，可令
通过在方向上进行一维搜索，即可确定 。
一维搜索的过程实际上就是求一元实值函数 的极小点，看起来比较简单， 实际计算过程却不容易。
牛顿法的另外一个缺陷是必须计算黑塞矩阵 和求解方程 ，即计算
为了避免这种矩阵求逆运算，可以通过设计 的近似矩阵来代替 ，这就是拟牛顿法的基本思路。 的近似矩阵随着迭代的进行不断更新，使其至少拥有 的部分性质。为了分析近似矩阵所应该具有的关于 的性质，引人等式
是 实矩阵， 为搜索步长
在 处对 进行一阶泰勒展开，并将 代人后，可得
当 趋向于 0 时，上式等号右侧的第 2 项主导了第 3 项。因此，当 较小时，为了保证函数 从 到 是下降的，必须有
要保证上式成立，最简单的方式就是保证 是正定的。
函数一阶连续可微 是对称正定实矩阵，如果令 ，其中， ，那么有
在拟牛顿法中，构造黑塞矩阵逆矩阵的近似矩阵时，只需要用到目标函数值和梯度。 因此，只要确定了合适的近似矩阵 构造方法，那么迭代过程中不需要任何涉及到黑塞矩阵以及线性方程求解的计算工作。
黑塞矩阵逆矩阵的近似
令 表示黑塞矩阵逆矩阵的一系列近似矩阵。假定目标函数的黑塞矩阵是常数矩阵，与 的取值无关，即目标函数是二次型函数， ，且，则有
令
可得
记对称正定矩阵作为近似矩阵的初始矩阵，在给定的下，矩阵 应满足
近似矩阵 应满足
如果共开展 次迭代，则近似矩阵 应满足
将其改写为
矩阵能够满足
和
说明，如果 非奇异，那么矩阵能够在次迭代后唯一确定，即
由此可得，如果 能够使方程成立，那么利用迭代公式
求解维二次型优化问题，可得 ，这与牛顿迭代公式是一致的，说明一定能够在 次迭代内完成求解。
拟牛顿法的迭代公式为：
其中，矩阵是对称矩阵。目标函数为二次型函数时，必须满足
其中， 。
实际上，拟牛顿法也是一种共轭方向法。将拟牛顿法应用到二次型问题中，黑塞矩阵为 , 对于 , 有
其中， 。 如果 , 那么是 共轭的。
对于维二次型问题，拟牛顿法最多经过步迭代即可解出最优解。
注意：由满足条件并不能唯一确定矩阵 ，因此，这就给了计算矩阵的自由发挥空间。矩阵 可由矩阵增加修正项得到。
秩1修正公式
秩1修正公式中，修正项为 ， ，是一个对称矩阵，近似矩阵的更新方程为
注意
故称为秩1修正算法(也称为单秩对称算法)。很明显，如果是对称的，则也是对称的。
由于需满足条件
则
是一个标量，因此
得
据此可得
可得近似矩阵的中间更新方程
为将上式中右端整理为只与 、 、 有关，在两端同时左乘 ，可得
由于 为标量， 为标量，因此
将上式带入中间更新方程，得最终更新方程
秩1算法：
- 令 ；选择初始点 ，任选一个对称正定实矩阵 。
- 如果 ，停止迭代；否则，令 。
- 计算
- 计算
- 令 ，返回第2步。
秩1算法是基于方程 推导出来的。但是，希望能够满足的条件是
可以证明，秩1算法能够自动满足上述方程
例题： 目标函数为，利用秩1算法求函数 极小点。初始值为 的单位阵 。
目标函数 写为矩阵的形式：
可得函数在处的梯度为：
由于 ，故：
目标函数为二次型函数，因此：
可得新的迭代点为
接下来计算：
由于
因此可得
故可确定搜索方向为
步长为
计算新的迭代点为
注意，也就是说 ，秩 1 算法能够在两次迭代内得到函数的极小点。方向 和 是 共轭的。
秩1算法产生的矩阵 并不一定是正定的，这将导致 可能不是下降方向。即使对于二次型问题，这种情况也有可能发生。其次，如果接近于 0 , 在计算时可能会面临一些计算上的困难。
幸运的是，还有其他一些算法能够避免这一问题。比如，秩2算法可以保证在任意第步迭代下，只要一维搜索是精确的，近似矩阵就都是正定的。
DFP算法（变尺度法）
秩2 算法最初是由Davidon 于1959 年提出的。1963 年，Fletcherr和Powell 对其进行了修改。因此，该算法称为DFP 算法，有时候也称为变尺度法。
算法步骤：
- 令 ；选择初始点 ，任选一个对称正定实矩阵 。
- 如果 ，停止迭代；否则，令 。
- 计算
- 计算
- 令 ，返回第2步。
DFP算法也是一种拟牛顿法，即利用该算法求解二次型问题，有 , 成立。
利用 DFP 算法求解二次型问题时，黑塞矩阵为 , 有 , 。
DFP算法中，只要矩阵 是正定的， 就是正定的。
DFP 算法能够使得矩阵保持正定，因此，其优于秩1 算法。但是当处理一些规模较大的二次型问题时，迭代过程中会出现矩阵非常接近成为奇异矩阵，造成迭代无法继续开展。BFGS 算法能够解决这一问题。
BFGS算法
20 世纪70 年代， Broyden、Fletcher 、Goldfard 和Shanno分别独立地提出了一种近似矩阵的更新算法，该方法被称为BFGS 算法。
黑塞矩阵逆矩阵的近似矩阵需要满足以下条件：
,
这是根据 推导出的。基于这一条件，可以构造黑塞矩阵逆矩阵 近似矩阵的更新公式，秩1算法和DFP 算法都是据此而来的。但是，除了构造 的近似矩阵，还可以构造矩阵 的近似矩阵。令矩阵 表示在第次迭代中关于矩阵的估计， 则 应该满足
可以看出， 这组方程与 应该满足的方程非常相似，唯一的区别在于 和 互换了位置。因此，给定关于 的更新公式，交换 和 的位置，并将 替换为 ，即可得到 的更新公式。在 BFGS 算法中， 矩阵 就对应于 DFP 算法中的 满足这种结构的两类公式称为对偶或互补的。
已知DFP算法中黑塞矩阵逆矩阵的近似矩阵的更新公式为
利用互补的概念，可得到黑塞矩阵近似矩阵的更新公式为
得BFGS方法中黑塞矩阵逆矩阵的近似矩阵的更新公式为
关于矩阵求逆的计算公式，谢尔曼一莫里森( Shennan-Momson) 公式：
如果矩阵 非奇异， 和 为列向量，满足，那么 非奇异，其逆矩阵可以用 表示， 如下所示：
应用谢尔曼-莫里森矩阵求逆公式，得
BFGS算法保持了拟牛顿法的共轭方向性质，也能够使近似矩阵一直保持正定。
当迭代过程中一维搜索的进度不高时，BFGS算法扔比较稳健。
多数情况下，BFGS算法效率远超DFP算法。
对于非二次型问题，也需要对拟牛顿法进行一些修正。比如，可以每经过几次迭代（ 或 ），将搜索方向重置为梯度负方向，然后继续迭代，知道满足停止规则。
例：利用 BFGS 算法求解二次型函数 的极小点。其中，
令 ，初始点 。计算结束后，可以验证 。
计算
目标函数为二次型函数，可得步长 为
因此，可得迭代点
计算 之前，首先计算
因此
接下来, 可得搜索方向和步长, 分别为
得到新的迭代点为
由于目标函数是定义在 上的二次型函数，因此 就是其极小点。目标函数在 处的梯度为, 即 。
验证 , 计算
故有
由于，因此