最优化方法第二章_线搜索算法_最速下降法

《最优化方法第二章_线搜索算法_最速下降法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一一维搜索二最速下降法下降三Newton法算法四共轭梯度法五多尺度法（拟Newton法）二、最速下降法假设f连续可微，取线搜索方向kkdfx()kkkkfx(d)min(fxd)k0步长由精确一维搜索得到。k从而得到第k+1次迭代点，即k1kkkkxx+dxfx()kk单位向量kk负梯度方向dfx()是函数值减少最快的方向。Tkkkfxd()fx()dcos(fxd(),)二、最速下降法最速下降法的计算流程0(1)选定某一初始点x，0并令k:0kk(2)若fx(),*xx，否则转（3）；kk(3)dfx()(4)

2、由精确一维搜索确定步长步长k，即由一个极小化kk问题求得最佳步长min(fxd)k1kk令xxdk,k1,转（2）。k最速下降法可以用来求解系数矩阵正定线性方程组。1Tfx()xAxbxfx()Axb02二、最速下降法22例1.利用最速下降法求解min()fxx2x2xx4,x121210T取初始向量x1,1.2xx2412解：函数的梯度为fx(),2+4xx12第1次迭代：44000fx,d=,fx221+40000xd+=，()=fx+d=1+4,

3、12f1222=1+421221+41241+42=40203'=1/4,令0=()8020,得0二、最速下降法10014211xx=+d=+1/4=，fx,0121/22第2次迭代：1112+11xd+=，d=,fx21/2+211()=fx+d=f2+,1/2+222=2+21/2+222+1/2+242+,2=5511/2'=1/2,令0

4、=()105,得1215/222112x=+xd=+1/2=，fx,11/223/21继续迭代可得到函数的近似最优解……二、最速下降法最速下降法的收敛性分析(收敛性定理)设目标函数f(x)连续可微，且水平集0Lxfx()fx()有界，则最速下降法或者在有限迭代步k后终止；或者得到点列x，它的任何聚点都是f(x)的驻点。(推论)在收敛定理的假设下，若f(x)为凸函数，则最速下降k法或在有限迭代步后达到最小点；或得到点列x，它的任何聚点都是f(x)的全局最小点。二、最速下降法最速下降法特征：相邻两次

5、迭代的方向互相垂直。kk令()fx(d),利用精确一维搜索，可得'kkTk()fx(d)d0kkkkfx()d由此得出kkTkk+1Tkk+1Tk0=fx(d)d=fx()d=(dd)k最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。影响收敛速度！！二、最速下降法最速下降法收敛速度慢！在最速下降法中，利用精确一维2搜索求最佳步长，使得相邻两次迭代xd21的搜索方向总是垂直的，0dx01dx使得逼近极小点过程是“之”字形，这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小

6、点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内可能得不到需要的结果。二、最速下降法用于二次函数时的收敛速度分析1T定理：二次函数fx()xAx,A为对称正定，12,分别20为其最小和最大特征值，从任意初点x出发，对二次函k数，用最速下降法产生的序列{}x，对于k0有kfx(kk12)(21)fx(),k2210xx2112121k由于1x0.211T*而函数fx()xAx的极小点恰好是x0。故最2速下降法对于二次函数关于任意初始点均收敛，而且是线性收敛的。二、最速下降法

7、对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点。15分析：因为相邻搜索方向正交，100242kd//d//d//...//d520kt,dtdt与k有关0-520kAxtAx-10kkk(dfx()Ax)-15-1.5-1-0.500.511.520kfx()10x22xxtx.12二、最速下降法最速下降法收敛性的几何意义（对二次函数）考虑具有对称正定矩阵的