最优化理论与算法

1、百度文库-让每个人平等地提升自我第四章共钝梯度法/ 共轲方向法共轲方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈 锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轲方 向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。一、共轲方向 TOC o 1-5 h z 定义 设G是n n对称正定矩阵，d1 , 2是n维非零向量，若d；Gd20()则称d1, 2是6 共轲的。类似地，设 dj/dm是Rn中一组非零向量。若dTGdj 0(i j)()则称向量组dijdm是G 共轲的。注：(1)当G I时，共轲性就变为正交性，

2、故共轲是正交概念的推广。(2)若dij,dm G 共轲，则它们必线性无关。二、共轲方向法共轲方向法就是按照一组彼此共轲方向依次搜索。模式算法：1)给出初始点xo,计算go g(xo),计算do,使dTg。 0 , k : 0 (初始共轲方向)2)计算 k 和 Xki,使得 f(Xkkdk) mipf(Xkdk),令 Xki Xkkdk；3)计算 dk i,使 dTiGdj 0, j 0,1,|,k,令 k: k 1,转 2)。,/三、共轲方向法的基本定理共轲方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得 到最优解(当然要执行精确一维搜索)。百度文库-让每个人平等

3、地提升自我定理 对于正定二次函数，共轲方向法至多经过n步精确搜索终止；且对每个为1,都是f (x)在线性流形x x Xojd j, j中的极小点。、j 0证明：首先证明对所有的i n 1,都有gTidj 0, j 0,1,|,i (即每个迭代点处的梯度与以前的搜索方向均正交)事实上，由于目标函数是二次函数，因而有gk 1 gk G xk i xkkGdkT , T , iT ,i)当 j i 时，gi idjgj idjgk i gk djk j igT idjkdTGdj 0k j i2)当j i时，由精确搜索性质知：gTidj 0综上所述，有gT1dj 0 (j 0,i1|,i)o再证算法

4、的有限终止结论。若有某个gi i 0 ( i n i),则结论已知。若不然，那么由上面已证则必有：g：dj 0(j 0,| | ,n i)。而由于d0,|,dn i是Rn的一组基，由此可得gn 0。故至多经过n次精确一维搜索即可获得最优解。 下面证明定理的后半部分。由于f (x) xT Gx bTx c 2是正定二次函数，那么可以证明(t0, ,ti) f(xtjdj) TOC o 1-5 h z j 0/是线性流形上的凸函数。事实上，(tJ|,ti) f(xtjdj)j 0iiTiTi二(xtjdj) G(xtjdj) b (xtjdj) c2j 0j 0j 01 i 2 二-tj(djGd

5、j)2 j 0百度文库-让每个人平等地提升自我_ T _ . T . _1 T _T%Gdj b djtj (2 xoGxo b x c)由 d；Gdj0(j 0,|U，i)知(to,|,ti)为 to,|“,ti 的凸函数。因而(”限1 (toJl 卜 ti)% 0 (j Ml)f(xotjdj)Tdj 0 (j 0,|1i)j 01注意到：当tjj , (j 0,“|,i)时,xtjdjj 0 x0jd j xi 1 j 0而由定理前部分证明，在x 1处有f(x)Tdjg：1dj 0(j 01|,i),故在(t0，Mti)( 0,|, i)处，(t0,|,ti)取得极小，即x 1x0idj

6、j 0是f(x)在线性流形上的极小点。 共辗梯度法上节一般地讨论了共轲方向法，在那里n个共轲方向是预先给定的，而如何获得这些共轲方向并为提及。本节讨论一种重要的共轲方向法一一共轲梯度法。这种方法在迭代过程中通过对负梯度 方向进行适当校正获得共轲方向，故而称之为共轲梯度法。一、共轲梯度的构造(算法设计针对凸二次函数)、一1 TT设f (x) x Gx b x c2其中G为n n正定矩阵，则g (x) Gx b。对二次函数总有gk 1gkG xk1kGdk百度文库-让每个人平等地提升自我1）设x0为初始点。首先取 d0 go,令X1X00 d0（ 0为精确步长因子）则有：g1Td00 （精确一维搜

7、索性质）2)令 d1 g10d0,适当选择 ，使 d：Gd00,g；Gd00 d0Gd0g1 (g1 g。)dT(gi g)T粤如（从而得到djg0 g0由前一节共轲方向法的基本定理有:gTd10,gTd00,再由d0与d/勺构造，还可得:gTg10,3)再令 d2 g20d01d1,适当选择1,使得 d；Gdi 0 (i0,1）,由此得:0,1gT(g2 gi)d1T (g2gi)Tg2 g2Tg1 g1般地，在第k次迭代中,令dkkgk可得到gTGdi i dTGdig：(g 1同样由前一节共轲方向的基本定理有：gTdi0 (iidigi)diT(gi 1 gi)0,|,k 1),再由gi

8、与di的关系得:gTgi 0 ( i 0,将（）与（）代入（）得：当 i 0,|,kgT(gk gk共物梯度法的迭代公式为对二次函数适当选取使dTGdi0 (i 0,|,k 1),i 0,|,k 1)（）II2时,1)k 1 dT 1(gk gk 1)OT gkgkT gk 1gk 1Xk 1 Xkkdk （dk为共轲方向，k为最佳步长因子）百度文库-让每个人平等地提升自我gTdkdTGdk ；而对非二次函数，则采用精确一维搜索得到共轲方向的修正公式为：d其中,gk 1k由下面诸式之kdk1)Tgk1(gk1 gk) dkT(gk 1 gk)C Crowder-Wolfe 公式)2)Tgk 1

9、gk 1Tgkgk()0(Fletcher-Reeves 公式)3)gT1(gk1 gk)Tgkgk(Polak-Ribiere-Polyak 公式)0Tgk 1gk 1dTgk(Dixon 公式)对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轲方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轲的。在一个常值正定矩阵 G ,共轲的提法都已无意义）（事实上，此时不存二、共辗梯度法的性质定理 对于正定二次函数， 采用基于精确一维搜索的共轲梯度算法，必定经过m n步迭代后终止。且对1 i m,下列关系式成立：1) dGdj 0(j 0,1,|,i 1

10、)()2)gTgj 0( j0,1,|,i 1)()3)diTgigTgi/() HYPERLINK l bookmark92 o Current Document 4)g0,g1,|,gi g0,Gg0,(|,Gig0/()5)d0,d1,|,di g0,Gg0,|,Gig0/()证明：先用归纳法证明（）（）。对于i 1 ,容易验证（），（），）成立。现假设这些关系式对某个i m成立，下面证明对于i 1 ,这些关系式仍然成立。事实上，对于二次函数，显然有百度文库-让每个人平等地提升自我gi i gi G(Xi i x)giiGd对上式左乘diT,并注意到i是精确步长因子，得利用(),(),得

11、Tgi gjgTdidiTGdiTgi gidiTGdiT gi igjidiTGgjT gi gjidTG(dji时，（）成为日T gi igjTgi giTgi gidiT GdidTGdij idi时，由归纳法假设可知T gi igjTgi gjdTi iG(djj idj i)0得证。再由共轲梯度法的迭代公式及（）dTiGdjgTiGdjidiTGdjgT1ggj iidTGdj当j i时,由（），（）及（），（）成为当j i时,又由于dTiGdiTgi遍iTgi gidTGdiTg4gLi diTGdi 0 gi gi直接由归纳法假设知（）0得证。是（）得证。dTigi iT gi

12、igiidTgi iT gi igi i卜面利用归纳法证明0 与二（）当i 1时,看出:goGg。再由d0g0 及 di gi0d0gi0g ，易见:g由d0 g。及gig00Gg 0，容易do,di gO,gig0,Gg0。故当i i时，（）与（）成立。假定（）与（）对 i成立。下证结论对i i也成立。百度文库-让每个人平等地提升自我由于giiGdi ,而从归纳法假设知故有还可证明：否则由则必有因此再由立即有：定理证毕。gi,di g0,Gg0,|,Gig0gi i goGgoJ/Gi 4gi 1 go,Ggo, IGigo do, di,| ,digi 1 d0,dij”,di及 gTid

13、j 0 （j 0,|,i）（共轲方向法基本定理）gi i 0 （与算法结束前，不会出现gi i 0矛盾）g0,gi, |（,gi i g0,Gg0,|,Gi ig0di i gi i idid0, |di i g, gi J|, gi i g0,Gg0,|,Gi ig0 o注：i)上面定理中出现的这些生成子空间通称为Krylov子空间;2)在共轲梯度法中， dk igkikdk ,若采用精确一维搜索，则k不论采用哪种公式计算，都有 gT idk i gTigk ikgTidkgT igk i 0,即dk总是下降方向，若不采用精确一维搜索，则就不一定了;gjdk,(0,i),能保证搜索方向总是3

14、)对Dixon公式，使用不精确搜索准则gT idk下降的。事实上，由Tgk igk i .dk igk i.Tdkdk gkTTgk idkgk idk igk igk i i -r-，gkdkgT idkgTdkgTidkgTdk ,%哈 i （由 gTdk 。）,gkdk由此即得gT idk i 0故dk1为下降方向;4) FletcherReeves公式最为简洁，使用得最多;百度文库-让每个人平等地提升自我5)共轲梯度算法用于非二次函数时，没有有限终止性质，一般经过 n次搜索后，就取一次负梯 度方向，称再开始。Polak-Ribiere-Polyak具有自动再开始的特点，事实上，当算法改

15、进不大时，会出现gk 1 gk,这时用Polak-Ribiere-Polyak公式计算出的k 0 ,从而导致dk 1 gk1。 4. 3共轲梯度法的收敛性由前面的讨论已经知道，当共轲梯度算法用于正定二次函数时必定有限终止。本节研究将其用 于一般非二次函数祢收敛性问题。一、共轲梯度法的总体收敛性定理 设水平集L x f(x) f(x0)有界，f是Rn上具有一阶连续偏导数的凸函数xk是由Fletcher-Reeves共轲梯度算法产生的迭代点列。则1) f (xk)为严格单调下降序列，且 lim f(xk)存在。k2) xk的任意聚点都是最优解，于是： lim f (xk) min f(x)。kx

16、Rn证明：在算法迭代过程中，由于每隔n次采用一次再开始措施。因而搜索方向要么是共轲梯度方向，要么是最速下降方向。但不管是哪种情形都有：gTdk|gk|2 0(采用严格一维搜索)因而f (xk)单调下降，又由L有界，故f(xk)也有下界，因此lim f(xk)存在，记为f 。又由 k f (xk)单调下降，知xkL ,故xk是有界序列。设xkK1是*1中的这样的一个子列：从xk出发按最速下降方向gk得到xk1。由xkK1有界,故存在收敛子列xkK 使lim xk x。 TOC o 1-5 h z kZk K2又xk 1K2也是有界点列，故存在子列xk 1 K3 ,使lim xk 1 x ,且23

17、 k/k K3小 HYPERLINK l bookmark110 o Current Document f (x) f (x) lim f(xk) f(*)k k.一、一、一一I*. . .*. . .下面用反证法证明f(x ) 0。若不然，设 f(x ) 0,则对充分小的 ，有_ * _ * _ *f(x f (x ) f (x )注意当k K3时,f (xk i)f (xkkdk)f (xkkgk) f (xkgk)百度文库-让每个人平等地提升自我令k ，则有f(x) f(x g ) f(x )与(*)式矛盾，故必有f (x ) 0。再由f(x)是凸函数，即知x是最优解。因而有_ _ *m

18、in f (x) f (x )X R1lim f (xk) k进一步地，对点列xk的任一极限点必存在Xk的子列XkK0,使得lim xk X。 kk Ko进而有f (X) f (lim Xk)kk Kolim f(Xk) f (x ) k这表明：？也是问题的最优解。注：由这个定理的证明过程易见：上述收敛定理对其它几种共轲梯度算法也是成立的定理假设水平集L x f(x) f(x)是有界集,f (x)在其上Lipschitz连续，则采用精确一维搜索的Crowder-Wolfe再开始共轲梯度法产生的点列xj至少存在一个聚点是驻点。定理与前一定理的证明类似，略。(Polak-Ribbiere-Poly

19、ak算法的总体收敛性)设f(x)二阶连续可微，水平集L x f (x)f (Xo)有界。又设存在常数 m 0 ,使得对x L ,有:m|y|2yT 2f(x)y yRn则采用精确一维搜索的P-R-P共轲梯度算法产生的点列 xk收敛于f(x)的唯一极小点。证明：只要证明cos kkgTdkgk dk，即 gTdk|gk|dk|即可。事实上，若cos kgTdkgk dk0)成立。由第二章的定理知，必有f(xk)0,若* _ _ _ .X是Xk的极限点，由 f (x)的连续性，则有f (x ) 0,由f(x)的凸性，即知x是极小点。再由f (x)在水平集L上一致凸，知xj的极限点必唯一。否则设/

20、?是xk的另一极限点，则 也有 f(5?) 0。因此,z_ T 9 _*_0 (x X) ( f (x ) f (X) (x X) f ( )(x X)这与一致凸的假设矛盾，所以 xk只有唯一极限点。百度文库-让每个人平等地提升自我可证：有界点列Xk若只有唯一极限点*x，则必有kim人*X。故xk收敛于f(x)的唯一极小点。下证:gTdk由于采用了精确一维搜索,故有|gk|g因而(i)1gk dk得:gkA2gkgkdkgk 1dk 1gT1dkdT1G(xk1 t k其中dkGkdk2*1dk Gk 1dk 1Gkgk10G(Xk 1 tgk 1 f (xk)应 1)dt 。1f(xk 1)

21、0G 1gT(gk gk 1)T gk & 1gk Gk 1dk 1g；(2)应 1)dk 1dt(3)k 1dk 1)k 1dk 1dt k 1Gk 1dk 1由(3)得gTGk 1dk1dk 1Gk 1dk 1gk | Gk 1dk 1m|dk J|又由L有界，故存在常数 M 0,使得|G(x)y| M | y| ,x L, y Rngk M lldk 1m |gk|m dk Jm dk 1因而dkgkdk1 gkM|gk m(1M) gk mllgkllIdkll(1M) 1m由前述分析，定理得证。上述总体收敛性定理均建立在精确一维搜索基础之上。Al-Baali (1985)研究了采用不

22、精确一维搜索的Fletcher-Reeves共轲梯度法。发现若采用Wolfe-Powell不精确一维搜索准则，也有总体收敛性。10百度文库-让每个人平等地提升自我定理若k由不精确一维搜索的Wolfe-Powell 准则产生,那么Fletcher-Reeves共轲梯度算法具体下降性质：g：dk 0。证明:先用归纳法证明:gTdk其中小1、口(0,2) 是w-p准则中的0时,(*)成为等式,故结论成立。假设对任何0,(*)式成立，现考虑k 1情形。gk 1dk 17T /gk i( gk 1gk12Tgkkd k )1dkT gk a 1gT 1dkgk2 gk1gTdkk 1dkgk2有gTdkgk2gk 1dk 1gk1gTdk gk2再由归纳法假设,1dk 12-gk1A,TgkTgkj 0利用已经证明的*)最后得gTdk0,证毕。111dkgk 1gTdk2gk并注意到gkdkgk