最优化方法第三章(2).课件.ppt

1、3.4 共轭方向法与共轭梯度法共轭方向法与共轭梯度法 共轭方向法是介于最速下降法和Newton法之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与Newton法相比，减少了计算量和存储量。它是比较实用而有效的最优化方法。 共轭方向法涉及共轭方向的概念和性质。共轭方向的概念是在研究正定二次函数 12TTfxx Qxb xc（3.36） 时产生的。本节和下节所介绍的方法有一个共同的特点，即首先以（3.36）为目标函数给出有关的算法，然后再把算法用到更一般的目标函数上。本节内容对今后许多章节起着基础的作用。1. 基本思想基本思想

2、现在把下降法用于形式为（3.36）的二次函数。为便于说明共轭方向法的基本思想，首先考虑二维的情形。（图314）0 x0p任选初始点，沿它的某个下降方向，例如向量的方向，作直线搜索，得到（图314）。 由（4.16）知 10()0Tf xp(3.37)一个设想是，干脆选择下一个迭代的搜索方向 1p1x*x就从直指极小点 1p怎样确定，它应该满足什么条件？1p1x*x*x因为从直指极小点，所以可以表示为*111xxt p（3.38）1t*1xx10t 其中是最优步长因子。显然，当时，。对（3.36）求导数，有 f xQxb （3.39）因为*x是极小点，所以有*0f xQxb将（3.38）代入此式

3、，并由（3.39）可得 1110f xt Qp0Tp 010Tpf x10,t 上式两边同时左乘，并注意到和便得到010Tp Qp （3.40）.1p*x1p这就是为使直指极小点，所必须满足的条件。0p1pQ0p1pQ满足（3.40）的两个向量和称为共轭向量，和的方向是共轭方向。或称利用（3.40）可以给出1p的表达式。设 1100pf xa p （3.41）,上式两边同时左乘0Tp Q，得 010000TTp Q f xa p Qp由此解出01000TTp Q fxap Qp并代回到（3.41），便得0111000TTp Q fxpfxpp Qp （3.42）.0 x0p1x1x0p1p2x

4、*x归纳一下，对于二元二次目标函数，从任意初始点出发，沿任意下降方向做直线搜索得到；再从出发，沿的共轭方向 （可由（3.42）确定）作直线必是极小点。搜索，所得到的nnnnnn上面的结果可以推广到维空间中，即在维空间中，个互相共轭的方向，对于元正定二次函数，个共轭方向最多作直线搜索，就可以求到目标函数的极小点。可以找出从任意初始点出发，顺次沿着这次n 对于 元正定二次目标函数，如果从任意初始点出发经过有限次迭代就能够求到极小点，那么称这种算法具有二次终止性二次终止性。例如，Newton法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；而最速下降法就不具有二次终止性。共轭方向法（

5、如共轭梯度法、拟Newton法等）也是二次终止的。一般说来，具有二次终止性的算法，在用于一般函数时，收敛速度是较快的。2. 共轭向量及其性质共轭向量及其性质Qn nn011,mppp定义定义3.33.3 设是对称正定矩阵。若维向量满足空间中的非零向量0,0,1,1()Tijp Qpi jmij（3.43）011,mpppQ011,mpppQ则称是共轭向量共轭向量或称向量是共轭的共轭的（简称共轭），称 011,mpppQ的方向是方向方向。共轭共轭当1Q （单位矩阵）时，（3.43）为0,0,1,1()Tijp pi jmij 即向量 互相正交。由此看到，“正交”是“共轭”的一种特殊情形，或说，“

6、共轭”是“正交”的推广。011,mppp 以下各定理都是描述共轭向量的性质以及在极小化正定二次函数的过程中以共轭方向作为搜索方向所得到的有关结论。011,mpppQ定理定理3.23.2 若非零向量是共轭的，则线性无关。nn推论推论3.33.3 在维向量空间中，非零的共轭向量的。个数不超过011,mpppnRQnRmmx设是中的非零共轭向量。因为的一个维子空间，维子空间中的任意一个向量均可表示为线性无关，所以由它们可以张成且这个10,miiixa p其中121,ma aa是任意实数。011,mpppnR0nxR定义定义3.43.4 设是中的线性无关向量，。那么形式为101210,miimizxa

7、 pa aaR0011;,mL xppp0 x011,mppp的向量构成的集合，记为，称为由点和向量所生成的线性流形线性流形。3. 共轭方向法共轭方向法共轭方向法的理论基础是下面的定理。定理定理3.4 假设Qn n（1）为对称正定矩阵；011,mpppQ（2） 非零向量是共轭向量； （3）对二次目标函数（3.36）顺次进行m次直线搜索11,0,1,1iiixs x pim 其中0nxR是任意选定的初始点，则）0,0Tjmpf xjm； （3.44）mx0011;,mL xppp）是二次函数（3.36）在线性流形上的极小点。10Tmmpf x0,1,2jm证证 ）根据（1.46），直接有证明：对

8、于，（3.44）也成立。以下由条件（3），有1iiiixxt pitixip其中是从点出发沿方向作直线搜索得到的最优步长因子。 Qb用左乘上式两边，然后再同时加上， 利用（3.39）就得到 1iiiif xf xtQp（3.45）由这个公式，可以递推得到11102mmjiiijf xf xtQpjm 该式两边同时左乘Tip，得11102mTTTjmjjijiijpf xpf xt p Qpjm .此式右边各项实际全部为零。这是因为 11,jjjxs xp故由（1.46）知 10Tjjpfx。又由 011,mppp的共轭性知其余各项也全部为零。这就证明了（3.44）。 0011;,.mmxL x

9、ppp011,ma aa）按条件（3），必有于是，存在一组数使得100mmiiixxa p（3.46）0011;,mxL xppp011,m而对于任意给定得，存在另一组数使得100miiixxp（3.47）（3.47）减（3.46），得10mmiiiixxap利用（3.44），由上式即得10()0mTTmmiiimixxf xapf x（3.48） f xmxxx把二次函数在点处作Taylor级数展开，注意到（3.48），就有然后令， 121.2TTmmmmmTmmmf xf xxxf xxxQ xxf xxxQ xxmxx0TmmxxQ xx由条件（1），当时，有 。于是，对于任意0011;

10、,mxL xppp mxx mfxfx，但，总有 mx0011;,mL xppp，即是（3.36）在线性流形上的（严格）极小点。 这个定理看来较繁，但可借用直观的几何图形来帮助2, 3mn的情形为例，如图示。理解。以0p1pQ2R和是共轭向量，张成了二维空间，这是过坐标原点的一个平面。 0 x0p1x1x1p2x现在，过点沿方向作直线，再过点沿方向作直线搜索得到 搜索得到0 x0p1p点由向量和张成的平面就是线性流形， 。过,;100ppxL2R2x)(2xf0p1p，它是的平行平面。定理3.4的论断是，处的梯度必与和并且 最后一个迭代点垂直，2x)(xf,;100ppxL0 x0p1p是三元

11、二次目标函数在线性流形（即过由和张成的平面）上的极小点。 nm ,;1100mpppxLnnR当时，线性流形整个维空间，因此有如下推论。就是nm nxnR推论推论3.53.5 在定理3.4中，当时，是正定中的极小点。函数（3.36）在二次110,mppp10miiip110,m 推论推论3.6 在定理3.4中，的任意线性组合（其中是任意实 数）都与)(mxf正交。 0 xnQn上述论断提供了求正定二次函数（3.36）极小点的一出发，顺次沿个共轭方向作直线搜索，最多经过次迭代就一定可以求种原则方法。这就是，从任意初始点到极小点。 算法算法3.6（共轭方向法） P136 算法第4步中提供共轭方向的

12、方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名，例如共轭梯度法。 下面将介绍几个有效的共轭方向法。 4. 共轭梯度法共轭梯度法0p0 x0g(1,2,1)kp kn 在共轭方向法中，如果初始共轭向量恰好取为处的负梯度，而其余共轭向量 点初始kkxkg1kp由第个迭代点处的负梯度与已经得到的共轭向量 负梯度而得名。首先针对目标函数是（3.36）形式的正定的线性组合来确定，那么这个共轭方向法就称为共轭共轭梯度法梯度法。它因每一个共轭向量的产生都依赖于迭代点处的二次函数来讨论。（1）第1个迭代点的获得0 x*0 xx0()0f x选定初始点。设（否则迭代终止），

13、因此。取00gp（3.52）则第1个迭代点 0001ptxx其中 000000000.TTTTp gg gtp Qpp Qp 显然00t。（2）第2个迭代点的获得*1xx10g 000gpT0p1g设，因此。由知与线性无关。取0011pgp（3.53）01p0p其中是使与共轭的待定系数。令00000101pQppQgpQpTTT由此解出10000,TTg Qpp Qp 并代回（3.53）确定1p。并获得第2个迭代点1112ptxx其中 1111111110.TTTTp gg gtp Qpp Qp （3）第3个迭代点的获得*2xx20g 021gpT1p2g设，因此。由知与线性无关。取1122p

14、gp12p1p其中是使与共轭的待定系数。令01111212pQppQgpQpTTT由此解出21111,TTg Qpp Qp 从而确定2p。并获得第3个迭代点2223ptxx其中 2222222220.TTTTp gg gtp Qpp Qp 0p1p1p2p0p2p上述过程仅表明与， 与共轭。问：与也共轭吗？计算2021 10201102010210021200() =0()3.45 )TTTTTTTTTp QpgPQpg Qpp Qpg Qpp Qpgggtg gg gt 因由（）（，0g1g0p1p且由（3.52）和（3.53）知和都是和的线性组合，而必有00212ggggTT200Tp Q

15、p 2p0p，因此，即与也共轭。如此做下去，设已经构造出共轭向量110,kppp，1,kxx110,kttt并已获得前个迭代点，而且步长因子均不为零。个迭代点的获得nk *xxk0kg 01kTkgp1kp设（否则迭代终止），此时。由知是线性无关的，取11kkkkpgp（3.54）1kkp1kp其中是使与共轭的待定系数。令k, 011111kTkkkTkkTkpQppQgpQp（4）第1k和k，且1kp由此解出kp1k从而确定了。并获得第个迭代点kkkkptxx1其中 1111,TkkkTkkg QppQp0.TTkkkkkTTkkkkp gg gtp Qpp Qp kp1kp210,kppp

16、除与共轭外，它还与共轭。,110nxxx*x因此，在均不是极小点的前提下，可以按照上述方法顺序构造出 n个非零共轭向量。根据定理3.4，第 nnx*x个迭代点必是（3.36）的极小点 mnm*mxx。实际次迭代（）就求。计算中，也有可能第到了极小点，此时*mxx算法算法3.7（用于正定二次函数的共轭梯度法） P166例例3.3 P167用共轭梯度法求解2212min4,xx01,1Tx 初始点取为 。为使共轭梯度算法3.7也适用于非二次函数，最好消Q。去（3.57）中的由（3.45），有)(11kkkkggtpQ代入到（3.57）中，得,)()(111kkTkkkTkkggpggg（3.59）

17、此式中已不再出现矩阵Q。另外，此式还可以有以下三种不同的等价形式。将（3.54）两端作转置运算，并同时右乘1kg，得.11111kTkkkTkkTkgpgggp（3.60） 根据定理3.4知，011kTkgp；又根据直线搜索的性质知01kTkgp（3.61）于是，由（3.60）得10Tkkg g （3.62）又将（3.54）两端作转置运算，并同时右乘kg，得.11kTkkTkkkTkkTkgggpgggp（3.63） （1）把（3.61）、（3.62）和（3.63）代入到（3.59）中，得21112,TkkkkTkkkgggg gg （3.64)此式称为FletcherReeves公式公式(1

18、964年)。（2）把（3.61）和（3.62）代入到（3.59）中，得11TkkkTkkggp g （3.65) 此式称为DixonMyers公式公式(1972年)。（3）把（3.61）和（3.63）代入到（3.59）中，得11()TkkkkTkkgggg g (3.66)此式称为PolakRibiere公式公式(1969年)。 在前面给出的用于正定二次函数的共轭梯度算法3.6中，分别以（3.59）、（3.64）、（3.65）和（3.66）替换（3.57）就将得到四种不使用Hesse矩阵的共轭梯度法，它们对于正定二次目标函数和精确的直线搜索是完全等价的，都可以用于非二次目标函数。由公式（3.6

19、3）看到，对于一般目标函数，仍有20TTkkkkkp gg gg 这说明共轭梯度法对于一般目标函数仍然是下降算法，即使迭代点距极小点很远，这种方法也可以使用。 实际上，可以把共轭梯度法当作最速下降法的一种改进方法，因为当令所有的时，它就变为最速下降法。共轭梯度法的效果不低于最速下降法。共轭梯度法是收敛的算法。 共轭梯度法还有一个优点，就是存储量小。因为它不涉及矩阵，仅仅存放向量就够了，因此适用于维数较高的最优化问题。 共轭梯度不要求精确的直线搜索，这也是一个优点。但是，不精确的直线搜索可能导致迭代出来向量不再共轭，从而有可能不再线性无关，这将降低方法的效能。克服的办法是，重设初始点，即把经过 1n次迭代后得到的 1nx作为初始点，再开始新一轮的迭代。计算实践指出，用 1nx比用nx 作初始点要好。 理论上，共轭方向法对每一步的一维搜索有很高的精度要求。算法算法3.8 (FletcherReeves共轭梯度法) P169