最速下降法&牛顿法求极值推导

最速下降法推导过程

1. 一阶泰勒展开近似

在 x=x_n 处做一阶泰勒展开近似：

f\left(x_n+\Delta x\right) \approx f\left(x_n\right)+ \nabla f\left(x_n\right)^{T} \Delta x

其中：

  • \nabla f(x_n) 是 f(x) 在 x_k 处的 梯度向量

问题转化为：
Δx^* = \arg \min (f\left(x_n\right)+ \nabla f\left(x_n\right)^{T} \Delta x)
除去无关项：
Δx^* = \arg \min (\nabla f\left(x_n\right)^{T} \Delta x)

2. 求下降方向

\nabla f\left(x_n\right)^{T} \Delta x 是两个向量的内积，根据 柯西不等式，当两个向量方向相反时，其内积最小。因此得：

Δx^* = -\nabla f(x_n)

最速下降法优点

  • 相比牛顿法时间复杂度低，只计算梯度向量，不用计算海森矩阵

最速下降法缺点

  • 有时下降路径会呈Z字形，收敛速度比牛顿法慢

牛顿法推导过程

1. 二阶泰勒展开近似

在 x=x_n 处二阶泰勒展开：
f(x_n+Δx) =f(x_{n}) +∇f(x_{n})Δx +\frac{1}{2} Δx^T H Δx +o(Δx)^{2}\

得近似表达：
f(x_n+Δx) ≈f(x_{n}) +∇f(x_{n})Δx +\frac{1}{2} Δx^T H Δx

其中：

  • ∇f(x_{n}) 为函数 f(x) 在 x_n 处的 梯度向量
  • H 为函数 f(x) 在 x_n 处的 海森矩阵

2. 求极值

令：
g(Δx) =f(x_{n}) +∇f(x_{n})Δx +\frac{1}{2} Δx^T H Δx

问题转换为求一个 Δx 使 g(Δx) 最小：
Δx^*=\arg \min (f(x_{n})+∇f(x_{n})Δx+\frac{1}{2} Δx^T H Δx)

将问题转化为导数=0：

g^{\prime}(x) =∇f(x_n) +HΔx =0

得：
Δx=-H^{-1}∇f(x_n)

牛顿法优点

  • 收敛速度比最速下降法快

牛顿法缺点

  • 需要目标函数 f(x) 具备一阶、二阶导数。
  • 需要 f(x) 的海森矩阵为正定矩阵，当海森矩阵为正定矩阵时，最小值才存在。牛顿法经常会因为海森矩阵不正定而发散。
  • 求海森矩阵的计算难度大
  • 求海森矩阵的逆的计算难度大
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

  • 机器学习中常用的优化算法总结
    [TOC]优化算法是机器学习中的“方法论”，优化算法会告诉机器应该如何优化学习的进程，让自己能够更好地掌握学习到的...
    JuneHsia阅读 8,304评论 0赞 0
  • 梯度下降法与牛顿法
    梯度下降和牛顿法的推导均与泰勒公式有关，所以先介绍泰勒展开公式：基本形式： 上面这个迭代形式将应用到下面的梯度下降...
    小松qxs阅读 16,050评论 1赞 10
  • 机器学习常见的优化算法
    1 梯度下降法 梯度：如果函数是一维的变量，则梯度就是导数的方向；如果是大于一维的，梯度就是在这个点的法向量，并指...
    Bobby0322阅读 9,711评论 0赞 11
  • [机器学习必知必会]牛顿法与拟牛顿法
    前言 同梯度下降法一样，牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法，每一步需要求解...
    TOMOCAT阅读 4,629评论 0赞 0
  • 牛顿下降法和梯度下降法基础
    前言 学习机器学习一直是用梯度下降法的，对于牛顿下降法并没有什么了解，但是小学期同学的一个项目用到了牛顿下降法，同...
    WZFish0408阅读 12,022评论 0赞 12

友情链接更多精彩内容