最優(yōu)化課程設(shè)計--牛頓法與阻尼牛頓法算法分析

1、<p><b>　　《最優(yōu)化》課程設(shè)計</b></p><p>　　題 目：牛頓法與阻尼牛頓法算法分析 </p><p>　　學(xué) 院: 數(shù)學(xué)與計算科學(xué)學(xué)院 </p><p>　　專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué) </p><p><b>　　摘 要<

2、/b></p><p>　　本文基于阻尼牛頓法在解決無約束最優(yōu)化問題中的重要性，對其原理與算法予以討論。論文主要是參閱大量數(shù)學(xué)分析和最優(yōu)化理論方法，還有最優(yōu)化方法課程以及一些學(xué)術(shù)資料，結(jié)合自己在平時學(xué)習(xí)中掌握的知識，并在指導(dǎo)老師的建議下，拓展敘述牛頓法和其改進方法——阻尼牛頓法的優(yōu)缺點，同時針對阻尼牛頓法的基本思路和原理進行研究，其搜索方向為負(fù)梯度方向，改善了牛頓法的缺點，保證了下降方向。</p>

3、;<p>　　關(guān)鍵詞：無約束 牛頓法 下降方向 阻尼牛頓法 最優(yōu)解</p><p><b>　　Abstract</b></p><p>　　This thesis is based on the importance of the damping Newton's method to solve unconstrained optimi

4、zation problems, we give the discussion about its principles and algorithms. We search a large number of mathematical analysis and optimization theory methods, optimization methods courses, as well as some academic infor

5、mation ,and at the same time combined with knowledge we have learning in peacetime and thanks to the instructor's advice, we also give an expanding narrative for the Newton's method</p><p>　　Keywords

6、: unconstrained , Newton's method , descent direction , damping Newton's method ,optimal solution</p><p><b>　　目錄</b></p><p>　　引言——————————————————————————4</p>&l

7、t;p><b>　　2. 基本原理</b></p><p>　　2.1無約束問題的最優(yōu)性條件——————————————5</p><p>　　2.2牛頓法的基本思想—————————————————6</p><p>　　2.3阻尼牛頓法的基本思想和迭代步驟——————————7</p><p>　　3.阻尼牛頓

8、法與牛頓法的比較 ———————————————8</p><p>　　3.1牛頓法 —————————————————————8</p><p>　　3.2阻尼牛頓法 ———————————————————10</p><p>　　4.算法實現(xiàn) ———————————————————————13</p><p>　　4.1牛頓法C++程

9、序 —————————————————13</p><p>　　4.2阻尼牛頓法Matlab算法 ——————————————14</p><p>　　5.總結(jié)——————————————————————————15</p><p>　　5.1總結(jié)慨括————————————————————15</p><p>　　5.2具體分工及個人感言

10、———————————————16 </p><p>　　6.參考文獻 ———————————————————————21</p><p><b>　　一、引言</b></p><p>　　最優(yōu)化方法是近幾十年形成的，它主要運用數(shù)學(xué)方法研究各種系統(tǒng)各種問題的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。而無約束優(yōu)化問題是最優(yōu)化問題的基礎(chǔ)，是數(shù)值計

11、算領(lǐng)域中十分活躍的研究課題之一。其中非線性無約束最優(yōu)化方法在科學(xué)計算和工程分析中起著越來越重要的作用。對于無約束優(yōu)化問題min f(x) (其中x∈Rn，f:Rn->R是一個連續(xù)可微函數(shù))，牛頓法則是解決最優(yōu)化問題的有效方法之一。然而牛頓法雖具有較好的局部收斂性質(zhì)，但卻存在有一定的局限性的，只在初始點充分接近目標(biāo)函數(shù)極小點時收斂速度才相對較快，對目標(biāo)函數(shù)要求嚴(yán)格，也不能保證下降方向。是以，在解決非線性無約束優(yōu)化問題的過程中，我們改

12、用牛頓法的改進方法——阻尼牛頓法來解決問題。并詳細(xì)分析其過程且對結(jié)果進行討論研究。</p><p><b>　　二、基本原理</b></p><p>　　2.1、無約束問題的最優(yōu)性條件</p><p>　　無約束問題的最優(yōu)解所要滿足的必要條件和充分條件是我們設(shè)計算法的依據(jù)，為此我們有以下幾個定理。</p><p>　　定

13、理1：設(shè)f:Rn→R1在點X*∈Rn處可微。若存在p∈Rn，使?𝑓(𝑥*)𝑇 p < 0,則向量p是f在點X*的下降方向。</p><p>　　定理2：設(shè)設(shè)f:Rn→R1在點X*∈Rn處可微。若X*是無約束問題的局部最優(yōu)解，則?𝑓(𝑥*) =0。</p><p>　　由上課所學(xué)知識我們知道，使?f(x)=

14、0的點x為函數(shù)f的平穩(wěn)點。函數(shù)f的穩(wěn)定點。函數(shù)f的一個穩(wěn)定點可以是極小點，也可以是極大點，甚至兩者都不是。若是最后一種情況，則成它為函數(shù)f的鞍點。以上定理告訴我們，X*是無約束問題的局部最優(yōu)解的必要條件是：X*是目標(biāo)函數(shù)f的穩(wěn)定點?，F(xiàn)給出無約束問題局部最優(yōu)解的充分條件。</p><p>　　定理3：設(shè)f:Rn→R1在點X*∈Rn處的Hesse陣?2𝑓((𝑥*)存在可微。若?

15、9891;(𝑥*) =0，并且?2𝑓((𝑥*)正定，則X*是無約束問題的嚴(yán)格局部最優(yōu)解。</p><p>　　一般而言，無約束問題的目標(biāo)函數(shù)的穩(wěn)定點不一定是無約束問題的最優(yōu)解。但對于其目標(biāo)函數(shù)是凸函數(shù)的無約束凸規(guī)劃，下面定理證明了，它的目標(biāo)函數(shù)的穩(wěn)定點就是它的整體最優(yōu)解。</p><p>　　定理4：設(shè)f:Rn→R1，X*∈Rn，f是Rn上的

16、可微凸函數(shù)。若有?𝑓(𝑥*) =0，則X*無約束問題的整體最優(yōu)解。</p><p>　　2.2．牛頓法的基本思想</p><p>　　牛頓法的基本原理是：原目標(biāo)函數(shù)f(X)用在迭代點X(k)鄰域展開的泰勒二次多項式(X)去近似的代替，再以(X)這個二次函數(shù)的極小點作為原目標(biāo)函數(shù)的下一個迭代點X(k+1），這樣重復(fù)迭代若干次后，使迭代點點列逐步逼近原目標(biāo)函數(shù)f

17、(X)的極小點X*。二次逼近函數(shù)(X)可寫為：</p><p>　　(X)= f(X(k）)+[ ▽f(X(k))]T [X-X(k)]+1/2[X-X(k)]T H(X(k)) [X-X(k)] f(X) (1）式中，▽f(X(k))，H(X(k))分別為原目標(biāo)函數(shù)f(X)在X(k)點的梯度和赫森矩陣。</p><p>　　(X)的極小點可由極值存在的必要條件，令其梯度▽ (X(k))=

18、0來求得，亦即▽ (X(k))= ▽f(X(k))+ H(X(k)) - X(k)</p><p>　　這樣， H(X(k)) - X(k)=- ▽f(X(k))</p><p>　　若H(X(k))為可逆矩陣，將上式等號兩邊左乘以[H(X(k))]-1，則得</p><p>　　X(k) =X(k)- [H(X(k))]-1▽f(X(k))（2）</p>

19、;<p>　　將取作下一個優(yōu)化迭代點X(k+1)，即可得到牛頓法的迭代公式為</p><p>　　X(k+1）=X(k)- [H(X(k))]-1▽f(X(k)) （3）</p><p>　　由上式可知牛頓法的搜索方向為S(k)=- [H(X(k))]-1▽f(X(k)) （4）</p><p>　　這個方向稱牛頓方向。由式(3)還可看到迭代公

20、式中沒有步長因子α(k)，所以牛頓法是一種定步長的搜索迭代。當(dāng)目標(biāo)函數(shù)f(X)是二次函數(shù)時，由于二次泰勒展開函數(shù)(X)與原目標(biāo)函數(shù)f(X)不是近似而是完全相同的二次式，赫森矩陣H(X(k))是一個常數(shù)矩陣，用式(3)牛頓法從任一初始點出發(fā)，只需一步迭代即達f(X)的極小點X*，因此牛頓法也是一種具有二次收斂性的算法。對于非二次函數(shù)，若函數(shù)的二次性態(tài)較強，或迭代點已進入極小點的鄰域，則其收斂速度也是很快的，這是牛頓法的主要優(yōu)點。但牛頓法由

21、于迭代公式中沒有步長因子，而是定步長迭代，對于非二次型目標(biāo)函數(shù)，有時會使函數(shù)值上升，即出現(xiàn)f(X(k+1）) >f(X(k）)的情況，這表明牛頓法不能保證函數(shù)值穩(wěn)定地下降，在嚴(yán)重的情況下甚至可能造成迭代點列的發(fā)散而導(dǎo)致一計算失敗。</p><p>　　2.3．阻尼牛頓法的基本思想</p><p>　　阻尼牛頓法每次迭代方向仍與牛頓法的方向一致，即為負(fù)梯度方向S(k)，但每次迭代需沿此

22、方向作一維搜索，求其最優(yōu)步長因子α(k)。</p><p>　　即： f[X(k)+ α(k)S(k)]= min f[X(k)+ αS(k)],即阻尼牛頓法的迭代公式為X(k+1）=X(k)- α(k) [H(X(k))]-1▽f(X(k)) 。式中α(k)又稱為阻尼因子，是通過沿牛頓方向一維搜索尋優(yōu)而得。當(dāng)目標(biāo)函數(shù)f(X*)的赫森矩陣H(X(k))處處正定時，阻尼牛頓法能保證每次迭代點的函數(shù)值均有所下降，從而

23、保持了二次收斂的特性。迭代步驟如下：</p><p>　　(l)給定初始點X(0) ∈Rn，迭代精度ε，維數(shù)n 。</p><p>　　(2)置0 =>k。</p><p>　　(3)計算迭代點 X(k)的梯度▽f(X(k))和梯度的模|| ▽f(X(k))||。</p><p>　　(4)檢驗是否滿足迭代終止條件|| ▽f(X(k))

24、||< ε?若滿足，停止迭代，輸出最優(yōu)解：(X(k）)=>X*,f(X(k）) => f(X*)。否則進行下一步。</p><p>　　(5)計算X(k）處的赫森矩陣H(X(k))，并求其逆矩陣 [H(X(k))]-1。</p><p>　　(6)確定牛頓方向S(k)=- [H(X(k))]-1▽f(X(k))，從X(k)點出發(fā)，沿S(k)方向進行一維搜索求最優(yōu)步長，使f

25、[X(k)+ α(k)S(k)]= min f[X(k)+ αS(k)]。</p><p>　　(7)計算迭代新點X(k+1）=X(k)+ α(k)S(k) 。</p><p>　　(8)置k+1=> k，返回步驟(3)進行下一次迭代計算。</p><p>　　三、阻尼牛頓法與牛頓法的比較</p><p><b>　　3.1.

26、牛頓法：</b></p><p>　　牛頓法又稱為牛頓-拉弗森方法（Newton-Raphson method），它是一種在實數(shù)域和復(fù)數(shù)域上近似求解方程的方法,是求解無約束最優(yōu)化問題最古老的算法之一。若用牛頓法求某二次目標(biāo)函數(shù)的最優(yōu)解，則構(gòu)造的逼近函數(shù)與原始目標(biāo)函數(shù)是完全相同的二次式，其等值線完全重合，故從任一點出發(fā)，一定可以一次達到目標(biāo)函數(shù)的極小點。</p><p>　　因此

27、，牛頓法是具有二次收斂性的算法。其優(yōu)點是：對于二次正定函數(shù)，迭代一次即可得到最優(yōu)解，對于非二次函數(shù)，若函數(shù)二次性較強或迭代點已經(jīng)進入最優(yōu)點的較小領(lǐng)域，則收斂速度也很快。</p><p>　　牛頓法的算法框圖如圖所示：</p><p>　　例：用牛頓法求函數(shù) 的極小值</p><p>　　解：（1）取初始點 = </p><p><b&

28、gt;　　(2)計算牛頓方向</b></p><p><b>　　= </b></p><p><b>　　H </b></p><p><b>　　= </b></p><p>　　故 =- =- = </p><p>　　(3)極小值 =

29、 = </p><p><b>　　故 </b></p><p>　　上述例子表明，牛頓法具有很好的局部收斂性質(zhì)，對二次函數(shù)來說，進一步就達到優(yōu)化點。但是對一般的函數(shù)來說，在一定的條件下，當(dāng)初始點的選取充分接近目標(biāo)函數(shù)的極小點時，有很快的收斂速度，但若初始點選取離最小點較遠(yuǎn)，就難保證收斂；牛頓法必須求一階、二階導(dǎo)數(shù)及求逆陣，這對比較復(fù)雜的目標(biāo)函數(shù)來說是比較困

30、難的。</p><p>　　牛頓法主要存在以下兩個缺點:</p><p>　　1.對目標(biāo)函數(shù)有較嚴(yán)格的要求。函數(shù)必須具有連續(xù)的一、二階偏導(dǎo)數(shù)，赫森矩陣必須正定且非奇異。</p><p>　　2.計算相當(dāng)復(fù)雜。除需計算梯度而外，還需計算二階偏導(dǎo)數(shù)矩陣和它的逆矩陣。計算量、存儲量均很大，且均以維數(shù)平方比增加，維數(shù)高時這個問題更加突出。</p><p&

31、gt;　　我們知道牛頓法的算法步驟迭代公式中沒有步長因子，是一種定步長的搜索迭代。不能保證函數(shù)值穩(wěn)定地下降，在嚴(yán)重的情況下甚至可能造成迭代點列的發(fā)散而導(dǎo)致計算失敗。為了改正牛頓法的局限性，提出了阻尼牛頓法這一改進方法。</p><p>　　3.2．阻尼牛頓法：</p><p>　　阻尼牛頓法能保證每次迭代點的函數(shù)值均有所下降，從而保持了二次收斂的特性。</p><p&g

32、t;　　阻尼牛頓法的算法框圖如圖所示：</p><p>　　例：用阻尼牛頓法求目標(biāo)函數(shù)的極小點和極小值，已知目標(biāo)函數(shù) ，設(shè)初始點 = ，迭代梯度精度=0.01。</p><p>　　解：（1）目標(biāo)函數(shù)的梯度為 f </p><p><b>　　f </b></p><p>　　(2) H </p&g

33、t;<p><b>　　= </b></p><p>　　(3)牛頓方向 =- =- = </p><p>　　（4）從 出發(fā)經(jīng)行一維搜索</p><p>　　由X= + = ，令 =0 </p><p><b>　　化簡得：</b></p><p>　　解得：

34、 =1 </p><p>　　在進行下一步迭代點 = </p><p>　?。?）計算x(1) 點的梯度及梯度的模，有 檢驗迭代終止條件 =0<0迭代結(jié)束，得極小點 ，</p><p>　　極小值f( )=10.8125</p><p>　　這個例子表明雖然阻尼牛頓法能保證每次迭代點的函數(shù)值均有所下降，從而保持了二次收斂的特

35、性，但是他對目標(biāo)函數(shù)要求高，函數(shù)必須具有連續(xù)的一階、二階偏導(dǎo)數(shù)。同時其Hess陣必須正定且非奇異性。</p><p><b>　　四、算法實現(xiàn)</b></p><p>　　4.1.牛頓法C++算法</p><p><b>　　運行結(jié)果如下：</b></p><p>　　注意：迭代結(jié)果與初始值有關(guān)，迭

36、代的結(jié)果總是初始值x附近。而對于只有1個0點的函數(shù)求解或只有一個極值的函數(shù)求解時，迭代結(jié)果一般與初始值的關(guān)系不大，但迭代次數(shù)會受影響。</p><p>　　4.2.阻尼牛頓法的Matlab算法：</p><p>　　function y=fun (x);</p><p>　　y=100*(x (1)^2-x (2))^2+(x (1)-1)^2;</p>

37、<p>　　function g=gfun (x);</p><p>　　g=[400*(x (1)^2-x (2))*x (1)+2*(x (1)-1),-200*(x (1)^2-x (2))];</p><p>　　function He=Hess (x);</p><p>　　n=length (x);</p><p>

38、　　He=zeros (n,n);</p><p>　　He=[1200*x (1)^2-400*x (2)+2,-400*x (1);-400*x (1),200]; </p><p>　　function[x,val,k]=dampnm (fun,gfun,Hess,x0);</p><p>　　% 功能：用阻尼牛頓法求解無約束優(yōu)化問題：minf (

39、x);</p><p>　　% 輸入：x0是初始點，fun,gfun,Hess分別是目標(biāo)函數(shù)和梯度Hess陣函數(shù)；</p><p>　　% 輸出：x,val分別是近似最優(yōu)解和近似最優(yōu)值，k是迭代次數(shù)；</p><p><b>　　maxk=100;</b></p><p><b>　　rho=0.55;<

40、/b></p><p>　　sigma=0.4;</p><p><b>　　k=0;</b></p><p>　　epsion=le-5;</p><p>　　while (k<maxk)</p><p>　　gk=feval (gfun,x0);</p><p&

41、gt;　　Gk=feval (Hess,x0);</p><p><b>　　dk=Gk\gk;</b></p><p>　　if (norm (dk)<epsion)</p><p><b>　　break;</b></p><p><b>　　end</b></

42、p><p><b>　　m=0;</b></p><p><b>　　mk=0;</b></p><p>　　while (m<20)</p><p>　　if (feval (fun.x0+rho^m*dk)<feval (fun,x0)+sigma*rho^m*gk*dk)</p&

43、gt;<p>　　mk=m;break;</p><p><b>　　end</b></p><p><b>　　m=m+1;</b></p><p><b>　　end</b></p><p>　　x0=x0+rho^mk*dk; k=k+1;</p&

44、gt;<p><b>　　end</b></p><p>　　x=x0;val=feval (fun,x);</p><p>　　輸入：x0=[1,1];</p><p>　　[x,val,k]=dampnm(‘fun’,’gfun’,’Hess’,x0)</p><p><b>　　運行結(jié)果：&

45、lt;/b></p><p><b>　　五、課程設(shè)計總結(jié)</b></p><p><b>　　5.1總結(jié)慨括</b></p><p>　　最優(yōu)化方法是近幾十年形成的，它主要運用數(shù)學(xué)方法研究各種系統(tǒng)各種問題的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。而無約束優(yōu)化問題是最優(yōu)化問題的基礎(chǔ)，是數(shù)值計算領(lǐng)域中十分活躍的研究

46、課題之一。牛頓法則是解決最優(yōu)化問題的有效方法之一，然而牛頓法雖具有較好的局部收斂性質(zhì)，但卻存在有一定的局限性的。而阻尼牛頓法則可以較好地來解決問題。我們通過對這兩種方法的詳細(xì)分析并舉例說明，對結(jié)果進行討論研究，并設(shè)計了相應(yīng)的算法，從而總結(jié)出了他們的優(yōu)缺點。</p><p>　　5.2.具體分工及個人感言</p><p>　　本次課程設(shè)計中，我們小組的主要分工形式為：</p>

47、<p><b>　　個人感言：</b></p><p>　　本次課設(shè)為了更好地了解牛頓法的迭代思想和步驟，進而利用以前學(xué)過的C++知識設(shè)計出牛頓法的C++算法。我查閱了很多資料，并進行整理，總結(jié)出了牛頓法的優(yōu)缺點，和組員一起討論并再根據(jù)迭代步驟畫出了牛頓法的框架圖，再進行舉例說明，最后我根據(jù)這些理論知識設(shè)計出合理的算法，該程序可以輸入不同的初始值從而得到不同的迭代結(jié)果，并對結(jié)果進行

48、分析總結(jié)出：迭代結(jié)果與初始值有關(guān)，迭代的結(jié)果總是初始值x附近。而對于只有1個0點的函數(shù)求解或只有一個極值的函數(shù)求解時，迭代結(jié)果一般與初始值的關(guān)系不大，但迭代次數(shù)會受影響。再者牛頓法迭代沒有步長因子，是一種定步長的搜索迭代。不能保證函數(shù)值穩(wěn)定地下降，在嚴(yán)重的情況下甚至可能造成迭代點列的發(fā)散而導(dǎo)致計算失敗。為了改正牛頓法的局限性，提出了阻尼牛頓法這一改進方法。</p><p>　　通過和組員的分工合作，我們對牛頓法和

49、阻尼牛頓法有了進一步的了解。我在設(shè)計程序的過程中遇到了一些問題，但是最后在組員的討論和百度的幫助下都解決了，相當(dāng)于重新溫習(xí)了一遍C++語言，C++編程語言也可以用來解決一些數(shù)學(xué)問題。</p><p><b>　　六、參考文獻</b></p><p>　　【1】趙瑞安，吳方.《非線性最優(yōu)化理論和方法》.高等教育出版社.1900</p><p>　

50、　【2】薛毅.《最優(yōu)化原理與方法》.北京工業(yè)大學(xué)出版社.2003</p><p>　　【3】朱德通編著.《最優(yōu)化模型與實驗》.同濟大學(xué)出版社.2003</p><p>　　【4】盧險峰.《最優(yōu)化方法應(yīng)用基礎(chǔ)》.同濟大學(xué)出版社.2003</p><p>　　【5】賴炎連，賀國平.《最優(yōu)化方法》.清華大學(xué)出版社.2008</p><p>　　【6

51、】倪勤.《最優(yōu)化方法與程序設(shè)計》.科學(xué)出版社.2009</p><p>　　【7】馬昌鳳.《最優(yōu)化方法及Matlab程序設(shè)計》.科學(xué)出版社.2010</p><p>　　【8】Rafail F.Gabasov and Faina M.Kirillova.《Methods of optimization》.Optimization Softiware,Inc.1998</p>