1、數學與計算科學學院實 驗 報 告實驗項目名稱 使用非精確線搜索Armijo算法確定步長的 最速下降法 所屬課程名稱 最優化方法 實 驗 類 型 算法編程 實 驗 日 期 班 級 學 號 姓 名 成 績 一、實驗概述：【實驗目的】1. 通過實驗掌握最速下降法的Matlab算法的基本步驟；2. 通過實驗掌握Armijo算法確定步長；3. 掌握最速下降法的思想及迭代步驟。【實驗原理】1.最速下降法： 最古老的優化方法，十九世紀中葉由Cauchy提出 思想 ：每次沿負梯度方向進行搜索等值線(面)負梯度方向也稱為最速下降方向：舉例：算法步驟：優點：最速下降法的收斂性：全局收斂性：收斂速度估計：結論：最速

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

3、的計算過程就是沿梯度下降的方向求解極小值（也可以沿梯度上升方向求解極大值）。 其迭代公式為 ,其中 代表梯度負方向， 表示梯度方向上的搜索步長。梯度方向我們可以通過對函數求導得到，步長的確定比較麻煩，太大了的話可能會發散，太小收斂速度又太慢。一般確定步長的方法是由線性搜索算法來確定，即把下一個點的坐標ak+1看做是的函數，然后求滿足f(ak+1)的最小值的 即可。 因為一般情況下，梯度向量為0的話說明是到了一個極值點，此時梯度的幅值也為0.而采用梯度下降算法進行最優化求解時，算法迭代的終止條件是梯度向量的幅值接近0即可，可以設置個非常小的常數閾值。【實驗結論】（結

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

5、和完善，對提供的問題作出了較好的解答。總的來說，對無約束最優化的求解，每種方法在解決不同的問題中效果不能都達到最優，所以我們在實際應用中，要根據實際情況選擇合適的方法，爭取最大可能的盡快的接近最優。  本次實驗不僅使我們基本了解了最優化的實用算法的結構及性能，而且也使得我們對matlab的一些編程技巧更加熟悉，收獲很大。三、指導教師評語及成績：評 語評語等級優良中及格不及格1.實驗報告按時完成,字跡清楚,文字敘述流暢,邏輯性強2.實驗方案設計合理3.實驗過程（實驗步驟詳細,記錄完整,數據合理,分析透徹）4實驗結論正確. 成 績： 指導教師簽名： 批閱日期：附錄1：源 程 序Armij

6、o算法實現：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; 最速下降法實現：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：實驗報告填寫說明 1實驗項目名稱：要求與實驗教學大綱一致。2實驗目的：目的要明確，要抓住重點，符合實驗教學大綱要求。3實驗原理：簡要說明本實驗項目所涉及的理論知識。4實驗環境：實驗用的軟、硬件環境。5實驗方案（思路、步驟和方法等）：這是實驗報告極其重要的內容。概括整個實驗過程。對于驗證性實驗，要寫明依據何種原理、操作方法進行實驗，要寫明需要經過哪幾個步驟來實現其操作。對于設計性和綜合性實驗，在上述內容基礎上還應該畫出流程圖、設計思路和設計方法，再配以相應的文字說明。對于創新性實驗，還應注明其創新點