第10 章 使用导数的最优化方法

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