Kuang Algorithm Engineer&Data Mining Engineer

优化算法——牛顿法和拟牛顿法

2017-12-02
Kuang
ML

牛顿法和拟牛顿法常用于无约束最优化问题 ,优点是收敛速度快。

牛顿法

对于有约束最优化问题,可以使用拉格朗日乘子法构建极大极小或者极小极大问题,再求最优解。而对于无约束最优化问题,常用牛顿法或者拟牛顿法解决。

对于无约束最优化问题

其中$x^*$ 为目标函数的的极小值点。

进行二阶泰勒展开(假设能展开) ,结果为(多元函数的泰勒展开)

其中, 处的梯度向量。 处对应的Hessian矩阵。

函数 有极值点的必要条件是在极值点处一阶导数为0, 即梯度向量为0. 当 为正定矩阵时,函数 的极值为极小值。

目标就是找到使梯度向量为0的点。每次迭代从 开始,求目标函数的极小点,第k+1次迭代值 ,假设 满足

进行求导(对二阶泰勒展开式求导)可得

,综合(3).(4)得

, 有

用式(6) 作为迭代公式的算法就是牛顿法。

牛顿法算法流程

输入:目标函数 ,梯度 ,Hessian矩阵 ,精度要求

输出: 的极小值点

  • 取初始点 ,

  • 计算

  • ,则得到近似解 , 结束

  • 否则计算 , 并求

  • , k=k+1 ,转第二步

拟牛顿法

事实上,求hessian矩阵的逆矩阵比较复杂,因此相办法找一个矩阵 来代替hessian矩阵

Hessian矩阵需要满足的条件

根据公式(4),取

, ,有

或者

称(9)或(10)为拟牛顿条件。

正定时,可以保证牛顿法的搜索方向 是下降方向而不是上升方向。有

处的泰勒展开式可以写作

由于 正定,故有 ,当 为一个充分小的正数时,总有 , 也就是说, 是下降方向。

综上, 应当满足两个条件

  • 为正定矩阵

因此要找到一个 近似 ,应当满足同样的条件。

按照拟牛顿条件选择 作为 的近似或选择 作为 的近似算法称为拟牛顿法,按照拟牛顿条件,每次迭代中可以选择更新矩阵 :

DFP算法

迭代 的方法是,假设每一步迭代中矩阵 是由 加上两个附加项构成的,即

其中 是待定矩阵,这时

为使 满足拟牛顿条件,可使 满足

可以取

该算法称为DFP算法,可以证明,如果初始矩阵 为正定矩阵,则迭代过程中每个矩阵 都是正定。

DFP算法流程

输入:目标函数 ,梯度 ,精度要求

输出: 的极小点

  • 选定初始点 ,取 为正定对称矩阵,置

  • 计算

  • ,则得到近似解 , 结束

  • 否则,置

  • 一维搜索:求得 使

  • 计算 ,若 ,则停止计算,得到近似解 , 否则按照公式(13)计算

  • k=k+1 ,转第二步

BFGS 算法

BFGS算法类似于DFP算法,只不过它是用 逼近Hessian矩阵


Comments