资源描述：
《共轭梯度法直接搜索法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§3.6共轭方向法与共轭梯度法由Taylor公式，一个函数在一点附近的性态与二次函数是很接近的，因此，一个算法如果对于二次函数很有效，那么它对一般函数也会是好的。因而，为了建立有效算法，往往采用二次模型，即现针对正定二次函数建立有效的算法，然后再推广到一般函数上去。问题1:什么算法被认为是对二次函数是有效的？二次终止性算法特点（１）建立在二次模型上，具有二次终止性．（２）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点．（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．一
2、、共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关于共轭的．注：若则是正交的，因此共轭是正交的推广．定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关．推论1:设为阶正定阵，非零向量组关于共轭，则向量构成的一组基．推论2:设为阶正定阵，非零向量组关于共轭，若向量与关于共轭，则共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生成的维超平面．引理1:设是连续可微的严格凸函数，维向量组线性无关，则：是在上唯一极小点的充要条件是：证：构造：分析：是(1)维严格凸函数．(2)是在上的极小点的充要条件是是在上的极
3、小点．定理2:设为阶正定阵，向量组关于共轭，对正定二次函数由任意开始，依次进行次精确线搜索：则：(１)(２)是在上的极小点．推论:当时，为正定二次函数在上的极小点．二、二次函数共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代．Step3:计算使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.先讨论共轭方向与梯度的关系三、共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：共轭方向的形成系数的其他形式（１）FR公式（1964）（2）PRP公式（1969）上面两式做比
4、较即得FR公式的推导共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）一般目标函数的FR共轭梯度法算法Step1:给出Step2:计算如果，停．否则转Step3.Step3:Step4:由精确线搜索求Step5:转Step2.FR共轭梯度法收敛定理定理4:假定在有界水平集上连续可微，且有下界，那么采用精确线搜索下的FR共轭梯度法产生的点列至少有一个聚点是驻点，即：(1)当是有穷点列时，其最后一个点是的驻点．(2)当是无穷点列时，它必有聚点，且任
5、一聚点都是的驻点．例1：用FR共轭梯度法求解：解：化成形式(1)(2)例2：用FR共轭梯度法求解：解：化成形式(1)(2)练习：FR共轭梯度法上机实现FR共轭梯度法．并求解Rosenbrock函数，初始点选解：进一步迭代得到的结果见下表，终止准则对于PRP算法,计算过程类似.计算15步收敛,x*≈(1,1)T对于此例,PRP方法比FR方法收敛快.对于FR算法和PRP算法,如果初始方向不取负梯度方向,即使对于二次函数,也不能产生n个共轭方向.因此,在用这两个方法时,如果迭代到距离最优点比较近,函数接近与一个二次函数时,我们重新取
6、搜索方向为负梯度方向.一般在实际应用中迭代n步或n+1步时重新设定搜索方向为负梯度方向.四、重新开始的共扼梯度法重新开始FR共轭梯度法算法Step1:给出Step2:计算如果停，否则转step3Step4:由精确线搜索求并令：Step3:若k是n+1的倍数，则否则令转step2§3.7直接搜索法在实际工程的最优化问题中，目标函数的导数往往很难求出或根本无法求出。这就需要用直接法来求。这种方法适用面较广，但收敛速度较，同时计算量也往往随问题维数的增加而迅速增大。主要介绍：Powell方向加速法考虑正定二次函数n=2时,其等值线是
7、一族椭圆,这族椭圆的共同中心为函数的极小点x*.从不同的初始点x0,x1出发,沿相同的方向p0进行一维搜索,分别得到极小点xa,xb.连接xa,xb的直线必通过x*.·将直线xa,xb的方向记为p1,则从x0出发,沿p0，p1进行一维搜索,可以得到极小点.一、Powell法（方向加速法）对于上面的二维的二次函数,从一点出发,沿两个方向进行一维搜索即可得到极小点,可以推测这两个方向是共轭的.定理1.对于n维正定二次函数设关于G共轭，分别得到极小点xa,xb.如果xa≠xb，则x0与x1为不同的任两点，分别从这两点出发，依次沿进行
8、一维搜索,与关于G共轭，证明:设关于G共轭，xa,xb分别是沿上述方向依次进行一维搜索得到的极小点，因而有两式相减得即得给定初始点，给定n个线性无关的向量（一般取为对依次沿上面的n个方向进行一维搜索，最终得到的点为以为方向去掉方向沿方向进行搜索得到新的初始点再由初始点沿方向进
