最優(yōu)化課程設計--最速下降法算法分析與實現

1、<p>　　《最 優(yōu) 化 方 法》</p><p><b>　　課 程 設 計</b></p><p>　　題 目：最速下降法算法分析與實現</p><p>　　院 系： 數學與計算科學學院 </p><p>　　專 業(yè)： 數學與應用數學 </p><

2、;p>　　姓名學號： XXX XXXXXXXX </p><p>　　指導教師： XXX </p><p>　　日 期： 2014 年 01 月 11 日</p><p><b>　　摘 要</b></p><p>　　在各種優(yōu)化算法中，下降

3、梯度法是非常重要的一種.本文主要介紹的最速下降法是一種無約束優(yōu)化算法，它具有線性收斂速度，而且算法結構簡單，容易編程實現.</p><p>　　在本次課設中,我首先分析無約束問題的最優(yōu)性條件，根據其求解的充分必要條件列出四個定理，運用最速下降法進行無約束優(yōu)化問題的求解.無約束最優(yōu)化方法的核心問題是選擇搜索方向.最速下降法的基本思想是以負梯度方向作為極小化方法的下降方向，并沿下降方向進行搜索，求出目標函數的極小點.

4、再結合該算法編寫matlab程序，求解無約束優(yōu)化問題，最后分析結果得出最速下降法的優(yōu)缺點.</p><p>　　最速下降法又稱為梯度法，是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到，因此它是最優(yōu)化方法的基礎，在最優(yōu)化方法中占有非常重要的地位.最速下降法是 n元函數的非線性無約束規(guī)劃問題 的一種重要解析法，優(yōu)點是工作量少，存儲變量較少，初始點要求不高；缺點是收斂慢，效率不高，有時達不到最優(yōu)

5、解.</p><p>　　關鍵詞：一維搜索；線性收斂；梯度；無約束優(yōu)化 </p><p><b>　　Abstract</b></p><p>　　In a variety of optimization algorithms, steepest descent method is a very important one. In this p

6、aper, we mainly introduce the steepest descent method ,it has convergence rate and the algorithm is simple and easy programming.</p><p>　　In this experiment, we first analyze the unconstrained conditions of

7、the unconstrained optimization problems.Using the steepest descent method to solve the unconstrained optimization problems. Unconstrained optimization method is to select the core issue of the search direction. The basic

8、 idea of steepest descent method is treating the negative gradient direction as the down direction of minimization method, then, along the down direction to search combining write the MATLAB program, finally, an</p>

9、;<p>　　The steepest descent method is also called as the gradient method. Other methods or its deformation, or inspired by it. So it occupies a very important position . The steepest descent method is the n nonli

10、near unconstrained programming function \* MERGEFORMAT analytical method. It is less workload, less storage variable, initial request is not high; Defect is convergence slow, inefficient, sometimes can’t reach the opti

11、mal solution.</p><p>　　Key words: One dimensional search; Linear convergence; Gradient; Unconstrained optimization</p><p><b>　　目 錄</b></p><p><b>　　1、引言1</b

12、></p><p>　　2、最速下降法的基本原理1</p><p>　　2.1 無約束問題的最優(yōu)性條件1</p><p>　　2.2 最速下降法的基本原理與迭代步驟2</p><p>　　2.3 負梯度方向使目標函數下降最快的原因3</p><p>　　2.4 最速下降法的收斂性和收斂速度4</p

13、><p>　　3、最速下降法算法實現4</p><p>　　3.1算法流程圖5</p><p><b>　　3.2代碼編程6</b></p><p>　　3.3 算法測試7</p><p>　　3.4 最速下降法優(yōu)缺點分析12</p><p><b>　　4

14、、總結13</b></p><p>　　4.1 總結概括13</p><p>　　4.2 個人感言14</p><p><b>　　5、參考文獻14</b></p><p><b>　　1、引言</b></p><p>　　在各種優(yōu)化算法中，最速下降法（T

15、he steepest descent method）是非常重要的一種.以負梯度方向作為極小化方法的下降方向，這種方法就是最速下降法.最速下降法又稱為梯度法，是1847年由著名數學家 給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到，因此它是最優(yōu)化方法的基礎. 作為一種基本的算法，它在最優(yōu)化方法中占有非常重要的地位.最速下降法正是 n元函數的非線性無約束規(guī)劃問題 的一種重要解析法，研究最速下降法原理及其算

16、法分析與實現對我們有著極其重要的意義.</p><p>　　最速下降法的基本原理</p><p>　　2.1 無約束問題的最優(yōu)性條件</p><p>　　無約束問題求最優(yōu)解的算法設計需要依據其充分條件和必要條件，有幾個重要定理如下：</p><p>　　定理 1 設 \* MERGEFORMAT 在點 \* MERGEFORMAT 處

17、可微.若 \* MERGEFORMAT 存在,使</p><p>　　則向量d是f 在點 \* MERGEFORMAT 處的下降方向.</p><p>　　定理 2 設 \* MERGEFORMAT 在點 \* MERGEFORMAT 處可微.若 \* MERGEFORMAT 是無約束問題的局部最優(yōu)解，則</p><p>　　在數學分析中我們已經知道，

18、使 \* MERGEFORMAT 的點 \* MERGEFORMAT 為函數 \* MERGEFORMAT 的駐點或平穩(wěn)點.函數 \* MERGEFORMAT 的一個駐點可以是極小點也可以是極大點,甚至也可能既不是極小點也不是極大點，此時稱它為函數 \* MERGEFORMAT 鞍點.以上定理告訴我們， \* MERGEFORMAT 是無約束問題的的局部最優(yōu)解的必要條件是： \* MERGEFORMAT 是其目標函數

19、\* MERGEFORMAT 的駐點.</p><p>　　定理 3 設 \* MERGEFORMAT 在點 \* MERGEFORMAT 處的 \* MERGEFORMAT 矩陣 \* MERGEFORMAT 存在.若</p><p>　　且 \* MERGEFORMAT 是正定的，則 \* MERGEFORMAT 是無約束問題的嚴格局部最優(yōu)解.以上定理說明， \* M

20、ERGEFORMAT 無約束問題的局部最優(yōu)解的充分條件是： \* MERGEFORMAT 在處的二階導數等于零.</p><p>　　一般而言，無約束問題的目標函數的駐點不一定是無約束問題的最優(yōu)解.但對于其目標函數是凸函數的無約束凸規(guī)劃，下面定理證明了，它的目標函數的駐點就是它的整體最優(yōu)解.</p><p>　　定理 4 設 \* MERGEFORMAT ,點 \* MERGEF

21、ORMAT , \* MERGEFORMAT 是 \* MERGEFORMAT 上的可微凸函數.若</p><p>　　則 \* MERGEFORMAT 是無約束問題的整體最優(yōu)解.</p><p>　　2.2 最速下降法的基本思想和迭代步驟</p><p>　　最速下降法又稱為梯度法，是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到，因

22、此它是最優(yōu)化方法的基礎.</p><p>　　設無約束問題中的目標函數 \* MERGEFORMAT 一階連續(xù)可微.</p><p>　　最速下降法的基本思想是：從當前點 \* MERGEFORMAT 出發(fā)，取函數 \* MERGEFORMAT 在點 \* MERGEFORMAT 處下降得最快的方向作為我們的搜索方向 \* MERGEFORMAT .由 \* MERGE

23、FORMAT 的 \* MERGEFORMAT 展開式知</p><p>　　略去 \* MERGEFORMAT 的高階無窮小項不計，可知當取 \* MERGEFORMAT =- \* MERGEFORMAT 時，函數值下降得最快.于是，我們可以構造出最速下降法的迭代步驟.</p><p>　　解無約束問題的最速下降法計算步驟</p><p>　　\* M

24、ERGEFORMAT 選取初始點 \* MERGEFORMAT ，給定終止誤差 \* MERGEFORMAT ，令 \* MERGEFORMAT ；</p><p>　　\* MERGEFORMAT 計算 \* MERGEFORMAT ，若‖ \* MERGEFORMAT ‖ \* MERGEFORMAT ，停止迭代.輸出 \* MERGEFORMAT .否則轉入 \* MERGEFO

25、RMAT </p><p>　　\* MERGEFORMAT 取 \* MERGEFORMAT = - \* MERGEFORMAT ；</p><p>　　\* MERGEFORMAT 進行一維搜索，求 \* MERGEFORMAT ，使得</p><p>　　令 \* MERGEFORMAT , \* MERGEFORMAT ，轉 \

26、* MERGEFORMAT .</p><p>　　由以上計算步驟可知，最速下降法迭代終止時，求得的是目標函數駐點的一個近似點.</p><p>　　確定最優(yōu)步長 \* MERGEFORMAT 的方法如下：</p><p>　　方法一：采用任一種一維尋優(yōu)法</p><p>　　此時的 \* MERGEFORMAT 已成為步長 \* ME

27、RGEFORMAT 的一元函數，故可用任何一種一維尋優(yōu)法求出 \* MERGEFORMAT ，即</p><p><b>　　方法二：微分法</b></p><p><b>　　因為</b></p><p>　　所以，一些簡單情況下，可令</p><p>　　以解出近似最優(yōu)步長 \* MER

28、GEFORMAT 的值.</p><p>　　2.3 負梯度方向使目標函數值下降最快的原因</p><p>　　為什么是負梯度方向使目標函數值下降最快？下面，我們討論的是n維空間中的一個點移動到另一個點之后，目標函數值的改變情況，因此，先直接寫出代表最終的目標函數值的數學表達式：</p><p>　　\* MERGEFORMAT 代表第k個點的自變量（一個向量）.

29、</p><p>　　\* MERGEFORMAT :單位方向（一個向量），即 \* MERGEFORMAT </p><p>　　\* MERGEFORMAT ：步長（一個實數）.</p><p>　　\* MERGEFORMAT 目標函數在 \* MERGEFORMAT 這一點的梯度（一個向量）.</p><p>　　\* MERGE

30、FORMAT ： \* MERGEFORMAT 的高階無窮小.</p><p>　　顯然，這個數學表達式是用泰勒公式展開得到的，對比自變量為一維的情況下的泰勒展開式:</p><p>　　在目標函數值的數學表達式中，高階無窮小可以忽略，因此，要使該式取到最小值，應使 \* MERGEFORMAT 取到最小——這是兩個向量的點積（數量積），何種情況下其值最小呢？來看兩向量 \* MER

31、GEFORMAT 的夾角 \* MERGEFORMAT 的余弦是如何定義的：</p><p>　　假設向量 \* MERGEFORMAT 與負梯度 \* MERGEFORMAT 的夾角為 \* MERGEFORMAT ，我們便可求出點積 \* MERGEFORMAT 的值為：</p><p>　　可見， \* MERGEFORMAT 為0時，上式取得最小值.也就是說， \*

32、MERGEFORMAT 取 \* MERGEFORMAT 時，目標函數值下降得最快，這就是稱負梯度方向為“最速下降”方向的由來.</p><p>　　2.4 最速下降法的收斂性以及收斂速度</p><p>　　最速下降法的收斂性：對一般的目標函數是整體收斂的（所謂整體收斂，是指不會非要在某些點附近的范圍內，才會有好的收斂性）.</p><p>　　最速下降法的收

33、斂速度：至少是線性收斂的.</p><p><b>　　最速下降法算法實現</b></p><p>　　3.1最速下降法程序流程圖</p><p>　　圖1：最速下降法算法流程圖</p><p><b>　　3.2 代碼編程</b></p><p><b>　　3.

34、3 算法實現</b></p><p>　　我們通過求解幾個無約束優(yōu)化例題來驗證算法的穩(wěn)定性和準確性.</p><p>　　例1：求解 \* MERGEFORMAT ，設初始點為 \* MERGEFORMAT ，求迭代一次后的迭代點 \* MERGEFORMAT .</p><p>　　解：因為 \* MERGEFORMAT </p

35、><p>　　所以 \* MERGEFORMAT </p><p>　　所以 \* MERGEFORMAT </p><p>　　令 \* MERGEFORMAT </p><p>　　求解 \* MERGEFORMAT </p><p>　　令 \* MERGEFORMAT </p><p&

36、gt;　　所以 \* MERGEFORMAT </p><p>　　例2： \* MERGEFORMAT 給定初始點為 \* MERGEFORMAT .</p><p>　　解：目標函數 \* MERGEFORMAT 的梯度為 \* MERGEFORMAT </p><p>　　\* MERGEFORMAT ,令搜索方向 \* MERG

37、EFORMAT </p><p>　　再從 \* MERGEFORMAT 方向出發(fā)，沿 \* MERGEFORMAT 方向作一維搜索尋優(yōu)，令步長變量為 \* MERGEFORMAT 最優(yōu)步長為 \* MERGEFORMAT 則有 \* MERGEFORMAT </p><p>　　故 \* MERGEFORMAT </p><p>　　\* MERGEF

38、ORMAT 進行第二次迭代.</p><p>　　從 \* MERGEFORMAT 方向出發(fā)，沿 \* MERGEFORMAT 方向作一維搜索尋優(yōu)，令步長變量為最優(yōu)步長為 \* MERGEFORMAT 則有 \* MERGEFORMAT </p><p>　　令 \* MERGEFORMAT 可得</p><p><b>　　則有</b&g

39、t;</p><p>　　\* MERGEFORMAT 與上類似，進行第三次迭代，直到 \* MERGEFORMAT 為止.求得本題最優(yōu)解為 \* MERGEFORMAT ,代入求解出 \* MERGEFORMAT .</p><p>　　例3：用最速下降法求解無約束非線性規(guī)劃問題：</p><p>　　其中 \* MERGEFORMAT ，要求選取初始點

40、 \* MERGEFORMAT = \* MERGEFORMAT ，終止誤差 \* MERGEFORMAT </p><p>　　解：目標函數的梯度為</p><p>　　因為 \* MERGEFORMAT = \* MERGEFORMAT 則有</p><p>　　\* MERGEFORMAT 求單變量極小化問題：</p><p>

41、;　　的最優(yōu)解由黃金分割法得于是</p><p>　　\* MERGEFORMAT 再求單變量極小化問題：</p><p>　　的最優(yōu)解，計算結果如下表 \* MERGEFORMAT 所示：</p><p>　　表1：例3無約束規(guī)劃迭代過程表</p><p>　　\* MERGEFORMAT 由表1可知， \* MERGEFORMAT

42、 ，停止計算，所以 \* MERGEFORMAT 為近似最優(yōu)解，原問題的近似最優(yōu)值為0.007.</p><p>　　例4：用最速下降法求解無約束問題</p><p>　　取 \* MERGEFORMAT </p><p>　　解：計算目標函數的梯度和Hesse陣</p><p>　　設, \* MERGEFORMAT </p

43、><p>　　得到精確一維搜索步長</p><p>　　取 \* MERGEFORMAT ,則 \* MERGEFORMAT ，</p><p>　　所以 \* MERGEFORMAT , \* MERGEFORMAT </p><p><b>　　因此</b></p><p><b&

44、gt;　　再循環(huán)計算，</b></p><p>　　得到迭代結果如下表2所示：</p><p>　　表2：例4無約束規(guī)劃問題迭代表</p><p>　　由上表可知， \* MERGEFORMAT 為原問題的最優(yōu)解，最優(yōu)值為-2.000.</p><p>　　3.4 最速下降法的優(yōu)缺點</p><p>&l

45、t;b>　　3.4.1 優(yōu)缺點</b></p><p>　　最速下降法的優(yōu)點：算法簡單，每次迭代計算量小，占用內存小，且對初始點要求不高，即使從一個不好的初始點出發(fā)，往往也能收斂到局部極小點.</p><p>　　最速下降法的缺點：收斂速度慢，特別是當目標函數的等值線為比較扁平的橢圓時，收斂就更慢了.</p><p>　　3.4.2 優(yōu)缺點分析&l

46、t;/p><p>　　由于沿負梯度方向目標函數的最速下降性，很容易使人們誤認為負梯度方向是最理想的搜索方向，最速下降法是一種理想的極小化方法.必須指出的是，某點的負梯度方向，通常只是在該點附近才具有這種最速下降的性質.</p><p>　　在一般情況下，當用最速下降法尋找極小點時，其搜索路徑呈直角鋸齒狀（圖2），在開頭幾步，目標函數下降較快；但在接近極小點時，收斂速度長久不理想了.特別適當目標

47、函數的等值線為比較扁平的橢圓時，收斂就更慢了.</p><p>　　圖2：最速下降法搜索路徑圖</p><p>　　對于最優(yōu)化目標函數來說，圖3中的一束橢圓表示函數的等值線，愈是內圈的橢圓，所對應的函數值愈小.由于最速下降法相鄰兩次的搜索方向互相垂直，搜索路徑實際上是一條鋸齒狀的路徑，也就是最速下降法的鋸齒現象.</p><p>　　其中， \* MERGEFOR

48、MAT 分別是對稱正定矩陣 \* MERGEFORMAT 的最大與最小特征值，當 \* MERGEFORMAT 時，收斂速度變得非常慢，而且當 \* MERGEFORMAT 很小時，由于舍入誤差的影響，計算將出現不穩(wěn)定.</p><p><b>　　圖3：函數等值線圖</b></p><p>　　因此，在實用中常將最速下降法和其他方法聯(lián)合應用，在前期使用最速下降

49、法，而在接近極小點時，可改用收斂較快的其他方法.</p><p><b>　　4、總結</b></p><p><b>　　4.1 總結概括</b></p><p>　　此次課設我對最速下降法有了更深一步的了解，鞏固了以前的知識.對其原理和算法都有了更深理解.</p><p>　　最速下降法算法分析

50、總結：以負梯度方向作為極小化方法的下降方向，這種方法就是最速下降法.其基本思想是以負梯度方向作為極小化方法的下降方向，并沿下降方向進行一維搜索，求出目標函數的極小點.其優(yōu)點是工作量少，存儲變量較少，初始點要求不高；缺點是收斂慢，效率不高，有時達不到最優(yōu)解.因此，在實用中常將最速下降法和其他方法聯(lián)合應用，在前期使用最速下降法，而在接近極小點時，可改用收斂較快的其他方法.</p><p><b>　　4.2

51、 個人感言</b></p><p>　　最初接觸最速下降法是在學習最優(yōu)化課程時，在課堂上只是簡單了解了其基本原理以及迭代步驟，并沒有進行深入了解和探討.在做課設的過程中，我了解到最速下降法是最古老的一種解析方法，也是最基本的一種解析方法，在無約束求解中有著重要的作用.課設中，我深深感受到以前學到的知識是遠遠不夠的.我去圖書館查閱了許多相關書籍，并引用了一些例題來實現算法的展示（其中有些題是我自己編寫并

52、計算的）.為了在MATLAB中實現編程，我也上網查閱了相關資料.最后，終于憑借自己的努力完成了此次課設.</p><p>　　通過這次課設，我重新學習了以前遺忘的知識，加深了記憶和理解，真正做到了理論和實踐相結合，鍛煉了自己分析、處理實際問題的能力，也認識到了自己的不足.這次課設給我?guī)砹撕芏鄬氋F的經驗和財富，讓我受益匪淺.</p><p><b>　　5、參考文獻</b&

53、gt;</p><p>　　[1］趙瑞安，吳方.非線性最優(yōu)化理論和方法[M].北京:高等教育出版社.1900</p><p>　?。?］陳開明.非線性規(guī)劃[M].上海：復旦大學出版社.1991</p><p>　　[3］周維，楊鵬飛.運籌學[M].北京：科學出版社.2008</p><p>　?。?］劉建永.運籌學算法與編程實踐[M].北京：