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

《最速下降法PPT及MATLAB程序.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、最速下降法最速下降法，也稱(chēng)為梯度下降法，是由法國(guó)著名數(shù)學(xué)家Cauchy在1847年提出的。最速下降法是求解無(wú)約束優(yōu)化問(wèn)題最簡(jiǎn)單和最古老的方法之一，雖然現(xiàn)在已經(jīng)不具有實(shí)用性，但是許多有效算法都是以它為基礎(chǔ)進(jìn)行改進(jìn)和修正而得到的。最速下降法是用負(fù)梯度方向?yàn)樗阉鞣较?，算法非常?jiǎn)單，并且通常對(duì)凸解析函數(shù)也有良好的收斂性。最速下降法的基本思想從任意一點(diǎn)xk出發(fā)，沿該點(diǎn)負(fù)梯度方向pk=-▽f(xk)進(jìn)行一維搜索，設(shè)f(xk+λkpk)=minf(xk+λpk)(λ>0)，令xk+1=xk+λkpk為f(x)新的近似最優(yōu)解。

2、再?gòu)男曼c(diǎn)xk+1出發(fā)，沿該點(diǎn)的負(fù)梯度方向pk+1=-▽f(xk+1)進(jìn)行一維搜索，進(jìn)一步求出新的近似最優(yōu)解xk+2。如此迭代，直到某點(diǎn)的梯度為零向量或梯度的范數(shù)小于事先給定的精度為止。給定x0，ε>0，k=0計(jì)算pk=-▽f(xk)

3、

4、▽f(xk)

5、

6、<εf(xk+λkpk)=minf(xk+λpk)(λ>0)xk+1=xk+λkpk，k=k+1停止，打印xkYN算法例.用最速下降法求函數(shù)f(x1,x2)＝2x12+x22的極小點(diǎn),取x0=[1,1]T,ε=0.1。解由題意得由于故進(jìn)行第一次迭代從x0=(1,1

7、)T出發(fā)進(jìn)行一維搜索，即構(gòu)造得從而得故進(jìn)行第二次迭代運(yùn)算:令從x1=(-1/9,4/9)T出發(fā)進(jìn)行一維搜索，即構(gòu)造得從而得令故進(jìn)行第三次迭代運(yùn)算:從x2=(2/27,2/27)T出發(fā)進(jìn)行一維搜索，即構(gòu)造得從而得令停止迭代故最優(yōu)解為最速下降法的搜索路徑呈直角鋸齒形設(shè)xk=(xk1,xk2…..xkn),pk=(pk1,pk2…..pkn),則令θ(λ)=f(xk+λpk)=f(xk1+λpk1,xk2+λpk2,….,xkn+λpkn)是一元函數(shù)f(xk+λpk)的極值點(diǎn)，▽f(xk+λkpk)Tpk=0，即(p

8、k+1)Tpk=0。也就是說(shuō)，有目標(biāo)函數(shù)在一維搜索產(chǎn)生的新點(diǎn)xk+1=xk+λkpk處的梯度與產(chǎn)生該點(diǎn)時(shí)所用的搜索方向是正交的。改進(jìn)后的算法精度ε>0，自然數(shù)N>=2,k=0Step1:計(jì)算Step2：Step3：如果，則轉(zhuǎn)Step5；否則進(jìn)行一維搜索，令若k>=N,且k/3-[k/3]=0.則轉(zhuǎn)Step4，否則轉(zhuǎn)Step2.Step4：計(jì)算，進(jìn)行一維搜索令，轉(zhuǎn)Step2Step5：停止，輸出小結(jié)1、優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單，需記憶的容量小；對(duì)初始點(diǎn)要求低，穩(wěn)定性高；遠(yuǎn)離極小點(diǎn)時(shí)收斂快，常作為其它方法的第一步。2、缺點(diǎn)：

9、收斂速度較慢。尤其當(dāng)目標(biāo)函數(shù)等值面是很扁的橢圓、橢球或類(lèi)似圖形時(shí)，收斂更慢。