《最优化：最速下降法和Newton法【业界研究】.ppt》由会员分享，可在线阅读，更多相关《最优化：最速下降法和Newton法【业界研究】.ppt（34页珍藏版）》请在三一文库上搜索。
1、最优化,主讲：刘陶文,课件制作：刘陶文,唯楚有材 於斯为盛,学好最优化，走遍天下都不怕,1,深层分析,第三章 无约束问题算法(I) 最速下降法、 Newton法,第一节 最速下降法 第二节 Newton法及其修正形式,2,深层分析,3,深层分析,第一节 最速下降法,1、 思想 ：每次沿负梯度方向进行搜索,最古老的优化方法，十九世纪中叶由Cauchy提出,4,深层分析,负梯度方向也称为最速下降方向：,以负梯度为搜索方向的算法称为最速下降法,5,深层分析,2、 算法步骤,最优化算法看来是如此的简单？,6,深层分析,7,深层分析,事实上，上面的例子刻画了最速下降法的所有收 敛特征,8,深层分析,3、
2、 最速下降法的收敛性,全局收敛性,9,深层分析,收敛速度估计,10,深层分析,11,深层分析,从上图可以看出，最速下降法 具有锯齿现象,12,深层分析,对一般的非二次函数有下面的收敛速度估计：,定理的证明参见文献19,定理3.4,13,深层分析,由上面的分析可知，最速下降法的收敛速度 比较慢，通常将其用在某些算法的初始阶段求较 好的初始点或作为某些算法的间插步.,思考题：,有点难啊,14,深层分析,15,深层分析,16,深层分析,第二节 Newton法及其修正形式,1、思想：用近似二次函数的极小点作为原问题的新的近似解,几何解释：,17,深层分析,18,深层分析,19,深层分析,2、 Newt
3、on法的算法步骤,20,深层分析,21,深层分析,对不同的两个初始点，经一次迭代求出最优解，,这是偶然还是必然的呢？,22,深层分析,23,深层分析,下面我们来看看最速下降法与Newton法求解二次 函数的比较,24,深层分析,等值线,25,深层分析,3、Newton 的收敛性,26,深层分析,4、 局部二次收敛性,27,深层分析,(1) 收敛性略，参见前面的牛顿法的收敛性,(2) 收敛速度,28,深层分析,29,深层分析,30,深层分析,5、 Newton法的修正形式：如何有效计算下降方向,31,深层分析,32,深层分析,该算法有较好的稳定性及较快的收敛速度,33,深层分析,从Newton法出发进行修改 ，利用其优点，克服 其缺点，产生很多效果非常好的其他新算法,上面的Newton法的两种修正形式，在较弱的条件下 具有超线性收敛性或二次收敛性. 还有很多其他的修正形式,Newton法 的优点：收敛快； 缺点：对初始点要求很高，而且 计算量大,注意：,34,深层分析,