共轭梯法72373实用教案

1、(1) 建立在二次模型建立在二次模型(mxng)上，具有二次终止性上，具有二次终止性(2) 一种一种(y zhn)有效的算法，克服了最速下降法的锯齿有效的算法，克服了最速下降法的锯齿现象，现象， 又避免了牛顿法的计算量大和局部收敛性的缺点又避免了牛顿法的计算量大和局部收敛性的缺点(3) 算法简单，易于编程，无需计算二阶导数，存储算法简单，易于编程，无需计算二阶导数，存储 空间小等优点，是求解中等规模优化问题的主要空间小等优点，是求解中等规模优化问题的主要(zhyo) 方法方法特点特点共轭方向法和共轭梯度法共轭方向法和共轭梯度法第1页/共16页第一页，共17页。共轭方向共轭方向(fngxing)

2、法法定义定义(dngy)-(dngy)-共轭共轭方向方向注：注：若若则则 是正交的，是正交的，因此因此, 共轭是正交的推广共轭是正交的推广定义定义(dngy)-(dngy)-共共轭方向法轭方向法第2页/共16页第二页，共17页。共轭方向共轭方向(fngxing)法法性质性质(xng(xngzh)zh)特例特例(tl)(tl)n第3页/共16页第三页，共17页。共轭方向共轭方向(fngxing)法法算法算法(sun (sun f)f)步骤步骤Step1:Step2:Step3:Step4:Step5:第4页/共16页第四页，共17页。共轭方向共轭方向(fngxing)法法特例特例(tl)(tl)

3、注注共轭方向共轭方向(fngxing)法具有二法具有二次终止性次终止性第5页/共16页第五页，共17页。共轭梯度共轭梯度(t d)法法简介简介(jin (jin ji)ji) 共轭梯度法（共轭梯度法（conjugate gradient method, CG）是）是以共轭方向（以共轭方向（conjugate direction）作为）作为(zuwi)搜索搜索方向的一类算法。方向的一类算法。CG法是由法是由Hesteness和和Stiefel于于1952年为求解线性方程组而提出的。后来用于求解无约束年为求解线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。这种方最优化

4、问题，它是一种重要的数学优化方法。这种方法具有二法具有二次终止性。次终止性。第6页/共16页第六页，共17页。共轭梯度共轭梯度(t d)法法基本基本(jbn)(jbn)思想思想确定确定(qudng)？ CG的基本思想是把共轭性与最速下降法相结合，利用已知点处的的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数的极小点。极小点。定义定义-共轭梯度法共轭梯度法一一第7页/共16页第七页，共17页。（Hestenes-Stiefel公式公式(gngsh)）共轭梯度共轭梯度(t d

5、)法法共轭梯度共轭梯度(t d)(t d)法法的形式的形式(A) 正定二次函数的无约束最优化问题的共轭梯度法形式正定二次函数的无约束最优化问题的共轭梯度法形式消除消除Qdk结合性质结合性质:第8页/共16页第八页，共17页。共轭梯度共轭梯度(t d)法法共轭梯度共轭梯度(t d)(t d)法的法的形式形式一般最优一般最优化问题的化问题的共轭梯度共轭梯度(t d)法形式法形式第9页/共16页第九页，共17页。共轭梯度共轭梯度(t d)法法共轭梯度共轭梯度(t d)(t d)法法的形式的形式(B) 一般无约束最优化问题一般无约束最优化问题(wnt)的共轭梯度法的共轭梯度法形式形式（1969）（19

6、64）（1971）第10页/共16页第十页，共17页。共轭梯度共轭梯度(t d)法法注意注意(zh y)说明说明(shu(shummng)ng) 根据根据 的上述三种形式，可分别绪出的上述三种形式，可分别绪出FR共轭梯度法、共轭梯度法、DM共轭梯度法和共轭梯度法和PRP共轭梯度法对于目标函数是正定二次函数共轭梯度法对于目标函数是正定二次函数的无约束最优化问题的无约束最优化问题(7. 3. 3)和最优一维投索，这些方法是完全和最优一维投索，这些方法是完全等价的但是，对于目标函数是非二次函数的无约束最优化问等价的但是，对于目标函数是非二次函数的无约束最优化问题题 (7. 1. 1)，它们所产生的按

7、索方向是不同的，它们所产生的按索方向是不同的 由于由于Rn中共扼方向最多有中共扼方向最多有 n 个，因此在用上述二种方法求个，因此在用上述二种方法求解目标函数为非二次函数的无约束最优化问题解目标函数为非二次函数的无约束最优化问题(7.1.1)时，在时，在 n 步之后步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设初始点，即把经过初始点，即把经过 n 次迭代得到的次迭代得到的 xn 作为初始作为初始点重新迭代点重新迭代第11页/共16页第十一页，共17页。共轭梯度共轭梯度(t d)法法算法步骤算法步骤(bzhu)F

8、R(bzhu)FR共共轭梯度法轭梯度法Step1:Step2:Step3:Step5:Step6:Step4:Step7:第12页/共16页第十二页，共17页。共轭梯度共轭梯度(t d)法法举例举例(j l)(j l)参见参见(cnjin) P187 例例7.3.1.第13页/共16页第十三页，共17页。共轭梯度共轭梯度(t d)法法收敛性分析收敛性分析(fnx)(fnx)与与Newton法相比，共轭梯度法相比，共轭梯度 法具有法具有(jyu)较弱的收敛条较弱的收敛条件件.注注全局收敛性全局收敛性第14页/共16页第十四页，共17页。共轭梯度共轭梯度(t d)法法优点优点(yud(yudin)in)收敛速度收敛速度(sd)(sd)优于最速下降法，存贮量小，优于最速下降法，存贮量小，计算简单计算简单. . 缺点缺点当 时，收敛速度是线性的. 收敛速度不如Newton法快.适合于优化变量数目较多的中等规模优化问题适合于优化变量数目较多的中等规模优化问题. . 第15页/共16页第十五页，共17页。谢谢您的观看(gunkn)！第16页/共16页第十六页，共17页。NoImage内容(nirng)总结(1) 建立(jinl)在二次模型上，具有二次终止性。(1) 建立(jinl)在二次模型上，具有二次终止性。(2) 一种有效的算法，克服了最速下降法的锯齿现象，。又避免了牛顿