最優(yōu)化之最速下降法

1、主講人：王俊俊最優(yōu)化 最速下降法LOGO最速下降法的由來最速下降法的方向選擇最速下降法的算法步驟最速下降法的實例最速下降法LOGOLOGO最速下降法的由來考慮無約束問題其中，函數(shù)法f(x)具有一階連續(xù)偏導(dǎo)數(shù)。 人們在處理這類問題時，總希望從某一點出發(fā)，選擇一個目標(biāo)函數(shù)值下降最快的方向，以利于盡快達(dá)到極小點，基于此種愿望，早在1847年法國數(shù)學(xué)家Cauchy提出了最速下降法。后來，Curry等人作了進(jìn)一步研究，得出現(xiàn)在眾所周知的一種最基本算法。 nRxxf,minLOGO最速下降法的由來其主要思想 每次沿負(fù)梯度方向進(jìn)行搜索每次沿負(fù)梯度方向進(jìn)行搜索kx)(kxf*x等值線(面)1kxLOGOLOG

2、O最速下降法的方向選擇最速下降法用負(fù)梯度為方向作為搜索方向。設(shè) f(x) 在XK附近連續(xù)可微，dk為搜索方向向量， .由泰勒展開式得那么目標(biāo)函數(shù) f(x)在Xk處沿方向dk下降的變化率為kkxfdkkxfg , 0,kTkkkkdgxfdxfLOGOLOGO最速下降法的方向選擇 coslimlim00kkkTkkTkkkkdgdgdgxfdxf其中 為gk與dk的夾角。要使得變化率最小，只有當(dāng)cos值為-1時，才能達(dá)到，也即dk應(yīng)取得負(fù)梯度方向。( )J aaka( )J a ( )J a LOGO 1.選取初始點 ，容許誤差 。令k:=1. 2. 計算 。若 ，停算，輸出Xk作為近似最優(yōu)解。

3、 3.取方向dk=-gk。 4.由線搜索技術(shù)確定步長因子 。 5.令 ， 轉(zhuǎn)步長1。最速下降法的步驟nRx 010kkxfgkgk, 1:,:1kkdxxkkkkLOGO由式 得， 即新點xk+1處的梯度是正交的，也就是說，迭代點列所走 的路線是鋸齒型的，故收斂速度是很慢的。kkxfd01kTkxfxfLOGO步長因子步4中，步長因子 的確定即可以采用精確線搜索又可以采用非精確線搜索。采用精確線搜索時 那么 應(yīng)該滿足 由此我們可以求出步長因子。 kkkkkkdxfdxf 0limk 0kTkkkkkddxfdxfddxkLOGO函數(shù) f（x1,x2）=(1-x2)2+100*(x2-x12)2

4、,它叫羅森布羅克方程。LOGO羅森布羅克方程的三維圖它的全局最優(yōu)點位于一個長長的、狹窄的、拋物線形狀的、扁平的“山谷”中。找到“山谷”并不難，難的是收斂到全局最優(yōu)解（全局最優(yōu)解在 (1,1) 處）。LOGO求 使其滿足0min ()()kkkkkf xpf xpk令1kkkkxxp輸出：minkxx結(jié)束開始給定初始點， ，0nxE0: 0k 計算()kkpf x kp否否是是程序圖LOGOmatlabmatlab仿真實例LOGOmatlabmatlab仿真實例LOGO最速下降法的優(yōu)缺點由于沿負(fù)梯度方向目標(biāo)函數(shù)的最速下降性，很容易使人們誤認(rèn)為負(fù)梯度方向是最理想的搜索方向，最速下降法是一種理想的極小化方法。必須指出的是，某點的負(fù)梯度方向，通常只是在該點附近才具有這種最速下降的性質(zhì)。在一般情況下，當(dāng)用最速下降法尋找極小點時，其搜索路徑呈直角鋸齒狀，在開頭幾步，目標(biāo)函數(shù)下降較快；但在接近極小點時，收斂速度長久不理想了。特別適當(dāng)目標(biāo)函數(shù)的