使用导数的最优化方法.ppt
第10章 使用导数的最优化方法,无约束最优化问题,2.最速下降法,4.共轭梯度法5.拟牛顿法,3.牛顿法,一.无约束最优化问题,无约束非线性规划问题的求解方法分为解析法和直接法两类。,解析法 需要计算函数的梯度，利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法,直接法 仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直接方法。,无约束非线性规划问题的求解方法分为解析法和直接法两类。,一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。,本章主要介绍解析法;另一类只用到目标函数值,不必计算导数,通常称为直接方法,放在第11章讨论.,本章考虑如下的下降算法：,主要介绍最速下降法、牛顿法，共轭梯度法，拟牛顿法等,其中函数 具有一阶连续偏导数.人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向.,解：,第二次迭代：,第三次迭代：,在最速下降法的一位搜素中,即在最速下降法中相邻两次搜索方向是正交的。,对于二次严格凸函数,其中A为n维对称正定矩阵,可以求出步长因子k,（本章习题7）,锯齿现象,最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向d(k+1)与前一次搜索方向 d(k),总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。,最速下降法的收敛性,从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。,已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的(定理10.1.2)，而且恰好是线性收敛的。,则牛顿法产生的序列收敛于.,实际上,当牛顿法收敛时,有下列关系:,其中 C 是某个常数.因此,牛顿法至少2级收敛,参看文献19.可见牛顿法的收敛速率是很快的.,例 用牛顿法解下列问题:,我们取初点,解：,第2次迭代：,第2次迭代：,继续迭代，得到,最终收敛到最优解x*=(1,0)T,我们先用极值条件求解.令,下面用牛顿法求解.任取初始点x(1),根据牛顿法的迭代公式：,特别地,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点.,设有二次凸函数,其中A是对称正定矩阵。,求迭代点x(2),即1次迭代达到极小点.,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点,10.3、共轭梯度法,10.3.1 共轭方向法,1.共轭方向和共轭方向法,共轭是正交的推广。,几何意义,几何意义,推论：,共轭方向法,对于上述正交方向法，它是下降算法吗？,不难得到：,故正交方向法，它是下降算法。,可由一组线性无关向量组，类似于schmidt正交化过程，,.共轭梯度法,如何选取一组共轭方向？,以下分析算法的具体步骤。,我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形,初始搜索方向为最速下降方向,常用两个公式:著名的FR和PPR公式,求解二次凸规划的FR 共轭梯度法,求解二次凸规划的FR 共轭梯度法迭代多少次才可以达到最优解？,.用于一般函数的共轭梯度法,.用于一般函数的共轭梯度法,10.4 拟牛顿法,6.4.1 拟牛顿条件,前面介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵.,Newton法的优缺点都很突出。优点：高收敛速度（二阶收敛）；缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。,拟Newton法是模拟Newton法给出的一个保优去劣的算法,拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。,由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经成为一类公认的比较有效的算法,下面分析怎样构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆.,前面已经给出牛顿法的迭代公式,即,k是从 xk 出发沿牛顿方向搜索的最优步长.,(10.4.7),
