拟牛顿法
在牛顿法中提到了牛顿法的两个缺陷:
- 计算黑塞矩阵的求导次数太多
- 需要计算逆矩阵(复杂度一般为 )
上面两个问题集中体现在在牛顿法的迭代公式 中的
项上.
为了避免这两个问题而仍采用类似于牛顿法的思想/迭代公式, 显然要将 替换成一个不用求逆的其他矩阵,
也即构造矩阵来对
进行近似. 我们希望得到一个好的近似,
就要在计算简便的基础上让近似矩阵(序列) 拥有尽可能多的与 相似的性质, 这启发我们先分析
具有的性质.
首先对于二阶连续可微的函数黑塞矩阵对称, 于是 首先要为对称矩阵, 即
其次, 在牛顿法中我们已经知道了使序列
收敛的一个必要条件是黑塞矩阵正定(这是使得 为下降方向的条件), 于是
还要满足正定的条件.
最后, 在共轭梯度法部分, 对于非二次型函数, 为了避免黑塞矩阵的计算,
采用了三种修正, 这些修正都在用梯度来近似黑塞矩阵,
这也启发我们用梯度来近似
由梯度得到黑塞矩阵的首选方式是Taylor展开, 于是对 在 处进行Taylor展开并代入点 得
仍记
就有
要用 来近似 就可将 满足的上式中的 替换为 即
这称之为拟牛顿条件. 令 就有
这样写在后面的计算中会更简便一些.
此时可以给出拟牛顿法的迭代公式, 即:
构造 的具体方法
上面仅仅分析了
满足的最基本性质, 而要构造出这样 并不是一件容易的事, 在给出构造 的具体该方法之前, 先给出构造 的一般思路. 思路其实很简单,
就是构造递推公式, , 这里 也是一个矩阵,
根据它的性质进行构造即可, 下面采用了矩阵的秩.
秩 修正
现在就用上面提到的思想构造
于是令
首先 也为对称矩阵.
为了更容易求出
的形式, 我们用到了矩阵的秩, 同时分解矩阵是一个不错的选择.
显然秩为
的矩阵对我们没有任何帮助, 那考虑为简单的情况, 即
的情况. 秩 矩阵常用的处理方法是秩
分解(满秩分解), 即 总可以写成 的形式, 其中 又由于 是对称阵, 因此对任意 有 ,于是
线性相关, , 把 的系数 并入 中, 可令
这样就得到了秩
修正公式: 现在要用
所满足的条件确定项 注意在真正的迭代过程中
是已知条件.
由拟牛顿条件知 于是 注意到
是个标量, 则 令
再回代入 中有 也即 因此 因此 需要注意的是我们最终目的是求出 所以 包括设出的 都没有必要求出来.
因此最终的迭代公式为
性质分析
秩
修正的可行方向不一定是下降方向.
在 正定的条件下, 满足 时,
正定.
DFP算法(秩 修正)
DFP算法由Davidon1959年提出. 1963年，Fletcher和Powell进行了修改.
秩 修正的 不一定正定, 这显然不是我们想要的,
现在要来思考怎么修正秩 修正来保证
的正定性. 先直接给出秩 修正.
秩 修正中,
现在不妨让 但是并不采用满秩分解,
而是借助下面的引理写成两个秩为
的矩阵的和.
引理1 秩为
的矩阵可以表示为 个秩为 的矩阵之和，但是不能表示为少于 个秩为 的矩阵之和.
因此可以得到秩
修正公式/DFP算法迭代公式:
现在求出项 和
思路和秩 修正迭代公式求法差不多.
将迭代公式代入拟牛顿条件得到 这里面有
两个未知的向量, 因此该方程有无穷多组解, 那我们只需要找到一组特解即可.
这特解很容易找, 不妨令 同样地, 根据 可设 分别回代入上述方程组可得 于是 于是得到DFP算法的迭代公式为
性质分析
若 正定, 则 DFP 算法得到的
一定也是正定的.
PROOF 对任意 有 于是 定义内积 则由Cauchy-Schwartz不等式有 因此 这就是要证的.
BFGS算法
BFGS 算法有 Broyden, Fletcher, Goldfrab, Shanno 提出, 所以称为 BFGS
算法.
BFGS 算法和 DFP 算法几乎一致, 只不过 DFP 算法沿用秩 1 修正对 进行近似, 而 BFGS 是直接对
进行近似, 设近似的矩阵为
, 现在也用秩 2 修正, 有 采用几乎一致的思路, 可以得到 相比 DFP 算法的结果, 实际上就是把 和 互换位置, 把 换成 即可. 现在需要求 , 需要用到
Shermann-Morrison-Woodbury 公式:
已知
非奇异, 设 则
需要保证 成立.
等于 加上两个秩 1 矩阵, 因此计算 要应用两次
Shermann-Morrison-Woodbury 公式, 计算十分繁琐, 这里给出最终的公式:
L-BFGS
L-BFGS 又称为限制内存 BFGS 算法, 这里限于篇幅仅介绍其思路,
不给出具体的算法.
计算 需要提前将 算出来后存起来, 这里需要 的内存消耗.
考虑将上述递推公式展开, 这样 的计算实际上需要的是向量
这 个向量, 如果只存向量就只需要 的内存, 同时对于大部分情况而言
BFGS 的迭代次数非常少(具有介于牛顿法和梯度下降法之间的收敛率),
所以所需要的内存就会远少于存矩阵的内存.
具体细节的实现会有所不同, 总之就是通过提前展开将存矩阵转化成了存向量,
降低了内存消耗.
参考细节是这篇文章.
