第9讲梯度法和共轭梯度法课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第9讲梯度法和共轭梯度法课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 梯度 共轭 课件
- 资源描述:
-
1、4.1 梯度法和共轭梯度法梯度法和共轭梯度法1.无约束最优化问题无约束最优化问题2.梯度法梯度法3.共轭梯度法共轭梯度法一一.无约束最优化问题无约束最优化问题无无约约束束最最优优化化问问题题nRxtsxf.)(min有有一一阶阶连连续续偏偏导导数数。其其中中)(xf解析方法:利用函数的解析性质构造迭代公式使之收敛到最优解。二二.梯度法(最速下降法)梯度法(最速下降法)迭代公式:迭代公式:kkkkdxx 1如何选择下降最快的方向?如何选择下降最快的方向?)(kxf)(kxf 函函数数值值下下降降最最快快的的方方向向函函数数值值增增加加最最快快的的方方向向函函数数值值下下降降的的方方向向kx梯度法
2、(最速下降法):梯度法(最速下降法):也称为最速下降方向;也称为最速下降方向;搜索方向:搜索方向:,)(.1kkxfd。即即满满足足取取最最优优步步长长搜搜索索步步长长)(min)(,:.2kkkkkkdxfdxf 梯度法算法步骤:梯度法算法步骤:。令令允许误差允许误差给定初始点给定初始点1,0,.11 kRxn;)(.2kkxfd 计算搜索方向计算搜索方向kkkxd 否则,求最优步长否则,求最优步长为所求极值点;为所求极值点;则停止计算,则停止计算,若若,|.3。使得使得)(min)(kkkkkdxfdxf 。转转令令令令2,1:,.41 kkdxxkkkk,)1,2(,3)(min:.12
3、221Txxxxf 设初始点为设初始点为用最速下降法求解用最速下降法求解例例。求迭代一次后的迭代点求迭代一次后的迭代点2x解:解:,)6,2()(21Txxxf .)6,4()(11Txfd .)61,42(11Tdx ,令令2211)61(3)42()()(dxf)(min 求解求解0)61(36)42(8)(令令62131 Tdxx)318,3136(1112 收敛性收敛性)(min)(kkkkkdxfdxf 。则有则有0)(kTkkkddxf 性质性质.证明:证明:所以所以,令令)()(kkdxf .)()(kTkkddxf )(min)(kkkkkdxfdxf .0)()(kTkkkk
4、ddxf 满足满足步长步长有一阶连续偏导数,若有一阶连续偏导数,若设设kxf)(注:注:。kkkTkdddd 110)(所以所以,因为梯度法的搜索方向因为梯度法的搜索方向)(1kkkkdxfd 锯齿现象锯齿现象在极小点附近,目标函数可以用二次函数近似,其等值面近似椭球面。椭球面。1x*x2x3x它只是它只是。标函数的一种局部性质标函数的一种局部性质最速下降方向反映了目最速下降方向反映了目局部目标函数值下降最快的方向。锯齿形状,越接近极小点,步长越小,前进越慢!注注 最速下降法反映的目标函数的一种局部性质最速下降法反映的目标函数的一种局部性质,从局部看从局部看,最速下降方向确是目标函数值下降最快
5、的方向最速下降方向确是目标函数值下降最快的方向,选择这样的选择这样的方向进行搜索是有利的方向进行搜索是有利的.但从全局来看但从全局来看,由于由于锯齿现象锯齿现象的影响的影响,即使向着极小点即使向着极小点移近不太大的距离移近不太大的距离,也要经历不小的也要经历不小的”弯路弯路”,因此收敛速度因此收敛速度大为减慢大为减慢.最速下降法一般适用于计算过程的前期迭代最速下降法一般适用于计算过程的前期迭代,或者作为或者作为间插步骤间插步骤.3共轭梯度法共轭梯度法1.共轭方向和共轭方向法共轭方向和共轭方向法定义定义共轭。共轭。关于关于和和,则称,则称若有若有AddAddT21210 ARdddnk它们两两关
6、于它们两两关于中一组非零向量,如果中一组非零向量,如果是是设设,21。共轭,即共轭,即kjijiAddjTi,2,1,0 共共轭轭方方向向。组组共共轭轭的的,也也称称它它们们是是一一则则称称这这组组方方向向是是关关于于AA注注:002121 dddIdTT21dd 共轭是正交的推广。共轭是正交的推广。,和和中的两个非零向量中的两个非零向量的对称正定矩阵,对于的对称正定矩阵,对于是是设设21ddRnnAn 是是单单位位矩矩阵阵,则则如如果果 A共轭的非零共轭的非零个个是是阶对称正定矩阵,阶对称正定矩阵,是是设设AkdddnAk,21性无关。性无关。向量,则这个向量组线向量,则这个向量组线2.定理
7、证明证明,使得,使得设存在实数设存在实数k ,21,01 kiiid jTdA上式两边同时左乘,则有,01 kiiTjiAdd 可化简为可化简为共轭的向量,所以上式共轭的向量,所以上式个个是是因为因为Akdddk,21.0 jTjjAdd 0,0jjTjdAdAd因为而 是正定矩阵,所以,所以所以。kjj,2,1,0 线性无关。线性无关。因此因此kddd,21几何意义几何意义设设有有二二次次函函数数)()(21)(xxAxxxfT 对称正定矩阵,对称正定矩阵,是是其中其中nnA 是一个定点。是一个定点。x的等值面的等值面则函数则函数)(xfcxxAxxT )()(21为中心的椭球面。为中心的椭
8、球面。是以是以 x由于由于,0)()(xxAxf,0)(2 AxfA所以所以正定,正定,因为因为的极小点。的极小点。是是因此因此)(xfxx,)(2Axf 而而点,点,是在某个等值面上的一是在某个等值面上的一设设)0(x处的法向量为处的法向量为该等值面在点该等值面在点)1(x.)()()1()1(xxAxf o1x2xx)1(d)0(x中的一个方向,中的一个方向,是是nRd)1(。以最优步长搜索得到点以最优步长搜索得到点沿着沿着)1()1()0(xdx所所在在等等值值面面的的切切向向量量。是是点点则则)1()1(xd正交,正交,与与则则)()1()1(xfd,0)()1()1(xfdT即即,)
9、1()2(xxd 令令)1(x所以所以,0)2()1(AddT共轭。共轭。小点的向量关于小点的向量关于向量与由这一点指向极向量与由这一点指向极即等值面上一点处的切即等值面上一点处的切A)2(d3.定理,设有函数设有函数cxbAxxxfTT 21)(共轭向量。共轭向量。一组一组是是阶对称正定矩阵。阶对称正定矩阵。是是其中其中AdddnAk)()2()1(,进行搜索,进行搜索,为初始点,依次沿为初始点,依次沿以任意的以任意的)()2()1()1(,kndddRx 上的上的在在是函数是函数则则得到点得到点kkkBxxfxxxx )1()1()1()3()2()(,极小点,其中极小点,其中,|1)(R
展开阅读全文