10使用导数的最优化方法.ppt

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

1、§10，使用导数的最优化方法最优化理论与算法第十章使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法10.1最速下降法10.1最速下降法考虑无约束问题minf(x),xRn(10.1.1)其中f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。10.1最速下降法－1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，

2、方向导数求函数f(x)在点x处下降最快的方向,归结为求10.1最速下降法－2由上式知.当时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.注意:在不同的尺度下最速下降方向是不同的.10.1最速下降法－3最速下降算法最速下降算法的迭代公式为10.1最速下降法－4算法描述例1.1用最速下降法求解下列问题第一次迭代目标函数f(x)在点x处的梯度令搜索方向令在直线上的极小点第二次迭代令得到第三次迭代令此时已经满足精度要求,得近似解问题的最优解为x*=(0.0)算法的收敛性证明:最速下降算法A可表

3、示为合成映射A=MD其中D(x)=(x,-f(x)),是EnEnEn的映射.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是EnEnEn映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当f(x)0时,M是闭映射.由于f(x)是连续可微实函数,故D连续,据Th8.1.1推论2,A在x(f(x)0)处是闭的.其次,当x时,d=-f(x)0,则f(x)Td<0,因此对于y

4、A(x),有f(y)

5、其意义下的最速下降方向.设A为对称正定矩阵,向量d的A范数定义为由A,A-1对称正定,故存在对称平方根A1/2,A-1/2,使得于是10.2牛顿法去掉绝对值符号,有根据Schwartz不等式,得到10.2牛顿法即为得到在点x处下降最快的方向,按下式选取d这时上式等号成立,由此确定的方向即度量A意义下的最速下降方向10.2牛顿法若取则牛顿法的搜索方向实际上是关于向量椭球范数10.2牛顿法10.2牛顿法例用牛顿法求解下列问题第1次迭代10.2牛顿法第2次迭代10.2牛顿法第3次迭代继续下去,第4次迭代,…得到点列收敛于(1,0

6、),此为最优解.10.2牛顿法10.2.2局部收敛性10.2牛顿法证明:根据(10.2.2)，牛顿算法映射定义为下证(x)是关于解集合和算法A的下降函数.10.2牛顿法于是可得从而(x)是关于解集合和算法A的下降函数10.2牛顿法10.2牛顿法当牛顿法收敛时,有下列关系特别的,对于二次凸函数,用牛顿法求解,经一次迭代即达到极小点.设有二次凸函数其中A是对称正定矩阵10.2牛顿法先用极值条件求解.令得最优解下用牛顿法解,任取一初始点x(1)定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限

7、次迭代后可到达函数的极小值点,称此算法具有二次终止性.于是牛顿法具有二次终止性10.2牛顿法注意,当初始点远离极小点时,牛顿法可能不收敛阻尼牛顿法基本思想:增加了沿牛顿方向的一维搜索.迭代公式为10.2牛顿法算法(阻尼牛顿法)10.2牛顿法10.2.3修正牛顿法例用阻尼牛顿法求解下列问题牛顿方向10.2牛顿法显然,用阻尼牛顿法不能产生新点,而点x(1)=(0,0)T并不是问题极小点.可见从x(1)出发,用阻尼牛顿法求不出问题的极小点,原因在于Hessian矩阵2f(x(1))非正定再令10.2牛顿法考虑(10.2.2),

8、记搜索方向d(k)=x-x(k)阻尼牛顿法所用搜索方向是上述方程的解此处假设逆矩阵存在10.2牛顿法再沿此方向作一维搜索10.2牛顿法算法修正牛顿法10.2牛顿法10.3共轭梯度法1共轭方向与扩张子空间定理定义10.3.1设A是n×n对称矩阵,若Rn中的两个方向d1和d2满足(d1)TAd2=0（10.