最優(yōu)化課程設(shè)計(jì)--最速下降法算法分析與實(shí)現(xiàn)

1、<p>　　《最 優(yōu) 化 方 法》</p><p><b>　　課 程 設(shè) 計(jì)</b></p><p>　　題 目：最速下降法算法分析與實(shí)現(xiàn)</p><p>　　院 系： 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 </p><p>　　專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué) </p><

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

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

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

5、解.</p><p>　　關(guān)鍵詞：一維搜索；線性收斂；梯度；無約束優(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 負(fù)梯度方向使目標(biāo)函數(shù)下降最快的原因3</p><p>　　2.4 最速下降法的收斂性和收斂速度4</p

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

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

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

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

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

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

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

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

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

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

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

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

25、RMAT </p><p>　　\* MERGEFORMAT 取 \* MERGEFORMAT = - \* MERGEFORMAT ；</p><p>　　\* MERGEFORMAT 進(jìn)行一維搜索，求 \* MERGEFORMAT ，使得</p><p>　　令 \* MERGEFORMAT , \* MERGEFORMAT ，轉(zhuǎn) \

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

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

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

29、</p><p>　　\* MERGEFORMAT :單位方向（一個(gè)向量），即 \* MERGEFORMAT </p><p>　　\* MERGEFORMAT ：步長(zhǎng)（一個(gè)實(shí)數(shù)）.</p><p>　　\* MERGEFORMAT 目標(biāo)函數(shù)在 \* MERGEFORMAT 這一點(diǎn)的梯度（一個(gè)向量）.</p><p>　　\* MERGE

30、FORMAT ： \* MERGEFORMAT 的高階無窮小.</p><p>　　顯然，這個(gè)數(shù)學(xué)表達(dá)式是用泰勒公式展開得到的，對(duì)比自變量為一維的情況下的泰勒展開式:</p><p>　　在目標(biāo)函數(shù)值的數(shù)學(xué)表達(dá)式中，高階無窮小可以忽略，因此，要使該式取到最小值，應(yīng)使 \* MERGEFORMAT 取到最小——這是兩個(gè)向量的點(diǎn)積（數(shù)量積），何種情況下其值最小呢？來看兩向量 \* MER

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

32、MERGEFORMAT 取 \* MERGEFORMAT 時(shí)，目標(biāo)函數(shù)值下降得最快，這就是稱負(fù)梯度方向?yàn)椤白钏傧陆怠狈较虻挠蓙?</p><p>　　2.4 最速下降法的收斂性以及收斂速度</p><p>　　最速下降法的收斂性：對(duì)一般的目標(biāo)函數(shù)是整體收斂的（所謂整體收斂，是指不會(huì)非要在某些點(diǎn)附近的范圍內(nèi)，才會(huì)有好的收斂性）.</p><p>　　最速下降法的收

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

34、3 算法實(shí)現(xiàn)</b></p><p>　　我們通過求解幾個(gè)無約束優(yōu)化例題來驗(yàn)證算法的穩(wěn)定性和準(zhǔn)確性.</p><p>　　例1：求解 \* MERGEFORMAT ，設(shè)初始點(diǎn)為 \* MERGEFORMAT ，求迭代一次后的迭代點(diǎn) \* MERGEFORMAT .</p><p>　　解：因?yàn)?\* 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 給定初始點(diǎn)為 \* MERGEFORMAT .</p><p>　　解：目標(biāo)函數(shù) \* MERGEFORMAT 的梯度為 \* MERGEFORMAT </p><p>　　\* MERGEFORMAT ,令搜索方向 \* MERG

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

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

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

40、 \* MERGEFORMAT = \* MERGEFORMAT ，終止誤差 \* MERGEFORMAT </p><p>　　解：目標(biāo)函數(shù)的梯度為</p><p>　　因?yàn)?\* MERGEFORMAT = \* MERGEFORMAT 則有</p><p>　　\* MERGEFORMAT 求單變量極小化問題：</p><p>

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

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

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

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

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

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

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

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

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

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

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

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

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