北邮最优化课件 10使用导数的最优化方法

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

1、帅天平北京邮电大学数学系Email:tpshuai@gmail.com,Tel:62281308,Rm:主楼814§10，使用导数的最优化方法最优化理论与算法1TPSHUAI第十章使用导数的最优化方法最速下降法牛顿法共轭梯度法拟牛顿法信赖域法2TPSHUAI10.1最速下降法10.1最速下降法考虑无约束问题minf(x),xRn(10.1.1)其中f(x)具有一阶连续偏导数。在处理这类问题时，一般策略是，希望从某一点出发，选择一个目标函数值下降最快的方向，沿此方向搜索以期尽快达到极小点，基于这一思想，Cauchy于1847年提出了最速下降法。这是无约束最优化中最简单的方法。3TPSHU

2、AI10.1最速下降法－1函数f(x)在点x处沿方向d的变化率可用方向导数表示，当函数可微时有，方向导数求函数f(x)在点x处下降最快的方向,归结为求4TPSHUAI10.1最速下降法－2由上式知.当时等号成立.故在点x处沿(1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.注意:在不同的尺度下最速下降方向是不同的.5TPSHUAI10.1最速下降法－3最速下降算法最速下降算法的迭代公式为6TPSHUAI10.1最速下降法－4算法描述7TPSHUAI例1.1用最速下降法求解下列问题第一次迭代目标函数f(x)在点x处的梯度8TPSHUAI令搜索方向9TPSHUAI令在直线上的极小

3、点第二次迭代10TPSHUAI令11TPSHUAI得到第三次迭代12TPSHUAI令13TPSHUAI此时已经满足精度要求,得近似解问题的最优解为x*=(0.0)14TPSHUAI算法的收敛性证明:最速下降算法A可表示为合成映射A=MD其中D(x)=(x,-f(x)),是EnEnEn的映射.每给定一点x,经算法D作用,得到点x和在x处的负梯度(从x出发的方向d).算法M是EnEnEn15TPSHUAI映射.每给定一点x及方向d=-f(x),经M作用,即一维搜索,得到一个新点,在这一点,与前面的迭代点相比,具有较小的目标函数值,根据Th1.1,当f(x)0时,M是闭映射.由

4、于f(x)是连续可微实函数,故D连续,据Th8.1.1推论2,A在x(f(x)0)处是闭的.其次,当x时,d=-f(x)0,则f(x)Td<0,因此对于yA(x),有f(y)

5、PSHUAI即10.2牛顿法(x)=0为求(x)的驻点,令21TPSHUAI注意:牛顿法的迭代格式也可以从最速下降方向的角度来理解.下求A度量下的最速下降方向,为此,考虑10.2牛顿法下面介绍一下A度量及其意义下的最速下降方向.设A为对称正定矩阵,向量d的A范数定义为22TPSHUAI由A,A-1对称正定,故存在对称平方根A1/2,A-1/2,使得于是10.2牛顿法23TPSHUAI去掉绝对值符号,有根据Schwartz不等式,得到10.2牛顿法24TPSHUAI即为得到在点x处下降最快的方向,按下式选取d这时上式等号成立,由此确定的方向即度量A意义下的最速下降方向10.2牛顿法2

6、5TPSHUAI若取则牛顿法的搜索方向实际上是关于向量椭球范数10.2牛顿法26TPSHUAI10.2牛顿法例用牛顿法求解下列问题第1次迭代27TPSHUAI10.2牛顿法第2次迭代28TPSHUAI10.2牛顿法第3次迭代继续下去,第4次迭代,…得到点列收敛于(1,0),此为最优解.29TPSHUAI10.2牛顿法10.2.2局部收敛性30TPSHUAI10.2牛顿法证明:根据(10.2.2)，牛顿算法映射定义为下证(x)是关于解集合和算法A的下降函数.31TPSHUAI10.2牛顿法于是可得从而(x)是关于解集合和算法A的下降函数32TPSHUAI10.2牛顿法33TPSHU

7、AI10.2牛顿法当牛顿法收敛时,有下列关系特别的,对于二次凸函数,用牛顿法求解,经一次迭代即达到极小点.设有二次凸函数其中A是对称正定矩阵34TPSHUAI10.2牛顿法先用极值条件求解.令得最优解下用牛顿法解,任取一初始点x(1)定义:若一个算法用于求解严格二次凸函数极小值问题时从任意初始点出发,算法在有限次迭代后可到达函数的极小值点,称此算法具有二次终止性.于是牛顿法具有二次终止性35TPSHUAI10.2牛顿法注意,当初始点