《最优化方法ppt课件》由会员分享，可在线阅读，更多相关《最优化方法ppt课件（33页珍藏版）》请在金锄头文库上搜索。
1、1,3.4共轭方向法和共轭梯度法,2,共轭方向法是介于最速下降法和Newton法 之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与Newton法相比，减少了计算量和存储量。它是比较实用而有效的最优化方法。,3,共轭方向法涉及共轭方向的概念和性质。 共轭方向的概念是在研究正定二次函数,本节和下节所介绍的方法有一个共同的特点，即首先以上式为目标函数给出有关的 算法，然后再把算法用到更一般的目标函 数上。,本节内容对今后许多章节起着基础的作用。,时产生的。,4,共轭方向法的思路,定义 3.4.1设n维向量组p1,pk线性无关,
2、x(0)Rn, 称向量集合 为由点x(0)与p1,p2,pk 生成的k维超平面.,我们希望x(k)是k维超平面的极小点,于是x(n)是n维超平面(即整个Rn空间)的极小点.,若k=1,上述集合表示以p1为方向向量,且过点x(0)的一条直线.,5,超平面上极小点的判断,引理 3.4.1 设f (x)为连续可微的严格凸函数,又 p1,p2,pk为一组线性无关的n维向量, x1Rn ,则 是f(x)在x1与p1,p2,pk所生成的k维超平面Hk上唯一极小点的充分必要条件是,注:若k=n,易推出在xk+1的梯度为零向量.因此,这一引理是一常用定理(极小点梯度为0)的推广.,6,已知k个点与k个方向之后
3、,令xk+1=xk+ak pk,进行精确一维搜索,确定xk+1,再确定pk+1.,共轭方向法(用于二次函数),对于正定二次函数,确定pk的准则是希望 xk+1是目标函数在k维超平面上的极小点. xn+1就是目标函数在整个空间的极小点.,给定一个初始点x1,给出一个下降方向p1 ,令x2=x1+a1 p1,进行精确一维搜索,确定x2,再确定p2(方法待定).,7,共轭向量,对于f(x)=xTGx/2+bTx+c,有g(x)=Gx+b,因此 gj+1-gj=G(xj+1-xj)=ajGpj, 因此,根据引理3.4.1,左边应为零,于是搜索方向满足性质piTGpj=0(i j). 共轭向量:设G为n
4、阶正定矩阵,p1,p2,pk为n维向量组,如果piTGpj=0(i j)则称向量组 p1,p2,pk关于G共轭. 实际上是在新的内积意义下,这是一组正交向量.,8,共轭方向法(用于二次函数),注:在前面讨论思路时,根据方向的共轭性(正交性)得到xk+1是目标函数在k维超平面上的极小点(后面的定理3.4.3给出严格证明). 根据上一页的推导,根据极小点可以推出共轭性(正交性),即若一种迭代方法每次求出的是二次函数在k维超平面上的极小点,则对应的方向是共轭的.,9,基本概念,二次终止性 如果一个算法经过有限次迭代就得到正定二次函数的极小点,称该算法具有二次终止性. 共轭方向法 是一种迭代方法,每次
5、所取方向与前面的方向关于G共轭,然后进行精确一维搜索确定步长及下一步的迭代点.,10,定理3.4.1设G为n阶正定矩阵,非零向量组 p1,p2,pk关于G共轭,则此向量组线性无关.,证明:设存在常数a1,a2,ak使得 a1p1+a2p2+akpk=0, 以piTG左乘上式,显然有ai piTGpi=0. 又,G是正定矩阵,pi0,因此ai=0(i=1,2,k) 于是p1,p2,pk线性无关.,共轭方向的性质,11,推论1设G为n阶正定矩阵,非零向量组p1,p2,pn 关于G共轭,则此向量组构成 Rn的一组基.,推论2设G为n阶正定矩阵,非零向量组p1,p2,pn 关于G共轭,若向量v与p1,
6、p2,pn 关于G共轭， 则v=0.,共轭方向的性质,12,共轭方向法(用于二次函数),定理 3.4.2 设G是n阶正定阵,向量组p1,p2,pk关于G共轭,对正定二次函数f(x)=xTGx/2+bTx+c 由任意初始点x1开始,依次进行k次一维搜索,xi+1=xi+aipi(i=1,2,k) 则(i)gTk+1pi=0 (i=1,2,k). (ii)xk+1是二次函数在k维超平面Hk上的极小点. 推论 当k =n时,xn+1为二次函数在Rn上的极小点.,13,共轭方向法(用于二次函数),证明要点:只要证明gTk+1pi=0.,精确一维搜索,14,算法（共轭方向法）,15,共轭梯度法(共轭方向
7、的形成),我们首先讨论针对下面二次函数的共轭梯度法,给定初始点x0,初始下降方向取为p0= -g0,从x0出发,沿方向p0进行一维搜索得x1.,设p1是-g1与p0的线性组合p1= -g1+0p0, p1与p0共轭,于是,因此,16,共轭梯度法(共轭方向的形成),假设已经沿k个共轭方向p0, p1, pk-1逐次进行一维搜索得xk.,若gk=g(xk)=0,则xk已是极小点,否则构造下一个方向pk.令pk为-gk以及p0,p1,pk的线性组合.,用pjTG(j=0,1,k-1)左乘上式,因此,17,共轭梯度法(共轭方向的形成),再根据二次函数的性质,有,由于,有,因此,由于xk是由点x0及向量
8、p0,p1,pk-1得到的k维超平面上的极小点,因此gkTpj=0(j=0,1,k-1).,由pj的构造方式,因此gkTgj=0(j=0,1,k-1).,18,共轭梯度法(共轭方向的形成),因此,gkTgj=0(j=0,1,k-1),根据,得,所以,19,定理3.4.3 对正定二次函数 由上面三式所确定共轭方向并采用精确一维 搜索得到的共轭梯度法,在m(n)次迭代后可得函数的极小点,并且对所有i(1im)有,共轭梯度法(用于二次函数),其中,20,21,FR算法,(1)Flecher-Reeves公式,为了能将上述方法用于其它函数,我们必须消去系数中的G.,所以,22,(2)Polak-Rib
9、iere-Polyak公式,PRP算法,由于gkTgk-1=0,所以有,对于二次函数,这两个函数是等价的,但对于一般的函数,根据这两个公式的出的算法的计算效果有差异.,FR算法中:,注:对于这两个算法,可以证明pkTgk= -gkTgk0,因而都是下降算法.,23,FletcherReeves 共轭梯度法,24,由g0=(-2,0)T0,故取p0=(2,0)T,从x0出发,沿p0作一维搜索, 即求min f (x0+a p0)=6a 2-4a 的极小点, 得a0 =1/3 ,于是x1=x0+a 0 p0=(2/3,0)T,g1=(0,-2/3)T, 由FR公式得b0=g1Tg1/g0Tg0=1
10、/9 故p1=-g1+b0p0=(2/9,2/3)T.,例3.4.1 用FR共轭梯度法求解(x0=(0,0)T),共轭梯度法算例,解,注:此处不需求G.,25,从x1出发,沿p1作一维搜索,求,解得a1=3/2,于是,此时,的极小点,故,此算例中,f(x)为二元的正定二次函数,因此FR算法迭代两次得到最优点,26,共轭梯度法算例,例3.3.2 用FR方法与PRP方法求解,设初始点为x0=(0,0)T.,解:,由g0=(-2,0)T0,故取p0=(2,0)T,从x0出发,沿p0作一维搜索,即求 min f (x0+a p0)=1600a 4+4a2-4a+1的极小点, 得a0 =0.080632
11、,(精确一维搜索方法求得,e =10-5,) 于是x1=x0+a 0 p0=(0.161264,0)T, g1=(0.000065,-5.201215)T.,27,共轭梯度法算例,p0=(2,0)T,x1=(0.161264,0)T,g1=(0.000065,-5.201215)T,由FR公式得b0=g1Tg1/g0Tg0=6.763160 故p1=-g1+b0 p0=(13.526254,5.201215)T. 进一步可以以下的迭代,所得的结果(终止准则为|gk|10-12 ,55步收敛)见下表.,最终得到x*(1,1)T.,28,FR方法计算结果,从最后两组数据可以看出,虽然函数值下降,但
12、是迭代点离最优点的距离却有所增加.,29,对于PRP算法,计算过程类似. 计算15步收敛, x*(1,1)T 对于此例,PRP方法比FR方法收敛快. 计算结果见下表.,30,PRP方法计算结果,31,32,重新开始的共轭梯度法,对于FR算法和PRP算法,如果初始方向不取负梯度方向,即使对于二次函数,也不能产生n个共轭方向. 因此,在用这两个方法时,如果迭代到距离最优点比较近,函数接近与一个二次函数时,我们重新取搜索方向为负梯度方向. 一般在实际应用中迭代n步或n+1步时重新设定搜索方向为负梯度方向.,33,重新开始的共轭梯度法,对于前面的例子,采用重新开始的共轭梯度法得到的收敛步数为: FR算法: 迭代n步重新开始,49步收敛 迭代n+1步重新开始,31步收敛 PRP算法:迭代n步重新开始,27步收敛 迭代n+1步重新开始,13步收敛 由于此处n比较小,改善并不明显.,
