最优化理论及算法(第四章).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.72> 〔Fletcher-Reeves公式 〔4.83 〔Polak-Ribiere-Polyak 公式 〔4.94 〔Dixon公式 〔4.10注：对二次函数而言,上述四个公式都是等价的而且求得的搜索方向均为共轭方向；若对非二次函数,则将导出互不相同的算法,而且据此求出的搜索方向不再保证是共轭的〔事实上,此时不存在一个常值正定矩阵,共轭的提法都已无意义二、共轭梯度法的性质定理4.3 对于正定二次函数,采用基于精确一维搜索的共轭梯度算法,必定经过步迭代后终止且对,下列关系式成立：1 〔〔4.112 〔〔4.123〔4.134〔4.145〔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公式,使用不精确搜索准则 ,,能保证搜索方向总是下降的。

事实上,由有,而〔由,由此即得故为下降方向；4Fletcher－Reeves公式最为简洁,使用得最多； 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中〔*式得又由,得递推可得〔2下面用反证法证明〔1成立。

若不然,则存在常数,使得对充分大的,都有由在水平集上有界,从〔2即有 〔为常数由 故级数发散若设为在上的上界,则再由Wolfe-Powell准则 〔1即故有因而有 又由Wolfe-Powell准则 〔2由〔2知单调下降且有下界,故存在再由及由此又推得收敛,矛盾从而定理结论成立。