最速下降法原理及其算法實(shí)現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè) 本科畢業(yè)論文（設(shè)計(jì)）模板本科畢業(yè)論文（設(shè)計(jì)）模板 課程論文課程論文論文題目：論文題目：最速下降法原理及其算法實(shí)現(xiàn)最速下降法原理及其算法實(shí)現(xiàn) 課程名稱：課程名稱： 現(xiàn)代信號(hào)處理新方法現(xiàn)代信號(hào)處理新方法 學(xué)學(xué) 院：院： 自動(dòng)化學(xué)院自動(dòng)化學(xué)院 專業(yè)班級(jí)：專業(yè)班級(jí)： 控制科學(xué)與工程控制科學(xué)與工程 1 1 班班 學(xué)學(xué) 號(hào)：號(hào)： 姓姓 名：名： 嚴(yán)春景嚴(yán)春景 任課教師：任課教師： 謝勝利謝勝利 20142014 年年 6 6 月月 2020 日日 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)最速下降法原理及其算法實(shí)現(xiàn)內(nèi) 容 摘 要摘要：基于最速下降法在解決無(wú)約束非

2、線性規(guī)劃問(wèn)題中的重要性，對(duì)其原理與算法予以討論。論文主要是參閱大量數(shù)學(xué)分析和運(yùn)籌學(xué)書籍以及一些學(xué)術(shù)資料，結(jié)合自己在平時(shí)學(xué)習(xí)中掌握的知識(shí)，并在指導(dǎo)老師的建議下，針對(duì)最速下降法的基本思路和原理進(jìn)行研究。關(guān)鍵詞：運(yùn)籌學(xué) 最速下降法 無(wú)約束 梯度法 最優(yōu)解精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)The steepest descent method, principle and its algorithmAbstractBased on the steepest descent method in solving unconstrained nonlinear programming problem

3、, the importance of the principle and the algorithm is discussed. Paper mainly refer to a mathematical analysis and operations research books and some academic material, usually in the study of knowledge and mastery in teachers suggestion, the steepest descent method according to the basic ideas and

4、 principles were studied.Key words：operational research steepest descent method Unconstrained gradient method optimal solution精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)序言最速下降法又稱為梯度法，是 1847 年由著名數(shù)學(xué)家 Cauchy 給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的，因此它是最優(yōu)化方法的基礎(chǔ)。作為一種基本的算法，他在最優(yōu)化方法中占有重要地位。其優(yōu)點(diǎn)是工作量少，存儲(chǔ)變量較少，初始點(diǎn)要求不高；缺點(diǎn)是收斂慢，效率不高，有

5、時(shí)達(dá)不到最優(yōu)解。非線性規(guī)劃研究的對(duì)象是非線性函數(shù)的數(shù)值最優(yōu)化問(wèn)題。它的理論和方法滲透到許多方面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過(guò)程自動(dòng)化、工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)計(jì)等方面都有著重要的應(yīng)用。而最速下降法正是元函數(shù)的無(wú)約束非線性規(guī)劃問(wèn)題的一種重要解析法，研究最速下降法nmin( )f x原理及其算法實(shí)現(xiàn)對(duì)我們有著極其重要的意義。一、最速下降法基本原理(一)無(wú)約束問(wèn)題的最優(yōu)性條件無(wú)約束問(wèn)題的最優(yōu)解所要滿足的必要條件和充分條件是我們?cè)O(shè)計(jì)算法的依據(jù)，為此我們有以下幾個(gè)定理。定理 1 設(shè)在點(diǎn)處可微。若存在，使f:1nRRnxRnpR( )0Tf xp則向量是在點(diǎn)處的下降方向。pfx定理 2 設(shè)在點(diǎn)處可微。若是

6、無(wú)約束問(wèn)題的局部最優(yōu)解，則1:nfRRnxRx()0f x由數(shù)學(xué)分析中我們已經(jīng)知道，使的點(diǎn)為函數(shù)的駐點(diǎn)或平穩(wěn)點(diǎn)。函數(shù)的一個(gè)( )0f xxff駐點(diǎn)可以是極小點(diǎn)；也可以是極大點(diǎn)；甚至也可能既不是極小點(diǎn)也不是極大點(diǎn)，此時(shí)稱它為函數(shù)的鞍點(diǎn)。以上定理告訴我們，是無(wú)約束問(wèn)題的的局部最優(yōu)解的必要條件是：是其目標(biāo)函數(shù)fxx的駐點(diǎn)。f現(xiàn)給出無(wú)約束問(wèn)題局部最優(yōu)解的充分條件。定理 3 設(shè)在點(diǎn)處的 Hesse 矩陣存在。若1:nfRRnxR2()f x，并且正定()0f x2()f x則是無(wú)約束問(wèn)題的嚴(yán)格局部最優(yōu)解。x一般而言，無(wú)約束問(wèn)題的目標(biāo)函數(shù)的駐點(diǎn)不一定是無(wú)約束問(wèn)題的最優(yōu)解。但對(duì)于其目標(biāo)函數(shù)精選優(yōu)質(zhì)文檔-傾情

7、為你奉上專心-專注-專業(yè)是凸函數(shù)的無(wú)約束凸規(guī)劃，下面定理證明了，它的目標(biāo)函數(shù)的駐點(diǎn)就是它的整體最優(yōu)解。定理 4 設(shè)，是上的可微凸函數(shù)。若有1:nfRRnxRfnR()0f x則是無(wú)約束問(wèn)題的整體最優(yōu)解。x(二)最速下降法的基本思想和迭代步驟最速下降法又稱為梯度法，是 1847 年由著名數(shù)學(xué)家 Cauchy 給出的。他是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的，因此它是最優(yōu)化方法的基礎(chǔ)。設(shè)無(wú)約束問(wèn)題中的目標(biāo)函數(shù)一階連續(xù)可微。1:nfRR最速下降法的基本思想是：從當(dāng)前點(diǎn)出發(fā)，取函數(shù)在點(diǎn)處下降最快的方向作為我kx( )f xkx們的搜索方向.由的 Taylor 展式知k

8、p( )f x()()()(kkkkTkkf xf xtpt f xpotp )略去 的高階無(wú)窮小項(xiàng)不計(jì)，可見取時(shí)，函數(shù)值下降得最多。于是，我們可以構(gòu)造tkp ()kf x出最速下降法的迭代步驟。解無(wú)約束問(wèn)題的的最速下降法計(jì)算步驟第 1 步 選取初始點(diǎn)，給定終止誤差，令；0 x0: 0k 第 2 步 計(jì)算，若，停止迭代.輸出.否則進(jìn)行第三步；()kf x(kf x)kx第 3 步 ?。?)kkpf x 第 4 步 進(jìn)行一維搜索，求，使得kt0()min()kkkkktf xt pf xtp令，轉(zhuǎn)第 2 步。1kkkkxxt p:1kk由以上計(jì)算步驟可知，最速下降法迭代終止時(shí)，求得的是目標(biāo)函數(shù)駐

9、點(diǎn)的一個(gè)近似點(diǎn)。確定最優(yōu)步長(zhǎng)的方法如下：kt方法一：采用任一種一維尋優(yōu)法此時(shí)的已成為步長(zhǎng) 的一元函數(shù)，故可用任何一種一維尋優(yōu)法求出，即()kkf xt f x tkt1()()min()kkkkkktf xf xtf xf xt f x 方法二：微分法因?yàn)榫x優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)()( )kktf xt f xt 所以，一些簡(jiǎn)單情況下，可令( )0t以解出近似最優(yōu)步長(zhǎng)的值。kt(三)最速下降法應(yīng)用舉例例 1 給定初始點(diǎn)22121122min( )22f xxxxx xx 1(0,0)TX解：目標(biāo)函數(shù)的梯度( )f x112122( )()142( )122( )()f xxx

10、xf xxxf xx 令搜索方向再?gòu)某霭l(fā)，沿方向作一維尋優(yōu)，(1)1()1f X(1)(1)1()1df X (1)X(1)d令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為，則有1(1)(1)0101Xd 故(1)(1)2221( )()()2()2()2( )f xf Xd 令可得 求出點(diǎn)之后，與1( )220 11(2)(1)(1)1011011XXd (2)X上類似地，進(jìn)行第二次迭代： 令(2)1()1f X(2)(2)1()1df X 令步長(zhǎng)變量為，最優(yōu)步長(zhǎng)為，則有2(2)(2)111111Xd 故(2)(2)2222( )()(1)(1)2(1)2(1)(1)(1)521( )f xf Xd 令可得 2(

11、 )1020 215(3)(2)(2)2110.81111.25XXd 此時(shí)所達(dá)到的精度(3)0.2()0.2f X(3)()0.2828f X本題最優(yōu)解，11.5X()1,25f X 例 2 用最速下降法求解無(wú)約束非線性規(guī)劃問(wèn)題：42112min()(2)(2)f Xxxx其中，要求選取初始點(diǎn)，終止誤差.12( ,)TXx x0(0,3)TX0.1解：因 311212()4(2)2(2), 4(2)Tf Xxxxxx則 0()( 44,24)Tf X 精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)0()50.12f X00()(44, 24)Tpf X 求單變量極小化問(wèn)題：0000min()mi

12、n(44 ,324 )ttf xtpftt420min(442)(926)ttt的最優(yōu)解，由 0.618 法可得，于是0t00.06t 1000(2.70,1.51)TXxt p1()(0.73,1.28)Tf X1()1.47f X令 11()pf X 再求單變量極小化問(wèn)題110min()tf Xtp的最優(yōu)解.略去計(jì)算步驟，由表 1-1 給出計(jì)算結(jié)果.由表 1-1 可以知道，所7()0.09f X以為近似最優(yōu)解，原問(wèn)題的近似最優(yōu)值為.7(2.28,1.15)TX0.007表 1-1迭代次數(shù)kkX()kf X()kf X()kf Xkt1kX0(0.00,3.00)T52.00( 44,24)

13、T50.120.06(2.70,1.51)T1(2.70,1.51)T0.34(0.73,1.28)T1.470.24(2.52,1.20)T2(2.52,1.20)T0.09(0.80, 0.48)T0.930.11(2.43,1.25)T3(2.43,1.25)T0.04(0.18,0.28)T0.330.31(2.37,1.16)T4(2.37,1.16)T0.02(0.30, 0.20)T0.360.12(2.33,1.18)T5(2.33,1.18)T0.01(0.08,0.12)T0.140.36(2.30,1.14)T6(2.30,1.14)T0.009(0.15, 0.08)T

14、0.170.13(2.28,1.15)T7(2.28,1.15)T0.007(0.05,0.08)T0.09例 3用最速下降法求解無(wú)約束問(wèn)題 221212131min( )222f xxxx xx取，。 1(0,0)TX210解：計(jì)算目標(biāo)函數(shù)的梯度和 Hesse 陣，12121232()xxgf Xxxg231()11f XG設(shè)，得到精確一維搜索步長(zhǎng)( )12,Tkdd d( )12(),Tkf Xg g112222121232kg dg dddd d精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)取，則，所以， 1(0,0)TX(1)()2,0Tf X (1)(1)()2,0Tdf X 21221

15、3 23因此 (2)(1)(1)1120,02,0,033TTTXXd再計(jì)算第二輪循環(huán)，表 1-2 列出了各次迭代的計(jì)算結(jié)果。共計(jì)算了 9 個(gè)點(diǎn)，(9)()0.025f X，停止計(jì)算，所以作為問(wèn)題的最優(yōu)解。210(9)0.988,0.988TX表 1-2k( )kX( )()kf X( )()kf X( )kdk1(0.000,0.000)0.000( 2.000,0.000)(2.000,0.000)0.3332(0.667,0.000)0.667(0.000, 0.667)(0.000,0.667)1.0003(0.667,0.667)0.889( 0.667,0.000)(0.667,0

16、.000)0.3334(0.889,0.667)0.963(0.000, 0.222)(0.000,0.222)1.0005(0.889,0.889)0.988( 0.222,0.000)(0.222,0.000)0.3336(0.963,0.889)0.996(0.000, 0.074)(0.000,0.074)1.0007(0.963,0.963)0.999( 0.074,0.000)(0.074,0.000)0.3338(0.988,0.963)1.000(0.000, 0.025)(0.000,0.025)1.0009(0.988,0.988)1.000( 0.025,0.000)(四

17、)最速下降法的缺點(diǎn)由于沿負(fù)梯度方向目標(biāo)函數(shù)的最速下降性，很容易使人們誤認(rèn)為負(fù)梯度方向是最理想的搜索方向，最速下降法是一種理想的極小化方法。必須指出的是，某點(diǎn)的負(fù)梯度方向，通常只是在該店附近才具有這種最速下降的性質(zhì)。在一般情況下，當(dāng)用最速下降法尋找極小點(diǎn)時(shí)，其搜索路徑呈直角鋸齒狀（圖 1-3） ，在開頭幾步，目標(biāo)函數(shù)下降較快；但在接近極小點(diǎn)時(shí)，收斂速度長(zhǎng)久不理想了。特別適當(dāng)目標(biāo)函數(shù)的等值線為比較扁平的橢圓時(shí)，收斂就更慢了。(4)xO(2)x(3)x精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)圖 1-3因此，在實(shí)用中常將最速下降法和其他方法聯(lián)合應(yīng)用，在前期使用最速下降法，而在接近極小點(diǎn)時(shí)，可改用收斂

18、較快的其他方法。二、最速下降法算法實(shí)現(xiàn)(一)最速下降法程序流程圖最速下降法的程序流程圖，如圖 1-4 所示開始給定初始點(diǎn)，0nxE0: 0k 計(jì)算()kkpf x kp求使其滿足k0min()()kkkkkf xpf xp令1kkkkxxp輸出：minkxx結(jié)束是精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)圖 1-4(二)最速下降法程序清單 用 C 語(yǔ)言編寫的最速下降法的程序清單如下。其中 R 是梯度模，P 是梯度方向的的單位向量，h 是步長(zhǎng)，f 是目標(biāo)函數(shù)。#include “math.h”#include “stdio.h”float x10,y10,p10,f,h;int n;vod fu

19、n( )int i;for(i=1,in;i+) xi=yi-h*pi;f=x1*x1+x2*x2-x1*x2-10*x1-4*x2;f=f+60;return;main( )float g10,d10,q,r,e,h1,h2,h3,h4,t,t0,c1,c2,f1,f2,f3,f4,f5,v;int i,k,u;printf(“input n,en”)；scanf(“%d,%f”,&n,&e);x1=0;x2=0;p4: g1=2*x1-x2-10;g2=2*x2-x1-4;q=0;for(i=1;in;i+) q=gi*gi+q;r=sqrt(q);for(i=1;in;i

20、+) yi=xi;pi=gi/r;if(rf2) t=t+t;u=u+1;elset=-t;h3=h1;f3=f1;h1=h2;f1=f2;h2=h3;f2=f3;p1: h3=h2+t; h=h3;fun( ) f3=f;if(f2f3) t=t+t;u=u+1;h1=h2;f1=f2;h2=h3;f2=f3;goto pl; elseif(u0)h4=0.5*(h2+h3);h=h4;fun( );f4=f;if(f4f2) h3=h4;f3=f4;elseh1=h2;f1=f2;h2=h4;f2=f4;c1=（f3-f1）/(h3-h1);c2=(f2-f1)/(h2-h1)-c1)/(h2-h3);if(fabs(c2)e) h1=h2;f1=f2;t0=v*t0;goto p2;elseh4=0.5*(h1+h3-(c1/c2);h=h4;fun( );f4=f;if(f21) f5=1;else f5=f2;if(fabs(f4-f2)/f5)e)for(i=1;if2) h1=h2;f1=f2;else h1=h4;f1=f4;t0=v*t0;goto p2; p3:h0;fun( );printf(“OBJ.FUNC F=%fn”,f);精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)for(i=1;in;i+)printf(“X(%d”,I);pr