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

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