文档介绍：该【2022年常见的几种最优化方法 】是由【小屁孩】上传分享，文档一共【7】页，该文档可以免费在线阅读，需要了解更多关于【2022年常见的几种最优化方法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。优选文档
常见的几种最优化方法〔梯度下降法、牛顿法、拟牛顿法、共轭
梯度法等〕
我们每个人都会在我们的生活或者工作中遇到各种各样的最优化问题,比方每个企
业和个人都要考虑的一个问题“在肯定本钱下,如何使利润最大化〞等。最优化方
法是一种数学方法,它是研究在给定约束之下如何寻求某些因素(的量),以使某一(或
某些)指标到达最优的一些学科的总称。随着学****的深刻,博主越来越发觉最优化方
法的重要性,学****和工作中遇到的大多问题都可以建模成一种最优化模型进行求解,
比方我们现在学****的机器学****算法,大局部的机器学****算法的本质都是建立优化模
型,通过最优化方法对目标函数〔或损失函数〕进行优化,从而训练出最好的模型。
常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。
〔GradientDescent〕
梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法完成简单,当
目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,其解不保证是全局
最优解,梯度下降法的速度也未必是最快的。梯度下降法的优化思想是用当前位置
负梯度方向作为搜索方向,因为该方向为当前位置的最快下降方向,所以也被称为
是〞最速下降法“。最速下降法越接近目标值,步长越小,前进越慢。梯度下降法
的搜索迭代示意图如下列图所示:
梯度下降法的缺点:
〔1〕靠近极小值时收敛速度减慢,如下列图所示;
〔2〕直线搜索时可能会产生一些问题;
〔3〕可能会“之字形〞地下降。
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!
优选文档
从上图可以看出,梯度下降法在接近最优解的地域收敛速度明显变慢,利用梯度下
降法求解需要很屡次的迭代。
在机器学****中,基于根本的梯度下降法开展了两种梯度下降方法,分别为随机梯度
下降法和批量梯度下降法。
比方对一个线性回归〔LinearLogistics〕模型,假设下面的h(x)是要拟合的函数,
J(theta)为损失函数,theta是参数,要迭代求解的值,theta求解出来了那最终要
拟合的函数h(theta)就出来了。其中m是训练集的样本个数,n是特征的个数。
1〕批量梯度下降法〔BatchGradientDescent,BGD〕
〔1〕将J(theta)对theta求偏导,得到每个theta对应的的梯度:
〔2〕由于是要最小化风险函数,所以按每个参数theta的梯度负方向,来更新每个
theta:
〔3〕从上面公式可以注意到,它得到的是一个全局最优解,但是每迭代一步,都要
用到训练集全部的数据,如果m很大,那么可想而知这种方法的迭代速度会相当的
慢。所以,这就引入了其它一种方法——随机梯度下降。
对于批量梯度下降法,样本个数m,x为n维向量,一次迭代需要把m个样本全部
带入计算,迭代一次计算量为mxn2。
2〕随机梯度下降〔StochasticGradientDescent,SGD〕
〔1〕上面的风险函数可以写成如下这种形式,损失函数对应的是训练集中每个样本
的粒度,而上面批量梯度下降对应的是全部的训练样本:
〔2〕每个样本的损失函数,对theta求偏导得到对应梯度,来更新theta:
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!
优选文档
〔3〕随机梯度下降是通过每个样本来迭代更新一次,如果样本量很大的情况〔例如
几十万〕,那么可能只用其中几万条或者几千条的样本,就已经将theta迭代到最
优解了,比照上面的批量梯度下降,迭代一次需要用到十几万训练样本,一次迭代
不可能最优,如果迭代10次的话就需要遍历训练样本10次。但是,SGD伴随的
一个问题是噪音较BGD要多,使得SGD并不是每次迭代都向着整体最优化方向。
随机梯度下降每次迭代只使用一个样本,迭代一次计算量为n2,当样本个数m很
大的时候,随机梯度下降迭代一次的速度要远高于批量梯度下降方法。两者的关系
可以这样理解:随机梯度下降方法以损失很小的一局部X度和增加肯定数量的迭代
次数为代价,换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。
对批量梯度下降法和随机梯度下降法的总结:
批量梯度下降---最小化全部训练样本的损失函数,使得最终求解的是全局的最优解,
即求解的参数是使得风险函数最小,但是对于大规模样本问题效率低下。
随机梯度下降---最小化每条样本的损失函数,虽然不是每次迭代得到的损失函数都
向着全局最优方向,但是大的整体的方向是向全局最优解的,最终的结果往往是在
全局最优解附近,适用于大规模训练样本情况。
〔Newton'smethod&Quasi-NewtonMethods〕
1〕牛顿法〔Newton'smethod〕
牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数f(x)的
泰勒级数的前面几项来寻觅方程f(x)=0的根。牛顿法最大的特点就在于它的收敛
速度很快。
具体步骤:
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!
优选文档
首先,选择一个接近函数f(x)零点的x,计算相应的f(x)和切线斜率f'(x)
000
〔这里f'表示函数f的导数〕。然后我们计算穿过点(xf(x))并且斜率为f'(x)
0,00
的直线和x轴的交点的x坐标,也就是求如下方程的解:
我们将新求得的点的x坐标命名为x,通常x会比x更接近方程f(x)=0
110
的解。因此我们现在可以利用x开始下一轮迭代。迭代公式可化简为如下所示:
1
已经证明,如果f'是连续的,并且待求的零点x是孤立的,那么在零点x周
围存在一个地域,只要初始值x位于这个邻近地域内,那么牛顿法必定收敛。并
0
且,如果f'(x)不为0,,这意味着每
迭代一,牛顿法次结果的有效数字将增加一倍。下列图为一个牛顿法执行过程的例
子。
由于牛顿法是基于当前位置的切线来确定下一的位次置,所以牛顿法又被很形
象地称为是"切线法"。牛顿法的搜索路径〔二维情况〕如下列图所示:
牛顿法搜索动态例如图:
关于牛顿法和梯度下降法的效率比照:
从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。
如果更通俗地说的话,比方你想找一条最短的路径走到一个盆地的最底部,梯度下
降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,
不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,
可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。〔牛顿法目光更
加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思
想。〕
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!
优选文档
依据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所
处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况
下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最
优下降路径。
注:红色的牛顿法的迭代路径,绿色的是梯度下降法的迭代路径。
牛顿法的优缺点总结:
优点:二阶收敛,收敛速度快;
缺点:牛顿法是一种迭代算法,每一步都需要求解目标函数的Hessian矩阵的
逆矩阵,计算比拟复杂。
2〕拟牛顿法〔Quasi-NewtonMethods〕
拟牛顿法是求解非线性优化问题最有效的方法之一,于20世纪50年代由美国
Argonne国家实验室的物理学家所提出来。Davidon设计的这种算法在当时看来
是非线性优化领域X制造性的制造之一。
了这种新的算法远比其他方法快速和可靠,使得非线性优化这门学科在一夜之间突
飞猛进。
拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩
阵的缺陷,它使用正定矩阵来近似Hessian矩阵的逆,从而简化了运算的复杂度。
拟牛顿法和最速下降法一样只要求每一步迭代时了解目标函数的梯度。通过测量梯
度的变化,构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优
于最速下降法,尤其对于困难的问题。其它,因为拟牛顿法不需要二阶数的导信息,
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!
优选文档
所以有时比牛顿法更为有效。如今,优化软件中包含了大量的拟牛顿算法用来解决
无约束,约束,和大规模的优化问题。
具体步骤:
拟牛顿法的根本思想如下。首先构造目标函数在当前迭代x的二次模型:
k
这里B是一个对称正定矩阵,于是我们取这个二次模型的最优解作为搜索方向,
k
并且得到新的迭代点:
其中我们要求步长a满足Wolfe条件。这样的迭代与牛顿法类似,区别就在
k
于用近似的Hesse矩阵B
k
替代真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵B
k
的更新。现在假设得到一个新的迭代x,并得到一个新的二次模型:
k+1
我们尽可能地利用上一步的信息来选取B。具体地,我们要求
k
从而得到
这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。
〔ConjugateGradient〕
共轭梯度法是介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,
但克服了最速下降法收敛慢的缺点,又防止了牛顿法需要存储和计算Hesse矩阵并
求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大
型非线性最优化最有效的算法之一。在各种优化算法中,共轭梯度法是非常重要的
一种。其优点是所需存储量小,具有步收敛性,稳定性高,而且不需要任何外来参
数。
具体的完成步骤请参加wiki百科共轭梯度法。
下列图为共轭梯度法和梯度下降法搜索最优解的路径比照示意图:
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!
优选文档
注:绿色为梯度下降法,红色代表共轭梯度法
启发式方法指人在解决问题时所采取的一种依据经验规则进行发觉的方法。其
特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以
确定的步骤去寻求答案。启发式优化方法种类繁多,包含经典的模拟退火方法、遗
传算法、蚁群算法以及粒子群算法等等。
还有一种特别的优化算法被称之多目标优化算法,它主要针对同时优化多个目
标〔两个及两个以上〕的优化问题,这方面比拟经典的算法有NSGAII算法、MOEA/D
算法以及人工免疫算法等。
——拉格朗日乘数法
有关拉格朗日乘数法的介绍请见一另篇博客:《拉格朗日乘数法》
.
欢迎您阅读并下载本文档,本文档来源于互联网,如有侵权请联系删除!我们将竭诚为您提供优质的文档!