1、第五章 无约束问题算法（III）共轭梯度法共轭方向法的思路共轭方向法的思路对于简单的二次函数1122() ()TTTTx xb xcxbxbcb b任给一个初始向量x(0),沿着方向e1=(1,0,0)T进行搜索,即求解下面问题100111 11 1( )( )min()() ()Tfxebxeb 由于0202111112( )( )()()()niiifxbxb 因此0111*( ),xb 10001112( )( )*( )( )(,) .Tnxxebxx n注:此处的一维搜索中1的范围是整个实数集,即x(1)是函数在集合x(0)+1e1,1R中的极小点.共轭方向法的思路共轭方向法的思路n
2、x(1)与x(0)唯一不同的是它们的第一个分量.其中x(1)的第一个分量与原问题最优解 b 的第一个分量一致,其余的分量未发生变化.n下面再沿着方向e2=(0,1,0,0)T进行搜索,得到的x(2)的前两个分量与最优解 b 的前两个分量一致,其余分量不变.211123( )( )( )(,) .Tnxbbxx n显然, x(2)是函数在集合x(0) +1e1+2e2,1,2R中的极小点.共轭方向法的思路共轭方向法的思路n因此,上述的迭代过程每一步在一个分量上达到最优,且每一步求得了函数在一个集合中的极小点,这种集合在迭代过程中逐渐扩大,迭代n步之后得到原问题的最优解.n将此过程进行下去有111
3、1( )( )( )(,) .kTkknxbbxx n进行n步后有12( )(,).nTnxbbbb n x(k)是函数在x(0) +1e1+2e2+kek,1,2,kR中的极小点.共轭方向法的思路共轭方向法的思路n在三维情况下,上面的迭代过程可以用图形来表示.x(0)x(1)x(2)x(3)xyzO=x*共轭方向法的思路共轭方向法的思路n上面的方法对一般的二次函数是否适用呢?n考虑问题1min( )2Tf xx Gx 其中1225G n易见G是正定的,f(x)的极小点为(0,0)T.n以x(0)=(-1,-1)T为初始点,在方向e1=(1,0)T上进行一维搜索.即求解问题2111min( 1
4、, 1)(1,0) )(1)4(1)5TTf n易求得1*=3,x(1)=x(0)+1*e1=(2,-1)T.n第一个分量没有变为0,进一步沿e2=(0,1)T搜索显然不能达到 f (x)的极小点.共轭方向法的思路共轭方向法的思路n在空间Rn上,重新定义内积与范数:,Tx yx Gy 1 21 2/|,()TGxx xx Gx n给定最优化问题(其中G对称正定)12min( )TTf xx Gxb xc则212( )|TGf xxb xc1111122()()TTxG bG xG bcb G b1211122|TGxG bcb G b 共轭方向法的思路共轭方向法的思路n在Rn上,按照上面定义的
5、内积给出一组正交基p1,p2,pn,n因此原问题等价于12min |GxG b n即p1,p2,pn线性无关,且0,()ijppij n设问题的最优解x*= -G-1b在这组基底下的表示为x*= u1 p1+u2 p2+un pnn任取初始点x(0) =s1 p1+s2 p2+sn pn, 在方向p1上进行一维搜索,即求解问题21111222min | ()()()|nnnGsu psupsup 共轭方向法的思路共轭方向法的思路n显然,当1=u1s1时,上面的函数取最小值,nx(1) =u1 p1+s2 p2+sn pn.21111222| ()()()|nnnGsu psupsup 1111
6、2221111222()()(),()()()nnnnnnsu psupsupsu psupsup 222211112() |() |nGiiiGisupsup n即x(1)与最优点在基底中第一个向量p1前的系数达到一致.nx(1)是函数在集合x(0)+1p1,1R中的极小点.共轭方向法的思路共轭方向法的思路n最终x(n)= u1 p1+u2 p2+un pn =x*n即迭代过程同样在n步之后找到最优点.n因此,对二次函数12( )TTf xx Gxb xcn我们可以找到n个方向(向量),对其依次进行一维搜索,最多n步可以找到函数的最优点.n类似的,再依次沿着p2,pk进行一维搜索,可以得到x
7、(k)= u1 p1+uk pk+sk+1 pk+1+un pn ,nx(k)是函数在x(0) +1p1+2p2+kpk,1,2,kR中的极小点.共轭方向法的思路共轭方向法的思路n定义 设n维向量组p1,pk线性无关, x(0)Rn,n称向量集合 为由点x(0)与np1,p2,pk 生成的k维超平面.(0)1|,1,2, kiiiixpR ik n我们希望x(k)是k维超平面的极小点,于是x(n)是n维超平面(即整个Rn空间)的极小点.n若k=1,上述集合表示以p1为方向向量,且过点x(0)的一条直线.超平面上极小点的判断超平面上极小点的判断n若函数f(x)连续可微, p1,p2,pk为一组线
8、性无关的n维向量, x(0)Rn,(0)1|,1,2, kkiiiiHxpR ik (0)1kiikixxpH n若 是f(x)在Hk上的极小点,则p1,p2,pk都不是下降方向,因此x( )0Tif xpn p1,p2,pk也不是下降方向,因此( )0Tif xpn于是有( )0(1,2, )Tif xpik超平面上极小点的判断超平面上极小点的判断n严格证明:Hk上的点可以表示为n若 是f(x)在Hk上的极小点.则(0)1kiiixxp n定义(0)11(,)()kkiiihf xp (0)1kiikixxpH 10(,)kh 1(,)TTTkg pg p 其中( ).gf x 因此0(1,
9、2, )Tig pik超平面上极小点的判断超平面上极小点的判断n反之,若( )0(1,2, )Tif xpikn如果f(x)是严格凸函数,对于(0)1kiikixxpH 则( )( )( ) ()Tf xf xf xxx 1( )()( )( )kTiiiif xf xpf x n因此 是f(x)在Hk上的唯一极小点.x超平面上极小点的判断超平面上极小点的判断引理 设f (x)为连续可微的严格凸函数,又 p1,p2,pk为一组线性无关的n维向量, x1Rn ,则是f(x)在x1与p1,p2,pk所生成的k维超平面Hk上唯一极小点的充分必要条件是111kkiiixxp 10(1,2, ).Tki
10、gpik n注:若k=n,易推出在xk+1的梯度为零向量.因此,这一引理是一常用定理(极小点梯度为0)的推广.n已知k个点与k个方向之后,令xk+1=xk+k pk,进行精确一维搜索,确定xk+1,再确定pk+1.共轭方向法共轭方向法(用于二次函数用于二次函数)n对于正定二次函数,确定pk的准则是希望 xk+1是目标函数在k维超平面上的极小点. xn+1就是目标函数在整个空间的极小点.n给定一个初始点x1,给出一个下降方向p1 ,令x2=x1+1 p1,进行精确一维搜索,确定x2,再确定p2(方法待定).1TTTjijijijgpg pp Gp 共轭向量共轭向量n对于f(x)=xTGx/2+b
11、Tx+c,有g(x)=Gx+b,因此ngj+1-gj=G(xj+1-xj)=jGpj, 因此n根据引理,左边应为零,于是搜索方向满足性质piTGpj=0(i j).共轭向量:设G为n阶正定矩阵,p1,p2,pk为n维向量组,如果piTGpj=0(i j)则称向量组 p1,p2,pk关于G共轭.实际上是在新的内积意义下,这是一组正交向量.共轭方向法共轭方向法(用于二次函数用于二次函数)n注:在前面讨论思路时,根据方向的共轭性(正交性)得到xk+1是目标函数在k维超平面上的极小点(后面的定理将给出严格证明).n根据上一页的推导,根据极小点可以推出共轭性(正交性),即若一种迭代方法每次求出的是二次函
12、数在k维超平面上的极小点,则对应的方向是共轭的. 基本概念基本概念n二次终止性n如果一个算法经过有限次迭代就得到正定二次函数的极小点,称该算法具有二次终止性.n共轭方向法是一种迭代方法,每次所取方向与前面的方向关于G共轭,然后进行精确一维搜索确定步长及下一步的迭代点.定理 设G为n阶正定矩阵,非零向量组 p1,p2,pk关于G共轭,则此向量组线性无关.证明:设存在常数1,2,k使得1p1+2p2+kpk=0,以piTG左乘上式,显然有i piTGpi=0.又,G是正定矩阵,pi0,因此i=0(i=1,2,k)于是p1,p2,pk线性无关.共轭方向的性质共轭方向的性质推论1 设G为n阶正定矩阵,
13、非零向量组p1,p2,pn关于G共扼,则此向量组构成 Rn的一组基.推论2 设G为n阶正定矩阵,非零向量组p1,p2,pn关于G共扼,若向量v与p1,p2,pn 关于G共扼，则v=0.共轭方向的性质共轭方向的性质共轭方向法共轭方向法(用于二次函数用于二次函数)n定理 设G是n阶正定阵,向量组p1,p2,pk关于G共轭,对正定二次函数f(x)=xTGx/2+bTx+c 由任意初始点x1开始,依次进行k次一维搜索,xi+1=xi+ipi(i=1,2,k) 则(i)gTk+1pi=0 (i=1,2,k). (ii)xk+1是二次函数在k维超平面Hk上的极小点.n推论 当k =n时,xn+1为二次函数
14、在Rn上的极小点.共轭方向法共轭方向法(用于二次函数用于二次函数)n证明要点:只要证明gTk+1pi=0.11211()()TTTTTTkikkiiiiiigpggpggpgp1211()()TTTkkiiiiiiGxGxpGxGxpgp111TTTkkiiiiiip GppGpgp1kkkkxxp 0Tjip Gp 1Tiigp 精确一维搜索0 1( )2TTf xx Gxb xc共轭梯度法共轭梯度法(共轭方向的形成共轭方向的形成)n我们首先讨论针对下面二次函数的共轭梯度法n给定初始点x0,初始下降方向取为p0= -g0n从x0出发,沿方向p0进行一维搜索得x1.n设p1是-g1与p0的线性
15、组合p1= -g1+b0p0,np1与p0共轭,于是01010000TTTp Gpp Ggp Gpb b n因此01000TTp Ggp Gpb b 共轭梯度法共轭梯度法(共轭方向的形成共轭方向的形成)n假设已经沿k个共轭方向p0, p1, pk-1逐次进行一维搜索得xk.n若gk=g(xk)=0,则xk已是极小点,否则构造下一个方向pk.令pk为-gk以及p0,p1,pk的线性组合.10kkkiiipgpb b n用pjTG(j=0,1,k-1)左乘上式100kTTTjkjkijiip Gpp Ggp Gpb b TTjkjjjp Ggp Gpb b TjkjTjjp Ggp Gpb b n
16、因此共轭梯度法共轭梯度法(共轭方向的形成共轭方向的形成)再根据二次函数的性质,有0TTjkjjjp Ggp Gpb b 10kkkiiipgpb b 1jjjjxxp 由于有11()jjjjGpG xx 11()jjjjG xxgg因此11()TTjkkjjjp Ggggg 由于xk是由点x0及向量p0,p1,pk-1得到的k维超平面上的极小点,因此gkTpj=0(j=0,1,k-1).由pj的构造方式10jjjijiipgpb b 因此gkTgj=0(j=0,1,k-1).共轭梯度法共轭梯度法(共轭方向的形成共轭方向的形成)0TTjkjjjp Ggp Gpb b 111111011Tkkkk
17、kiikkkkkTikkgGppgpgpgppGpbbbb 因此11()TTjkkjjjp Ggggg gkTgj=0(j=0,1,k-1)0(0,1,2)Tjkp Ggjk根据得0(0,1,2)jjkb b所以1111TkkkTkkg GppGpb b 定理 对正定二次函数由上面三式所确定共扼方向并采用精确一维搜索得到的共轭梯度法,在m(n)次迭代后可函数的极小点,并且对所有i(1im)有1( )2TTf xx Gxb xc10011111,TkkkkkkkTkkg GppgpgppGpbbbb 0,0,0,TTTTTijijijiiiip Gpg gg pp gg g 0,1,1.ji共轭
18、梯度法共轭梯度法(用于二次函数用于二次函数)其中FR算法算法111TkkkTkkg gggb b (1)Flecher-Reeves公式为了能将上述方法用于其它函数,我们必须消去系数中的G.1111TkkkTkkg GppGpb b 1111111()()kkkkkkkGpGxxgg1111()TTkkkkkkg Gpggg 11Tkkkg g 11122111() ()TTkkkkkkkkpGpgpggb b 1111Tkkkgg 所以(2)Polak-Ribiere-Polyak公式1111()TkkkkTkkgggggb b PRP算法算法111TkkkTkkg gggb b 由于gkT
19、gk-1=0,所以有对于二次函数,这两个函数是等价的,但对于一般的函数,根据这两个公式的出的算法的计算效果有差异.FR算法中:n注:对于这两个算法,可以证明pkTgk= -gkTgk0,因而都是下降算法.由g0=(-2,0)T0,故取p0=(2,0)T,从x0出发,沿p0作一维搜索,即求min f (x0+ p0)=6 2-4 的极小点,得0 =1/3 ,于是x1=x0+ 0 p0=(2/3,0)T,g1=(0,-2/3)T,由FR公式得b0=g1Tg1/g0Tg0=1/9故p1=-g1+b0p0=(2/9,2/3)T.例 用FR共轭梯度法求解(x0=(0,0)T)221212131min(
20、)222f xxxx xx1221( )(32,)Tg xxxxx共轭梯度法算例共轭梯度法算例解注:此处不需求G.从x1出发,沿p1作一维搜索,求211442min()2793f xp2111(1,1) .Txxp 2(0,0) ,Tg *2(1,1) ,1Txxf 解得1=3/2,于是此时的极小点故此算例中,f(x)为二元的正定二次函数,因此FR算法迭代两次得到最优点共轭梯度法算例共轭梯度法算例例 用FR方法与PRP方法求解222211min( )100()(1)f xxxx设初始点为x0=(0,0)T.解:22211121( )( 400()2(1),200()Tg xxxxxxx 由g0
21、=(-2,0)T0,故取p0=(2,0)T,从x0出发,沿p0作一维搜索,即求min f (x0+ p0)=1600 4+42-4+1的极小点,得0 =0.080632,(精确一维搜索方法求得,e =10-5,)于是x1=x0+ 0 p0=(0.161264,0)T,g1=(0.000065,-5.201215)T.共轭梯度法算例共轭梯度法算例222211min( )100()(1)f xxxx22211121( )( 400()2(1),200()Tg xxxxxxx p0=(2,0)T,x1=(0.161264,0)T,g1=(0.000065,-5.201215)T,由FR公式得b0=g
22、1Tg1/g0Tg0=6.763160故p1=-g1+b0 p0=(13.526254,5.201215)T.进一步可以以下的迭代,所得的结果(终止准则为|gk|10-12 ,55步收敛)见下表.最终得到x*(1,1)T.FR方法计算结果n从最后两组数据可以看出,虽然函数值下降,但是迭代点离最优点的距离却有所增加.kxkf(xk)|g(xk) |0 (0,0)T121 (0.161264,0)T0.7711105.2012152 (0.292861,0.050603)T0.6237037.53526110 (1.006492,1.015405)T6.07e-41.05720420 (1.000
23、035,1.000074)T3.02e-90.00184330 (1+1.31e-7,1+2.69e-7)T2.21e-142.89e-640 (1+0.51e-9,1+1.03e-9)T2.79e-195.40e-950 (1+2.10e-12,1+4.26e-12)T4.74e-242.16e-1154 (1-1.14e-13,1-2.51e-13)T6.14e-269.63e-1255 (1-1.42e-13,1-2.86e-13)T2.06e-265.55e-13对于PRP算法,计算过程类似.计算15步收敛, x*(1,1)T对于此例,PRP方法比FR方法收敛快.计算结果见下表.PRP
24、方法计算结果kxkf(xk)|g(xk) |0 (0,0)T121 (0.161264,0)T0.7711105.2012152 (0.292861,0.050603)T0.6237047.5353503 (1.139761,1.300789)T0.0198340.61764810 (1+6.95e-10,1+9.93e-10)T1.63e-171.79e-711 (1+1.36e-9,2.69e-9)T1.90e-181.27e-812 (1+2.13e-10,1+4.66e-10)T1.99e-191.71e-813 (1-0.69e-11,1-1.35e-11)T6.31e-231.85
25、e-1014 (1-2.43e-13,1-5.50e-13)T4.60e-272.79e-1215 (1-0.93e-14,1-1.82e-14)T1.07e-282.15e-13重新开始的共轭梯度法（补充）重新开始的共轭梯度法（补充）n对于FR算法和PRP算法,如果初始方向不取负梯度方向,即使对于二次函数,也不能产生n个共轭方向.n因此,在用这两个方法时,如果迭代到距离最优点比较近,函数接近与一个二次函数时,我们重新取搜索方向为负梯度方向.n一般在实际应用中迭代n步或n+1步时重新设定搜索方向为负梯度方向.重新开始的共轭梯度法n对于前面的例子,采用重新开始的共轭梯度法得到的收敛步数为:nFR算法: 迭代n步重新开始,49步收敛n迭代n+1步重新开始,31步收敛nPRP算法: 迭代n步重新开始,27步收敛n迭代n+1步重新开始,13步收敛n由于此处n比较小,改善并不明显.
