最优化理论与算法(第四章).doc

第四章 共轭梯度法4.1 共轭方向法共轭方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。一、共轭方向定义4.1 设是对称正定矩阵，是维非零向量，若 （4.1）则称，是共轭的。类似地，设是中一组非零向量。若 （4.2）则称向量组是共轭的。注：(1) 当时，共轭性就变为正交性，故共轭是正交概念的推广。(2) 若共轭，则它们必线性无关。二、共轭方向法共轭方向法就是按照一组彼此共轭方向依次搜索。模式算法：1）给出初始点，计算，计算，使， （初始共轭方向）；2）计算和，使得，令；3）计算，使，令，转2）。三、共轭方向法的基本定理共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。定理4.2 对于正定二次函数，共轭方向法至多经过步精确搜索终止；且对每个，都是在线性流形中的极小点。证明：首先证明对所有的，都有，（即每个迭代点处的梯度与以前的搜索方向均正交）事实上，由于目标函数是二次函数，因而有1）当时， 2）当时，由精确搜索性质知：综上所述，有 。再证算法的有限终止结论。若有某个（），则结论已知。若不然，那么由上面已证则必有： 。而由于是的一组基，由此可得。故至多经过次精确一维搜索即可获得最优解。下面证明定理的后半部分。由于是正定二次函数，那么可以证明是线性流形上的凸函数。事实上， 由知为的凸函数。因而 注意到：当，时，。而由定理前部分证明，在处有，故在处，取得极小，即 是在线性流形上的极小点。4.2 共轭梯度法上节一般地讨论了共轭方向法，在那里个共轭方向是预先给定的，而如何获得这些共轭方向并为提及。本节讨论一种重要的共轭方向法共轭梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭梯度法。一、共轭梯度的构造 （算法设计针对凸二次函数）设 其中为正定矩阵，则。对二次函数总有 1）设为初始点。首先取，令 （为精确步长因子）则有：（精确一维搜索性质）。2）令，适当选择，使，得 （从而得到） 由前一节共轭方向法的基本定理有：，再由与的构造，还可得：，3）再令，适当选择，使得 （），由此得：， 4） 一般地，在第次迭代中，令 适当选取，使 （），可得到 （） （4.3）同样由前一节共轭方向的基本定理有：（）， （4.4）再由与的关系得： （） （4.5）将（4.4）与（4.5）代入（4.3）得：当时，而 。共轭梯度法的迭代公式为：（为共轭方向，为最佳步长因子）对二次函数；而对非二次函数，则采用精确一维搜索得到。共轭方向的修正公式为： （4.6）其中，由下面诸式之一计算：1） （Crowder-Wolfe公式） （4.7）2) （Fletcher-Reeves公式） （4.8）3） （Polak-Ribiere-Polyak 公式） （4.9）4） （Dixon公式） （4.10）注： 对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轭方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的。（事实上，此时不存在一个常值正定矩阵，共轭的提法都已无意义）。二、共轭梯度法的性质定理4.3 对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过步迭代后终止。且对，下列关系式成立：1） （） （4.11）2） （） （4.12）3） （4.13）4） （4.14）5） （4.15）证明：先用归纳法证明（4.11）（4.13）。对于，容易验证（4.11），（4.12），4.13）成立。现假设这些关系式对某个成立，下面证明对于，这些关系式仍然成立。事实上，对于二次函数，显然有 （4.16）对上式左乘，并注意到是精确步长因子，得 （4.17）利用（4.16），（4.17），得 （4.18）当时，（4.18）成为当时，由归纳法假设可知于是（4.12）得证。再由共轭梯度法的迭代公式及（4.17），有 （4.19）当时，由（4.12），（4.17）及（4.8），（4.19）成为当时，直接由归纳法假设知（4.19）为零，于是（4.11）得证。又由于 于是（4.13）得证。 下面利用归纳法证明（4.14）与（4.15）。当时，由及，容易看出： 再由 及 ，易见：。故当时，（4.14）与（4.15）成立。假定（4.14）与（4.15）对成立。下证结论对也成立。由于 ，而从归纳法假设知 故有 还可证明： 否则由 及 （共轭方向法基本定理）则必有 （与算法结束前，不会出现矛盾）因此 再由 立即有： 。定理证毕。注：1）上面定理中出现的这些生成子空间通称为Krylov子空间；2）在共轭梯度法中，若采用精确一维搜索，则不论采用哪种公式计算，都有，即总是下降方向，若不采用精确一维搜索，则就不一定了；3）对Dixon公式，使用不精确搜索准则 ，能保证搜索方向总是下降的。事实上，由 有 ，而 （由），由此即得 故为下降方向；4）FletcherReeves公式最为简洁，使用得最多； 5）共轭梯度算法用于非二次函数时，没有有限终止性质，一般经过次搜索后，就取一次负梯度方向，称再开始。Polak-Ribiere-Polyak具有自动再开始的特点，事实上，当算法改进不大时，会出现，这时用Polak-Ribiere-Polyak公式计算出的，从而导致。4. 3 共轭梯度法的收敛性由前面的讨论已经知道，当共轭梯度算法用于正定二次函数时必定有限终止。本节研究将其用于一般非二次函数时的收敛性问题。一、共轭梯度法的总体收敛性定理4.4 设水平集有界，是上具有一阶连续偏导数的凸函数。是由Fletcher-Reeves共轭梯度算法产生的迭代点列。则1）为严格单调下降序列，且存在。2）的任意聚点都是最优解，于是：。证明：在算法迭代过程中，由于每隔次采用一次再开始措施。因而搜索方向要么是共轭梯度方向，要么是最速下降方向。但不管是哪种情形都有： （采用严格一维搜索）因而单调下降，又由有界，故也有下界，因此存在，记为。又由单调下降，知，故是有界序列。设是中的这样的一个子列：从出发按最速下降方向得到。由有界，故存在收敛子列，使。又也是有界点列，故存在子列，使，且 （*）下面用反证法证明。若不然，设，则对充分小的，有注意当时， 令，则有 与（*）式矛盾，故必有。再由是凸函数，即知是最优解。因而有进一步地，对点列的任一极限点，必存在的子列，使得。进而有 这表明：也是问题的最优解。注：由这个定理的证明过程易见：上述收敛定理对其它几种共轭梯度算法也是成立的。定理4.5 假设水平集是有界集，在其上Lipschitz连续，则采用精确一维搜索的Crowder-Wolfe再开始共轭梯度法产生的点列至少存在一个聚点是驻点。证明: 与前一定理的证明类似，略。定理4.6 （Polak-Ribbiere-Polyak算法的总体收敛性）设二阶连续可微，水平集有界。又设存在常数，使得对，有： 则采用精确一维搜索的P-R-P共轭梯度算法产生的点列收敛于的唯一极小点。证明：只要证明，即即可。事实上，若 （）成立。由第二章的定理2.7知，必有，若是的极限点，由的连续性，则有，由的凸性，即知是极小点。再由在水平集上一致凸，知的极限点必唯一。否则设是的另一极限点，则也有。因此，这与一致凸的假设矛盾，所以只有唯一极限点。可证：有界点列若只有唯一极限点，则必有。故收敛于的唯一极小点。下证： （1）由于采用了精确一维搜索，故有因而（1）式等价于 （2）由 得： （3）其中 。再注意到， 有 ，由（3）得 又由有界，故存在常数，使得 ，故 因而 即 由前述分析，定理得证。上述总体收敛性定理均建立在精确一维搜索基础之上。Al-Baali（1985）研究了采用不精确一维搜索的Fletcher-Reeves共轭梯度法。发现若采用Wolfe-Powell不精确一维搜索准则，也有总体收敛性。定理4.7 若由不精确一维搜索的Wolfe-Powell准则产生，那么Fletcher-Reeves共轭梯度算法具体下降性质：。证明：先用归纳法证明： （*）其中是W-P准则中的。当时，（*）成为等式，故结论成立。假设对任何，（*）式成立，现考虑情形。由 及 有 再由归纳法假设，有即 。利用已经证明的（*）式，并注意到 有 最后得 ，证毕。定理4.8 设二阶连续可微，水平集有界。设由Wolfe-Powell准则确定，那么Fletcher-Reeves共轭梯度算法产生的点列总体收敛，即有. （1）证明：由Wolfe-Powell准则，及定理4.7中（*