第三章梯度法和共轭梯度法课件.ppt

《第三章梯度法和共轭梯度法课件.ppt》由会员分享，可在线阅读，更多相关《第三章梯度法和共轭梯度法课件.ppt（27页珍藏版）》请在三一办公上搜索。

1、梯度法和共轭梯度法,1.,无约束最优化问题,2.,梯度法,3.,共轭方向法,4.,共轭梯度法,一,.,无约束最优化问题,无约束最优化问题,min,f,(,x,),s,.,t,.,x,?,R,n,其中,f,(,x,),有一阶连续偏导数。,解析法,：利用函数的解析性质构造迭代公式。,二,.,梯度法（最速下降法）,迭代公式：,x,k,?,1,?,x,?,?,k,d,k,k,如何选择下降最快的方向？,?,f,(,x,k,),函数值增加最快的方向,x,k,函数值下降的方向,?,?,f,(,x,k,),函数值下降最快的方向,梯度法（最速下降法）：,1,.,搜索方向：,d,?,?,f,(,x,),也称为最速

2、下降方向；,k,k,k,k,k,k,2,.,搜索步长,:,?,k,取最优步长,即满足,f,(,x,?,?,k,d,),?,min,f,(,x,?,?,d,),。,?,梯度法算法步骤：,1,.,给定初始点,x,?,R,允许误差,?,?,0,令,k,?,1,。,2,.,计算搜索方向,d,?,?,f,(,x,),;,3,.,若,|,d,|,?,?,则停止计算，,x,为所求极值点；,否则，求最优步长,?,k,使得,f,(,x,?,?,k,d,),?,min,f,(,x,?,?,d,),。,?,k,k,k,k,1,n,k,k,k,k,4,.,令,x,k,?,1,?,x,?,?,k,d,令,k,:,?,k

3、,?,1,转,2,。,k,k,例,.,用最速下降法求解,:,min,f,(,x,),?,x,?,3,x,设初始点为,x,?,(,2,1,),2,1,2,2,1,T,求迭代一次后的迭代点,x,2,。,解：,?,?,f,(,x,),?,(,2,x,1,6,x,2,),?,d,?,?,f,(,x,),?,(,?,4,?,6,),.,?,x,?,?,d,?,(,2,?,4,?,1,?,6,?,),.,令,?,(,?,),?,f,(,x,?,?,d,),?,(,2,?,4,?,),?,3,(,1,?,6,?,),，,1,1,2,2,1,1,T,1,1,T,T,求解,min,?,(,?,),?,13,令,

4、?,?,(,?,),?,?,8,(,2,?,4,?,),?,36,(,1,?,6,?,),?,0,?,?,1,?,62,36,?,8,T,2,1,1,?,x,?,x,?,?,1,d,?,(,),31,31,收敛性,性质,.,设,f,(,x,),有一阶连续偏导数，若,步长,?,k,满足,f,(,x,?,?,k,d,),?,min,f,(,x,?,?,d,),?,k,k,k,k,则有,?,f,(,x,?,?,k,d,),d,?,0,。,k,k,令,?,(,?,),?,f,(,x,?,?,d,),，,所以,证明：,k,k,T,k,?,?,(,?,),?,?,f,(,x,k,?,?,d,k,),T,d

5、,k,.,?,f,(,x,k,?,?,k,d,k,),?,min,f,(,x,k,?,?,d,k,),?,k,k,T,k,?,?,?,(,?,k,),?,?,f,(,x,?,?,k,d,),d,?,0,.,注：,因为梯度法的搜索方向,d,k,?,1,?,?,f,(,x,?,?,k,d,),，,所以,k,k,(,d,k,?,1,),T,d,k,?,0,?,d,k,?,1,?,d,k,。,锯齿现象,在极小点附近，目标函,数可以用二次函数近似,，其等值面近似,椭球面。,x,2,x,3,?,x,*,x,1,注,最速下降方向反映了目,标函数的一种局部性质,。,它只是,局部目标函数值下降最,快的方向。,最

6、速下降法是线性收敛,的算法。,三、共轭方向法,1.,何谓共轭方向？,几何解释,1,T,设有二次函数,f,(,x,),?,(,x,?,x,),A,(,x,?,x,),2,其中,A,是,n,?,n,对称正定矩阵，,x,是一个定点。,则函数,f,(,x,),的等值面,1,(,x,?,x,),T,A,(,x,?,x,),?,c,2,x,是以,x,为中心的椭球面。,由于,?,f,(,x,),?,A,(,x,?,x,),?,0,而,?,f,(,x,),?,A,2,2,1,f,(,x,),?,(,x,?,x,),T,A,(,x,?,x,),2,因为,A,正定，,所以,?,f,(,x,),?,A,?,0,因此

7、,x,是,f,(,x,),的极小点。,x,设,x,d,x,(,1,),(,0,),是在某个等值面上的一,点，,n,x,(,0,),是,R,中的一个方向，,(,1,),d,(,1,),(,0,),沿着,d,以最优步长,搜索得到点,x,(,1,),。,x,d,(,2,),x,(,1,),x,1,o,则,d,(,1,),是点,x,(,1,),所在等值面的切向量。,该等值面在点,x,(,1,),处的法向量为,?,f,(,x,1,),?,f,(,x,(,1,),),?,A,(,x,(,1,),?,x,),.,x,d,(,1,),d,(,2,),则,d,(,1,),与,?,f,(,x,(,1,),),正交

8、，,x,(,1,),x,1,即,d,(,1,),T,(,2,),?,f,(,x,(,1,),),?,0,。,o,?,?,f,(,x,1,),令,d,所以,?,x,?,x,d,(,1,),T,Ad,(,2,),?,0,。,(,1,),即等值面上一点处的切,向量与由这一点,指向极,小点的向量关于,A,共轭。,2.,共轭方向,n,1,2,定义,设,A,是,n,?,n,的对称正定矩阵，对于,R,中的两个非零向量,d,和,d,，,若有,1,d,2,1,T,Ad,2,?,0,，则称,d,1,和,d,2,关于,A,共轭。,k,n,设,d,d,?,d,是,R,中一组非零向量，如果,它们两两关于,A,共轭，即,

9、d,i,T,Ad,?,0,i,?,j,i,j,?,1,2,?,k,。,j,则称这组方向是关于,A,共轭的，也称它们是一,组,A,共轭方向。,注：,如果,A,是单位矩阵，则,d,1,T,?,I,?,d,?,0,?,d,2,1,T,?,d,?,0,2,?,d,1,?,d,2,共轭是正交的推广。,1,2,k,设,A,是,n,阶对称正定矩阵，,d,d,?,d,是,k,个,A,共轭的非零,定理,1,.,向量，则这个向量组线,性无关。,证明,设存在实数,?,1,?,2,?,?,k,，使得,i,?,1,?,?,i,d,?,0,j,T,i,k,i,上式两边同时左乘,d,i,?,1,k,A,，则有,?,?,i,

10、d,j,T,k,j,T,Ad,?,0,因为,d,1,d,2,?,d,是,k,个,A,共轭的向量，所以上式,可化简为,?,j,d,j,Ad,j,?,0,.,j,T,因为,d,?,0,而,A,是正定矩阵，所以,d,所以,1,2,Ad,?,0,，,j,?,j,?,0,j,?,1,2,?,k,。,k,因此,d,d,?,d,线性无关。,1,T,定理,2,.,设有函数,f,(,x,),?,x,Ax,?,b,T,x,?,c,，,2,(,1,),(,2,),(,k,),其中,A,是,n,阶对称正定矩阵。,d,d,?,d,是,一组,A,共轭向量。,以任意的,x,得到点,x,(,2,),(,1,),?,R,为初始

11、点，依次沿,d,(,3,),n,(,1,),d,(,2,),?,d,(,1,),(,k,),进行搜索，,x,?,x,(,k,?,1,),则,x,(,k,?,1,),是函数,f,(,x,),在,x,?,B,k,上的,极小点，其中,(,1,),(,2,),B,k,?,x,|,x,?,?,?,i,d,(,i,),?,i,?,R,i,?,1,(,k,),k,是由,d,d,n,?,d,生成的子空间。特别地,，,当,k,?,n,时，,x,(,n,?,1,),是,f,(,x,),在,R,上的唯一极小点。,推论,在上述定理条件下，必,有,?,f,(,x,(,k,?,1,),T,),d,(,i,),?,0,i,

12、?,1,2,?,k,。,3,、共轭方向法,对于极小化问题,1,T,T,min,f,(,x,),?,x,Ax,?,b,x,?,c,2,其中,A,是正定矩阵，称下述算,法为共轭方向法,:,(,1,),取定一组,A,共轭方向,d,(,1,),d,(,2,),?,d,(,n,),；,(,2,),任取初始点,x,(,1,),依次按照下式由,x,(,k,),确定点,x,(,k,?,1,),(,k,?,1,),(,k,),(,k,),?,x,?,x,?,?,d,k,?,?,f,(,x,(,k,),?,?,d,(,k,),),?,min,f,(,x,(,k,),?,?,d,(,k,),),k,?,?,?,直到

13、某个,x,(,k,),满足,?,f,(,x,(,k,),),?,0,。,注,由定理,2,可知，利用共轭方向法,求解上述极小化问题，,至多经过,n,次迭代必可得到最优解,。,如何选取一组共轭方向？,四,.,共轭梯度法,：,?,二次函数情形,?,非二次函数情形,1,、,二次函数情形,Fletcher,?,R,eeves,共轭梯度法,:,1,T,T,min,f,(,x,),?,x,Ax,?,b,x,?,c,2,n,n,其中,x,?,R,A,是对称正定矩阵，,b,?,R,，,c,是常数。,基本思想：,将共轭性和最速下降方,向相结合，利用已知迭,代点,处的梯度方向构造一组,共轭方向，并沿此方向,进行搜索

14、，求出,函数的极小点。,以下分析算法的具体步骤。,(,1,),任取初始点,x,，第一个搜索方向取为,d,(,1,),(,1,),?,?,f,(,x,(,1,),),；,(,2,),设已求得点,x,(,k,?,1,),，,若,?,f,(,x,(,k,?,1,),),?,0,，,令,g,k,?,1,?,?,f,(,x,(,k,?,1,),),，,则下一个搜索方向,d,(,k,?,1,),按如下方式确定,:,令,d,(,k,?,1,),?,?,g,k,?,1,?,?,k,d,(,k,),(,1,),如何确定,?,k,？,要求,d,(,k,?,1,),和,d,(,k,),关于,A,共轭。,(,k,),

15、T,则在（,1,）式两边同时左乘,d,0,?,d,(,k,),T,A,，得,A,d,(,k,),Ad,(,k,?,1,),?,?,d,(,k,),T,Ag,k,?,1,?,?,k,d,(,k,),T,解得,?,k,?,d,d,(,k,),T,(,k,),T,A,g,k,?,1,A,d,(,k,),(,2,),(,3,),搜索步长的确定,:,已知迭代点,x,(,k,),和搜索方向,d,(,k,),利用一维搜索确定最优,步长,?,k,，,即求解,min,?,f,(,x,(,k,),(,k,),?,?,d,(,k,),(,k,),),。,记,令,即有,?,(,?,),?,f,(,x,?,?,d,),

16、(,k,),(,k,),T,(,k,),?,?,(,?,),?,?,f,(,x,?,?,d,),d,?,0,，,A,(,x,(,k,),?,?,d,(,k,),),?,b,T,d,(,k,),?,0,，,令,g,k,?,?,f,(,x,(,k,),),?,Ax,(,k,),?,b,，则有,g,k,?,?,Ad,(,k,),T,d,(,k,),?,0,，,解得,?,k,?,?,d,T,(,k,),g,k,d,(,k,),T,(,k,),(,3,),Ad,1,T,FR,算法在,m,?,n,次,定理,3,对于正定二次函数,f,(,x,),?,x,Ax,?,b,T,x,?,c,，,2,一维搜索后即终止

17、，并,且对所有的,（,i,1,?,i,?,m,），下列关系成立,(,1,),d,(,i,),T,Ad,(,j,),?,0,j,?,1,2,?,i,?,1,;,(,2,),g,i,T,g,j,?,0,j,?,1,2,?,i,?,1,;,(,3,),T,(,i,),g,i,d,?,T,?,g,i,g,i,。,注,（,1,）由定理,3,可知搜索方向,d,(,1,),d,(,2,),?,d,(,m,),是,A,共轭的。,(,2,),算法中第一个搜索方向,必须取负梯度方向，否,则构造的搜索,方向不能保证共轭性。,(,3,),由定理,3,的（,3,）可知，,T,(,i,),g,i,d,?,T,?,g,i,

18、g,i,?,?,|,g,i,|,?,0,2,所以,d,是迭代点,x,(,i,),(,i,),处的下降方向。,(,4,),由定理,3,，,FR,算法中,?,i,的计算公式可以简化。,?,i,?,?,d,(,i,),T,(,i,),T,A,g,i,?,1,Ad,(,i,),d,?,g,i,?,1,T,A,d,(,i,),d,(,i,),T,Ad,(,i,),T,g,i,?,1,(,i,),T,A,(,x,(,i,?,1,),?,x,(,i,),),/,?,i,A,(,x,(,i,?,1,),?,x,(,i,),),/,?,i,(,i,),d,?,g,i,?,?,f,(,x,),?,A,x,(,i,

19、),?,b,.,?,?,i,?,T,g,i,?,1,(,i,),T,(,g,i,?,1,?,g,i,),(,g,i,?,1,?,g,i,),2,2,?,|,g,i,?,1,|,?,d,(,i,),T,2,d,g,i,?,|,g,i,?,1,|,|,g,i,|,(,4,),FR,算法步骤：,1,.,任取初始点,x,(,1,),，,精度要求,?,，令,k,?,1,。,2,.,令,g,1,?,?,f,(,x,(,1,),),若,|,g,1,|,?,?,停止，,x,(,1,),为所求极小点；,否则，令,d,(,1,),?,?,g,1,利用公式（,3,）计算,?,1,，,令,x,(,2,),?,x,(,

20、1,),?,?,1,d,(,1,),。,3,.,令,g,k,?,1,?,?,f,(,x,(,k,?,1,),),若,|,g,k,?,1,|,?,?,停止，,x,(,k,?,1,),为所求极小点；,否则，令,d,(,k,?,1,),?,?,g,k,?,1,?,?,k,d,(,k,),其中,?,k,用公式（,4,）计算。,令,k,:,?,k,?,1,。,4,.,利用公式（,3,）计算,?,k,，令,x,(,k,?,1,),?,x,(,k,),?,?,k,d,(,k,),转,3,。,例,用,FR,算法求解下述问题：,min,2,2,f,(,x,),?,2,x,1,?,x,2,初始点取为,x,(,1,

21、),?,(,2,2,),T,。,解：,?,?,4,0,?,?,4,0,?,?,x,1,?,1,.,f,(,x,),?,(,x,1,x,2,),?,?,A,?,?,?,?,?,?,2,?,0,2,?,?,0,2,?,?,x,2,?,T,?,f,(,x,),?,(,4,x,1,2,x,2,),.,第,1,次迭代：,(,1,),T,令,d,?,?,g,1,?,(,?,8,?,4,),T,(,1,),g,1,d,而,?,1,?,?,?,?,8,?,(,8,4,),?,?,?,4,?,?,?,?,?,4,0,?,?,?,8,?,(,?,8,?,4,),?,?,?,?,?,0,2,?,?,?,4,?,d,

22、(,1,),T,Ad,(,1,),5,?,18,所以,x,(,2,),?,x,(,1,),?,?,1,d,(,1,),5,?,2,8,T,T,?,(,2,2,),?,(,?,8,?,4,),?,(,),18,9,9,T,第,2,次迭代：,?,8,16,T,?,g,2,?,(,),.,9,9,?,8,2,16,2,|,g,2,|,2,(,9,),?,(,9,),4,?,?,1,?,?,?,.,2,2,2,81,|,g,1,|,8,?,4,?,d,(,2,),?,?,g,2,?,?,1,d,(,1,),8,?,16,T,4,?,(,),?,(,?,8,?,4,),T,9,9,81,40,T,?,(

23、,1,?,4,),81,?,?,2,?,?,d,T,(,2,),g,2,d,(,2,),T,(,2,),Ad,40,?,8,16,?,1,?,(,),?,?,81,9,9,?,?,4,?,9,?,?,?,20,?,4,0,?,?,1,?,40,2,(,),(,1,?,4,),?,?,?,?,4,?,81,0,2,?,?,?,?,?,x,(,3,),?,x,(,2,),?,?,2,d,(,2,),?,2,8,T,9,40,?,(,),?,?,(,1,?,4,),T,9,9,20,81,?,(,0,0,),?,g,3,?,(,0,0,),(,3,),T,T,?,x,即为所求极小点。,2.,用于一般

24、函数的共轭梯度法,min,s,.,t,.,f,(,x,),x,?,R,n,对用于正定二次函数的,共轭梯度法进行修改：,(,1,),第一个搜索方向仍取最,速下降方向，即,d,(,1,),?,?,f,(,x,(,1,),),。,其它搜索方向按下式计,算：,d,(,i,?,1,),?,?,f,(,x,(,i,?,1,),),?,?,i,d,(,i,),其中,?,i,?,|,?,f,(,x,(,i,?,1,),),|,2,|,?,f,(,x,(,i,),),|,2,。,(,2,),搜索步长,?,i,不能利用公式（,3,）计算，需由一维搜索,确定。,(,3,),算法在有限步迭代后不,一定能满足停止条件，

25、,此时可采取,如下措施：,以,n,次迭代为一轮，每次完,成一轮搜索后，如果还,没有求,得极小点，则以上一轮,的最后一个迭代点作为,新的初始点，,取最速下降方向作为第,一个搜索方向，开始下,一轮搜索。,注,在共轭梯度法中，计算,?,i,可采用不同形式的公式,，如,?,i,?,g,T,i,?,1,T,i,g,i,?,1,g,g,i,Fletcher,and,Re,eves,(,FR,),共扼梯度法,1964,年,g,i,T,?,1,(,g,i,?,1,?,g,i,),?,i,?,?,Polak,Ribiere,and,Polyar,(,PRP,),共轭梯度法,1969,年,T,g,i,g,i,?,i,?,g,d,T,i,?,1,(,i,),T,g,i,?,1,g,i,?,1,Dixon,and,Myers,(,DY,),共扼梯度法,1972,年,?,i,?,g,d,T,i,?,1,(,i,),T,(,g,i,?,1,?,g,i,),(,g,i,?,1,?,g,i,),?,Sorenson,and,Wolfe,(,SW,),共扼梯度法,?,i,?,d,(,i,),T,?,2,f,(,x,i,?,1,),g,i,?,1,?,2,f,(,x,i,?,1,),d,(,i,),d,(,i,),T,?,Daniel,共扼梯度法,