最优化方法-牛顿法

牛顿法

泰勒级数

• 泰勒级数展开
  $$
  \begin{aligned}

  f(x)&=\lim\limits_{n\rightarrow \infin}\sum\limits_{i=1}^{n\frac{1}{n!}f}{(n)}(x_0)(x-x_0)^n\
  &=f(x_0)+f’(x_0)(x-x_0)+\frac{f’'(x_0)}{2!}(x-x_0)^{2+\cdots+\frac{1}{n!}f}n(x_0)(x-x_0)^n\
  &\quad~ + O\left[(x-x_0)^n\right] /\frac{f^{{(n+1)(\xi)}}{(n+1)!}(x-x_0)}{n+1}

  \end{aligned}
  $$

• 麦克劳林级数展开

  泰勒展开式在 0 处展开
  $$\begin{array}{rl}f(x)& =\underset{n\to \infty }{\lim }\sum _{i=1}^n\frac{1}{n!}{f}^{(n)}(0)x^n\\ & =f(0)+f^{\prime }(0)x+\frac{f^{\prime \prime }(0)}{2!}{x}^2+\cdots +\frac{1}{n!}{f}^n(0)x^n\\ & +O\left(x^n\right)/\frac{f^{(n+1)(\xi )}}{(n+1)!}{x}^{n+1}\end{array}$$
  其中

  1. $f^{(n)}$：表示对函数$f$求 n 阶导数；
  2. $O\left(x^n\right)$ ：为佩亚诺余项，代表$x^n$的高阶无穷小，要求 $f(x)$n 阶可导；
  3. $\frac{f^{(n+1)(\xi )}}{(n+1)!}{x}^{n+1}$：为拉格朗日型余项，要求 $f(x)$ n+1 阶可导。

  ---

牛顿法

原理（一维情况）

• 假如已知函数 $f(x)$, 想要求 $f(x)=0$ 的解 (或者叫根)。
  牛顿法（Newton's method）大致的思想是:

  1. 选一个初始位置 $x_0$ （这个位置最好是在根的附近）；
  2. 在这个位置上找一个 $f(x)$ 的近似函数（通常用泰勒展开 $Q$ )；
  3. 令近似函数为 0 , 求解;
  4. 以这个解为新的位置 $x_1$;
  5. 重复上述迭代, 到第 $n$ 次迭代得到 $x_n$ ，当 $\left|x_n-x_{n-1}\right|$ 足够小, 结束。 $x_n$ 就是 $f(x)=0$ 的近似解。

• 牛顿法思想：使用 $f(x)$ 的泰勒展开式（前几项）
  $$\begin{array}{rl}f(x)& \approx f(x_0)+f^{\prime }(x_0)\end{array}$$
  不断迭代来近似寻找方程$f(x)=0$ 的根。

  设第一次迭代在 $x_0$ 处，则有
  $$\begin{array}{rl}f(x)& =0\\ \rightrightarrows f(x_0)+f^{\prime }(x_0)& (x-x_0)=0\\ f^{\prime }(x_0)(x_0-x)& =f(x_0)\\ x_0-x& =\frac{f(x_0)}{f^{\prime }(x_0)}\\ x=x_0& -\frac{f(x_0)}{f^{\prime }(x_0)}\end{array}$$
  则$f(x)=0$ 第一次迭代的近似解$x_1$为
  $$x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}$$
  由此得到第 n+1 次的迭代解为
  $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$
  由于对 $f(x)$ 的近似只是一阶展开, 因此 $x_1$ 并非 $f(x)=0$ 的解, 只能说 $f\left(x_1\right)$ 比 $f\left(x_0\right)$ 更接近0。

• 迭代过程图（维基百科）

  

• 牛顿法一维情况

  迭代公式

  $$x_{n+1}=x_n-\frac{f^{\prime }(x_0)}{f^{\prime \prime }(x_0)}$$

  牛顿法的推导基于二阶可微函数的泰勒展开
  $$\begin{array}{rl}f(x)& =0\\ \rightrightarrows f(x_0)+f^{\prime }(x_0)(x-x_0)& +\frac{f^{\prime \prime }(x_0)}{2!}(x-x_0{)}^2=0\\ \text{两边求导}& \\ f^{\prime }(x_0)+f^{\prime \prime }(x_0)& (x-x_0)=0\\ f^{\prime \prime }(x_0)(x_0-x)& =f^{\prime }(x_0)\\ x_0-x& =\frac{f^{\prime }(x_0)}{f^{\prime \prime }(x_0)}\\ x=x_0& -\frac{f^{\prime }(x_0)}{f^{\prime \prime }(x_0)}\end{array}$$

求解最优化问题（高维情况）

• 对于无约束最优化问题 ${\min }_{x\in {\mathbf{R}}^n}f(x)$ ，可根据极小点的必要条件 $\nabla f(x)=0$ 采用牛顿法求解：
  $$x_{k+1}=x_k-H_k^{-1}{g}_k$$

  其中

  1. $g_k=g\left(x_k\right)=\nabla f\left(x_k\right)$ 是 $f(x)$ 的梯度向量在点 $x_k$ 的值;

  2. $H_k=H\left(x_k\right)$, $H(x)={\left[\frac{{\partial }^{2}f}{\partial x_i\partial x_j}\right]}_{n\times n}$ 是 $f(x)$ 的海塞矩阵(二阶偏导数矩阵)。
     $$H(f)=\left[\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1^2}& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}\\ \frac{{\partial }^{2}f}{\partial x_2\partial x_1}& \frac{{\partial }^{2}f}{\partial x_2^2}& \cdots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n\partial x_1}& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}& \cdots & \frac{{\partial }^{2}f}{\partial x_n^2}\end{array}\right]$$

• 具体步骤

  输入：目标函数 $f(x)$, 梯度 $g(x)=\nabla f(x)$, 海塞矩阵 $H(x)$, 精度要求 $ϵ$ ；
  输出: $f(x)$ 的极小点 $x^{\ast }$ 。

  1. 取初始点 $x_0$, 置 $k=0$
  2. 计算 $g_k$, 若 $\Vert g_k\Vert <ϵ$, 则 $x^{\ast }=x_k$, 停止计算; 否则转 (3)
  3. 计算 $H_k$, 令 $x_{k+1}=x_k-H_k^{-1}{g}_k$
  4. 置 $k=k+1$ ，转 $(2)$

  备注: 第 (3) 步中, 涉及到 $H_k^{-1}$ 的计算, 实际应用中, 通常并不直接对 $H_k$ 进行求逆, 而是将其转化为求解线性代数方程组 $H_k{d}_k=-g_k$, 此时可根据系数矩阵 $H_k$ 的性态来选择合适的迭代法, 如预条件共轭梯度法（PCG）、代数多重网格法 (AMG) 等。

  ---

小结

• 当目标函数是二次函数时, 海塞矩阵退化成一个常数矩阵, 从任一初始点出发, 牛顿法可一步到达, 因此它是一种具有二次收玫性的算法。对于非二次函数, 若函数的二次性态较强, 或迭代点已进入极小点的邻域, 则其收敛速度也是很快的, 这是牛顿法的主要优点。

  牛顿法的迭代公式中由于没有步长因子, 是定步长迭代, 对于非二次型目标函数, 有时会使函数值上升, 即出现 $f\left(x_{k+1}\right)>f\left(x_k\right)$ 的情况, 更甚者, 可能出现迭代点列 { x k } \left\{x_k\right\} {xk​} 发散而导致计算失败的情况。为解决这个问题, 出现了“阻尼牛顿法”, 增加一个步长因子 ${\lambda }_k$, 将算法流程 (3) 中的计算公式修改为:
  $$x_{k+1}=x_k-{\lambda }_k{H}_k^{-1}{g}_k$$

  牛顿法的另一个弊病在于, 每一次迭代都要计算 $H^{-1}$, 这一步计算比较复杂, 拟牛顿法将解决这个问题。