最优化方法ppt课件.ppt

《最优化方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3.4共轭方向法和共轭梯度法1共轭方向法是介于最速下降法和Newton法之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与Newton法相比，减少了计算量和存储量。它是比较实用而有效的最优化方法。2共轭方向法涉及共轭方向的概念和性质。共轭方向的概念是在研究正定二次函数本节和下节所介绍的方法有一个共同的特点，即首先以上式为目标函数给出有关的算法，然后再把算法用到更一般的目标函数上。本节内容对今后许多章节起着基础的作用。时产生的。3共轭方向法的思路定义3.4.

2、1设n维向量组p1,···,pk线性无关,x(0)∈Rn,称向量集合为由点x(0)与p1,p2,···,pk生成的k维超平面.我们希望x(k)是k维超平面的极小点,于是x(n)是n维超平面(即整个Rn空间)的极小点.若k=1,上述集合表示以p1为方向向量,且过点x(0)的一条直线.4超平面上极小点的判断引理3.4.1设f(x)为连续可微的严格凸函数,又p1,p2,···,pk为一组线性无关的n维向量,x1∈Rn,则是f(x)在x1与p1,p2,···,pk所生成的k维超平面Hk上唯一极小点的充分必要条件是注:若k=n,易推出在

3、xk+1的梯度为零向量.因此,这一引理是一常用定理(极小点梯度为0)的推广.5已知k个点与k个方向之后,令xk+1=xk+akpk,进行精确一维搜索,确定xk+1,再确定pk+1.共轭方向法(用于二次函数)对于正定二次函数,确定pk的准则是希望xk+1是目标函数在k维超平面上的极小点.xn+1就是目标函数在整个空间的极小点.给定一个初始点x1,给出一个下降方向p1,令x2=x1+a1p1,进行精确一维搜索,确定x2,再确定p2(方法待定).6共轭向量对于f(x)=xTGx/2+bTx+c,有g(x)=Gx+b,因此gj+1-g

4、j=G(xj+1-xj)=ajGpj,因此根据引理3.4.1,左边应为零,于是搜索方向满足性质piTGpj=0(i≠j).共轭向量:设G为n阶正定矩阵,p1,p2,···,pk为n维向量组,如果piTGpj=0(i≠j)则称向量组p1,p2,···,pk关于G共轭.实际上是在新的内积意义下,这是一组正交向量.7共轭方向法(用于二次函数)注:在前面讨论思路时,根据方向的共轭性(正交性)得到xk+1是目标函数在k维超平面上的极小点(后面的定理3.4.3给出严格证明).根据上一页的推导,根据极小点可以推出共轭性(正交性),即若一种迭

5、代方法每次求出的是二次函数在k维超平面上的极小点,则对应的方向是共轭的.8基本概念二次终止性如果一个算法经过有限次迭代就得到正定二次函数的极小点,称该算法具有二次终止性.共轭方向法是一种迭代方法,每次所取方向与前面的方向关于G共轭,然后进行精确一维搜索确定步长及下一步的迭代点.9定理3.4.1设G为n阶正定矩阵,非零向量组p1,p2,···,pk关于G共轭,则此向量组线性无关.证明:设存在常数a1,a2,···,ak使得a1p1+a2p2+···+akpk=0,以piTG左乘上式,显然有aipiTGpi=0.又,G是正定矩阵,

6、pi≠0,因此ai=0(i=1,2,···,k)于是p1,p2,···,pk线性无关.共轭方向的性质10推论1设G为n阶正定矩阵,非零向量组p1,p2,···,pn关于G共轭,则此向量组构成Rn的一组基.推论2设G为n阶正定矩阵,非零向量组p1,p2,···,pn关于G共轭,若向量v与p1,p2,···,pn关于G共轭，则v=0.共轭方向的性质11共轭方向法(用于二次函数)定理3.4.2设G是n阶正定阵,向量组p1,p2,···,pk关于G共轭,对正定二次函数f(x)=xTGx/2+bTx+c由任意初始点x1开始,依次进行k次

7、一维搜索,xi+1=xi+aipi(i=1,2,···,k)则(i)gTk+1pi=0(i=1,2,···,k).(ii)xk+1是二次函数在k维超平面Hk上的极小点.推论当k=n时,xn+1为二次函数在Rn上的极小点.12共轭方向法(用于二次函数)证明要点:只要证明gTk+1pi=0.精确一维搜索13算法（共轭方向法）14共轭梯度法(共轭方向的形成)我们首先讨论针对下面二次函数的共轭梯度法给定初始点x0,初始下降方向取为p0=-g0从x0出发,沿方向p0进行一维搜索得x1.设p1是-g1与p0的线性组合p1=-g1+β0p0

8、,p1与p0共轭,于是因此15共轭梯度法(共轭方向的形成)假设已经沿k个共轭方向p0,p1,···,pk-1逐次进行一维搜索得xk.若gk=g(xk)=0,则xk已是极小点,否则构造下一个方向pk.令pk为-gk以及p0,p1,···,pk的线性组合.用pjTG(j=0,1,