最速下降法PPT及MATLAB程序.ppt

《最速下降法PPT及MATLAB程序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最速下降法最速下降法，也称为梯度下降法，是由法国著名数学家Cauchy在1847年提出的。最速下降法是求解无约束优化问题最简单和最古老的方法之一，虽然现在已经不具有实用性，但是许多有效算法都是以它为基础进行改进和修正而得到的。最速下降法是用负梯度方向为搜索方向，算法非常简单，并且通常对凸解析函数也有良好的收敛性。最速下降法的基本思想从任意一点xk出发，沿该点负梯度方向pk=-▽f(xk)进行一维搜索，设f(xk+λkpk)=minf(xk+λpk)(λ>0)，令xk+1=xk+λkpk为f(x)新的近似最优解。

2、再从新点xk+1出发，沿该点的负梯度方向pk+1=-▽f(xk+1)进行一维搜索，进一步求出新的近似最优解xk+2。如此迭代，直到某点的梯度为零向量或梯度的范数小于事先给定的精度为止。给定x0，ε>0，k=0计算pk=-▽f(xk)

3、

4、▽f(xk)

5、

6、<εf(xk+λkpk)=minf(xk+λpk)(λ>0)xk+1=xk+λkpk，k=k+1停止，打印xkYN算法例.用最速下降法求函数f(x1,x2)＝2x12+x22的极小点,取x0=[1,1]T,ε=0.1。解由题意得由于故进行第一次迭代从x0=(1,1

7、)T出发进行一维搜索，即构造得从而得故进行第二次迭代运算:令从x1=(-1/9,4/9)T出发进行一维搜索，即构造得从而得令故进行第三次迭代运算:从x2=(2/27,2/27)T出发进行一维搜索，即构造得从而得令停止迭代故最优解为最速下降法的搜索路径呈直角锯齿形设xk=(xk1,xk2…..xkn),pk=(pk1,pk2…..pkn),则令θ(λ)=f(xk+λpk)=f(xk1+λpk1,xk2+λpk2,….,xkn+λpkn)是一元函数f(xk+λpk)的极值点，▽f(xk+λkpk)Tpk=0，即(p

8、k+1)Tpk=0。也就是说，有目标函数在一维搜索产生的新点xk+1=xk+λkpk处的梯度与产生该点时所用的搜索方向是正交的。改进后的算法精度ε>0，自然数N>=2,k=0Step1:计算Step2：Step3：如果，则转Step5；否则进行一维搜索，令若k>=N,且k/3-[k/3]=0.则转Step4，否则转Step2.Step4：计算，进行一维搜索令，转Step2Step5：停止，输出小结1、优点：计算简单，需记忆的容量小；对初始点要求低，稳定性高；远离极小点时收敛快，常作为其它方法的第一步。2、缺点：

9、收敛速度较慢。尤其当目标函数等值面是很扁的椭圆、椭球或类似图形时，收敛更慢。