用目标函数的二阶泰勒展开近似该目标函数,通过求解这个二次函数的极小值来求解凸优化的搜索方向。
这从另一个角度揭示了为什么Newton步径是好的搜索方向了。
这里我没有去查找证明过程,我觉得只要知道就可以了,因为这有助于理解最速下降方法(《凸优化(六)——最速下降法》)。
在实际应用中,牛顿法往往比梯度下降法有更少的迭代次数。
2.2已经从一个角度说明了Newton步径是好的搜索方向。
知乎问答《最优化问题中,牛顿法为什么比梯度下降法求解需要的迭代次数更少?》[2]这篇也讲了一些,其中,排名第一的引自Wiki的“从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径”,比较有说服力和概括性。
图2形象地说明了牛顿法和梯度下降法的区别,红色为牛顿方法搜索路径,绿色为梯度下降法搜索路径。
牛顿法需要计算目标函数Hessian矩阵的逆矩阵,运算复杂度太高,计算效率很低,尤其维数很大时。拟牛顿算法的核心思想用一个近似矩阵替代逆Hessian矩阵。
[1]、《凸优化》,Stephen Boyd等著,王书宁等译
[2]、 《最优化问题中,牛顿法为什么比梯度下降法求解需要的迭代次数更少?》
凸优化(一)——概述
凸优化(二)——凸集
凸优化(三)——凸函数
凸优化(四)——问题求解
凸优化(五)——回溯直线搜索
凸优化(六)——最速下降法
凸优化(七)——牛顿法
凸优化(八)——Lagrange对偶问题
2016-08-08 第一次发布
//此函数是用来求一元3次方程ax^3+bx^2+cx+d=0的解//比如 x^3-27=0,我们就可以输入1 0 0 -27,这样我们就可以得到一个解#include<iostream>#include<cmath>using namespace stdint main(){double diedai(double a,double b,double c,double d,double x)double a,b,c,ddouble x=10000.0cout<<请依次输入方程四个系数:cin>>a>>b>>c>>dx=diedai(a,b,c,d,x)cout<<x<<endlreturn 0}double diedai(double a,double b,double c,double d,double x){while(abs(a*x*x*x+b*x*x+c*x+d)>0.000001){x=x-(a*x*x*x+b*x*x+c*x+d)/(3*a*x*x+2*b*x+c)}return x}可以得到一元3次方程3个解的程序(原创,超优化): #include<iostream>#include<vector>using namespace stdvector<double >v//stl vector链型数组vector<double >::iterator it//vector迭代器int x0=5double a,b,c,ddouble abs(double y){ while(y<0) y=-y return y}double f(double x){ return a*x*x*x+b*x*x+c*x+d}double fd(double x){ return 3*a*x*x+2*b*x+c}bool u//用来判断是否重复void newton(int a1,int b1,int c1,int d1){ for(x0=-5000x0<=5000x0++)//在一个大区域中逐个点用牛顿法,可找出大多数3次方程所有根 { double x1=x0 while(abs(f(x1))>0.001) { double x=x1 x1=x-f(x)/fd(x) } for( it=v.begin()it!=v.end()it++) { if(abs((*it-x1))<0.01) {u=1 break} } if(u!=1&&x1<1000000000) { cout<<x1<< v.push_back(x1)//把已得到的解添加到vector,用于防止重复 } u=0 } }int main(){ cin>>a>>b>>c>>d newton(a,b,c,d)}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)