无约束最优化(一) 最速下降法、Newton法、修正Newton法

最速下降法利用目标函数一阶梯度进行下降求解，易产生锯齿现象，在快接近最小值时收敛速度慢。Newton法利用了二阶梯度，收敛速度快，但是目标函数的Hesse矩阵不一定正定。于是出现了修正的Newton法，主要是对不同情况进行了分情况讨论。

最速下降法

最速下降法是最早的求解多元函数极值的数值方法。它直观、简单。它的缺点是，收敛速度较慢、实用性差。在点 $x_{k}$ 处，沿什么方向寻找下一个迭代点呢？显然应该沿下降方向。一个非常直观的想法就是沿最速下降方向，即负梯度方向： $p_{k}=-\nabla f(x_{k})$ 。

在这里插入图片描述

沿 $p_{k}$ 方向进行直线搜索，由此确定下一个点的位置 $x_{k+1} = x_{k} - t_{k}\nabla f(x_{k})$ ，我们将 $t_{k}$ 称为步长因子，满足以下等式：
$f\left(x_{k}-t_{k} \nabla f\left(x_{k}\right)\right)=\min _{t} f\left(x_{k}-t \nabla f\left(x_{k}\right)\right)$
简单合记为：
$x_{k+1}=l s\left(x_{k},-\nabla f\left(x_{k}\right)\right)$
为了书写方便，以后记 $g_{k}=g(x_{k})=\nabla f(x_{k})$ 。

到这里，我们已经大概知道最速下降法是怎么工作的，那这个步长因子 $t_{k}$ 到底怎么求呢？，我们考虑特殊情况，假设我们的目标函数是正定二次函数：
$f(x)=\frac{1}{2} x^{T} Q x+b^{T} x+c$
目标函数对 $x$ 的一阶梯度:
$g(x)=Qx+b$
这里引入一个定理，之后的求解就是依据这个定理的等式进行求解：

定理：设目标函数 $f(x)$ 具有一阶连续偏导数，若 $z=ls(x,p)$ ,则 $\nabla f(z)^{T}p=0$ 。

依据定理，我们可以得到 $g_{k+1}·g_{k}=0$ 。由此有：
$\begin{aligned} g_{k+1}·g_{k} & = [Q(x_{k}-t_{k}g_{k})+b]^{T}g(k)=0 \\ & = [Qx_{k}+b - t_{k}Qg_{k}]^{T}g(k)=0 \\ & = [g_{k}-t_{k}Qg_{k}]^{T}g(k)=0 \end{aligned}$
由此，可求解出 $t_{k}$ :
$t_{k}=\frac{g_{k}^{T}g_{k}}{g_{k}^{T}Qg_{k}}$
最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向 $p_{k+1}$ 与前一次搜索方向 $p_{k}$ 总是相互垂直的，称它为锯齿现象。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。

在这里插入图片描述

由于锯齿现象，在接近极小点的地方，每次迭代进行的距离变得越来越小，因而收敛速度不快，这正是最速下降法的缺点所在。

Newton法

由于最速下降法速度慢，Newton引入二阶梯度，通过求其Hesse矩阵，一步到位直接求到极小点 $x^{*}$ 。

如果目标函数 $f(x)$ 在 $R^{n}$ 上具有连续的二阶偏导数，其Hesse矩阵 $G(x)=\nabla^{2}f(x)$ 正定，那么就可以用Newton法对其进行求解了。原理如下：

考虑从 $x_{k}$ 到 $x_{k+1}$ 的迭代过程。在点 $x_{k}$ 处，对 $f(x)$ 按Taylor级数展开到第三项，即:
$f(x) \approx Q(x)=f\left(x_{k}\right)+g\left(x_{k}\right)^{T}\left(x-x_{k}\right)+\frac{1}{2}\left(x-x_{k}\right)^{T} G\left(x_{k}\right)\left(x-x_{k}\right)$
又因为Hesse矩阵 $G(x)$ 正定，所以 $Q(x)$ 是 $x$ 的正定二次函数。令 $Q(x)$ 其一阶导数等于0，求出来的点就是极小点。
$\nabla Q(x)=G\left(x_{k}\right)\left(x-x_{k}\right)+g\left(x_{k}\right)=0$
解出：
$x_{k+1}=x_{k}-G\left(x_{k}\right)^{-1} g\left(x_{k}\right)$
$x_{k+1}$ 是 $f(x)$ 极小点 $x$ 的新的近似点。上式称为Newton迭代公式，由该公式产生的算法称为Newton法。当目标函数 $f(x)$ 是正定二次函数时，有 $f(x)$ 恒等于 $Q(x)$ 。这说明：对于正定二次函数，Newton法一次迭代就会得到最优解。

现在从几何上我们来直观理解一下，我们要求目标函数 $f(x)$ 的极小值，函数 $f(x)$ 过点 $x_{k}$ 的等值面方程 $f(x)=f(x_{k})$ ,在点 $x_{k}$ 处，用一个与该曲面最密切的二次曲面来代替它(Taylor展开)，这个二次曲面的方程即是 $Q(x)=f(x)$ 。当 $G(x)$ 正定时，它是一个超椭球面， $Q(x)$ 的极小点 $x_{k+1}$ 正是这个超椭球面的中心。我们就用 $x_{k+1}$ 作为 $f(x)$ 极小点 $x^{*}$ 的近似点。如下图所示：

在这里插入图片描述

对于具有正定Hesse矩阵的一般目标函数，由于在极小点附近，它近似地呈现为正定二次函数，所以可以想见，Newton法在最优点附近应该具有较高的收敛速度。

修正Newton法

Newton法的优点是收敛速度快、程序简单。但是对于表达式很复杂的目标函数，由于其Hesse矩阵很难或不可能求出，这时显然不宜使用Newton法。下面介绍修正Newton法：

以下讨论仅假定Hesse矩阵可以求到。

在迭代点 $x_{k}$ 处Hesse矩阵 $G_{k}$ 变为不可逆，由线性方程组 $G_{k}p_{k}=-g_{k}$ 无法解出搜索方向 $p_{k}$ 。遇有此种情况，改取 $p_{k}=-g_{k}$ ，然后作直线搜索：
$x_{k+1}=ls(x_{k},p_{k})$
即用最速下降法的迭代公式代替Newton法的迭代公式，从而完成这一次迭代。
在迭代点 $x_{k}$ 处Hesse矩阵 $G_{k}$ 非奇异，即 $G_{k}^{-1}$ 存在这时可解出 $p_{k}=-G_{k}^{-1}g_{k}$ (称为Newton方向)。按Newton迭代公式，有:
$x_{k+1}=x_{k}+p_{k}$
上式可以理解为从点 $x_{k}$ 出发沿 $p_{k}$ 方向进行直线搜索，步长因子取为1。上面这个公式是Newton法中假设目标函数为二次正定而推到出来的，但是现在这个目标函数并没有这一项约束，所以目标函数可能很复杂，因而不能总保证 $p_{k}$ 的方向是下降方向，有时即使是下降方向，也会由于步长因子不加选择地取为1，而不能保证 $f(x_{k+1})< f(x_{k})$ 。对此又分情况进行处理：

a.若 $f(x_{k+1})< f(x_{})$ ,那函数是朝着下降方向去的，则该迭代有效。

b.若 $f(x_{k+1}) \leq f(x_{})$ ，则表明函数不是朝着下降方向去的，这里又分了两种情况进行了讨论

第一：当 $\left |g_{k}^{T}p_{k}\right | \leq \varepsilon \left \| g_{k} \right \| \left \|p_{k} \right \|$ ，( $\varepsilon$ 是某一很小的正数)时(说明 $p_{k}$ 与 $-g_{k}$ 几乎垂直，也就是说一阶梯度和假设目标函数为二次正定而求出的梯度方向完全不一致，也就是说明目标函数假设为二次正定函数错误，应该取一阶梯度方向)，故Newton方向 $p_{k}$ 是不利方向。这时，改取 $p_{k}=-g_{k}$ ，然后新进行直线搜索。

第二： $g_{k}^{T}p_{k} < \varepsilon \left \| g_{k} \right \| \left \|p_{k} \right \|$ 时说明Newton方向 $p_{k}=-G_{k}^{-1}g_{k}$ 是下降方向(一阶梯度和假设目标函数为二次正定而求出的梯度方向之间的夹角是小于90度的，大体方向一致)，这时重新进行直线搜索。否则，有 $g_{k}^{T}p_{k} > \varepsilon \left \| g_{k} \right \| \left \|p_{k} \right \|$ 时说明Newton方向 $p_{k}=-G_{k}^{-1}g_{k}$ 是上升方向(一阶梯度和假设目标函数为二次正定而求出的梯度方向之间的夹角是大于90度的，大体方向相反)改取Newton方向的反方向 $p_{k}=G_{k}^{-1}g_{k}$ 为搜索方向，然后重新进行直线搜索。