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

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

简介

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

特点

• 收敛速度快；

方式

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

分析

考虑无约束最优化问题

$$\underset{x\in R}{\min }f(x)$$

其中$x^{\ast }$为目标函数的极小点。

假设f(x)具有二阶连续偏导数，若第k次迭代值为$x^{(k)}$，则可将f(x)在$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)$$

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

这里详解下泰勒展开式的里面的海塞矩阵，暂时讲解下二元函数的泰勒展开式

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

$$\nabla (f(x))=0$$

对f(x)求导，则

$$\nabla (f(x)=f(x^k)+g_k^T(x-x^k)+1/2(x-x^k{)}^{T}H(x^k(x-x^k)))$$

$$=g_k+H(x^k)(x-x^k)$$

则

$$g_k+H(x^k)(x^{k+1}-x^k)=0$$

$$x^{k+1}-x^k=-H(x^k{)}^{-1}{g}_k$$

或者

$$x^{k+1}=x^k+p_k$$

其中

$$H(x^k)p_k=-g_k$$

到此公式推导完毕

算法

输入：目标函数f(x)，梯度$ g(x) = \nabla f(x)$，海塞矩阵H(x)，精度要求ε；

1. 取初始值点$x^{(0)}$，k=0；
2. 计算$g_k=g(x^{(k)})$
3. 若$||g_k||<\epsilon$，则停止计算，得到解$x^{\ast }=x^{(k)}$
4. 计算$H_k=H(x^{(k)})$，并且求解$p_k$
   $$H(x^k)p_k=-g_k$$
5. 进行迭代，$x^{k+1}=x^k+p_k$，请求k++，转到第2步；

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