单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,问题,1:,如何建立有效的算法？,从二次模型到一般模型,.,问题,2:,什么样的算法有效呢？,二次终止性,.,共轭方向法和共轭梯度法,问题1:如何建立有效的算法？从二次模型到一般模型.问题2:什,1,最初是由计算数学家,Hestenes,和几何学家,Stiefel,于,1952,年,为求正定系数矩阵线性方程组而独立提出的,.,他们合作的著名文章,Method of conjugate gradients for solving linear systems,被认为是共轭梯度法的奠基性文章。,1964,年，,Fletcher,和,Reeves,将此方法推广到非线性最优化，,得到了求解一般函数极小值的共轭梯度法,.,简介,共轭方向法和共轭梯度法,(3),共轭梯度法的收敛性分析的早期工作主要由,Fletcher,、,Powell,、,Beale,等学者给出,.,(4),Nocedal,、,Gilbert,、,Nazareth,、,Al-Baali,、,Storey,、,Dai,、,Yuan,和,Han,等学者在收敛性方面得到了不少新成果,.,共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算,Hesse,矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一,.,最初是由计算数学家Hestenes和几何学家Stiefel于,2,(1),建立在二次模型上，具有二次终止性,(2),一种有效的算法，克服了最速下降法的,锯齿现象,，,又避免了牛顿法的计算量大和局部收敛性的缺点,(3),算法简单，易于编程，无需计算二阶导数，存储,空间小等优点，是求解中等规模优化问题的主要,方法,特点,共轭方向法和共轭梯度法,(1)建立在二次模型上，具有二次终止性(2)一种有效的,3,共轭方向法,定义,-,共轭方向,注：,若,则,是正交的，,因此,共轭是正交的推广,定义,-,共轭方向法,共轭方向法定义-共轭方向注：若则,4,共轭方向法,性质,特例,n,共轭方向法性质特例n,5,共轭方向法,算法步骤,Step1:,Step2:,Step3:,Step4:,Step5:,共轭方向法算法步骤Step1:Step2:Step3:Ste,6,共轭方向法,特例,注,共轭方向法具有二次终止性,共轭方向法特例注共轭方向法具有二次终止性,7,共轭梯度法,简介,共轭梯度法（,conjugate gradient method,CG,）是以共轭方向（,conjugate direction,）作为搜索方向的一类算法。,CG,法是由,Hesteness,和,Stiefel,于,1952,年为求解线性方程组而提出的。后来用于求解无约束最优化问题，它是一种重要的数学优化方法。,这种方法具有二,次终止性。,共轭梯度法简介 共轭梯度法（conjugate,8,共轭梯度法,基本思想,确定？,CG,的基本思想是把共轭性与最速下降法相结合，利用已知点处的梯度构造一组共轭方向，并沿着此组方向进行搜索，求出目标函数的极小点。,定义,-,共轭梯度法,一,共轭梯度法基本思想确定？CG的基本思想是把共轭性与最,9,（,Hestenes-Stiefel,公式）,共轭梯度法,共轭梯度法的形式,(A),正定二次函数的无约束最优化问题的共轭梯度法形式,消除,Qd,k,结合性质,:,（Hestenes-Stiefel公式）共轭梯度法共轭梯度法,10,共轭梯度法,共轭梯度法的形式,一般最优,化问题的共轭梯度法形式,共轭梯度法共轭梯度法的形式一般最优,11,共轭梯度法,共轭梯度法的形式,(B),一般无约束最优化问题的共轭梯度法形式,（,1969,）,（,1964,）,（,1971,）,共轭梯度法共轭梯度法的形式(B)一般无约束最优化问题的共轭,12,共轭梯度法,注意,说明,根据 的上述三种形式，可分别绪出,FR,共轭梯度法、,DM,共轭梯度法和,PRP,共轭梯度法对于目标函数是正定二次函数,的无约束最优化问题,(7.3.3),和最优一维投索，这些方法是完全,等价的但是，对于目标函数是非二次函数的无约束最优化问,题,(7.1.1),，它们所产生的按索方向是不同的,由于,R,n,中共扼方向最多有,n,个，因此在用上述二种方法求,解目标函数为非二次函数的无约束最优化问题,(7.1.1),时，在,n,步之后构造的搜索方向不再是共轭的，从而降低了收敛速度克服的办法是重设初始点，即把经过,n,次迭代得到的,x,n,作为初始,点重新迭代,共轭梯度法注意说明 根据 的上述三种形,13,共轭梯度法,算法步骤,FR,共轭梯度法,Step1:,Step2:,Step3:,Step5:,Step6:,Step4:,Step7:,共轭梯度法算法步骤FR共轭梯度法Step1:Step2:S,14,共轭梯度法,举例,参见,P187,例,7.3.1.,共轭梯度法举例参见 P187 例7.3.1.,15,共轭梯度法,收敛性分析,与,Newton,法相比，共轭梯度,法具有较弱的收敛条件,.,注,全局收敛性,共轭梯度法收敛性分析与Newton法相比，共轭梯度 注全局收,16,共轭梯度法,优点,收敛速度优于最速下降法，存贮量小，计算简单,.,缺点,当 时，收敛速度是线性的,.,收敛速度不如,Newton,法快,.,适合于优化变量数目较多的中等规模优化问题,.,共轭梯度法优点收敛速度优于最速下降法，存贮量小，计算简单.,17,