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

2、(xk+1)進(jìn)行一維搜索，進(jìn)一步求出新的近似最優(yōu)解xk+2。 如此迭代，直到某點(diǎn)的梯度為零向量或梯度的范數(shù)小于事先給定的精度為止。,.,3,給定x0，0，k=0,計(jì)算pk=-f(xk),| f(xk)|0),xk+1= xk+ kpk，k=k+1,停止，打印xk,Y,N,算法,.,4,例. 用最速下降法求函數(shù)f (x1, x2)2x12+x22 的極小點(diǎn),取x0=1,1T , =0.1。,解 由題意得,由于,故進(jìn)行第一次迭代,從x0=(1,1)T出發(fā)進(jìn)行一維搜索，即構(gòu)造,.,5,得,從而得,故進(jìn)行第二次迭代運(yùn)算:,令,從x1=(-1/9,4/9)T出發(fā)進(jìn)行一維搜索，即構(gòu)造,.,6,得,從而得,

3、令,故進(jìn)行第三次迭代運(yùn)算:,從x2=(2/27,2/27)T出發(fā)進(jìn)行一維搜索，即構(gòu)造,.,7,得,從而得,令,停止迭代,故最優(yōu)解為,.,8,.,9,最速下降法的搜索路徑呈直角鋸齒形,設(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，即(pk+1)Tpk=0。也就是說，有目標(biāo)函數(shù)在一維搜索產(chǎn)生的新點(diǎn)xk+1= xk+ kpk處的梯度與產(chǎn)生該點(diǎn)時(shí)所用的搜索方向是正交的。,.,10,改進(jìn)后的算法,精度0，自然數(shù)N=2,k=0,Step1:,計(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)Step2,Step5：,停止，輸出,.,11,小結(jié),1、優(yōu)點(diǎn)： 計(jì)算簡單，需記憶的容量??；對初始點(diǎn)要求低，穩(wěn)定性高；遠(yuǎn)離極小點(diǎn)時(shí)收斂快，常