白话机器学习-最优化方法-牛顿法
发布日期:2021-10-10 05:31:08 浏览次数:10 分类:技术文章

本文共 1955 字,大约阅读时间需要 6 分钟。

白话机器学习-最优化方法-牛顿法


文章目录

简介

牛顿法,英文名称BFGS,是求解非线性优化问题的最有效的方法之一。

特点

  • 收敛速度快;

方式

  • 牛顿法是迭代算法,每一步需要求解目标函数的***海塞矩阵***的逆矩阵,计算比较复杂(后续会讲解拟牛顿法,拟牛顿法通过正定矩阵近似海塞矩阵的逆矩阵或海塞矩阵,简化了这个过程。

分析

考虑无约束最优化问题
min ⁡ x ∈ R f ( x ) \min_{x \in R} f(x) xRminf(x)
其中 x ∗ x^* x为目标函数的极小点。
假设f(x)具有二阶连续偏导数,若第k次迭代值为 x ( k ) x^{(k)} x(k),则可将f(x)在 x ( k ) x^{(k)} x(k)附近进行二阶泰勒展开:
f ( x ) = f ( x k ) + g k T ( x − x k ) + 1 / 2 ( x − x k ) T H ( x k ) ( x − x k ) f(x) = f(x^{k}) + g_{k}^{T}(x - x^{k}) + 1/2(x-x^{k})^TH(x^{k})(x - x^{k}) f(x)=f(xk)+gkT(xxk)+1/2(xxk)TH(xk)(xxk)

  • $g_k = g(x^{k})= \nabla(f(x^{k})) 是 f ( x ) 的 梯 度 向 量 在 是f(x)的梯度向量在 f(x)x^{(k)}$的值。
  • H ( x k ) H(x^{k}) H(xk)是f(x)的海塞矩阵 $ [\frac {\partial f^2} {\partial x_i \partial y_j}]_{nxn} 在 在 x^{(k)}$的值。

这里详解下泰勒展开式的里面的海塞矩阵,暂时讲解下二元函数的泰勒展开式
enter image description here

接着我们继续进行,函数f(x)有极值的必要条件是在极值点处的一阶导数为0,即梯度向量为0。特别是当 H ( x k ) H(x^{k}) H(xk)是正定矩阵的时候,函数f(x)的极值为极小值,所以:
∇ ( f ( x ) ) = 0 \nabla(f(x)) = 0 (f(x))=0

对f(x)求导,则
∇ ( f ( x ) = f ( x k ) + g k T ( x − x k ) + 1 / 2 ( x − x k ) T H ( x k ( x − x k ) ) ) \nabla(f(x) = f(x^{k}) + g_{k}^{T}(x - x^{k}) + 1/2(x-x^{k})^TH(x^{k}(x - x^{k}))) (f(x)=f(xk)+gkT(xxk)+1/2(xxk)TH(xk(xxk)))
= g k + H ( x k ) ( x − x k ) = g_k + H(x^{k})(x - x^{k}) =gk+H(xk)(xxk)

g k + H ( x k ) ( x k + 1 − x k ) = 0 g_k + H(x^{k})(x^{k+1} - x^{k}) = 0 gk+H(xk)(xk+1xk)=0
x k + 1 − x k = − H ( x k ) − 1 g k x^{k+1} - x^{k}= -H(x^k)^{-1}g_k xk+1xk=H(xk)1gk
或者
x k + 1 = x k + p k x^{k+1} = x^{k} + p_k xk+1=xk+pk
其中
H ( x k ) p k = − g k H(x^k)p_k = -g_k H(xk)pk=gk
到此公式推导完毕

算法

输入:目标函数f(x),梯度$ g(x) = \nabla f(x)$,海塞矩阵H(x),精度要求ε;
输出:f(x)的极小点x^*;

  1. 取初始值点 x ( 0 ) x^{(0)} x(0),k=0;
  2. 计算 g k = g ( x ( k ) ) g_k = g(x^{(k)}) gk=g(x(k))
  3. ∣ ∣ g k ∣ ∣ < ε ||g_k|| < ε gk<ε,则停止计算,得到解 x ∗ = x ( k ) x^* = x^{(k)} x=x(k)
  4. 计算 H k = H ( x ( k ) ) H_k = H(x^{(k)}) Hk=H(x(k)),并且求解 p k p_k pk
    H ( x k ) p k = − g k H(x^k)p_k = -g_k H(xk)pk=gk
  5. 进行迭代, x k + 1 = x k + p k x^{k+1} = x^{k} + p_k xk+1=xk+pk,请求k++,转到第2步;

转载地址:https://blog.csdn.net/qq_22054285/article/details/79045309 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:白话机器学习-线性模型之线性回归
下一篇:白话机器学习-最优化方法-梯度下降法

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.67.29.69]2022年12月05日 06时44分14秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章