最優(yōu)化方法課程設(shè)計(jì)參考模版

1、最最最最 優(yōu)優(yōu)優(yōu)優(yōu) 化化化化 方方方方 法法法法 課課課課 程程程程 設(shè)設(shè)設(shè)設(shè) 計(jì)計(jì)計(jì)計(jì) 題 目： 共軛梯度法算法分析與實(shí)現(xiàn) 院 系： 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院 專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué) 姓 名： 梁婷艷 學(xué) 號(hào)： 指導(dǎo)教師： 李豐兵 日 期： 2015 年 12 月 30 日 摘摘 要要 在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。本文主要介紹的共軛 梯度法是介于最速下降法與牛頓法之間的一種無(wú)約束優(yōu)化算法，它具有超線性 收斂速度, 而且算法結(jié)構(gòu)簡(jiǎn)單, 容易編程實(shí)現(xiàn)。 在本次實(shí)驗(yàn)中,我們首先分析共軛方向法、對(duì)該算法進(jìn)行分析，運(yùn)用基于共 軛方向的一種算法共軛梯度法進(jìn)行無(wú)約束優(yōu)化問(wèn)題的求解。無(wú)約束最優(yōu)

2、化方 法的核心問(wèn)題是選擇搜索方向。共軛梯度法的基本思想是把共軛性與最速下降 方法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜索， 求出目標(biāo)函數(shù)的極小點(diǎn)。根據(jù)共軛方向的基本性質(zhì)，這種方法具有二次終止性。 再結(jié)合該算法編寫(xiě) matlab 程序，求解無(wú)約束優(yōu)化問(wèn)題，再結(jié)合牛頓算法的理論 知識(shí)，編寫(xiě) matlab 程序，求解相同的無(wú)約束優(yōu)化問(wèn)題，進(jìn)行比較分析，得出共 軛梯度法和牛頓法的不同之處以及共軛梯度法 的優(yōu)缺點(diǎn)。 共軛梯度法僅需利用一階導(dǎo)數(shù)信息，避免了牛頓法需要存儲(chǔ)和計(jì)算 Hesse 矩陣并求逆的缺點(diǎn)，共軛梯度法不僅是解決大型線性方程組最有用的 方法之一，也是解大型非線性最優(yōu)化

3、最有效的算法之一。共軛梯度法是一個(gè) 典型的共軛方向法，它的每一個(gè)搜索方向是互相共軛的，而這些搜索方向僅 僅是負(fù)梯度方向與上一次迭代的搜索方向的組合，因此，存儲(chǔ)量少，計(jì)算方 便。 關(guān)鍵詞關(guān)鍵詞：共軛梯度法；超線性收斂；牛頓法；無(wú)約束優(yōu)化 Abstract In a variety of optimization algorithms, conjugate gradient method is a very important one. In this paper, the conjugate gradient method is between the steepest descent meth

4、od and Newton method for unconstrained optimization between a method, it has superlinear convergence rate, and the algorithm is simple and easy programming. In this experiment, we first analyze the conjugate direction method, the algorithm analysis, the use of a conjugate direction-based algorithm -

5、 conjugate gradient method for unconstrained optimization problems. Unconstrained optimization method is to select the core issue of the search direction. Conjugate gradient method is the basic idea of the conjugate descent method with the most combined points in the gradient using the known structu

6、re of a set of conjugate directions, and search along the direction of this group, find the minimum point of objective function. According to the basic nature of the conjugate direction, this method has the quadratic termination. Combined with the preparation of this algorithm matlab program for sol

7、ving unconstrained optimization problems, combined with Newtons theory of knowledge, writing matlab program to solve the same problem of unconstrained optimization, comparison analysis, the conjugate gradient method and Newton method different Office and the advantages and disadvantages of the conju

8、gate gradient method. Conjugate gradient method using only first derivative information, to avoid the Newton method requires storage and computing the inverse Hesse matrix and shortcomings, is not only the conjugate gradient method to solve large linear systems one of the most useful, but also large

9、-scale solution nonlinear optimization algorithm is one of the most effective. Conjugate gradient method is a typical conjugate direction method, each of its search direction is conjugate to each other, and the search direction d is just the negative gradient direction with the last iteration of the

10、 search direction of the portfolio, therefore, storage less computational complexity. Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization 目目 錄錄 1、引言引言.1 2、共軛梯度法的描述共軛梯度法的描述.1 2.1 共軛方向法.1 2.2 共軛梯度法.2 2.3 Armijo 準(zhǔn)則.6 3、數(shù)值實(shí)驗(yàn)數(shù)值實(shí)驗(yàn).7 3.1 代碼實(shí)現(xiàn).7 3.2 算法測(cè)試.8

11、 3.3 結(jié)果分析.10 4、算法比較算法比較.10 4.1 牛頓法的構(gòu)造.10 4.2 算法實(shí)現(xiàn).11 4.3 算法測(cè)試.12 4.4 算法比較.13 5、總結(jié)總結(jié).13 5.1 總結(jié)概括.13 5.2 個(gè)人感言.14 6、參考文獻(xiàn)、參考文獻(xiàn)：.16 1 1、引言引言 在各種優(yōu)化算法中，共軛梯度法（Conjugate Gradient）是非常重要的一種。 其優(yōu)點(diǎn)是所需存儲(chǔ)量小，具有 N 步收斂性，穩(wěn)定性高，而且不需要任何外來(lái)參 數(shù)。 共軛梯度法是介于最速下降法與牛頓法之間的一個(gè)方法，它僅需利用一階 導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲(chǔ)和計(jì) 算 Hesse 矩陣并求

12、逆的缺點(diǎn)，共軛梯度法不僅是解決大型線性方程組最有用的 方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。 共軛梯度法最早是又 Hestenes 和 Stiefle（1952）提出來(lái)的，用于解正定 系數(shù)矩陣的線性方程組，在這個(gè)基礎(chǔ)上， Fletcher 和 Reeves（1964）首先提 出了解非線性最優(yōu)化問(wèn)題的共軛梯度法。由于共軛梯度法不需要矩陣存儲(chǔ)， 且有較快的收斂速度和二次終止性等優(yōu)點(diǎn)，現(xiàn)在共軛梯度法已經(jīng)廣泛地應(yīng)用 與實(shí)際問(wèn)題中。 共軛梯度法是一個(gè)典型的共軛方向法，它的每一個(gè)搜索方向是互相共軛的， 而這些搜索方向僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合，因此，存 儲(chǔ)量少，計(jì)算方便。 2

13、 2、共軛梯度法的描述共軛梯度法的描述 2.1 共軛方向法共軛方向法 共軛方向法是介于最速下降法與牛頓法之間的一個(gè)方法。它僅需利用一階 導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了存貯和計(jì)算牛頓法所 需要的二階導(dǎo)數(shù)信息。共軛方向法是從研究二次函數(shù)的極小化產(chǎn)生的，但是它 可以推廣到處理非二次函數(shù)的極小化問(wèn)題。 一般共軛方向法步驟如下： 算法算法 2.1.1 （一般共軛方向法） 給出的初始點(diǎn)， * x 0 x 步 1 計(jì)算)( 00 xfg 步 2 計(jì)算，使 0 d0 00 gd T 步 3 令0k 步 4 計(jì)算和，使得 k 1k x )(min)( kkkkk dxfdxf kkkk dx

14、x 1 步 5 計(jì)算使得,。 1k d0 1 j T k Gddkj, 1 , 0 步 6 令,轉(zhuǎn)步 41 : kk 共軛方向法的一個(gè)基本性質(zhì)是：只要執(zhí)行精確線性搜索，就能得到二次終 止性。這就是下面的共軛方向法基本定理。 定理定理 2.1.1 （共軛方向法基本定理） 對(duì)于正定二次函數(shù)，共軛方向法之多經(jīng) n 步精確線性搜索終止；且每一 都是在和方向所張成的線性流行中 1i x)(xf 0 x i dd, 0 j i j jjd xxx, 0 0 的極小點(diǎn)。 2.2 共軛梯度法共軛梯度法 共軛梯度法是最著名的共軛方向法，它首先由 Hestenes 和 Stiefel（1952） 提出來(lái)作為解線性

15、方程組的方法。由于解線性方程組等價(jià)于極小化一個(gè)正定二 次函數(shù)，故 1964 年 Fletcher 和 Reeves 提出了無(wú)約束極小化的共軛梯度法，它 是直接從 Hestenes 和 Stiefel 解線性方程組的共軛梯度法發(fā)展而來(lái)的。共軛方向 法基本定理告訴我們，共軛性和精確線性搜索產(chǎn)生二次終止性。共軛梯度法就 是使得最速下降方向具有共軛性，從而提高算法的有效性和可靠性。下面針對(duì) 二次函數(shù)情形討論共軛梯度法，我們先給出共軛梯度法的推導(dǎo)。 設(shè) (2.2.1)cxbGxxxf TT 2 1 )( 其中是對(duì)稱正定矩陣，是向量， 是實(shí)數(shù)。的梯度為Gnnb1ncf (2.2.2)bGxxg)( 令 (

16、2.2.3) 00 gd 則 (2.2.4) 0001 dxx 由精確線性搜索性質(zhì)， (2.2.5)0 01 dgT 令 (2.2.6) 0011 dgd 選擇，使得 0 . (2.2.7)0 01 Gdd T 對(duì)（2.2.6）兩邊同乘以，得Gd T 0 . (2.2.8) 00 11 010 011 00 01 1 )( )( gg gg ggd ggg Gdd Gdg T T T T T T 由共軛方向法基本定理，。利用（2.2.3）和（2.2.6） ，可0 2 i Td g1 , 0i 知 , . (2.2.9)0 02 ggT0 12 ggT 又令 , (2.2.10) 110022

17、ddgd 選擇和，使得，。從而有 0 1 0 2 i TGd d1 , 0i ,0 0 . (2.2.11) 11 22 121 122 1 )( )( gg gg ggd ggg T T T T 一般地，在第次迭代，令k , (2.2.12) 1 0 k i iikk dgd 選擇，使得，。也假定 i 0 i T kGd d1, 1 , 0ki , , , (2.2.13)0 i T kd g0 i T kg g1, 1 , 0ki 對(duì)(2.2.12)左乘，則Gd T j 1, 1 , 0kj , . (2.2.14) )( )( 1 1 jj T j jj T k j T j j T k

18、j ggd ggg Gdd Gdg 1, 1 , 0kj 由(2.2.13)， , ,0 1 j T kg g2, 1 , 0kj , ,0 j T kg g1, 1 , 0kj 故得,和0 j 2, 1 , 0kj . (2.2.15) 1111 1 1 )( )( k T k k T k kk T k kk T k k gg gg ggd ggg 因此，共軛梯度法的公式為 , (2.2.16) kkkk dxx 1 其中，在二次函數(shù)情形， . (2.2.17) k T k k T k k Gdd dg 一般地，由精確線性搜索得到，當(dāng)然也可以由非線性搜索得到， k (2.2.18), 11k

19、kkk dgd (Crowder-Wolfe 公式) (2.2.19) )( )( 1 11 kk T k kk T k k ggd ggg .(Fletcher-Reeves 公式) (2.2.20) k T k k T k gg gg 11 另兩個(gè)常用的公式為 , (Polak-Ribiere-Polyak 公式) (2.2.21) k T k kk T k k gg ggg)( 11 .(Dixon 公式) (2.2.22) k T k k T k k gd gg 11 由上面的公式可見(jiàn)，共軛梯度法具有二次終止性（即對(duì)于二次函數(shù)，算法 在有限步終止） ，所以共軛梯度法是一個(gè)很吸引人的方法

20、。 共軛梯度法步驟如下： 算法算法 2.2.1(共軛梯度法) 步 0 給定迭代精度和初始點(diǎn).計(jì)算.令.10 0 x)( 00 xfg0 :k 步 1 若,停算,輸出. k g k xx * 步 2 計(jì)算搜索方向: k d 1, , , 0 , 11 kdg kg d kkk k k 其中當(dāng)時(shí),確定.1k 11 1 k T k k T k k gg gg 1k 步 3 利用精確(或非精確)線搜索方法確定搜索步長(zhǎng). k 步 4 令,并計(jì)算. kkkk dxx : 1 )( 11 kk xfg 步 5 令,轉(zhuǎn)步 1.1 : kk 下面證明算法 2.2.1 的收斂性定理。 定理定理 2.2.3 設(shè)是由

21、算法 2.2.1 產(chǎn)生的序列, 假定函數(shù)一階連續(xù)可 k x)(xf 微且水平集是有界的。那么算法 2.2.1 或者有限步終)()(|)( 00 xfxfxxL 止, 或者。0)(lim k k xg 證：不是一般性，不放假設(shè)是無(wú)窮序列，此時(shí)有，因 k x0)( k xg 故有 11 kkkk dgd ，0| 2 11 2 | kk T kkkk T k gdggdg 即是下降方向，從而由精度線性搜索規(guī)則可知，是單調(diào)下降的，故 k d)( k xf ，于是是有界的，因?yàn)楸赜芯埸c(diǎn)，即存在子列收)( 0 xLxk k x * x: 1 Kkxk 斂到，由的連續(xù)性，有 * xf .)()()( * )

22、1()1( * limlim xfxfxff k Kk k Kk 類似地，也是有界序列，故存在子列收斂到，這里: 11 Kkxk : 21 Kkxk * x 是無(wú)窮子序列，于是可得12KK .)()()( * )2()2( * limlim xfxfxff k Kk k Kk 故有 . (2.2.23) * * )()(fxfxf 下面用反證法證明.如果不然，即，則對(duì)于充分小，0)( * xg0)( * xg0 有 .)()( * xfdxf 注意到，對(duì)任意的，有0 .)()()( 1kkkkkk dxfdxfxf 對(duì)于，令對(duì)上式去極限得12KKkk ，)()()( * * xfdxfxf 這

23、與(2.2.23)式相矛盾，從而證明了. 證畢.0)( * xg 若在算法 2.2.1 中采用非精度搜索確定的補(bǔ)步長(zhǎng)因子，比如 Wolfe 準(zhǔn)則 k 和 Armijo 準(zhǔn)則，則利用一般下降類算法的全局收斂性定理，可得到非精確搜 索下的共軛梯度算法的收斂性定理。 定理定理 2.2.4 設(shè)是由算法 2.2.1 利用 Wolfe 準(zhǔn)則產(chǎn)生的序列，假定函數(shù) k x 一階連續(xù)可微且有下界，其梯度函數(shù)在上 Lipschitz 連續(xù)，即存在)(xf)(xg n R 常數(shù)，使得0L , .vuLvgug)()( n Rvu , 若選取的搜索方向與的夾角滿足條件 k d k g k , . 2 0 k ) 2

24、, 0( 那么算法 2.2.1 或者有限步終止，或者。0)(lim k k xg 證證: 不失一般性,不妨假設(shè)是無(wú)窮序列.由 Lipschitz 及連續(xù)條件和 Wolfe 準(zhǔn)則 k x 得 k T kkkkk T kkk gdgdxgddL)1 ()( , kkk gdcos)1 ( 即 . khkk g L d cos )1 ( 于是利用上式及 Wolfe 準(zhǔn)則可得 )()( kkkk dxfxf kkkkk T kk gdgdcos kk g L 2 2 cos )1 ( . 2 2 sin )1 ( k g L 注意到是有下界的,由上式不難推得)(xf , 0 2 k g 這蘊(yùn)含了當(dāng)時(shí),

25、有.證畢. k0 k g 2.3 Armijo 準(zhǔn)則準(zhǔn)則 Armijo 準(zhǔn)則是指: 給定,令步長(zhǎng)因子. 其中 )5 . 0 , 0(),1 , 0( k m k k m 是滿足下列不等式的最小非負(fù)整數(shù): (2.3.1) k T k m kk m k dxfxfdxf)()()( 可以證明, 若是連續(xù)可微的且滿足, 則 Armijo 準(zhǔn)則是有限終)(xf0)( k T k dxf 止的, 即存在正數(shù), 使得對(duì)于充分大的正整數(shù), (2.3.1) 式成立. 也就是說(shuō)，m 目標(biāo)函數(shù)的下降要與步長(zhǎng)和下降方向成一定的比例。f 為了程序?qū)崿F(xiàn)的方便, 我們將 Armijo 準(zhǔn)則寫(xiě)成下列詳細(xì)的算法步驟。 算法算

26、法 2.3.1 (Armijo 準(zhǔn)則) 步 0 給定.令.)5 . 0 , 0(),1 , 0(0:m 步 1 若不等式 k T k m kk m k dxfxfdxf)()()( 成立，置，停算，否則，轉(zhuǎn)步 2. kkd m kkk xxmm :,: 1 步 2 令，轉(zhuǎn)步 1.1: mmk 3 3、數(shù)值實(shí)驗(yàn)、數(shù)值實(shí)驗(yàn) 3.1 代碼實(shí)現(xiàn)代碼實(shí)現(xiàn) 在共軛梯度法的實(shí)際使用中，通常在迭代步或步之后，重新取負(fù)梯n1n 度方向作為搜索方向，我們稱之為再開(kāi)始共軛梯度法。這是因?yàn)閷?duì)于一般非二 次函數(shù)而言，步迭代后共軛梯度法產(chǎn)生的搜索方向往往不再具有共軛性。而n 對(duì)于大規(guī)模問(wèn)題，常常每 (或) 步就進(jìn)行再開(kāi)始

27、。此外，當(dāng)搜mnm nm 索方向不是下降方向時(shí)，也插入負(fù)梯度方向作為搜索方向。 基于Armijo 非精確線性搜索的再開(kāi)始FR共軛梯度法的Matlab程序如下： (分別新建 frcg.M , fun.M , gfun.M 三個(gè)M文件) function x,val,k=frcg(fun,gfun,x0) % 功能: 用 FR 共軛梯度法求解無(wú)約束問(wèn)題: min f(x) %輸入: x0 是初始點(diǎn), fun, gfun 分別是目標(biāo)函數(shù)和梯度 %輸出: x, val 分別是近似最優(yōu)點(diǎn)和最優(yōu)值, k 是迭代次數(shù). maxk=5000; %最大迭代次數(shù) rho=0.6;sigma=0.4; k=0; e

28、psilon=1e-4; n=length(x0); while(k=0.0) d=-g; end end if(norm(g)epsilon), break; end %檢驗(yàn)終止條件 m=0; mk=0; while(m20) %Armijo 搜索 if(feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; val=feval(fun,x0); g0=g; d0=d; k=k+1; end x=x0; val=feval(fun,x); 3.2 算法測(cè)試算法測(cè)試

29、 我們通過(guò)求解兩個(gè)無(wú)約束優(yōu)化問(wèn)題來(lái)驗(yàn)證算法的穩(wěn)定性和準(zhǔn)確性。 問(wèn)題一： 求解無(wú)約束優(yōu)化問(wèn)題，該問(wèn)題的有精確解 121 2 2 2 1 2 2 1 2 3 )(min 2 xxxxxxf Rx 。1)() 1 , 1 ( * xfx T， 問(wèn)題二： 求解無(wú)約束優(yōu)化問(wèn)題，該問(wèn)題的有精確 2 1 2 2 2 1 ) 1()(100)(min 2 xxxxf Rx 解。0)() 1 , 1 ( * xfx T， 解解： 利用程序 3.1 求解以上兩個(gè)問(wèn)題，終止準(zhǔn)則為，分別修改目 4 0 10)( xf 標(biāo)函數(shù)和梯度如下： fun.Mfun.M 文件文件 function f=fun(x) %目標(biāo)函數(shù)

30、f=(3*x(1)2)/2+x(2)2/2-x(1)*x(2)-2*x(1); %問(wèn)題一函數(shù) %f=100*(x(1)2-x(2)2+(x(1)-1)2; %問(wèn)題二函數(shù) gfun.Mgfun.M 文件文件 function gf=gfun(x) %目標(biāo)函數(shù)的梯度函數(shù) gf=3*x(1)-x(2)-2,x(2)-x(1); %問(wèn)題一梯度函數(shù) %gf=400*x(1)*(x(1)2-x(2)+2*(x(1)-1), -200*(x(1)2-x(2); %問(wèn)題二梯度函數(shù) 分別取不同的起始點(diǎn)的數(shù)值結(jié)果如下表： 表 3.1 問(wèn)題一 FR 共軛梯度法的數(shù)值結(jié)果 初始點(diǎn)() 0 x迭代次數(shù)（）k目標(biāo)函數(shù)值（

31、）)( k xf最優(yōu)解（） k x T )0 , 0(12-1.0000 T )9999. 0 ,0000. 1 ( T )5 . 0 , 5 . 0(11-1.0000 T )9999. 0 ,0000. 1 ( T )5 . 2, 2 . 1 (12-1.0000 T )0001. 1 ,0000. 1 ( T )3, 3( 15-1.0000 T )0000. 1 ,0000. 1 ( T )3 , 3(13-1.0000 T )0001. 1 ,0000. 1 ( 表 3.2 問(wèn)題二 FR 共軛梯度法的數(shù)值結(jié)果 初始點(diǎn)() 0 x迭代次數(shù)（）k目標(biāo)函數(shù)值（）)( k xf最優(yōu)解（） k

32、 x T )0 , 0(281.8462e-007 T )0000. 1 ,0000. 1 ( T )5 . 0 , 5 . 0(131.4796e-007 T )0001. 1 ,0000. 1 ( T )5 . 2, 2 . 1 (153.2749e-007 T )0000. 1 ,0000. 1 ( T )3, 3( 224.0962e-008 T )0000. 1 ,0000. 1 ( T )3 , 3(183.5854e-007 T )0000. 1 ,0000. 1 ( 3.3 結(jié)果分析結(jié)果分析 由表 3.1 和表 3.2 可見(jiàn) FR 共軛梯度法在不同的初始點(diǎn)，求解最優(yōu)解的迭代 次

33、數(shù)有所差異，分析可見(jiàn)，在接近精確解的輸出點(diǎn)處的迭代次數(shù)會(huì)相對(duì)較少。 并且計(jì)算結(jié)果比較穩(wěn)定，誤差在忽略范圍內(nèi)。 4 4、算法比較、算法比較 4.1 牛頓法的構(gòu)造牛頓法的構(gòu)造 牛頓法是一種經(jīng)典的無(wú)約束優(yōu)化算法, 并且因其收斂速度快以及具有自適 應(yīng)性等優(yōu)點(diǎn)而至今仍受到科技工作者的青睞.牛頓法也是求解無(wú)約束優(yōu)化問(wèn)題最 早使用的經(jīng)典算法之一. 其基本思想是用迭代點(diǎn)處的一階導(dǎo)數(shù)(梯度) 和二階 k x 導(dǎo)數(shù)(Hesse 陣) 對(duì)目標(biāo)函數(shù)進(jìn)行二次函數(shù)近似, 然后把二次模型的極小點(diǎn)作為 新的迭代點(diǎn), 并不斷重復(fù)這一過(guò)程, 直至求得滿足精度的近似極小點(diǎn). 下面來(lái)推導(dǎo)牛頓法的迭代公式. 設(shè)的 Hesse 陣連續(xù),

34、 )(xf)()( 2 xfxG 截取其在處的泰勒展開(kāi)式的前三項(xiàng)得 k x ,)()( 2 1 )()( kk T kk T kkk xxGxxxxgfxq 其中,.求二次函數(shù)的穩(wěn)定點(diǎn)，得)( kk xff )( kk xfg)( 2 kk xfG)(xqk .0)()( kkkk xxGgxq 若非奇異，那么解上面的線性方程組即得牛頓法的迭代公式 k G . kkkk gGxx 1 1 在迭代公式中每步迭代需求 Hesse 陣的逆，在實(shí)際計(jì)算中可通過(guò)先解 1 k G 得，然后令來(lái)避免求逆。這樣，可以寫(xiě)出基本牛頓法 kk gdG k d kkk dxx 1 的步驟如下： 算法算法 4.1.1（

35、基本牛頓法） 步 0 給定終止誤差,初始點(diǎn).令.10 n Rx 0 0 :k 步 1 計(jì)算.若,停算，輸出.)( kk xfg k g k xx 步 2 計(jì)算,并求解線性方程組得:)( 2 kk xfG k d . kk gdG 步 3 令,轉(zhuǎn)第一步. kkk dxx 1 1 : kk 牛頓法最突出的優(yōu)點(diǎn)是收斂速度快，具有局部二階收斂性。 4.2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) 根據(jù)牛頓算法，編寫(xiě) matlab 程序，求解無(wú)約束優(yōu)化問(wèn)題，代碼如下： function x,val,k=grad(fun,gfun,x0) % 功能: 用最速下降法求解無(wú)約束問(wèn)題: min f(x) %輸入: x0 是初始點(diǎn), f

36、un, gfun 分別是目標(biāo)函數(shù)和梯度 %輸出: x, val 分別是近似最優(yōu)點(diǎn)和最優(yōu)值, k 是迭代次數(shù). maxk=5000; %最大迭代次數(shù) rho=0.5;sigma=0.4; k=0; epsilon=1e-5; while(kmaxk) g=feral(gfun,x0); %計(jì)算梯度 d=-g; %計(jì)算搜索方向 if(norm(d)epsilon), break; end m=0; mk=0; while(m20) %Armijo 搜索 if(feral(fun,x0+rhom*d)feral(fun,x0)+sigma*rhom*g*d) mk=m; break; end m=m

37、+1; end x0=x0+rhomk*d; k=k+1; end x=x0; val=feral(fun,x0); 4.3 算法測(cè)試算法測(cè)試 使用此牛頓法求解此前的問(wèn)題一和問(wèn)題二，取不同的起始點(diǎn)的數(shù)值結(jié)果分 別如下表： 問(wèn)題一： 表 4.1 問(wèn)題一 牛頓法的數(shù)值結(jié)果 初始點(diǎn)() 0 x迭代次數(shù)（）k目標(biāo)函數(shù)值（）)( k xf最優(yōu)解（） k x T )0 , 0(23-1.0000 T )0000. 1 ,0000. 1 ( T )5 . 0 , 5 . 0(23-1.0000 T )0000. 1 ,0000. 1 ( T )5 . 2, 2 . 1 (25-1.0000 T )0000.

38、 1 ,0000. 1 ( T )3, 3( 37-1.0000 T )0000. 1 ,0000. 1 ( T )3 , 3(25-1.0000 T )0000. 1 ,0000. 1 ( 問(wèn)題二： 表 4.2 問(wèn)題二 牛頓法的數(shù)值結(jié)果 初始點(diǎn)() 0 x迭代次數(shù)（）k目標(biāo)函數(shù)值（）)( k xf最優(yōu)解（） k x T )0 , 0(382.8220e-009 T )0000. 1 ,0000. 1 ( T )5 . 0 , 5 . 0(281.4429e-011 T )0000. 1 ,0000. 1 ( T )5 . 2, 2 . 1 (371.3597e-009 T )0000. 1 ,0000. 1 ( T )3, 3( 392.1601e-009 T )0000. 1 ,0000. 1 ( T )3 , 3(371.4698e-009 T )0000. 1 ,0000. 1 ( 4.4 算法比較算法比較 通過(guò)求解問(wèn)題