最速下降法及MATLAB程序



《最速下降法及MATLAB程序》由会员分享,可在线阅读,更多相关《最速下降法及MATLAB程序(11页珍藏版)》请在文档大全上搜索。
1、编辑ppt1最速下降法 最速下降法,也称为梯度下降法,是由法国著名数学家Cauchy在1847年提出的。 最速下降法是求解无约束优化问题最简单和最古老的方法之一,虽然现在已经不具有实用性,但是许多有效算法都是以它为基础进行改进和修正而得到的。 最速下降法是用负梯度方向为搜索方向,算法非常简单,并且通常对凸解析函数也有良好的收敛性。编辑ppt2最速下降法的基本思想 从任意一点xk出发,沿该点负梯度方向pk=-f(xk)进行一维搜索,设f(xk+ kpk)=min f(xk+ pk) ( 0),令xk+1= xk+ kpk为f(x)新的近似最优解。 再从新点xk+1出发,沿该点的负梯度方向pk+1
2、=-f(xk+1)进行一维搜索,进一步求出新的近似最优解xk+2。 如此迭代,直到某点的梯度为零向量或梯度的范数小于事先给定的精度为止。编辑ppt3给定x0,0,k=0计算pk=-f(xk)| f(xk)|0)xk+1= xk+ kpk,k=k+1停止,打印xkYN算法编辑ppt4例. 用最速下降法求函数f (x1, x2)2x12+x22 的极小点,取x0=1,1T , =0.1。解 由题意得Txxxf)2,4()(21Txfp)2, 4()(001 . 0200p由于故进行第一次迭代2200)21 ()41 (2)()(pxf从x0=(1,1)T出发进行一维搜索,即构造编辑ppt5得185
3、0Tpxx)94,91(0001Txfp)98,94()(111.05941p从而得故进行第二次迭代运算:0)21(4)41(16)(令从x1=(-1/9,4/9)T出发进行一维搜索,即构造2211)9894()9491(2)()(pxf编辑ppt6得1251Tpxx)272,272(1112Txfp) 1, 2(274)(221.052742p从而得0)9894(916)9491(916)(令故进行第三次迭代运算:从x2=(2/27,2/27)T出发进行一维搜索,即构造2222)274272()278272(2)()(pxf编辑ppt7得1852Tpxx)2438,2432(2223Txfp
4、)24316,2438()(331.00368.0524343p从而得0)274272(278)278272(2732)(令停止迭代故最优解为Txx)2438,2432(3编辑ppt8编辑ppt9最速下降法的搜索路径呈直角锯齿形设xk=(xk1 , xk2 .xkn),pk=(pk1 , pk2 .pkn),则令( )= f(xk+ pk) = f(xk1 + pk1, xk2 + pk2 ,., xkn + pkn)0|)(|)(kkdpxdfddkkkTkkknknknnkkkkkkkkppxfppxfppxfppxfdpxdfdd)()(.)()()()(22221111是一元函数f(x
5、k+ pk)的极值点, kf(xk + kpk)Tpk=0,即(pk+1)Tpk=0。也就是说,有目标函数在一维搜索产生的新点xk+1= xk+ kpk处的梯度与产生该点时所用的搜索方向是正交的。编辑ppt10改进后的算法nRx 0精度0,自然数N=2,k=0Step1:计算)(kkxfpStep2:Step3:)(kxf如果,则转Step5;否则进行一维搜索)(min)(0kkkkkpxfpxf,令1,1kkpxxkkkk若k=N,且k/3-k/3=0.则转Step4,否则转Step2.Step4:计算2kkkxxs,进行一维搜索)(min)(0kkkkksxfsxf1,1kksxxkkkk令,转Step2Step5: 停止,输出kxx *编辑ppt11小结1、优点:、优点: 计算简单,需记忆的容量小;对初始点要求低,稳定性高;远离极小点时收敛快,常作为其它方法的第一步。2、缺点、缺点: 收敛速度较慢。尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时,收敛更慢。