混合牛顿法

综述

所谓混合牛顿法¹是指结合牛顿法和梯度下降法的特点，若牛顿方向可行，则使用牛顿法进行迭代，若不行，则使用梯度下降法确定搜索方向。
具体搜索方向选取的逻辑可以是这样的：
$$ \begin{align} &if\ \nabla^2 f(x_k)正定,则\quad d_k=-\nabla^2f(x_k)^{-1}\nabla f(x_k)\\ &if\ \nabla^2f(x_k)负定,则\quad d_k=\nabla^2f(x_k)^{-1}\nabla f(x_k)\\ &else\ \quad\quad d_k=-\nabla f(x_k) \end{align} $$

细节说明

Hessian矩阵

关于Hessian矩阵（$\nabla^2 f(x_k)$）的正定性说明²。
简单地说，如果Hessian矩阵正定，则

1. 函数的二阶偏导数恒 > 0
2. 函数的变化率（斜率）即一阶导数始终处于递增状态
3. 函数为凸

牛顿法

牛顿法求解方程近似解

若求解$f(x)=0$在$\mathbb R$上的解$x^*$，通过选取迭代初值$x_0$，使用牛顿迭代公式逼近$x^*$。
$$ x_{t+1}=x_t-\frac{f(x_t)}{f'(x_t)} $$ 将​$f(x)$在迭代初值$x_0$​处Taylor展开可得： $$ f(x)=f(x_0)+f'(x_0)(x-x_0)+o(|x-x_0|) $$ 舍去高阶项，可得： $$ f(x)=f(x_0)+f'(x_0)(x-x_0) $$ 将零点$x^*$代入可得： $$ f(x^*)=0=f(x_0)+f'(x_0)(x^*-x_0) \\ x^*=x_0-\frac{f(x_0)}{f'(x_0)} $$ 由于上式是舍去了高阶项后的近似，因此我们实际上并不能根据上式一步得到$x^*$​。而要通过多步迭代，由此得到牛顿迭代方程： $$ x_{t+1}=x_t-\frac{f(x_t)}{f'(x_{t})} $$

牛顿法在最优化上的应用

对于一阶可微的函数​$f:\mathbb R\to\mathbb R$ ，根据费马定理，其极值点$x^*$​满足$f'(x^*)=0$，而最优化方法的目的也就是通过种种手段，求出或近似这个极值点$x^*$。注意到牛顿法是用来求解函数$g(x)$​的一个零点的近似值​$\hat x$的，而最优化则是求解导数的零点的近似解，那么令$g(x)=f'(x)$​，迭代出来的​$\hat x$不就是极值点$x^*$​的近似解了吗？

因此，使用牛顿法优化函数$f$的迭代方程也就呼之欲出了： $$ x_{t+1}=x_t-\frac{g(x_t)}{g'(x_t)}=x_t-\frac{f'(x_t)}{f''(x_t)}=x_t-f''(x_t)^{-1}f'(x_t) $$ 当然，这需要​$f$是二阶可导的，此处就默许我们研究的函数足够正定。

上述为一维输入的情形，对于​$f:\mathbb R^n\to\mathbb R$也有类似的迭代式： $$ x_{t+1}=x_t-\nabla^2f(x_t)^{-1}\nabla f(x_t)\quad\quad x_t\in\mathbb R^n\ $$ 其证明方法和一维情形几乎一致。

牛顿法优化函数算法过程

牛顿法优化函数的算法： $$ \begin{align} 选定&迭代初值x_0\in\Omega,选取\epsilon>0,重复以下操作:\\ &若||\nabla f(x_t)||<\epsilon，停止循环\\ &计算梯度:\nabla f(x_t)\\ &计算Hessian矩阵:\nabla^2f(x_t)\\ &计算方向:d_t=-\nabla^2f(x_t)^{-1}\nabla f(x_t)\\ &更新迭代点:x_{t+1}=x_t-d\\ \end{align} $$

与梯度下降法比较

牛顿法： $$ x_{t+1}=x_t-\nabla^2f(x_t)^{-1}\nabla f(x_t) $$ 梯度下降法： $$ x_{t+1}=x_t-\gamma\nabla f(x_t) $$ 可以发现，这两个方法都是基于当前迭代点的梯度信息进行搜索方向的选择的，只不过梯队下降法是在梯度的反方向上进行线搜得到下一个迭代点，而牛顿法则是通过Hessian矩阵在梯度上进行线性变换得到搜索方向（甚至步长都不需要确定）。
所以牛顿法对函数在迭代点处的信息利用更加充分，直观来看，相比于梯度下降法，函数足够正则的情况下牛顿法迭代得更加准确，收敛速率也会更快。

所有基于梯度的迭代方程可以写成如下的形式： $$ x_{t+1}=x_t-H(x_t)\nabla f(x_t) $$ 其中$x\in\mathbb R^n,H(x_t)\in\mathbb R^{n\times n}$。

对于牛顿法来说，$H(x_t)=\nabla^2f(x_t)^{-1}$

对于梯度下降法来说，$H(x_t)=\gamma I$

可以看到，牛顿法$H$的​是随着当前迭代点的变化动态变化的，因此，相比于梯度下降法，牛顿法具有更加灵活的迭代过程。有的书上直接说牛顿法就是“自适应的梯度下降法”。

参考