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

RecursiveFrog · 发表于 2022-1-25 10:38

简介

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

特点

收敛速度快；

方式

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

分析

考虑无约束最优化问题

$\min_{x \in R} f(x) \\$

其中 $x^*$ 为目标函数的极小点。假设f(x)具有二阶连续偏导数，若第k次迭代值为，则可将f(x)在附近进行二阶泰勒展开:

$f(x) = f(x^{k}) + g_{k}^{T}(x - x^{k}) + 1/2(x-x^{k})^TH(x^{k})(x - x^{k}) \\$

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

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

接着我们继续进行，函数f(x)有极值的必要条件是在极值点处的一阶导数为0，即梯度向量为0。特别是当是正定矩阵的时候，函数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})^TH(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 \\$
其中

到此公式推导完毕
算法

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

取初始值点 $x^{(0)}$ ，k=0；
计算 $g_k = g(x^{(k)})$
若 $||g_k|| < ε$ ，则停止计算，得到解 $x^* = x^{(k)}$
计算 $H_k = H(x^{(k)})$ ，并且求解 $p_k$

进行迭代， $x^{k+1} = x^{k} + p_k$ ，请求k++，转到第2步；

		自动登录	找回密码
密码			立即注册

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

本帖子中包含更多资源