各种牛顿法、拟牛顿法
目录
一，牛顿法：求零点
1，牛顿法（切线法）
2，牛顿法的局限性
3，牛顿下山法
4，割线法
5，抛物线法
二，牛顿法：最优化
1，经典牛顿法
2，修正牛顿法
3，非精确牛顿法
三，拟牛顿算法
1，割线方程
2，曲率条件
3，拟牛顿算法
4，秩一更新
5，秩二更新（BFGS）
6，L-BFGS算法
7，L-BFGS-B
一，牛顿法：求零点
1，牛顿法（切线法）
牛顿法，也叫牛顿迭代法、切线法，是一种迭代求解函数零点的方法。
原理：
令f(x)=0则
取，在一定的范围（x的足够小的邻域）内，x1比x0更接近所求的零点x
根据这个原理，不断的迭代，即可越来越接近x值。
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;
}输出：
1.59968 1.28782 1.27494 1.27492 1.27492
1.27492 3.2081e-12
可以看出收敛很快。
牛顿法开方：
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(1000000);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
三，拟牛顿算法
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算法
L-BFGS算法：
7，L-BFGS-B
即 L-BFGS-B是L-BFGS的扩展，支持每个x都有一个常数上下界（也可以没有其中的1个或2个界）
附上网友的博文和代码：博文 代码
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！