繁依Fanyi0

这个屌丝很懒，什么也没留下！

热门标签

牛顿法

作者：繁依Fanyi0 | 2024-03-01 20:39:17

踩

牛顿法

牛顿法是一种经典的优化算法，本文主要介绍牛顿法的基本原理。

定义一元函数： $\phi(.):R \rightarrow R$ ,考虑等式： $\phi(t^*)=0$ , 通过线性近似可获得牛顿法的更新规则。

假设已知 $t$ 靠近最优解 $t^*$ ,在 $t$ 处对函数 $\phi(.)$ 做一阶泰勒展开有：

$\phi(t+\Delta t)=\phi(t)+\phi'(t)\Delta t+o(|\Delta t|)$ ,

则 $\phi(t+\Delta t)=0$ 可近似为：

$\phi(t)+\phi'(t)\Delta t=0$ 。

若将该方程看作一个系统，则可将其称为牛顿系统。在某些条件下，若将 $\Delta t$ 视作最优 $\Delta t^*=t^*-t$ 的近似，则有：

$t_{k+1}=t_k-\frac{\phi(t_k)}{\phi'(t_k)}$ , (1)

式（1）即为牛顿法的更新规则，该方案可进一步扩展至寻找非线性方程组（非线性系统）的解。

定义非线性方程组： $F(x)=0$ , 其中， $x \in R^n$ , $F(.):R^n \rightarrow R^n$ 。

与一元函数类似，构建牛顿系统：

$F(x)+F'(x)\Delta x=0$ ，

式中， $F'(x)$ 可视为Jacobian矩阵，若该矩阵满秩（不退化），则 $\Delta x$ 可表示为：

$\Delta x=-[F'(x)]^{-1}F(x)$ , (2)

因此，相应的迭代规则可表示为：

$x_{k+1}=x_k-[F'(x)]^{-1} F(x)$ 。 (3)

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

上述牛顿法的基本原理可进一步推广至求无约束最小化问题。即想通过 $\nabla f(x)=0$ 来求解极值的问题。

与一元函数时 $\phi(t)+\phi'(t)\Delta t=0$ 类似，在非退化情况下，如果想通过 $\nabla f(x)=0$ 来求解非线性系统，利用牛顿法可构建如下牛顿系统：

$\nabla f(x)+ \nabla^2 f(x) \Delta x=0$ ,

该式可进一步写为：

$x_{k+1}=x_k-[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$ （4）

如果想通过二阶泰勒近似来获得式（4）中的结果应该如何操作呢？

假设给定非线性函数 $\phi(x)$ ,在 $x_k$ 处的二阶泰勒可近似为：

$\phi(x)=f(x_k)+\langle \nabla f(x_k),x-x_k \rangle+\frac{1}{2} \langle \nabla^2f(x_k)(x-x_k),x-x_k\rangle$ ,

若 $\nabla^2f(x_k)>0$ （Hessian矩阵正定）， $x_{k+1}$ 为函数 $\phi(x)$ 的一个极小值， $\phi(x)$ 对 $x_{k+1}$ 求导有：

$\nabla \phi(x_{k+1})=\nabla f(x_k)+\langle \nabla^2 f(x_k), x_{k+1}-x_k \rangle =0$ ,

对该式进行整理即可得出式（4)中的结果。

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------

接下来介绍一个简单的例子来说明牛顿法的特点：

例：考虑一元函数:

$\phi(t)=\frac{t}{\sqrt{1+t^2}$ ,

显然，该函数的根 $t^*=0$ 。

其一阶导为：

$\phi'(t)=\frac{1}{(1+t^2)^{3/2}}$ ,

式（1）可表达为：

$t_{k+1}=t_k-\frac{\phi(t_k)}{\phi'(t_k)}=-t^3_k$ 。

因此，若初始位置 $|t_0|<1$ ,则牛顿法可快速收敛至 $t^*=0$ ；

若 $|t_0|=1$ ,此时牛顿法将一直振荡，无法收敛；

若 $|t_0|>1$ ,此时牛顿法将发散。

----------------------------------------------------------------------------------------------------------------------------------------------------------------------

总结：

牛顿法在最优点附近收敛很快，但其存在两个缺点：

1）牛顿法要求 $\nabla^2 f(x_k)$ 是非退化的，在实际应用中，这一条件往往不容易满足；

2）牛顿法很容易受到初始位置的影响，不理想的初始条件可能会导致牛顿法发散；

参考文献：Yurii Nesterov, Lectures on Convex Optimization,2010.

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/176759