深入探讨无约束最优化方法：最速下降法、Newton法与修正Newton法

时间：11-15 神话故事提交错误

大家好，今天小编来为大家解答深入探讨无约束最优化方法：最速下降法、Newton法与修正Newton法这个问题，很多人还不知道，现在让我们一起来看看吧！

这里插入图片描述沿着方向进行直线搜索，确定下一个点的位置。我们将称为步长因子，它满足以下方程：

简单概括为：

为了书写方便，今后写为。

至此，我们已经大致了解了最速下降法的工作原理。那么我们如何找到步长因子呢？我们考虑特殊情况，假设我们的目标函数是正定二次函数：

目标函数对的一阶梯度:

这里引入一个定理，后续的解就是基于这个定理的方程：

定理：假设目标函数具有一阶连续偏导数。如果是，则为。

根据定理，可得。由此我们有：

由此，我们可以解出:

最速下降法的迭代点在逼近极小点的过程中走了一条曲折的路线：上一次搜索方向和上一次搜索方向总是相互垂直的，称为010- 59000。这种现象除了非常特殊的目标函数（例如等值面为球面的函数）和非常特殊的初始点外，一般都会发生。

这里插入图片描述由于锯齿现象，每次迭代的距离在极小点附近变得越来越小，所以收敛速度不快。这就是最速下降法的缺点。

Newton法

由于最速下降法速度慢，牛顿引入二阶梯度，通过求其黑塞矩阵，直接一步找到极小点。

如果目标函数对有连续二阶偏导数，且其Hesse矩阵是正定的，则可以用牛顿法求解。原理如下：

考虑从到的迭代过程。在点处，将根据泰勒级数展开到第三项，即：

由于Hesse 矩阵是正定矩阵，因此是的正定二次函数。令的一阶导数等于0，计算出的点就是最小值点。

解决方案：

是最低点的新近似点。上述公式称为牛顿迭代公式，由该公式生成的算法称为锯齿现象。当目标函数是正定二次函数时，始终等于。这表明，对于正定二次函数，牛顿法将在一次迭代中获得最优解。

现在我们从几何上直观地理解一下。我们要求目标函数的最小值为。函数经过点的等值面方程。在点处，用一个和该曲面最接近的二次曲面可以代替它（泰勒展开）。该二次曲面的方程为。当为正定时，它是一个超椭球体，而的极小点正是这个超椭球体的中心。我们使用作为最小值点的近似点。如下图：

这里插入图片描述对于具有正定Hesse矩阵的一般目标函数，由于其在极小点附近近似表现为正定二次函数，因此可以想象牛顿法在最优点附近应该具有更高的收敛速度。

修正Newton法

牛顿法的优点是收敛速度快、程序简单。但是，对于表达式复杂的目标函数，由于Hesse矩阵很难或者不可能获得，此时使用牛顿法显然是不合适的。下面介绍修改后的牛顿法：

下面的讨论仅假设可以找到Hesse矩阵。

在迭代点处，Hesse矩阵变为Newton法，搜索方向无法从线性方程组求解。本例改为，然后进行直线查找：

即用最速下降法的迭代公式代替牛顿法的迭代公式来完成本次迭代。

在迭代点处，存在Hesse 矩阵不可逆，即。此时（称为牛顿方向）即可解出。根据牛顿迭代公式，有：

上式可以理解为从点开始，沿的方向进行直线搜索，步长因子设置为1。上式是由牛顿法推导出来的，假设目标函数为二次正定。但目前的目标函数没有这个约束，所以目标函数可能会很复杂，所以不能总是保证的方向是向下的。由于步长因子被不加区别地取为1，方向（有时甚至是向下方向）不能保证为。这将根据具体情况进行处理：

一个。如果，函数是向下的，那么迭代是有效的。

b.如果是，则表示该函数没有向下走。这里讨论两种情况。

第一：当时，（是一个很小的正数）（意味着和几乎垂直，也就是说，假设得到一阶梯度和目标函数是二次正定得到的梯度方向完全不一致，也就是说假设目标函数是二次正定函数是错误的，应该取一阶梯度方向），所以牛顿方向：010 -69500是不利方向。此时更改为，然后进行新的直线搜索。

第二：表示牛顿方向为下降方向（假设目标函数为二次正定得到的一阶梯度与梯度方向的夹角小于90度，大体方向一致），此时再次进行直线搜索。否则，有时表示牛顿方向为向上方向（假设目标函数为二次正定得到的一阶梯度与梯度方向的夹角大于90度，大体方向是相反的）。更改以与牛顿方向相反的方向作为搜索方向，然后再次进行直线搜索。

我的非奇异：深度学习与高级智能决策

微信公众号名称:MultiAgent1024

微信公众号ID：主要研究分享深度学习、机器游戏、强化学习等相关内容！我们期待您的关注，欢迎共同学习、交流、共同进步！