各种牛顿法、拟牛顿法

double f(double x) { return x * x + x * 5 - 8; } double df(double x) { double eps = 0.001; return (f(x + eps) - f(x)) / eps; } double newton(double x) { double eps = 0.000001; int times = 100; while (times--) { double x2 = x - f(x) / df(x); cout << x2 << " "; if (abs(x - x2) < eps)return x2; x = x2; } return 0; } int main() { double ans = newton(0); cout << endl << ans << " " << f(ans); return 0; }

输出：

可以看出收敛很快。

牛顿法开方：

double Sqrt(double x) { double t = x / 2; x = 1; for (int i = 0; i < 100; i++)x = x / 2 + t / x; return x; } int main() { cout << Sqrt(); return 0; }

输出1000

2，牛顿法的局限性

（1）牛顿法对于初始值有要求，而且没有很简单的方法去判断一个邻域是否已经足够小。

（2）序列{x0,x1,x2...}越来越接近x，单调有界必要极限，但是这个极限值是否一定是x，我个人不太确定，但是找到了一个课件中给出了答案：

牛顿法及其收敛性课件

结论是对于单根，|xi - x|平方收敛，但对于有重根的情况只是线性收敛。

如果知道是m重根，则可以改进公式为：

3，牛顿下山法

每取一个新值之前学习率设为1，每次取到新值之后，判断新的函数值是否更接近0，如果不是则降低学习率直到新的函数值更接近0。

在一定程度上降低对于初始值的范围要求。

double newton(double x) { double eps = 0.000001; int times = 100; double learningRate = 1; while (times--) { double x2 = x - f(x) / df(x)*learningRate; cout << x2 << " "; if (abs(x - x2) < eps)return x2; if (abs(f(x2)) < abs(f(x))) { x = x2, learningRate = 1; } else { learningRate /= 2; } } return 0; }

4，割线法

在曲线上取AB两点，求切线AB和x轴的交点C，让BC取代AB进入下一轮迭代，直到两点间距达到精度要求。

收敛定理：

5，抛物线法

二，牛顿法：最优化

参考：http://faculty.bicmr.pku.edu.cn/~wenzw/optbook/lect/11-lect-newton.pdf

1，经典牛顿法

只考虑f是二次函数：

2，修正牛顿法

算法步骤：

其中第3行即求海瑟矩阵这个对称矩阵的近似正定对称矩阵，具体参考数值分析

线搜索准则参考线搜索准则

3，非精确牛顿法

http://faculty.bicmr.pku.edu.cn/~wenzw/optbook/lect/11-lect-newton.pdf

三，拟牛顿算法

http://faculty.bicmr.pku.edu.cn/~wenzw/optbook/lect/12-lect-QN.pdf

1，割线方程

割线方程的本质是，根据s和y，求出B或H，这样就只需要计算一阶导数，不需要计算二阶导数。

2，曲率条件

由海瑟矩阵正定，可以直接推出曲率条件，即曲率条件是迭代过程中海瑟矩阵保持正定的必要条件。

如果线搜索使用Wolfe准则，那么可以证明曲率条件可以达到。

3，拟牛顿算法

下面的秩一更新和秩二更新，是用构造的方式，满足割线方程。

4，秩一更新

构造模式：

通过构造模式和割线方程联合求解，有无数解，其中一个形式简单的解：

PS：拟牛顿算法的秩一更新公式中，只需要计算矩阵乘法，不需要求逆。

第（2）条往往不能保证，所以秩一更新公式一般不用。

5，秩二更新（BFGS）

构造模式：

通过构造模式和割线方程联合求解，有无数解，其中一个形式简单的解：

拟牛顿算法的秩二更新公式也叫BFGS算法（Broyden–Fletcher–Goldfarb–Shanno algorithm）

因为Wolfe准则可以推导出曲率条件，所以比较容易满足条件（2）。

6，L-BFGS算法

Limited-memory BFGS (L-BFGS or LM-BFGS)即有限内存BFGS算法。

（1）BFGS算法的缺点

H的递推公式中，需要计算2次矩阵乘法，运算较慢。

L-BFGS的改进点在于，把H的递推公式进行变形，去掉矩阵乘法，只需要矩阵乘以向量的运算。

（2）重写BFGS迭代公式

把迭代公式的m步合成1步，并右乘▽f(x)，得到新的递推公式：

其中：

$q=V^{k-m}...V^{k-1}\bigtriangledown f(x^k)$

$\alpha _{k-i}=\rho _{k-i}(s^{k-i})^T[V^{k-i+1}...V^{k-1}\bigtriangledown f(x^k)],i=1,2,...,m$

我们定义：

$q_1=\bigtriangledown f(x^k)\\ q_i=V^{k-i+1}...V^{k-1}\bigtriangledown f(x^k),i=1,2,...,m,m+1\\ q=q_{m+1}$

那么，q和 $\alpha _i$ 的计算过程可以表示成螺旋递归（双循环递归的前半部分）：

$q_1=\bigtriangledown f(x^k)\\ \alpha _{k-i}=\rho _{k-i}(s^{k-l})^Tq_i,i=1,2,...,m\\ q_{i+1}=V^{k-i}q_i=qi-\alpha _{k-i}y^{k-i},i=1,2,...,m$

并且，主递推式可以表示成（双循环递归的后半部分）：

$r_{k-m}=H^{k-m}q\\ r_{i+1}=V_ir_i+s^i\alpha_i,i=k-m,k-m+1,...,k-1\\ H^k\bigtriangledown f(x^k)=r_k$

代入Vi的表达式，变形：

$r_{k-m}=H^{k-m}q\\ r_{i+1}=r_i-\rho_iy^i(s^i)^Tr_i+s^i\alpha_i,i=k-m,k-m+1,...,k-1\\ H^k\bigtriangledown f(x^k)=r_k$

（3）L-BFGS双循环递归

双循环递归就是计算新的递推公式的过程。

其中：

（4）L-BFGS算法

7，L-BFGS-B

L-BFGS-B是L-BFGS的扩展，支持每个x都有一个常数上下界（也可以没有其中的1个或2个界）

附上网友的博文和代码：博文代码

在论文《A LIMITED MEMORY ALGORITHM FOR BOUND CONSTRAINED OPTIMIZATION》中介绍了这种带boxed约束的最优化问题求解方法。

简单来说，无约束的拟牛顿方法是直接求出下降方向，而带boxed约束的拟牛顿方法是分2步求出下降方向，先求出柯西点，再求子空间内的最小值。无论是直接求下降方向，还是先求柯西点，都需要用到双循环递归。

（1）求柯西点

$m_k(-tg_k)=f(x_k)-g_k^Tg_kt+\frac{1}{2}g_k^TB_kg_kt^2,\: 0\leq t\leq \frac{\Delta _k}{||g_k||}$

由于Bk正定，所以当 $t=min(\frac{\Delta _k}{||g_k||},\frac{||g_k||}{g_k^TB_kg_k})$ 时取到最小值。

理论上直接按照这个公式去算出t，即可得到柯西点，但是分母的计算会比较耗时。

今天的文章各种牛顿法、拟牛顿法分享到此就结束了，感谢您的阅读。