最优化：最速下降法和Newton法课件

最优化主讲：刘陶文课件制作：刘陶文唯楚有材於斯为盛学好最优化，走遍天下都不怕最优化主讲：刘陶文课件制作：刘陶文唯楚有材1第三章无约束问题算法(I)——最速下降法、Newton法

第一节最速下降法

第二节Newton法及其修正形式第三章无约束问题算法(I)——第一节最速下降法2最优化：最速下降法和Newton法ppt课件3第一节最速下降法1、思想：每次沿负梯度方向进行搜索●●等值线(面)●最古老的优化方法，十九世纪中叶由Cauchy提出第一节最速下降法1、思想：每次沿负梯度方向进行搜索●4负梯度方向也称为最速下降方向：以负梯度为搜索方向的算法称为最速下降法负梯度方向也称为最速下降方向：以负梯度为搜索方向的算法称为最52、算法步骤最优化算法看来是如此的简单？2、算法步骤最优化算法看来是如此的简单？6最优化：最速下降法和Newton法ppt课件7事实上，上面的例子刻画了最速下降法的所有收敛特征事实上，上面的例子刻画了最速下降法的所有收83、最速下降法的收敛性全局收敛性3、最速下降法的收敛性全局收敛性9收敛速度估计收敛速度估计10最优化：最速下降法和Newton法ppt课件11从上图可以看出，最速下降法具有锯齿现象从上图可以看出，最速下降法具有锯齿现象12对一般的非二次函数有下面的收敛速度估计：定理的证明参见文献[19,定理3.4]对一般的非二次函数有下面的收敛速度估计：定理的证明参见文献[13由上面的分析可知，最速下降法的收敛速度比较慢，通常将其用在某些算法的初始阶段求较好的初始点或作为某些算法的间插步.思考题：有点难啊由上面的分析可知，最速下降法的收敛速度思考题：有点难14最优化：最速下降法和Newton法ppt课件15最优化：最速下降法和Newton法ppt课件16第二节Newton法及其修正形式1、思想：用近似二次函数的极小点作为原问题的新的近似解几何解释：●●第二节Newton法及其修正形式1、思想：用近似二次17最优化：最速下降法和Newton法ppt课件18最优化：最速下降法和Newton法ppt课件192、Newton法的算法步骤2、Newton法的算法步骤20最优化：最速下降法和Newton法ppt课件21对不同的两个初始点，经一次迭代求出最优解，这是偶然还是必然的呢？对不同的两个初始点，经一次迭代求出最优解，这是偶然还是必然的22最优化：最速下降法和Newton法ppt课件23下面我们来看看最速下降法与Newton法求解二次函数的比较下面我们来看看最速下降法与Newton法求解二次24●●●等值线●●●等值线253、Newton的收敛性3、Newton的收敛性264、局部二次收敛性4、局部二次收敛性27(1)收敛性略，参见前面的牛顿法的收敛性(2)收敛速度(1)收敛性略，参见前面的牛顿法的收敛性(2)收敛速度28最优化：最速下降法和Newton法ppt课件29最优化：最速下降法和Newton法ppt课件305、Newton法的修正形式：如何有效计算下降方向5、Newton法的修正形式：如何有效计算下降方向31最优化：最速下降法和Newton法ppt课件32该算法有较好的稳定性及较快的收敛速度该算法有较好的稳定性及较快的收敛速度33从Newton法出发进行修改，利用其优点，克服其缺点，产生很多效果非常好的其他新算法上面的Newton法的两种修正形式，在较弱的条件下具有超线性收敛性或二次收敛性.还有很多其他的修正形式Newton法的优