3
常用优化方法及其原理
source link: https://liangyaorong.github.io/blog/2017/%E5%B8%B8%E7%94%A8%E4%BC%98%E5%8C%96%E6%96%B9%E6%B3%95%E5%8F%8A%E5%85%B6%E5%8E%9F%E7%90%86/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
常用优化方法及其原理
若从x=0开始迭代,一阶导为1,二阶导=0,因此它会不知道往哪走,干脆就原地不动了,因此它不会收敛;
若从x=0.5开始迭代,一阶导>0,二阶导<0,因此它会往右走,最后到达极大值点;
若从x=-0.5开始迭代,一阶导>0,二阶导>0,因此它会往左走,最后到达极小值点;
上面讲的梯度下降法,我们提到它是用一阶泰勒展开来证明的 我们看一下它一阶泰勒展开是什么样子: 那如果我们用二阶泰勒展开,又会得到什么呢?我们来看一下 泰勒展开的实质是用多项式去逼近原函数. 对于梯度下降法,它只用了一阶泰勒展开,只有一次多项式的信息,因此要找到极值点只能通过方向导数,或者说斜率来寻找. 而对于二阶泰勒展开,我们有了二次多项. 二次多项式有个特点就是,它包含了极点的信息.由于该二次多项式是原函数的逼近,因此找到二次多项式的极值位置就能大概知道原函数的极值位置! 那我们在每次迭代中找近似函数的极值点就好了. 这样的优化可不是一星半点.我们可以想象,梯度下降就是往周围坡度最陡的方向一步一步走;而牛顿法是根据参照物直接找到了谷底大概在哪,然后一下子就跳了过去. 因此,牛顿法的收敛速度一般比梯度下降法快. 直观的看就是这样: 图中展示了 在x=0.7处的泰勒展开.从x=0.7开始迭代,实际极大值点在C.步长设为0.1
显然牛顿法收敛更快. 牛顿法的导出 根据上面的分析,我们进行下面推导
看,迭代公式出来了,就是 牛顿法流程 牛顿法的收敛性 非常值得注意的是,牛顿法的最后结果与初始值的选取有很大关系. 从算法提出过程来看,牛顿法是每次迭代都是为了到达近似函数的极值点,因此可能到达极大值点,也可能到达极小值点. 从迭代目标公式可以看到,迭代方向由”负梯度”与”海赛矩阵”共同构成,因此若海赛矩阵非正定,目标函数值可能会上升.若初始点远离极值点,也可能不收敛.
举个简单的例子,上面的若从x=0开始迭代,一阶导为1,二阶导=0,因此它会不知道往哪走,干脆就原地不动了,因此它不会收敛;
若从x=0.5开始迭代,一阶导>0,二阶导<0,因此它会往右走,最后到达极大值点;
若从x=-0.5开始迭代,一阶导>0,二阶导>0,因此它会往左走,最后到达极小值点;
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK