数值计算之 牛顿法与函数极值

前言

本篇继续优化理论的算法学习，牛顿法。

最速下降法

首先回顾上次提到的梯度下降法（其实就是最速下降法）：通过求取多元函数在某个点处的梯度，沿着梯度的反方向前进，直到达到迭代停止条件。

对于多元函数（实值向量函数） f ( x ) f(\bf x) f(x)，其在 x 0 \bf x_0 x0​处的泰勒展开可表示为： f ( x ) = f ( x 0 ) + ∇ f ( x 0 ) T ( x − x 0 ) + 1 2 ( x − x 0 ) T H ( x 0 ) ( x − x 0 ) f({\bf x}) = f({\bf x_0})+{\bf \nabla} f({\bf x_0})^T({\bf x-x_0}) + \frac {1}{2} ({\bf x-x_0})^T{\bf H(x_0)}({\bf x-x_0}) f(x)=f(x0​)+∇f(x0​)T(x−x0​)+21​(x−x0​)TH(x0​)(x−x0​) 其中， ∇ , H \nabla, H ∇,H分别是函数梯度，海森矩阵。

梯度下降法直接取一阶梯度的反方向作为优化方向，因此称为最速下降法（每次迭代的方向都是下降最快的方向）。

牛顿法

回到多元泰勒展开： f ( x ) = f ( x 0 ) + ∇ f ( x 0 ) ( x − x 0 ) + 1 2 ( x − x 0 ) T H ( x 0 ) ( x − x 0 ) f({\bf x}) = f({\bf x_0})+{\bf \nabla} f({\bf x_0})({\bf x-x_0}) + \frac {1}{2} ({\bf x-x_0})^T{\bf H(x_0)}({\bf x-x_0}) f(x)=f(x0​)+∇f(x0​)(x−x0​)+21​(x−x0​)TH(x0​)(x−x0​) f ( x ) f(\bf x) f(x)的极小值处的导数应当等于 0 \bf 0 0。现在取初始点 x 0 \bf x_0 x0​，将 f ( x ) f(\bf x) f(x)在 x 0 \bf x_0 x0​处的展开式对 x \bf x x进行求导： ∇ f ( x 0 ) T + ( x − x 0 ) T H ( x 0 ) = 0 ∇ f ( x 0 ) = − H ( x 0 ) ( x − x 0 ) x = x 0 − H ( x 0 ) − 1 ∇ f ( x 0 ) {\bf \nabla} f({\bf x_0})^T+{(\bf x-x_0)}^T{\bf H(x_0)}={\bf 0} \\ {\bf \nabla}f({\bf x_0})=-{\bf H(x_0)}({\bf x-x_0}) \\ \quad \\ {\bf x} = {\bf x_0} - {{\bf H(x_0)}}^{-1} {{\bf \nabla} f{\bf(x_0)}} ∇f(x0​)T+(x−x0​)TH(x0​)=0∇f(x0​)=−H(x0​)(x−x0​)x=x0​−H(x0​)−1∇f(x0​) 这样就得到了新的 x \bf x x，这就是牛顿法。

可以给出更具体的牛顿法求极值过程：

1. 确定实值向量函数 f ( x ) f(\bf x) f(x)的初始点 x 0 \bf x_0 x0​，梯度 ∇ f {\bf \nabla} f ∇f的表达式，海森矩阵 H ( x ) \bf H(x) H(x)的表达式，终止条件 δ , ϵ \delta, \epsilon δ,ϵ
2. 计算梯度 ∇ f ( x 0 ) {\bf \nabla}f({\bf x_0}) ∇f(x0​)，如果 ∣ ∣ ∇ f ( x 0 ) ∣ ∣ < δ ||{\bf \nabla}f({\bf x_0})||{\bf H(x_0)}}^{-1} {{\bf \nabla} f{\bf(x_0)}} {\bf H(x_0)}}^{-1} {{\bf \nabla} f{\bf(x_0)}} {\bf H(x_0)}}^{-1} {{\bf \nabla} f{\bf(x_0)}} \cdot {{\bf \nabla} f{\bf(x_0)}} \\ = -{{\bf \nabla} f{\bf(x_0)}}^T {{\bf H(x_0)}}^{-T}{{\bf \nabla} f{\bf(x_0)}} \\ = -{{\bf \nabla} f{\bf(x_0)}}^T {{\bf H(x_0)}}^{-1}{{\bf \nabla} f{\bf(x_0)}} \\