1、沙理工數學與計算科學學院實驗報告實驗項目名稱使用非精確線搜索 Armjo 算法確定步長的最速下降法所屬課程名稱最優化方法實驗類型算法編程實驗日期班 級學 號姓 名成 績、實驗概述:【實驗目的】1. 通過實驗掌握最速下降法的Matlab算法的基本步驟;2. 通過實驗掌握Armijo算法確定步長；3. 掌握最速下降法的思想及迭代步驟。等值線（面）事實上，對任意p Rn且|p |,由Cauchy - Schwarz不等式得 負梯度方向也稱為最速下降方向m汗 舉當取p廠臂時等號成立，即p的解-| f(Xk)|-f(Xk)是下列問題| f(Xk)|min|p|f(Xk)TP算法步驟：步1給定初始點X。R

2、n,精度0.令k 0;步2若| f(xk)| ，則得解xk,算法終止.否則 計算dk - f (xk),然后轉步3；步3由線性搜索計算步長k;步4 令xk 1 xkkdk,k : k 1,轉步 2.優點：對于簡單的二元二次函 數極小化問題， 最速下降法在有限次迭 代并沒有求出其精確最 優解,但能 以較慢的速度無限接近 最優解.最速下降法的收斂性：全局收斂性：由于最速下降法的搜索 方向與負梯度方向一致，即k 0,且II f(xQ| |dk|所以，我們很容易得到最速下 降算法的全局收斂性.的迭采用精確搜索，或Armijo搜索或Wolfe - Powell搜索的最速下降法產生 代序列Xk滿足kim

3、| f(Xk)| 0由例子看到，最速下降法的收斂速度至多是線性的，收斂速度估計:設矩陣Q對稱正定,q Rn.記max和min分別是Q的最大和最小特征值, maX .考察如下二次函數極小化min 問題：min f(x) 1xTQx qTx2則由米用精確搜索的最 速下降法產生的點列xk滿足* 1 *|Xk 1 - X |q, |Xk-x |q(3.2)11 其中x*是問題的惟一解,| x |Q xTQx 2對于二次函數，由于f(x) Qx q且在x*處f (x*) Qx* q 0*1* t*1*2則 f(x)- f(x )2(x-x ) Q(x-x )2|x-x |q所以(3.2)可以改寫成2I

4、f(xk 1)- f (x )- f (xk)- f (x )1由收斂速度估計式(3.2)看到,最速下降的收斂速度與 矩陣 Q的條件數 有關，當 接近于1,最速下降收斂很快，特別， 當1即Q的所有特征值相等時，算法只需一次迭代即可求出最優解.而當 較大時(Q接近病態)，算法收斂很慢.結論：最速下降法的收斂速度比較慢，通常將其用在某些算法的初 始階段求較好的初始點或作為某些算法的間插步.【實驗環境】Win7 ；二、實驗內容:【實驗方案】1、求梯度；2、 向梯度相反的方向移動 x,其中吃|為步長。如果步長足夠小，則可以保證每一次迭代都在 減小，但可能導致收斂太慢，如果步長太大，則不能保證每一次迭代

5、都減少，也不能保證收斂。3、 循環迭代步驟 2,直到x的值變化到使得！ 在兩次迭代之間的差值足夠小，比如，也就 是說，直到兩次迭代計算出來的 F2喘基本沒有變化，則說明此時 T 訶已經達到局部最小值了。4、 此時，輸出x，這個x就是使得函數最小時的x的取值。【實驗過程】梯度下降法的計算過程就是沿梯度下降的方向求解極小值（也可以沿梯度上升方向求解極大值）。其迭代公式為 蘇+1=聽+ P話朗,其中副町代表梯度負方向，卩上表示梯度方向上的搜索步長。梯度方向我們可以通過對函數求導得到，步長的確定比較麻煩，太大了的話可能會 發散，太小收斂速度又太慢。一般確定步長的方法是由線性搜索算法來確定，即把下一個點

6、的 坐標ak+1看做是的函數，然后求滿足 f（ak+1）的最小值的 即可。因為一般情況下，梯度向量為0的話說明是到了一個極值點， 此時梯度的幅值也為 0.而采用梯度下降算法進行最優化求解時，算法迭代的終止條件是梯度向量的幅值接近0即可，可以設置個非常小的常數閾值。【實驗結論】（結果）梯度下降法處理一些復雜的非線性函數會出現問題，例如Rosenbrock函數：其最小值在 （耳丁）二（lH處，函數值為f （xty = 0。但是此函數具有狹窄彎曲的山谷，最小點 就在這些山谷之中，并且谷底很平。優化過程是之字形的向極小值點靠近，速度非常 緩慢。靠近極小值時收斂速度減慢。直線搜索時可能會產生一些問題。可

7、能會“之字形”地下 降。【實驗小結】（收獲體會）這次的實驗報告，使得我們對這些算法的思想更加了解，在選擇線性搜索的方法時，我們 深刻體會到各類參數設置對程序效率的重要性，不冋的問題要選用合適的參數來求解，這樣使 得問題求解及程序運行的效率最高。通過不斷地翻閱課本，剖析程序，我們最后實現了對程序 的修改和完善，對提供的問題作出了較好的解答。總的來說，對無約束最優化的求解，每種方 法在解決不同的問題中效果不能都達到最優，所以我們在實際應用中，要根據實際情況選擇合 適的方法，爭取最大可能的盡快的接近最優。本次實驗不僅使我們基本了解了最優化的實用算法的結構及性能，而且也使得我們對 matlab的一些編

8、程技巧更加熟悉，收獲很大。三、指導教師評語及成績：評語評語等級優良中及格不及格1.實驗報告按時完成，字跡清楚，文字敘述流暢，邏輯性強2.實驗方案設計合理3.實驗過程（實驗步驟詳細，記錄完整，數據合理，分析透徹）4實驗結論正確.成績：指導教師簽名：批閱日期：附錄1源程序Armijo算法實現：pla in view pla in copyfun cti on mk = armijo( fun, xk, rho, sigma, gk )assert( rho 0 & rho 0 & sigma );mk = 0; max_mk = 100;while mk = max_mkx = xk - rhoA

9、mk * gk;if feval( fun, x ) = feval( fun, xk ) - sigma * rhoAmk * norm( gk )八2 break;endmk = mk + 1;endreturn;最速下降法實現：pla in view pla in copyfun cti on opt_x, opt_f, k = grad_desce nt( fun_obj, fun _grad, x0 )max_iter = 5000;% max nu mber of iterati onsEPS = 1e-5;% threshold of gradie nt n orm% Armij

10、o parametersrho = ; sigma =;% in itializatio nk = 0; xk = xO;while k max_iterk = k + 1;gk = feval( fun _grad, xk ); % gradie nt vectordk = -1 * gk;% search direct ionif norm( dk ) EPSbreak;endyk = feval( fun_obj, xk );fprintf( #iter = %5d, xk = %.5f, F = %.5fn, k, xk, yk );mk = armijo( fun_obj, xk,

11、rho, sigma, gk );xk = xk + rhoAmk * dk;endfprintf( n);if k = max_iterfprintf( P roblem Not solved!n);elsefpri ntf( Problem solved! n);end% record resultsopt_x = xk;opt_f = feval( fun _obj, xk );return;附錄2:實驗報告填寫說明1實驗項目名稱： 要求與實驗教學大綱一致。2 實驗目的：目的要明確，要抓住重點，符合實驗教學大綱要求。3 實驗原理：簡要說明本實驗項目所涉及的理論知識。4.實驗環境：實驗用的軟、硬件環境。5實驗方案（思路、步驟和方法等）：這是實驗報告極其重要的內容。概括整個實驗過程。對于驗證性實驗，要寫明依據何種原理、操作方法進行實驗，要寫明需要經過哪幾個步 驟來實現其操作。對于設計性和綜合性實驗，在上述內容基礎上還應該畫出流程圖、設 計思路和設計方法，再