4 无约束具体算法
【机器学习之数学】02 梯度下降法、最速下降法、牛顿法、共轭方向法、拟牛顿法 - wuliytTaotao - 博客园 (cnblogs.com)
4.1最速下降法
梯度方向
- 某点的梯度方向为该点的等值线的法线方向。
- 沿着梯度方向增加最快,负梯度方向下降最快。
最速下降法就是沿着负梯度方向进行,下面列出它的一般算法。
一个求偏导公式的推导
最优步长公式的推导
一维搜索(线性搜索)
- 非精确一维搜索,就是找到一个alpha满足一定条件即可,好比Wolfe-Powell,Armijo, goldstein条件。
- 精确一维搜索,就是找到一个参数α,使得min:f(x+αd),有插值法,黄金分割法,直接法等等
缺点
由于最速下降法在相继两次迭代中,搜索方向是相互正交的,可见逼近极小点的路线是锯齿形,而且越靠近极小点步长越小,即越走越慢。
收敛速度较慢,所以它不是使用的算法。
4.2 共轭梯度法
简单举个例子
向量( 1 , 2 , 3 ) T 关于3阶单位方阵的所有线性无关的共轭向量有_________?
这个期末只要求了解共轭梯度,并未要求计算。在我看来,其余上面梯度下降法最明显的差异就是采用了共轭方向进行迭代。
4.3 牛顿法
最速下降法本质是用线性函数去近似目标函数,收敛速度较慢,若考虑用二次函数近似目标函数则可以得到收敛速度更快的算法,下面写的牛顿法就是如此。
这里需要计算黑塞矩阵以及求逆的过程。
4.4 拟牛顿法
参考开头的博文链接。
5 约束优化算法
5.1 KKT
参考下面这篇文章
与KKT有关的一篇相关博文
5.2 例子
参考资料
1【书籍】最优化方法——李学文 闫桂峰
2 【书籍】最优化方法基础——专祥涛