最优化理论与算法

第四章共轭梯度法共轭方向法共辗方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共辗方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。一、共轭方向定义4.1设G是nxn对称正定矩阵，d1，d2是n维非零向量，若dTGd2=0 （4.1）则称di，d2是G一共辗的。类似地，设dj,dm是Rn中一组非零向量。若dTGd=0（i中j） （4.2）则称向量组d,,dm是G一共辗的。注：（1）当G=・I・时，共轭性就变为正交性，故共辗是正交概念的推广。（2）若dj,dmG一共辗，则它们必线性无关。♦♦♦二、共轭方向法共辗方向法就是按照一组彼此共辗方向依次搜索。模式算法：1）给出初始点X，计算g=g（X），计算d，使dTg<0,k:=0（初始共辗方向）；0 0 0 0 002）计算a和x，使得f（x+ad）=minf（x+ad），令x=x+ad；3）计算dk+i，使dTGdj=0,j=0,1,,k，令k:=k+1,转2）。•••三、共轭方向法的基本定理共辗方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。

定理4.2对于正定二次函数，共轭方向法至多经过n步精确搜索终止；且对每个),都是fx)在线性流形Jxx=x+£ad,Va1中的极小点。【0，J证明：首先证明对所有的i<n-1，都有gT+idj=0,j=0,1,,i(即每个迭代点处的梯度与以前的搜索方向均正交)事实上，由于目标函数是二次函数，因而有g-g=G(x-x)=aGd1)当j<i时，gTd=gTd+£(g-g>di+1jj+1j k+1jjk=j+1=gTd+£adTGd=0

j+1j kkjj=j+12)当j=i时，由精确搜索性质知：gTd=0综上所述，有 gTd=0(j—0,1,i50)i+1j再证算法的有限终止结论。若有某个.gi+1-0(i<n-1)，则结论已知。若不然，那么由上面已证则必有： gTd―0(j—0,n-0)nj而由于d,,d是Rn的一组基，由此可得.g—00故至多经过n次精确一维搜索即可获得最优解。0 n-1 n下面证明定理的后半部分。由于f(x)——xtGx+bTx+c2是正定二次函数，那么可以证明,t)―f(x0+lLtd)j=0是线性流形上的凸函数。事实上,3(3(t0,,t)―f(x0+^Ltd)j=0——(x+£td)tG(x+£td)+bT(x+Etd)+c2 0jj0jj 0jjj=0 j=0 j—0

=1Et2(dTGd)+2.x JJJJJ=0E[xTGd+bTd]t=1Et2(dTGd)+2.x JJJJJ=00JJJ20 0 0j=0,tj的凸函数。因而由d：Gd10(尸0,,0知0，,t)为1,tj的凸函数。因而min(1min(10,,t.)E必+19(t0,(J=0,ON(x+lLtd)Td=0(J=0, ,i)0JJJJ=0注意到：当t=a.,(J=0,,i)时，Vi+1x+Etdi+1j=0而由定理前部分证明,在x,+1处有Vf(x+i)Tdj=gT+idj=0(J=0,,i)，故在(10,,t)=(a。，,a)处，①(10,,t)取得极小，.即x二x+Eadi+1 0 iJJ=0是f(x)在线性流形上的极小点。§4.2共轭梯度法上节一般地讨论了共辗方向法，在那里n个共辅方向是预先给定的，而如何获得这些共辗方向并为提及。本节讨论一种重要的共辗方向法一一共辗梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共辗方向，故而称之为共辗梯度法。一、共轭梯度的构造(算法设计针对凸二次函数)设 f(x)=-2xtGx+bTx+c其中G为nxn正定矩阵，则g(x)=Gx+b。对二次函数总有 gki-gk=G(x^i-xk)=akGdk1)设X为初始点。首先取d=-g，令x=x+ad（a为精确步长因子）0 0 1 0 00 01)设X为初始点。首先取d=-g，令x=x+ad（a为精确步长因子）0 0 1 0 00 0则有：g巴=0（精确一维搜索性质）。22今di=-gi+P0d0，适当选择爆，使d1Gd「0，gfGdp= 00dTGd0gT(g-g) gTg=―k—i 0—=i~idT(g-g)gTg0i0 00（从而得到d）

i由前一节共轭方向法的基本定理有:gTd=0,gTd=0,再由d0与di的构造，还可得：gTg=0,gTg=02i 203)再令d2=-g2+P0d0+Pi4,适当选择P0,Pi使得d科=0（i=0」）,由此得:gT(g-g) gTgp=0,p=—2 2 i-=-2―20 i dT(g-g)gTgi2iii4)一般地，在第k次迭代中，令d=-g+tipd适当选取P，使diGd=0(i1=0,,k-1),kk ii ikii=0♦♦♦可得到 p=号Gi=g(gi+i_gi)(i=0,,k-1) (4.3)idrGddr(g-gi)同样由前一节共轭方向的基本定理有： ・•.gTd=0(i=0,,k-1),ki再由gi与dj的关系得： …gTg=0(i=0,,k-1)ki将(4.4)与(4.5)代入(4.3)得：当i=0,,k-2时，p=0,igT(g—g)….gTg而 p=-k k 1—= k-k-k-idT(g-g)gTgk-1k k-1 k-1k-1共轭梯度法的迭代公式为：（dk为共轭方向,ak为最佳步长因子）对二次函数gTda=———k——；k drGdkk而对非二次函数，则采用精确一维搜索得到a。kTOC\o"1-5"\h\z共轭方向的修正公式为：dk1=-g^1+P丸 （4.6）其中，Pk由下面诸式之一计算：p=8k।J号门-（Crowder-Wolfe公式） （4.7）k d（gk「gjgTgP=k.k门 （Fletcher-Reeves公式） （4.8）k gTgkkgT（g—g）p=—1^—I k- （Polak-Ribiere-Polyak公式） （4.9）k gTgkkgTgp=—kj1k. （Dixon公式） （4.10）kdTgkk注：对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轭方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的。（事实上，此时不存在一个常值正定矩阵G，共轭的提法都已无意义）。二、共朝梯度法的性质定理4.3对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过m<n步迭代后终止。且对1<i<m，下列关系式成立：1）drGd=0 （j=0,1,,i—1） （4.11）2）gTg=0 （j=0,1,：i—1） （4.12）ij3）dTg=-gTg … （4.13）4）[g°,g1,,g_]=[g0,Gg°,,Gig0] （4.14）5）[d0,d1,…,d.]=[g0,Gg」…,Gig0] （4.15）证明：先用归纳法证明（4.11）〜・・（4.13）。对于i=1,容易验证（4.11）,（4.12）,4.13）成立。现假设这些关系式对某个i<m成立，下面证明对于i+1,这些关系式仍然成立。事实上，对于二次函数，显然有+1i++1i+1—x)=g+aGd(4.16)对上式左乘dT，并注意到ai是精确步长因子，得drGddrGd(drGddrGd(4.17)利用(4.16),(4.17),得gTg=gTg=gTg+adTGgi+1jij=gTg,~adrG(d-Pjd)(4.18)当j=i当j=i时，（4.18）成为=gTg一ii■gg^dTGd=0dTGdiiii当j<i时，由归纳法假设可知gLgLgj=gTg—adTG(d-Pd)=0于是（4.12）得证。再由共轭梯度法的迭代公式及（4.17），有当j=i时,当j<i'时,又由于dTGd=-gTGd+PdT当j=i时,当j<i'时,又由于dTGd=-gTGd+PdTGd

i+1j i+1jiij由（4.12），山.17）及（4.8），（4.19）gjgj+1+PdTGda. ii成为(4.19)gTg gTgdTGd=-gi+1gi+1dTGd+3+13+1dTGd=0i+1i gTgiigTgiiii ii直接由归纳法假设知（4.19）为零，于是（4.11）得证。dTg=-gTg+pdTg =-gTgi+1i+1 i+1i+1 iii+1 i+1i+1于是（4.13）得证。下面利用归纳法证明（4.14）与（4.15）。当i1=1时,由d0=-g0及g1容易看出:[g0，g1]二[g0cg0]再由d=-g及d=-g+pd=-g-pg，001 1 00 1 00易见:[d0,d1]=[g0,g1]=[g0Gg0]。故当i=1时，（4.14）与（4.15）成立。假定（4.14）与（4.15）对i成立。下证结论对i+1也成立。由于g+1=g.+aGd,由于而从归纳法假设知g,de[g,Gg而从归纳法假设知g,de[g,Gg,,Gig]ii0 0故有ge[g,Gg,・；Gi+ig]i+1 0 0还可证明:g电[g,Gg，…,Gig]=[d,d,,d]i+1 0 0否则由g否则由ge[d,d,・,・d]及gTd=0(j=0,,i)(共轭方向法基本定理)i+1 01i i+1j则必有g=0（与算法结束前，不会出现g=0.矛盾）i+1i+1因此[g,g,,g]则必有g=0（与算法结束前，不会出现g=0.矛盾）i+1i+1因此[g,g,,g]=[g,Gg,0 1 i+1 0,Gi+1g0]再由立即有:[4，/i+1]=[g0，g1，，gi+1]=[g,Gg,,Gi+1g]。00定理证毕。注：1）上面定理中出现的这些生成子空间通称为Krylov子空间;2）在共轭梯度法中，dk--8卜+1+P乩，若采用精确一维搜索,则P女不论采用哪种公式计算，都有gTd =-gTg+pgTd=-gTgk+1k+1 k+1k+1 kk+1k k+1k+1<0，即dk+1总是下降方向，若不采用精确一维搜索，则就不一定了;3）对Dixon公式,使用不精确搜索准则降dj“gTdk，。e（0,1），能保证搜索方向总是下降的。事实上，由7 gTg1d=g——k+1-k+1dk+1 k+1 dTgkkkgTdgT+1dkgT+1dk+1=-%gk+11gTd

kkgg3dk«fgTdngTd<-gTdkk k+1kkk

gTdnk/k>一1(由gTd<0)，gTd kkkk由此即得 gT+1dk+1<0故dk+1为下降方向;4）Fletcher4）Fletcher—Reeves公式最为简洁,使用得最多;5)共轭梯度算法用于非二次函数时，没有有限终止性质，一般经诬次搜索后，就取一次负梯度方向，称再开始。Polak-Ribiere-Polyak具有自动再开始的特点，事实上，当算法改进不大时，会出现8k+1xgk，这时用Polak-Ribiere-Polyak公式计算出的Pk-0，从而导致d^讨«—g^讨。§4.3共朝梯度法的收敛性由前面的讨论已经知道，当共轭梯度算法用于正定二次函数时必定有限终止。本节研究将其用于一般非二次函数时的收敛性问题。一、共朝梯度法的总体收敛性定理4.4设水平集L=｛xf(x)<f(x)｝有界，f是Rn上具有一阶连续偏导数的凸函数。｛x｝是0 k由Fletcher-Reeves共轭梯度算法产生的迭代点列。则1)｛f(x))为严格单调下降序列，且limf(x)存在。k ks k2)｛x｝的任意聚点都是最优解，于是：limf(x)=minf(x)。k kfB k xeRn证明：在算法迭代过程中，由于每隔n次采用一次再开始措施。因而搜索方向要么是共轭梯度方向，要么是最速下降方向。但不管是哪种情形都有：gTd=—\|g||2<0 (采用严格一维搜索)kk k"因而｛f(x))单调下降，又由L有界，故｛f(x)］也有下界，因此limf(x)存在，记为f*。又由k k 7 kkfB｛f(xj｝单调下降，知｛xjuL，故｛xk｝是有界序列。设｛xJ1是｛xJ中的这样的一个子列：从，出发按最速下降方向-gk得到xk+1。由｛xJ1有界,故存在收敛子列｛x｝，使limx=x*。kK2 kfBk使limx=x，使limx=x，, k+1kfBkeK3IQ又｛x｝也是有界点列，故存在子列｛x｝K2 K3f(x*)=f(x)=limf(x)=fkfBk下面用反证法证明Vf(x*)=0。若不然，设Vf(x*)丰0，则对充分小的a，有f(x*-aVf(x*))<f(x*)注意当keK3时，f(x^+1)= f(x+a k d)= f( x— k gk)< f苫 ga>0

令k-8，则有 f(元)<f(x*—ag*)<f(x*)与(*)式矛盾，故必有Vf(x*)=0。再由f(x)是凸函数，即知x*是最优解。因而有minf(x)=f(x*)=limf(x)xeRn kf8 "进一步地，对点列｛x｝的任一极限点x，必存在｛x｝的子列IJ｛x｝，使得limx=x。k k kK0 k-8kkeK0进而有 f(x)=f(limx)=limf(x)=f(x*),k, kk-8 k-8keK0这表明：x也是问题的最优解。注：由这个定理的证明过程易见：上述收敛定理对其它几种共轭梯度算法也是成立的。定理4.5假设水平集L=｛x\f(x)<f(x0)｝是有界集，Vf(x)在其上Lipschitz连续，则采用精确一维搜索的Crowder-Wolfe再开始共钝梯度法产生的点列｛xk｝至少存在一个聚点是驻点。证明：与前一定理的证明类似，略。定理4.6(Polak-Ribbiere-Polyak算法的总体收敛性)设f(x)二阶连续可微，水平集L=｛x\f(x)<f(xj｝有界。又设存在常数m>0，使得对xeL，有：m\y\<yTV2f(x)yVyeRn则采用精确一维搜索的P-R-P共钝梯度算法产生的点列｛xJ收敛于f(x)的唯一极小点。证明：只要证明c0s0k—g证明：只要证明c0s0k—gTd k kdkgk即-gTd2Pkkg』ldk||即可。事实上，若cos0k一gTd成立。由第二章的定理2.7知，必有Vf(xk)-0,若x*是｛xk｝的极限点，由由f(x)的连续性，则有Vf(x*)=0，由f(x)的凸性，即知x*是极小点。再由f(x)在水平集L上一致凸，知｛x｝的极限点必唯一。否则设x是｛x｝的另一极限点，则kk也有Vf(x)=0。因此，0=(x*-x)t(Vf(x*)-Vf(x))=(x*-x)tV2f也)(x*-x)这与一致凸的假设矛盾，所以｛xJ只有唯一极限点。

可证：有界点列｛%｝若只有唯一极限点%*，则必有lim%=%*。故｛%k｝收敛于于（%）的唯一极小点。下证:-gTd>p(1)由于采用了精确一维搜索故有因而（1）式等价于k>p可证：有界点列｛%｝若只有唯一极限点%*，则必有lim%=%*。故｛%k｝收敛于于（%）的唯一极小点。下证:-gTd>p(1)由于采用了精确一维搜索故有因而（1）式等价于k>pIdkHk(2)得：其中再注意到，由（3）得又由L有界，因而由前述分析，grd -grd=aJ1drG(% +1akk-1 k-1k-1 k-10k-1 k-1 ,d)ddtak-1Gk-1gkPk-1grd k1k1—

kGk-1dk-1忆』2

k1叱Gk-1dk-（3）=J1G(% +ta d)dt。0 k-1 k-1k-1%)J= G%-1 0 -1OFt-1O) d 碎t Gd-1 -1 -1 -1 -1 -1gT(g,-g,,)—k k k-1-g-1gk-1=ak-1g；Gk111

.J2

k-1忆上

k-1gTG/-drGdk-1k-1k-1KJ陀1d/

mMJP故存在常数M>0，使得［GJ）y||<M||yPk-1同MdJ二"刈midJk-1MJ/目g」fk-Jidk-Jig』+》gJl=(1+竺)1gllkmk定理得证。上述总体收敛性定理均建立在精确一维搜索基础之上。Al-Baali（1985）研究了采用不精确一维搜索的Fletcher-Reeves共轭梯度法。发现若采用Wolfe-Powell不精确一维搜索准则，也有总体收敛性。10定理4.7若a由不精确一维搜索的Wolfe-Powell准则产生，那么Fletcher-Reeves共钝梯度算法具k体下降性质：g巴定理4.7若a由不精确一维搜索的Wolfe-Powell准则产生，那么Fletcher-Reeves共钝梯度算法具k体下降性质：g巴<°。证明：先用归纳法证明:j=ogTdT-)kJ4<—2+£oj|2j=0i其中。e(0,)是W-P准则中的。。当上=0时，(*)成为等式，故结论成立。假设对任何人20,(*)式成立，现考虑左+1情形。gTdgII2k+1”=—1+PkgTdhlkgII2

k+lu=-1+2储号"grd<Z+lk-agTdkkQTdstd,gTd—1+0-kk-«—^+4-V-1grd<Z+lk-agTdkkQTdstd,gTd—1+0-kk-«—^+4-V-1-O'-k:g/2gII2

k+1"再由归纳法假设，有Sgj=-1-c)2Lc>j«—1+oj=0J=0grdkk瓦『vgTd<hlhl似II2

k+111<一l—o <-l+c>2Lc>j=-2+Ec>jj=o-2aj<町41<-2+Ec>joJ=oJ=0利用已经证明的(*)式，并注意到j=°j=o—2+