最优化方法-牛顿法

牛顿法 泰勒级数

泰勒级数展开 $$ \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!}fn(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 处展开 f ( x ) = lim ⁡ n → ∞ ∑ i = 1 n 1 n ! f ( n ) ( 0 ) x n = f ( 0 ) + f ′ ( 0 ) x + f ′ ′ ( 0 ) 2 ! x 2 + ⋯ + 1 n ! f n ( 0 ) x n   + O ( x n ) / f ( n + 1 ) ( ξ ) ( n + 1 ) ! x n + 1 \begin{aligned} f(x)&=\lim\limits_{n\rightarrow \infin}\sum\limits_{i=1}^n\frac{1}{n!}f^{(n)}(0)x^n\\ &=f(0)+f'(0)x+\frac{f''(0)}{2!}x^2+\cdots+\frac{1}{n!}f^n(0)x^n\\ &\quad~ + O\left(x^n\right) /\frac{f^{(n+1)(\xi)}}{(n+1)!}x^{n+1} \end{aligned} f(x)​=n→∞lim​i=1∑n​n!1​f(n)(0)xn=f(0)+f′(0)x+2!f′′(0)​x2+⋯+n!1​fn(0)xn +O(xn)/(n+1)!f(n+1)(ξ)​xn+1​ 其中

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

---

牛顿法 原理（一维情况）

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

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

牛顿法思想：使用 f ( x ) f(x) f(x) 的泰勒展开式（前几项） f ( x ) ≈ f ( x 0 ) + f ′ ( x 0 ) \begin{aligned} f(x) &\approx f(x_0)+f'(x_0) \end{aligned} f(x)​≈f(x0​)+f′(x0​)​ 不断迭代来近似寻找方程 f ( x ) = 0 f(x)=0 f(x)=0 的根。

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

迭代过程图（维基百科）

牛顿法一维情况

迭代公式

x n + 1 = x n − f ′ ( x 0 ) f ′ ′ ( x 0 ) x_{n+1} = x_n - \frac{f'(x_0)}{f''(x_0)} xn+1​=xn​−f′′(x0​)f′(x0​)​

牛顿法的推导基于二阶可微函数的泰勒展开 f ( x ) = 0 ⇉ f ( x 0 ) + f ′ ( x 0 ) ( x − x 0 ) + f ′ ′ ( x 0 ) 2 ! ( x − x 0 ) 2 = 0 两边求导 f ′ ( x 0 ) + f ′ ′ ( x 0 ) ( x − x 0 ) = 0 f ′ ′ ( x 0 ) ( x 0 − x ) = f ′ ( x 0 ) x 0 − x = f ′ ( x 0 ) f ′ ′ ( x 0 ) x = x 0 − f ′ ( x 0 ) f ′ ′ ( x 0 ) \begin{aligned} f(x)&=0\\ \rightrightarrows f(x_0)+f'(x_0)(x-x_0)&+\frac{f''(x_0)}{2!}(x-x_0)^2=0\\ \text{两边求导}\\ f'(x_0)+f''(x_0)&(x-x_0)=0\\ f''(x_0)(x_0-x)&=f'(x_0)\\ x_0-x&=\frac{f'(x_0)}{f''(x_0)}\\ x=x_0&-\frac{f'(x_0)}{f''(x_0)} \end{aligned} f(x)⇉f(x0​)+f′(x0​)(x−x0​)两边求导f′(x0​)+f′′(x0​)f′′(x0​)(x0​−x)x0​−xx=x0​​=0+2!f′′(x0​)​(x−x0​)2=0(x−x0​)=0=f′(x0​)=f′′(x0​)f′(x0​)​−f′′(x0​)f′(x0​)​​

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

对于无约束最优化问题 min ⁡ x ∈ R n f ( x ) \min _{x \in \mathbf{R}^n} f(x) minx∈Rn​f(x) ，可根据极小点的必要条件 ∇ f ( x ) = 0 \nabla f(x)=0 ∇f(x)=0 采用牛顿法求解： x k + 1 = x k − H k − 1 g k x_{k+1}=x_k-H_k^{-1} g_k xk+1​=xk​−Hk−1​gk​

其中

g k = g ( x k ) = ∇ f ( x k ) g_k=g\left(x_k\right)=\nabla f\left(x_k\right) gk​=g(xk​)=∇f(xk​) 是 f ( x ) f(x) f(x) 的梯度向量在点 x k x_k xk​ 的值;

H k = H ( x k ) H_k=H\left(x_k\right) Hk​=H(xk​), H ( x ) = [ ∂ 2 f ∂ x i ∂ x j ] n × n H(x)=\left[\frac{\partial^2 f}{\partial x_i \partial x_j}\right]_{n \times n} H(x)=[∂xi​∂xj​∂2f​]n×n​ 是 f ( x ) f(x) f(x) 的海塞矩阵(二阶偏导数矩阵)。 H ( f ) = [ ∂ 2 f ∂ x 1 2 ∂ 2 f ∂ x 1 ∂ x 2 ⋯ ∂ 2 f ∂ x 1 ∂ x n ∂ 2 f ∂ x 2 ∂ x 1 ∂ 2 f ∂ x 2 2 ⋯ ∂ 2 f ∂ x 2 ∂ x n ⋮ ⋮ ⋱ ⋮ ∂ 2 f ∂ x n ∂ x 1 ∂ 2 f ∂ x n ∂ x 2 ⋯ ∂ 2 f ∂ x n 2 ] 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} \\ \vdots & \vdots & \ddots & \vdots \\ \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] H(f)= ​∂x12​∂2f​∂x2​∂x1​∂2f​⋮∂xn​∂x1​∂2f​​∂x1​∂x2​∂2f​∂x22​∂2f​⋮∂xn​∂x2​∂2f​​⋯⋯⋱⋯​∂x1​∂xn​∂2f​∂x2​∂xn​∂2f​⋮∂xn2​∂2f​​ ​

具体步骤

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

取初始点 x 0 x_0 x0​, 置 k = 0 k=0 k=0计算 g k g_k gk​, 若 ∥ g k ∥ < ϵ \left\|g_k\right\|<\epsilon ∥gk​∥<ϵ, 则 x ∗ = x k x^*=x_k x∗=xk​, 停止计算; 否则转 (3)计算 H k H_k Hk​, 令 x k + 1 = x k − H k − 1 g k x_{k+1}=x_k-H_k^{-1} g_k xk+1​=xk​−Hk−1​gk​置 k = k + 1 k=k+1 k=k+1 ，转 ( 2 ) (2) (2)

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

---

小结

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

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

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

---