Machine|【下降算法】最速下降法、Newton法、共轭梯度法算法|机器学习|人工智能|Lear

文章目录

- - 1. 一维搜索
  - 2. 最速下降法
  - - 最速下降法特征
    - 最速下降法的优缺点
  - 3. Newton法
  - - 算法基本思想
    - 牛顿法和梯度下降法的效率对比
  - 4. 共轭梯度法

1. 一维搜索
最优化问题一般选择某一组变量，然后在满足一定的限制条件下，求出使目标值达到最优（最大或最小）的变量值。大部分时候，最优化问题都采用迭代计算的方式来求解。而大多数迭代下降算法都具有的共同点是在得到某次迭代点 x k x^k xk后，需要按照一定规则来确定一个方向 d k d^k dk，沿着该方向在直线上求函数的极小点得到下一个迭代点 x x xk+1 。
这样不断在一维的目标函数上，求其在各迭代点的直线方向上的极小点，直到求出问题最优解的方式就被称为一维搜索，或者线搜索。其一般过程可用如下公式表示：

文章图片

其中d k d^k dk 表示在这一步的搜索方向，步长因子λ λ λ 决定了沿着该方向前进多远，这两者共同决定了该搜索算法的好坏。一维搜索的算法有好多种，以下介绍几种常见的。
2. 最速下降法
上文中的一维搜索（ x x xk+1 =x k x^k xk +λ d k λd^k λdk）可归结为单变量函数的最优化问题，也是最速下降法的基础。其迭代过程中最重要的就是为下次迭代选择一个合适的方向 d k d^k dk。
人们利用了梯度方向是函数值增长最快的方向的思想，来让迭代点沿着负梯度方向前进，保证函数的“最速”下降。
以下直接给出公式：

文章图片

在最速下降法中，步长λ λ λ 由式子求出，是一种精确步长的搜索方式。其与梯度下降法的区别也在于此，梯度下降中的步长往往是由工程师自己预先设置好的一个固定值，因此梯度下降法只是最速下降法中的一种特殊形式。

文章图片

补充：梯度下降法容易陷入局部极小值（如下图所示）。

文章图片

形象点地说，假设有一小球要从山顶滚到山脚，那么每次沿最陡峭（梯度）的方向向下滚是最快的。
在确定了每次下降的方向的同时也需要小心地选择一个合适的步长。若是过大，可能导致迭代点发散，过小则导致收敛太慢。
最速下降法在极小化目标函数时的相邻两个搜索方向是正交的。

文章图片

【例】利用最速下降法求m i n f ( x ) = x 1 2 + 2 x 2 2 ? 2 x 1 x 2 ? 4 x 1 minf(x) = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_1 minf(x)=x12?+2x22??2x1?x2??4x1? ，取初始向量x 0 = ( 1 , 1 ) T x_0 = (1,1)^T x0?=(1,1)T。

文章图片

文章图片

最速下降法特征相邻两次迭代的方向互相垂直。

文章图片

最速下降法在两个相邻点之间的搜索方向是正交的。
最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象，锯齿现象会影响收敛速度！

文章图片

缺点：最速下降法收敛速度慢！
在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形。

文章图片

这样从任何一个初始点开始，都可以很快达到极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内可能得不到需要的结果。

最速下降法的优缺点

优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不合格。
缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。

【补充】一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。在计算的前中期使用梯度下降，而在接近极小点时使用其他算法进行迭代会是更理想的方案。
3. Newton法
此处介绍的牛顿法是其在一维搜索中的推广形式。与最速下降法一样可用于求解一般无约束的多元优化问题。其基本思想还是采用泰勒二阶展开来拟合极小点附近的函数来进行迭代：

文章图片

算法基本思想考虑从x k x^k xk 到x x x k+1 的迭代过程，在x k x^k xk 点处对函数f ( x ) f(x) f(x) 泰勒展开：

文章图片

略去高阶项，得到

文章图片

对f ( x ) f(x) f(x) 求梯度得（第三项求导后是高阶可以省略）：

文章图片

移项得：

文章图片

两边同时乘二阶导数项的逆矩阵，然后移项可得极小点：

文章图片

Newton法的计算步骤如下：

文章图片

【例】用Newton方法求 f ( x 1 , x 2 ) = x 1 2 + 25 x 2 2 f(x_1,x_2) = x_1^2 + 25x_2^2 f(x1?,x2?)=x12?+25x22? 的极小点。

文章图片

由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径（二维情况）如下图所示：

文章图片

牛顿法和梯度下降法的效率对比从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。
如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）
根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

文章图片

图中红色的是牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。
4. 共轭梯度法
共轭梯度法是基于共轭方向的一种算法。针对目标函数为二次函数的问题，其搜索方向是与二次函数系数矩阵相关的共轭方向。用这类方法求解n元二次正定函数的极小问题，最多进行n次一维搜索。

文章图片

几何意义：
假设f ( x ) f(x) f(x) 是n n n 元正定二次函数：

文章图片

对于二维情况n = 2 n=2 n=2，任任取初始点x 0 x^0 x0 沿某个下降方向d 0 d^0 d0 作精确一维搜索，得x 1 = x 0 + l a m d a 0 d 0 x^1 = x^0 + lamda_0d^0 x1=x0+lamda0?d0 。
由精确一维搜索的性质，可知：