最優(yōu)化Armijo算法確定步長(zhǎng)的最速下降法

1、數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí) 驗(yàn) 報(bào) 告實(shí)驗(yàn)項(xiàng)目名稱 使用非精確線搜索Armijo算法確定步長(zhǎng)的 最速下降法 所屬課程名稱 最優(yōu)化方法 實(shí) 驗(yàn) 類 型 算法編程 實(shí) 驗(yàn) 日 期 班 級(jí) 學(xué) 號(hào) 姓 名 成 績(jī) 一、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹?. 通過實(shí)驗(yàn)掌握最速下降法的Matlab算法的基本步驟；2. 通過實(shí)驗(yàn)掌握Armijo算法確定步長(zhǎng)；3. 掌握最速下降法的思想及迭代步驟?！緦?shí)驗(yàn)原理】1.最速下降法： 最古老的優(yōu)化方法，十九世紀(jì)中葉由Cauchy提出 思想 ：每次沿負(fù)梯度方向進(jìn)行搜索等值線(面)負(fù)梯度方向也稱為最速下降方向：舉例：算法步驟：優(yōu)點(diǎn)：最速下降法的收斂性：全局收斂性：收斂速度估計(jì)：結(jié)論：最速

2、下降法的收斂速度比較慢，通常將其用在某些算法的初始階段求較好的初始點(diǎn)或作為某些算法的間插步.【實(shí)驗(yàn)環(huán)境】Win 7；Matlab7.0二、實(shí)驗(yàn)內(nèi)容：【實(shí)驗(yàn)方案】1、求梯度；2、向梯度相反的方向移動(dòng)x，其中 為步長(zhǎng)。如果步長(zhǎng)足夠小，則可以保證每一次迭代都在減小，但可能導(dǎo)致收斂太慢，如果步長(zhǎng)太大，則不能保證每一次迭代都減少，也不能保證收斂。3、循環(huán)迭代步驟2，直到x的值變化到使得在兩次迭代之間的差值足夠小，比如0.00000001，也就是說，直到兩次迭代計(jì)算出來的基本沒有變化，則說明此時(shí)已經(jīng)達(dá)到局部最小值了。4、此時(shí)，輸出x，這個(gè)x就是使得函數(shù)最小時(shí)的x的取值 ?！緦?shí)驗(yàn)過程】 梯度下降法

3、的計(jì)算過程就是沿梯度下降的方向求解極小值（也可以沿梯度上升方向求解極大值）。 其迭代公式為 ,其中 代表梯度負(fù)方向， 表示梯度方向上的搜索步長(zhǎng)。梯度方向我們可以通過對(duì)函數(shù)求導(dǎo)得到，步長(zhǎng)的確定比較麻煩，太大了的話可能會(huì)發(fā)散，太小收斂速度又太慢。一般確定步長(zhǎng)的方法是由線性搜索算法來確定，即把下一個(gè)點(diǎn)的坐標(biāo)ak+1看做是的函數(shù)，然后求滿足f(ak+1)的最小值的 即可。 因?yàn)橐话闱闆r下，梯度向量為0的話說明是到了一個(gè)極值點(diǎn)，此時(shí)梯度的幅值也為0.而采用梯度下降算法進(jìn)行最優(yōu)化求解時(shí)，算法迭代的終止條件是梯度向量的幅值接近0即可，可以設(shè)置個(gè)非常小的常數(shù)閾值?！緦?shí)驗(yàn)結(jié)論】（結(jié)

4、果）梯度下降法處理一些復(fù)雜的非線性函數(shù)會(huì)出現(xiàn)問題，例如Rosenbrock函數(shù)：其最小值在 處，函數(shù)值為 。但是此函數(shù)具有狹窄彎曲的山谷，最小點(diǎn) 就在這些山谷之中，并且谷底很平。優(yōu)化過程是之字形的向極小值點(diǎn)靠近，速度非常緩慢?？拷鼧O小值時(shí)收斂速度減慢。直線搜索時(shí)可能會(huì)產(chǎn)生一些問題?？赡軙?huì)“之字形”地下降?！緦?shí)驗(yàn)小結(jié)】（收獲體會(huì)） 這次的實(shí)驗(yàn)報(bào)告，使得我們對(duì)這些算法的思想更加了解，在選擇線性搜索的方法時(shí)，我們深刻體會(huì)到各類參數(shù)設(shè)置對(duì)程序效率的重要性，不同的問題要選用合適的參數(shù)來求解，這樣使得問題求解及程序運(yùn)行的效率最高。通過不斷地翻閱課本，剖析程序，我們最后實(shí)現(xiàn)了對(duì)程序的修改

5、和完善，對(duì)提供的問題作出了較好的解答。總的來說，對(duì)無約束最優(yōu)化的求解，每種方法在解決不同的問題中效果不能都達(dá)到最優(yōu)，所以我們?cè)趯?shí)際應(yīng)用中，要根據(jù)實(shí)際情況選擇合適的方法，爭(zhēng)取最大可能的盡快的接近最優(yōu)。  本次實(shí)驗(yàn)不僅使我們基本了解了最優(yōu)化的實(shí)用算法的結(jié)構(gòu)及性能，而且也使得我們對(duì)matlab的一些編程技巧更加熟悉，收獲很大。三、指導(dǎo)教師評(píng)語及成績(jī)：評(píng) 語評(píng)語等級(jí)優(yōu)良中及格不及格1.實(shí)驗(yàn)報(bào)告按時(shí)完成,字跡清楚,文字?jǐn)⑹隽鲿?邏輯性強(qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過程（實(shí)驗(yàn)步驟詳細(xì),記錄完整,數(shù)據(jù)合理,分析透徹）4實(shí)驗(yàn)結(jié)論正確. 成 績(jī)： 指導(dǎo)教師簽名： 批閱日期：附錄1：源 程 序Armij

6、o算法實(shí)現(xiàn)：plain view plaincopyfunction mk = armijo( fun, xk, rho, sigma, gk ) assert( rho > 0 && rho < 1 ); assert( sigma > 0 && sigma < 0.5 ); mk = 0; max_mk = 100; while mk <= max_mk x = xk - rhomk * gk; if feval( fun, x ) <= feval( fun, xk ) - sigma * rhomk * norm( g

7、k )2 break; end mk = mk + 1; end return; 最速下降法實(shí)現(xiàn)：plain view plaincopyfunction opt_x, opt_f, k = grad_descent( fun_obj, fun_grad, x0 ) max_iter = 5000; % max number of iterations EPS = 1e-5; % threshold of gradient norm % Armijo parameters rho = 0.5; sigma = 0.2; % initialization k = 0; xk = x0; whil

8、e k < max_iter k = k + 1; gk = feval( fun_grad, xk ); % gradient vector dk = -1 * gk; % search direction if norm( dk ) < EPS break; end yk = feval( fun_obj, xk ); fprintf( '#iter = %5d, xk = %.5f, F = %.5fn', k, xk, yk ); mk = armijo( fun_obj, xk, rho, sigma, gk ); xk = xk + rhomk * dk

9、; end fprintf( '-n' ); if k = max_iter fprintf( 'Problem Not solved!n' ); else fprintf( 'Problem solved!n' ); end % record results opt_x = xk; opt_f = feval( fun_obj, xk ); return;附錄2：實(shí)驗(yàn)報(bào)告填寫說明 1實(shí)驗(yàn)項(xiàng)目名稱：要求與實(shí)驗(yàn)教學(xué)大綱一致。2實(shí)驗(yàn)?zāi)康模耗康囊鞔_，要抓住重點(diǎn)，符合實(shí)驗(yàn)教學(xué)大綱要求。3實(shí)驗(yàn)原理：簡(jiǎn)要說明本實(shí)驗(yàn)項(xiàng)目所涉及的理論知識(shí)。4實(shí)驗(yàn)環(huán)境：實(shí)驗(yàn)用的軟、硬件環(huán)境。5實(shí)驗(yàn)方案（思路、步驟和方法等）：這是實(shí)驗(yàn)報(bào)告極其重要的內(nèi)容。概括整個(gè)實(shí)驗(yàn)過程。對(duì)于驗(yàn)證性實(shí)驗(yàn)，要寫明依據(jù)何種原理、操作方法進(jìn)行實(shí)驗(yàn)，要寫明需要經(jīng)過哪幾個(gè)步驟來實(shí)現(xiàn)其操作。對(duì)于設(shè)計(jì)性和綜合性實(shí)驗(yàn)，在上述內(nèi)容基礎(chǔ)上還應(yīng)該畫出流程圖、設(shè)計(jì)思路和設(shè)計(jì)方法，再配以相應(yīng)的文字說明。對(duì)于創(chuàng)新性實(shí)驗(yàn)，還應(yīng)注明其創(chuàng)新點(diǎn)、