《最优化方法第三章课件.ppt》由会员分享，可在线阅读，更多相关《最优化方法第三章课件.ppt（26页珍藏版）》请在三一办公上搜索。
1、3.4 共轭方向法与共轭梯度法,共轭方向法是介于最速下降法和Newton法之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与Newton法相比，减少了计算量和存储量。它是比较实用而有效的最优化方法。,共轭方向法涉及共轭方向的概念和性质。共轭方向的概念是在研究正定二次函数,（3.36）,时产生的。本节和下节所介绍的方法有一个共同的特点，即首先以（3.36）为目标函数给出有关的算法，然后再把算法用到更一般的目标函数上。,本节内容对今后许多章节起着基础的作用。,1.基本思想,现在把下降法用于形式为（3.36）的二次函数。为便于说明
2、共轭方向法的基本思想，首先考虑二维的情形。,（图314）,任选初始点,，沿它的某个下降方向，例如向量,的方向，作直线搜索，得到（图314）。,由（4.16）知,(3.37),一个设想是，干脆选择下一个迭代的搜索方向,就从,直指极小点,怎样确定，它应该满足什么条件？,因为,从,直指极小点,，所以,可以表示为,（3.38）,其中,是最优步长因子。显然，当,时，,。,对（3.36）求导数，有,（3.39）,因为,是极小点，所以有,将（3.38）代入此式，并由（3.39）可得,上式两边同时左乘,，并注意到,和,便得到,（3.40）,.,这就是为使,直指极小点,，,所必须满足的条件。,满足（3.40）的
3、两个向量,和,称为,共轭向量，,和,的方向是,共轭方向。,或称,利用（3.40）可以给出,的表达式。设,（3.41）,上式两边同时左乘,，得,由此解出,并代回到（3.41），便得,（3.42）,.,归纳一下，对于二元二次目标函数，从任意初始点,出发，沿任意下降方向,做直线搜索得到,；再从,出发，沿,的共轭方向,（可由（3.42）确定）作直线,必是极小点,。,搜索，所得到的,上面的结果可以推广到,维空间中，即在,维空间中，,个互相共轭的方向，对于,元正定二次函数，,个共轭方向最多作,直线搜索，就可以求到目标函数的极小点。,可以找出,从任意初始点出发，顺次沿着这,次,对于 元正定二次目标函数，如果
4、从任意初始点出发经过有限次迭代就能够求到极小点，那么称这种算法具有二次终止性。例如，Newton法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；而最速下降法就不具有二次终止性。共轭方向法（如共轭梯度法、拟Newton法等）也是二次终止的。,一般说来，具有二次终止性的算法，在用于一般函数,时，收敛速度是较快的。,2.共轭向量及其性质,定义3.3 设,是,对称正定矩阵。若,维向量,满足,空间中的非零向量,（3.43）,则称,是,共轭向量或称向量,是,共轭的（简称共轭），称,的方向是,方向。,共轭,当,（单位矩阵）时，（3.43）为,即向量 互相正交。由此看到，“正交”是“共轭”的
5、一种特殊情形，或说，“共轭”是“正交”的推广。,以下各定理都是描述共轭向量的性质以及在极小化正定二次函数的过程中以共轭方向作为搜索方向所得到的有关结论。,定理3.2 若非零向量,是,共轭的，,则线性无关。,推论3.3 在,维向量空间中，非零的共轭向量的,。,个数不超过,设,是,中的非零,共轭向量。因为,的一个,维子空间，,维子空间中的任意一个向量,均可表示为,线性无关，所以由它们可以张成,且这个,其中,是任意实数。,定义3.4 设,是,中的线性无关向量，,。那么形式为,的向量构成的集合，记为,，称为由点,和向量,所生成的线性流形。,3.共轭方向法,共轭方向法的理论基础是下面的定理。,定理3.4
6、 假设,（1）,为,对称正定矩阵；,（2）非零向量,是,共轭向量；,（3）对二次目标函数（3.36）顺次进行,次直线搜索,其中,是任意选定的初始点，则,）,；（3.44）,）,是二次函数（3.36）在线性流形,上的极小点。,证）根据（1.46），直接有,证明：对于,，（3.44）也成立。,。以下,由条件（3），有,其中,是从点,出发沿,方向作直线搜索得到的最优,步长因子。,用,左乘上式两边，然后再同时加上,，,利用（3.39）就得到,（3.45）,由这个公式，可以递推得到,该式两边同时左乘,，得,.,.,此式右边各项实际全部为零。这是因为,故由（1.46）知,。又由,的共轭性知其余各项也全部为
7、零。这就证明了（3.44）。,）按条件（3），必有,于是，存在一组数,使得,（3.46）,而对于任意给定得,，存在另一组数,使得,（3.47）,（3.47）减（3.46），得,利用（3.44），由上式即得,（3.48）,把二次函数,在点,处作Taylor级数展开,，注意到（3.48），就有,然后令,，,由条件（1），当,时，有,。,于是，对于任意,，但,，总有,，即,是（3.36）在线性流形,上的（严格）极小点。,这个定理看来较繁，但可借用直观的几何图形来帮助,的情形为例，如图示。,理解。以,和,是,共轭向量，张成了二维空间,，这是过,坐标原点的一个平面。,现在，过点,沿,方向作直线,，再过点
8、,沿,方向作直线搜索得到,搜索得到,点,由向量,和,张成的平面就是线性流形,，,。过,，它是,的平行平面。定理3.4的论断是，,处的梯度,必与,和,并且,最后一个迭代点,垂直，,是三元二次目标函数,在线性流形,（即过,由,和,张成的平面）上的极小点。,当,时，线性流形,整个,维空间,，因此有如下推论。,就是,推论3.5 在定理3.4中，当,时，,是正定,中的极小点。,函数（3.36）在,二次,推论3.6 在定理3.4中，,的任意线性组合,（其中,是任意实,数）都与,正交。,上述论断提供了求正定二次函数（3.36）极小点的一,出发，顺次沿,个,共轭方向作直线搜索，最多经过,次迭代就一定可以求,种
9、原则方法。这就是，从任意初始点,到极小点。,算法3.6（共轭方向法）P136,算法第4步中提供共轭方向的方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名，例如共轭梯度法。,下面将介绍几个有效的共轭方向法。,4.共轭梯度法,在共轭方向法中，如果初始共轭向量,恰好取为,处的负梯度,，而其余共轭向量,点,初始,由第,个迭代点,处的负梯度,与已经得到的共轭向量,负梯度而得名。首先针对目标函数是（3.36）形式的正定,的线性组合来确定，那么这个共轭方向法就称为,共轭,梯度法。它因每一个共轭向量的产生都依赖于迭代点处的,二次函数来讨论。,（1）第1个迭代点的获得,选定初
10、始点,。设,（否则迭代终止），因此,。取,（3.52）,则第1个迭代点,其中,显然,。,（2）第2个迭代点的获得,设,，因此,。由,知,与,线性无关。取,（3.53）,其中,是使,与,共轭的待定系数。令,由此解出,并代回（3.53）确定,。并获得第2个迭代点,其中,（3）第3个迭代点的获得,设,，因此,。由,知,与,线性无关。取,其中,是使,与,共轭的待定系数。令,由此解出,从而确定,。并获得第3个迭代点,其中,上述过程仅表明,与,，,与,共轭。问：,与,也共轭吗？计算,且由（3.52）和（3.53）知,和,都是,和,的线性组合，,而必有,，因此,，即,与,也共轭。,如此做下去，设已经构造出共
11、轭向量,，,并已获得前,个迭代点,，而且步长因子,均不为零。,个迭代点的获得,设,（否则迭代终止），此时,。由,知,是线性无关的，取,（3.54）,其中,是使,与,共轭的待定系数。令,（4）第,和,，且,由此解出,从而确定了,。并获得第,个迭代点,其中,除与,共轭外，它还与,共轭。,因此，在,均不是极小点,的前提下，,可以按照上述方法顺序构造出,个非零共轭向量。根据,定理3.4，第,个迭代点,必是（3.36）的极小点,。实际,次迭代（,）就求,。,计算中，也有可能第,到了极小点，此时,算法3.7（用于正定二次函数的共轭梯度法）P166,例3.3 P167,用共轭梯度法求解,初始点取为,。,为使
12、共轭梯度算法3.7也适用于非二次函数，最好消,。,去（3.57）中的,由（3.45），有,代入到（3.57）中，得,（3.59）,此式中已不再出现矩阵,。另外，此式还可以有以下三种,不同的等价形式。,将（3.54）两端作转置运算，并同时右乘,，得,（3.60）,根据定理3.4知，,；又根据直线搜索的性质知,（3.61）,于是，由（3.60）得,（3.62）,又将（3.54）两端作转置运算，并同时右乘,，得,（3.63）,（1）把（3.61）、（3.62）和（3.63）代入到（3.59）,中，得,（3.64),此式称为FletcherReeves公式(1964年)。,（2）把（3.61）和（3.
13、62）代入到（3.59）中，得,（3.65),此式称为DixonMyers公式(1972年)。,（3）把（3.61）和（3.63）代入到（3.59）中，得,(3.66),此式称为PolakRibiere公式(1969年)。,在前面给出的用于正定二次函数的共轭梯度算法3.6中，分别以（3.59）、（3.64）、（3.65）和（3.66）替换（3.57）就将得到四种不使用Hesse矩阵的共轭梯度法，它们对于正定二次目标函数和精确的直线搜索是完全等价的，都可以用于非二次目标函数。,由公式（3.63）看到，对于一般目标函数，仍有,这说明共轭梯度法对于一般目标函数仍然是下降算法，即使迭代点距极小点很远，
14、这种方法也可以使用。,实际上，可以把共轭梯度法当作最速下降法的一种改进方法，因为当令所有的时，它就变为最速下降法。共轭梯度法的效果不低于最速下降法。共轭梯度法是收敛的算法。,共轭梯度法还有一个优点，就是存储量小。因为它不涉及矩阵，仅仅存放向量就够了，因此适用于维数较高的最优化问题。,共轭梯度不要求精确的直线搜索，这也是一个优点。但是，不精确的直线搜索可能导致迭代出来向量不再共轭，从而有可能不再线性无关，这将降低方法的效能。克服的办法是，重设初始点，即把经过,次迭代后得到的,作为初始点，再开始新一轮的迭代。计算实践指出，,用,比用,作初始点要好。,理论上，共轭方向法对每一步的一维搜索有很高的精度要求。,算法3.8(FletcherReeves共轭梯度法)P169,
