第10-章-使用导数的最优化方法PPT课件

1、1,第10章 使用导数的最优化方法,无约束最优化问题,2. 最速下降法,4.共轭梯度法 5.拟牛顿法,3. 牛顿法,2,一. 无约束最优化问题,无约束非线性规划问题的求解方法分为解析法和直接法两类,解析法 需要计算函数的梯度，利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法,直接法 仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直接方法,3,无约束非线性规划问题的求解方法分为解析法和直接法两类,一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是解无约束非线性规划问题的核心问题，搜

2、索方向的不同选择，形成不同的求解方法,本章主要介绍解析法;另一类只用到目标函数值,不必计算导数,通常称为直接方法,放在第11章讨论,4,本章考虑如下的下降算法,主要介绍最速下降法、牛顿法，共轭梯度法，拟牛顿法等,5,其中函数 具有一阶连续偏导数. 人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样

3、选择最速下降方向,6,7,8,9,10,解,第二次迭代,11,第三次迭代,12,13,在最速下降法的一位搜素中,即在最速下降法中相邻两次搜索方向是正交的,14,对于二次严格凸函数,其中A为n维对称正定矩阵,可以求出步长因子k,本章习题7,15,锯齿现象,最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向d(k+1)与前一次搜索方向 d(k,总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生,最速下降法的收敛性,16,从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标

4、函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快,已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的(定理10.1.2)，而且恰好是线性收敛的,17,18,19,20,21,则牛顿法产生的序列收敛于,实际上,当牛顿法收敛时,有下列关系,其中 C 是某个常数.因此,牛顿法至少2级收敛,参看文献19.可见牛顿法的收敛速率是很快的,22,例10.2.1 用牛顿法解下列问题,我们取初点,解,第2次迭代,23,第2次迭代,继续迭代，得到,最终收敛到最优解x*=(1,0)T,24,我们先用极值条件求解.令,下面用牛顿法求解. 任取初始点

5、x(1) , 根据牛顿法的迭代公式,特别地,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点,设有二次凸函数,其中A是对称正定矩阵,求迭代点x(2,即1次迭代达到极小点,25,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点,26,27,28,10.3、共轭梯度法,29,10.3.1 共轭方向法,1. 共轭方向和共轭方向法,共轭是正交的推广,30,几何意义,31,几何意义,32,33,34,35,36,37,推论,38,共轭方向法,39,对于上述正交方向法，它是下降算法吗,不难得到,故正交方向法，它是下降算法,40,可由一组线性无关向量组，类似于schmidt正交化过程,41,42,43,

6、10.3.2. 共轭梯度法,如何选取一组共轭方向,以下分析算法的具体步骤,我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形,44,初始搜索方向为最速下降方向,45,46,47,48,常用两个公式: 著名的FR和PPR公式,49,求解二次凸规划的FR 共轭梯度法,求解二次凸规划的FR 共轭梯度法迭代多少次才可以达到最优解,50,51,52,53,10.3.3. 用于一般函数的共轭梯度法,54,10.3.3. 用于一般函数的共轭梯度法,55,56,57,58,59,60,61,62,63,64,10.4 拟牛顿法,6.4.1 拟牛顿条件,前面介绍了牛顿法,它的突出优

7、点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵,65,Newton法的优缺点都很突出。 优点：高收敛速度（二阶收敛）； 缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆,拟Newton法是模拟Newton法给出的一个保优去劣的算法,拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法,66,67,68,由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经