搜索极值
与牛顿法相同, 拟牛顿法是用一个二次函数以近似目标函数 . 的二阶泰勒展开是
-
其中, 表示 的梯度, 表示Hessian矩阵 的近似. 梯度 可进一步近似为下列形式
-
令上式等于 , 计算出Newton步长 ,
-
然后构造 的近似 满足
-
上式称作割线方程组. 但当 是定义在多维空间上的函数时, 从该式计算 将成为一个不定问题 (未知数个数比方程式个数多). 此时, 构造 , 根据Newton步长更新当前解的处理需要回归到求解割线方程. 几乎不同的拟牛顿法就有不同的选择割线方程的方法. 而大多数的方法都假定 具有对称性 (即满足 ). 另外, 下表所示的方法可用于求解 ; 在此, 于某些范数与 尽量接近. 即对于某些正定矩阵 , 以以下方式更新 :
-
近似Hessian矩阵一般以单位矩阵等作为初期值[1]. 最优化问题的解 由根据近似所得的 计算出的Newton步长更新得出.
以下为该算法的总结:
-
-
- 计算新一个迭代点下的梯度
- 令
- 利用 , 直接近似Hessian矩阵的逆矩阵 . 近似的方法如下表:
Method
|
|
|
DFP法
|
|
|
BFGS法
|
|
|
Broyden法
|
|
|
Broyden族
|
|
|
SR1法
|
|
|
与逆矩阵的关联
实现
拟牛顿法是现在普遍使用的一种最优化算法, 存在多种编程语言的实现方法。
参见
参考文献
- ^ William H. Press. Numerical Recepes. Cambridge Press. 2007: 521-526. ISBN 978-0-521-88068-8.
- ^ Robert Mansel Gower; Peter Richtarik. Randomized Quasi-Newton Updates are Linearly Convergent Matrix Inversion Algorithms. 2015. arXiv:1602.01768 [math.NA].