负梯度方法与Newton型方法-数值最优化方法-课程学习笔记-4

今天我们继续来学习数值最优化方法的第三章内容的后续知识

Newton方法

Newton方法是Newton方法的基础, 本节主要讨论的是基本Newton方法, 阻尼Newton方法以及修正Newton方法的构造和特性, 这类方法适合解决中小型最优化问题

基本Newton方法
对于$f(x)$如果有连续的二阶偏导数, 那么$f(x)$在当前迭代点$x_k$处有泰勒展开公式如下:
$$f(x_k+d)=f_k+g_k^{T}d+\frac{1}{2}{d}^T{G}_{k}d+o(||d|{|}^2)$$
所以在该迭代点合适的领域内我们用二次函数
$$q_k(d)\triangleq f_k+g_k^{T}d+\frac{1}{2}{d}^T{G}_{k}d$$
来近似$f(x_k+d)$
所以对于问题$\min f(x_k+d)$ 的求解就转化成了对问题$\min q_k(d)$的求解了
这里我们如果假设$G_k$正定, 则令方程组一阶导为零得: $G_{k}d=-g_k$
则: $d=-G^{-1}{g}_k$为该问题的唯一解, 我们把公式 $G_{k}d=-g_k$称作Newton方程
由这个方程得到的方向$d=-G^{-1}{g}_k$为Newton方向
以这个方向为迭代方向的最优化方法称为Newton方法

而基本Newton方法就是取全步长为固定的${\alpha }_k=1$的Newton方法, 所以基本Newton方法的步骤大致如下:

1. $x_0\in R^n,\epsilon >0,k:=0$
2. 若满足终止条件, 输出结果, 停止迭代
3. 计算$d=-G^{-1}{g}_k$
4. $x_{k+1}=x_k+d_k,k:=k+1$, 转第二步

在不引起混淆的情况下, 我们把基本Newton方法简称为Newton方法
在Newton方法中只要$G_k$是正定的, Newton方向就是下降的方向, 这是因为$g_k^T{d}_k=-g_k^T{G}_k^{-1}{g}_k<0$, 这个不等式表明Newton方向和梯度方向(上升最快的方向)成钝角, 也就是和下降最快的方向成锐角, 根据全微分公式$dz=\frac{\partial f}{\partial x}dx+\frac{\partial f}{\partial y}dy=g_k^T{d}_k<0$, 可知这个方向在整个迭代中使得函数值下降

那么接下来我们给出基本Newton方法的收敛性定理

设$f(x)\in C^2$, $f(x)$的Hesse矩阵$G(x)$满足: 存在$\beta >0$, 对任给的$x$与$y$, 有$||G(x)-G(y)||\le \beta ||x-y||$(Lipschitz条件), 若$x_0$充分接近$f(x)$的局部极小点$x^{\ast }$, 且$G^{\ast }$正定, 则Newton方法对所有的k有定义, 并以二阶收敛速度收敛

接下来我们给出证明:
首先我们提出几个概念, $g(x)$是函数的一阶导函数, 因为原函数是向量函数, 所以其导函数同样是向量函数, 而使用泰勒展开可以得到:
$$g(x_k+d)=g_k+G_{k}d+O(||d|{|}^2)$$
其中, $d=x-x_k$, 设$g_i(x)$是$g(x)$的分量, $G_{ij}(x)$是$G(x)$的元素, 我们先来使用一阶泰勒展开来推导上述展开式
首先, $g_i(x)$的展开式如下:
$$g_i(x_k+d)=g_i(x_k)+\sum _{j=1}^n{G}_{ij}(x_k+{\theta }_{i}d)d_j$$
这里${\theta }_i\in (0,1)$, ${\theta }_{i}d$表示$x_k$点向方向$d$的一小步, 近似拟合左边函数值

经过变换得到:
$$g_i(x_k+d)-g_i(x_k)-\sum _{j=1}^n{G}_{ij}(x_k)d_j=\sum _{j=1}^n[G_{ij}(x_k+{\theta }_{i}d)-G_{ij}(x_k)]d_j$$
由定理中提到的Lipschitz条件可得:
$$|G_{ij}(x)-G_{ij}(y)|\le \beta ||x-y||$$
且有:$||{\theta }_{i}d||\le ||d||,|d_j|\le ||d||$
则:
$$|g_i(x_k+d)-g_i(x_k)-\sum _{j=1}^n{G}_{ij}(x_k)d_j|\le \beta n||d|{|}^2$$
这里我们根据大O表示法的定义:
也就是说
$$|g_i(x_k+d)-g_i(x_k)-\sum _{j=1}^n{G}_{ij}(x_k)d_j|=O(||d|{|}^2)$$
则可得:
$$g_i(x_k+d)=g_i(x_k)+\sum _{j=1}^n{G}_{ij}(x_k)d_j+O(||d|{|}^2)$$
即公式$g(x_k+d)=g_k+G_{k}d+O(||d|{|}^2)$成立

若取$d=-h_k=x^{\ast }-x_k$, 且由一阶必要条件, 则由上式可得: $g^{\ast }=g_k-G_k{h}_k+O(||h_k|{|}^2)=0$

由$G(x)$的连续性可知, 存在$x^{\ast }$的一个邻域, 当$x_k$在此邻域中, 也就是说$||x_k-x^{\ast }||<\delta$时, 有$G_k$正定, $G_k^{-1}$有上界, 那么就说明第$k$次迭代存在, 对$g^{\ast }=g_k-G_k{h}_k+O(||h_k|{|}^2)=0$公式左右同时乘以$G_k^{-1}$得:
$$G_k^{-1}-h_k+O(||h_k|{|}^2)=-d_k-h_k+O(||h_k|{|}^2)=-h_{k+1}+O(||h_k|{|}^2)=0$$
也就是说:
$$h_{k+1}=O(||h_k|{|}^2)$$
有:$$h_{k+1}\le \gamma ||h_k|{|}^2$$
又因为:$||x_k-x^{\ast }||<\delta$, 则:
$$h_{k+1}\le \gamma ||h_k|{|}^2\le \gamma \delta ||h_k||$$
$x_k$充分接近$x^{\ast }$可以保证$\gamma \delta <1$, 所以:
$$||x_{k+1}-x^{\ast }||=||h_{k+1}||<||h_k||\le \delta$$
也就是说 $x_{k+1}$也在$x^{\ast }$的这一邻域内, 也就是说第$k+1$次迭代有意义, 根据数学归纳法, 我们可以知道方法对所有$k$次的迭代都有意义, 且$h_{k+1}\le (\gamma \delta {)}^{k+1}||h_k||,||h_k||\to 0$, 基本Newton方法收敛, 且由$h_{k+1}\le \gamma ||h_k|{|}^2$可知是二阶收敛

但是这个定理只能表明基本Newton方法的局部收敛性, 也就是说需要迭代点足够靠近局部极小点, 对于这个方法, 其二阶收敛性保证其在合适的初始点上会很快得收敛到极小点, 但是当初始点没有充分接近极小点的时候, 二阶导矩阵$G_k$可能会出现不正定或者是奇异的情况, 使得无法进行迭代, 即使正定, 也不能保证函数单调下降, 而每一步迭代都需要计算二阶导Hesse矩阵, 都需要解一个线性方程组, 计算量为$O(n^3)$, 这算是比较大的开销了