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

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

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

3、搜索方向是互相共軛的，而這些搜索方向僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便。關(guān)鍵詞：共軛梯度法；超線性收斂；牛頓法；無約束優(yōu)化 AbstractIn 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 method and Newton method for unconstrained

4、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 - conjugate gradient method for unconstra

5、ined 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 structure of a set of conjugate directions, and

6、 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 solving unconstrained optimization problems

7、, 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 conjugate gradient method.Conjugate gradient

8、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-scale solution nonlinear optimization al

9、gorithm 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 search direction of the portfolio, there

10、fore, storage less computational complexity.Key words: Conjugate gradient method; Superlinear convergence; Newton method Unconstrained optimization目 錄1、引言在各種優(yōu)化算法中，共軛梯度法（Conjugate Gradient）是非常重要的一種。其優(yōu)點是所需存儲量小，具有N步收斂性，穩(wěn)定性高，而且不需要任何外來參數(shù)。共軛梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算

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

12、法的描述2.1 共軛方向法共軛方向法是介于最速下降法與牛頓法之間的一個方法。它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點，又避免了存貯和計算牛頓法所需要的二階導(dǎo)數(shù)信息。共軛方向法是從研究二次函數(shù)的極小化產(chǎn)生的，但是它可以推廣到處理非二次函數(shù)的極小化問題。一般共軛方向法步驟如下：算法 2.1.1 （一般共軛方向法）給出的初始點，步1 計算步2 計算，使步3 令步4 計算和，使得步5 計算使得,。步6 令,轉(zhuǎn)步4共軛方向法的一個基本性質(zhì)是：只要執(zhí)行精確線性搜索，就能得到二次終止性。這就是下面的共軛方向法基本定理。定理 2.1.1 （共軛方向法基本定理）對于正定二次函數(shù)，共軛方向法之多經(jīng)n

13、步精確線性搜索終止；且每一都是在和方向所張成的線性流行中的極小點。2.2 共軛梯度法共軛梯度法是最著名的共軛方向法，它首先由Hestenes和Stiefel（1952）提出來作為解線性方程組的方法。由于解線性方程組等價于極小化一個正定二次函數(shù)，故1964年Fletcher和Reeves提出了無約束極小化的共軛梯度法，它是直接從Hestenes和Stiefel解線性方程組的共軛梯度法發(fā)展而來的。共軛方向法基本定理告訴我們，共軛性和精確線性搜索產(chǎn)生二次終止性。共軛梯度法就是使得最速下降方向具有共軛性，從而提高算法的有效性和可靠性。下面針對二次函數(shù)情形討論共軛梯度法，我們先給出共軛梯度法的推導(dǎo)。設(shè)

14、(2.2.1)其中是對稱正定矩陣，是向量，是實數(shù)。的梯度為 (2.2.2)令 (2.2.3)則 (2.2.4)由精確線性搜索性質(zhì)， (2.2.5)令 (2.2.6)選擇，使得. (2.2.7)對（2.2.6）兩邊同乘以，得. (2.2.8)由共軛方向法基本定理，。利用（2.2.3）和（2.2.6），可知, . (2.2.9)又令, (2.2.10)選擇和，使得，。從而有,. (2.2.11)一般地，在第次迭代，令, (2.2.12)選擇，使得，。也假定, , , (2.2.13)對(2.2.12)左乘，則, . (2.2.14)由(2.2.13)，, , ,故得,和. (2.2.15)因此，共

15、軛梯度法的公式為, (2.2.16)其中，在二次函數(shù)情形，. (2.2.17) 一般地，由精確線性搜索得到，當(dāng)然也可以由非線性搜索得到， (2.2.18) (Crowder-Wolfe公式) (2.2.19).(Fletcher-Reeves公式) (2.2.20)另兩個常用的公式為, (Polak-Ribiere-Polyak公式) (2.2.21).(Dixon公式) (2.2.22)由上面的公式可見，共軛梯度法具有二次終止性（即對于二次函數(shù)，算法在有限步終止），所以共軛梯度法是一個很吸引人的方法。共軛梯度法步驟如下：算法2.2.1(共軛梯度法)步0 給定迭代精度和初始點.計算.令.步1

16、若,停算,輸出.步2 計算搜索方向:其中當(dāng)時,確定.步3 利用精確(或非精確)線搜索方法確定搜索步長.步4 令,并計算.步5 令,轉(zhuǎn)步1.下面證明算法2.2.1的收斂性定理。定理 2.2.3 設(shè)是由算法 2.2.1 產(chǎn)生的序列, 假定函數(shù)一階連續(xù)可微且水平集是有界的。那么算法 2.2.1 或者有限步終止, 或者。證：不是一般性，不放假設(shè)是無窮序列，此時有，因 故有，即是下降方向，從而由精度線性搜索規(guī)則可知，是單調(diào)下降的，故，于是是有界的，因為必有聚點，即存在子列收斂到，由的連續(xù)性，有.類似地，也是有界序列，故存在子列收斂到，這里是無窮子序列，于是可得.故有. (2.2.23)下面用反證法證明.

17、如果不然，即，則對于充分小，有.注意到，對任意的，有.對于，令對上式去極限得，這與(2.2.23)式相矛盾，從而證明了. 證畢. 若在算法2.2.1中采用非精度搜索確定的補步長因子，比如Wolfe準則和Armijo 準則，則利用一般下降類算法的全局收斂性定理，可得到非精確搜索下的共軛梯度算法的收斂性定理。定理 2.2.4 設(shè)是由算法2.2.1利用Wolfe準則產(chǎn)生的序列，假定函數(shù)一階連續(xù)可微且有下界，其梯度函數(shù)在上Lipschitz連續(xù)，即存在常數(shù)，使得, .若選取的搜索方向與的夾角滿足條件, .那么算法2.2.1或者有限步終止，或者。證: 不失一般性,不妨假設(shè)是無窮序列.由Lipschitz

18、及連續(xù)條件和Wolfe準則得 , 即.于是利用上式及Wolfe準則可得 .注意到是有下界的,由上式不難推得,這蘊含了當(dāng)時,有.證畢. 2.3 Armijo 準則Armijo 準則是指: 給定,令步長因子. 其中 是滿足下列不等式的最小非負整數(shù): (2.3.1)可以證明, 若是連續(xù)可微的且滿足, 則Armijo 準則是有限終止的, 即存在正數(shù), 使得對于充分大的正整數(shù), (2.3.1) 式成立. 也就是說，目標(biāo)函數(shù)的下降要與步長和下降方向成一定的比例。為了程序?qū)崿F(xiàn)的方便, 我們將Armijo 準則寫成下列詳細的算法步驟。算法 2.3.1 (Armijo準則)步0 給定.令.步1 若不等式成立，置

19、，停算，否則，轉(zhuǎn)步2.步2 令，轉(zhuǎn)步1.3、數(shù)值實驗3.1 代碼實現(xiàn)在共軛梯度法的實際使用中，通常在迭代步或步之后，重新取負梯度方向作為搜索方向，我們稱之為再開始共軛梯度法。這是因為對于一般非二次函數(shù)而言，步迭代后共軛梯度法產(chǎn)生的搜索方向往往不再具有共軛性。而對于大規(guī)模問題，常常每 (或) 步就進行再開始。此外，當(dāng)搜索方向不是下降方向時，也插入負梯度方向作為搜索方向?；贏rmijo 非精確線性搜索的再開始FR共軛梯度法的Matlab程序如下：(分別新建 frcg.M , fun.M , gfun.M 三個M文件)function x,val,k=frcg(fun,gfun,x0)% 功能:

20、用FR共軛梯度法求解無約束問題: min f(x)%輸入: x0是初始點, fun, gfun分別是目標(biāo)函數(shù)和梯度%輸出: x, val分別是近似最優(yōu)點和最優(yōu)值, k是迭代次數(shù).maxk=5000; %最大迭代次數(shù)rho=0.6;sigma=0.4;k=0; epsilon=1e-4; n=length(x0);while(k<maxk) g=feval(gfun,x0); %計算梯度 itern=k-(n+1)*floor(k/(n+1); itern=itern+1; %計算搜索方向 if(itern=1) d=-g; else beta=(g'*g)/(g0'*g0

21、); d=-g+beta*d0; gd=g'*d; if(gd>=0.0) d=-g; end end if(norm(g)<epsilon), break; end %檢驗終止條件 m=0; mk=0; while(m<20) %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;endx=x0;val=feval(fu

22、n,x);3.2 算法測試我們通過求解兩個無約束優(yōu)化問題來驗證算法的穩(wěn)定性和準確性。問題一：求解無約束優(yōu)化問題，該問題的有精確解。問題二：求解無約束優(yōu)化問題，該問題的有精確解。解：利用程序3.1求解以上兩個問題，終止準則為，分別修改目標(biāo)函數(shù)和梯度如下：fun.M文件function f=fun(x) %目標(biāo)函數(shù)f=(3*x(1)2)/2+x(2)2/2-x(1)*x(2)-2*x(1); %問題一函數(shù)%f=100*(x(1)2-x(2)2+(x(1)-1)2; %問題二函數(shù)gfun.M文件function gf=gfun(x) %目標(biāo)函數(shù)的梯度函數(shù)gf=3*x(1)-x(2)-2,x(2)-x

23、(1)' %問題一梯度函數(shù)%gf=400*x(1)*(x(1)2-x(2)+2*(x(1)-1), -200*(x(1)2-x(2)' %問題二梯度函數(shù)分別取不同的起始點的數(shù)值結(jié)果如下表：表3.1 問題一 FR共軛梯度法的數(shù)值結(jié)果初始點()迭代次數(shù)（）目標(biāo)函數(shù)值（）最優(yōu)解（）12-1.000011-1.000012-1.000015-1.000013-1.0000表3.2 問題二 FR共軛梯度法的數(shù)值結(jié)果初始點()迭代次數(shù)（）目標(biāo)函數(shù)值（）最優(yōu)解（）281.8462e-007131.4796e-007153.2749e-007224.0962e-008183.5854e-007

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

25、代公式. 設(shè)的Hesse 陣連續(xù), 截取其在處的泰勒展開式的前三項得,其中,.求二次函數(shù)的穩(wěn)定點，得.若非奇異，那么解上面的線性方程組即得牛頓法的迭代公式.在迭代公式中每步迭代需求Hesse陣的逆，在實際計算中可通過先解得，然后令來避免求逆。這樣，可以寫出基本牛頓法的步驟如下：算法 4.1.1（基本牛頓法）步0 給定終止誤差,初始點.令.步1 計算.若,停算，輸出.步2 計算,并求解線性方程組得:.步3 令,轉(zhuǎn)第一步.牛頓法最突出的優(yōu)點是收斂速度快，具有局部二階收斂性。4.2 算法實現(xiàn)根據(jù)牛頓算法，編寫matlab程序，求解無約束優(yōu)化問題，代碼如下：function x,val,k=grad(

26、fun,gfun,x0)% 功能: 用最速下降法求解無約束問題: min f(x)%輸入: x0是初始點, fun, gfun分別是目標(biāo)函數(shù)和梯度%輸出: x, val分別是近似最優(yōu)點和最優(yōu)值, k是迭代次數(shù).maxk=5000; %最大迭代次數(shù)rho=0.5;sigma=0.4;k=0; epsilon=1e-5;while(k<maxk) g=feral(gfun,x0); %計算梯度 d=-g; %計算搜索方向 if(norm(d)<epsilon), break; end m=0; mk=0; while(m<20) %Armijo搜索 if(feral(fun,x0

27、+rhom*d)<feral(fun,x0)+sigma*rhom*g'*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; k=k+1;endx=x0;val=feral(fun,x0);4.3算法測試使用此牛頓法求解此前的問題一和問題二，取不同的起始點的數(shù)值結(jié)果分別如下表：問題一：表4.1 問題一 牛頓法的數(shù)值結(jié)果初始點()迭代次數(shù)（）目標(biāo)函數(shù)值（）最優(yōu)解（）23-1.000023-1.000025-1.000037-1.000025-1.0000問題二：表4.2 問題二 牛頓法的數(shù)值結(jié)果初始點()迭代次數(shù)（）目標(biāo)函數(shù)值（）最優(yōu)解（）3

28、82.8220e-009281.4429e-011371.3597e-009392.1601e-009371.4698e-0094.4算法比較通過求解問題一和問題二，由上表可以看出, 共軛梯度法的收斂速度是比較令人滿意的，在相同初始點處開始求解，使用牛頓法所需要的迭代次數(shù)共軛梯度法的迭代次數(shù)的兩倍。雖然在算法設(shè)計上比較相似，但是微小的改進，使得共軛梯度法無論是準確性上還是效率上都優(yōu)于牛頓法。5、總結(jié)5.1 總結(jié)概括求解最優(yōu)問題是一個艱難而具有挑戰(zhàn)性的過程，最優(yōu)化方法是近幾十年形成的一門運用研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)的學(xué)科，它涵蓋了無約束最優(yōu)化問題、凸集與凸函數(shù)、等式約束最優(yōu)化問題和不等式約束最優(yōu)化問題等知識點。本次課程設(shè)計，我們小組成員通過老師的點撥以及激