共軛梯度算法分析與實(shí)現(xiàn)

PAGE編號:_09《最優(yōu)化方法》課程設(shè)計(jì)題目：共軛梯度算法分析與實(shí)現(xiàn)院系：數(shù)學(xué)與計(jì)算科學(xué)學(xué)院專業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)姓名學(xué)號：指導(dǎo)教師：日期：2013年12月23日摘要在最優(yōu)化計(jì)算中，共軛梯度法是非常重要的一種方法。共軛梯度法是一種改進(jìn)的最速下降法，介于最速下降法與牛頓法之間的一種無約束優(yōu)化算法,是為求解目標(biāo)函數(shù)為二次函數(shù)的問題而設(shè)計(jì)的一類算法。它利用目標(biāo)函數(shù)的梯度逐步產(chǎn)生共軛方向并將其作為搜索方向的方法，收斂速度快。共軛梯度法僅需利用一階導(dǎo)數(shù)信息，避免了牛頓法需要存儲和計(jì)算Hesse矩陣并求逆的缺點(diǎn)，具有二次終止性。關(guān)鍵詞：共軛梯度法；牛頓法；二次函數(shù)；無約束優(yōu)化AbstractInthecalculationofoptimizationmethod,conjugategradientmethodisaveryimportantone.TheconjugategradientmethodisaunconstrainedoptimizationmethodbetweenthesteepestdescentmethodandNewtonmethod,andsovetheobjectivefunctionfortheoriginalquadraticfunctionproblemsanddesignforaclassofalgorithm.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,thismethodhasthequadratictermination.Keywords:Conjugategradientmethod;Newtonmethod;Unconstrainedoptimization目錄1、引言 12、共軛梯度算法的描述 12.1無約束優(yōu)化問題概述 12.2共軛方向 12.3共軛梯度法 2HYPERLINK3.1代碼實(shí)現(xiàn) 2HYPERLINK3.2算法測試 3HYPERLINK4、算法比較 54.1最速下降法描述 64.1.1最速下降方向 64.1.2最速下降法 6HYPERLINK4.2最速下降法實(shí)現(xiàn) 6HYPERLINK5、總結(jié) 8HYPERLINK\l"_5.1_總結(jié)概括"5.1總結(jié)概括 8HYPERLINK\l"_5.3_個人感言"5.2個人感言 9HYPERLINK\l"_6、參考文獻(xiàn)："6、參考文獻(xiàn)： 9最優(yōu)化方法課程設(shè)計(jì)PAGEPAGE101、引言共軛梯度法最早是由Hesternes和Stiefle(1952)提出來的，用于解正定系數(shù)矩陣的線性方程組，在這個基礎(chǔ)上，F(xiàn)letcher和Reeves(1964)首先提出了解非線性最優(yōu)化問題的共軛梯度法。在各種優(yōu)化算法中，共軛梯度法（ConjugateGradient）是非常重要的一種。是一種介于最速下降法與牛頓法之間的優(yōu)化算法，是為求解目標(biāo)函數(shù)為二次函數(shù)的問題而設(shè)計(jì)的一類算法。它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點(diǎn)，又避免了牛頓法需要存儲和計(jì)算Hesse矩陣并求逆的缺點(diǎn)，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一?？晌⒌姆嵌魏瘮?shù)在極小點(diǎn)附近的形態(tài)近似于二次函數(shù)，因此共軛梯度法也能用于求可微的非二次函數(shù)的無約束極小問題。共軛梯度法是一個典型的共軛方向法，它在共軛方向法基礎(chǔ)上增加了一些性質(zhì):計(jì)算當(dāng)前方向計(jì)算當(dāng)前方向只需用到前一方向，對其他方向則無要求；計(jì)算出來的當(dāng)前方向自動與前面所有方向共軛，因此，不需耗費(fèi)大量內(nèi)存存儲所有方向，也節(jié)省了計(jì)算時間。2、共軛梯度法的描述2.1無約束優(yōu)化問題概述一個非線性規(guī)劃問題的自變量x沒有任何約束，或說可行域既是整個n維向量空間：，稱這樣的非線性規(guī)劃問題為無約束問題：或2.2共軛方向無約束問題最優(yōu)化方法的核心問題是選擇搜索方向。以正定二次函數(shù)為例，來觀察兩個方向關(guān)于矩陣Ａ共軛的幾何意義。設(shè)有二次函數(shù)：f(x)

=

1/2

(x

-

x*)TA(x

-

x*)

,其中A是n×n對稱正定矩陣，x*是一個定點(diǎn)，函數(shù)f(x)的等值面1/2

(x

-

x*)TA(x

-

x*)

=

c是以x*為中心的橢球面，由于▽f(x*)

=

A(x

-

x*)

=

0，A正定，因此x*是f(x)的極小點(diǎn)。設(shè)x(1)是在某個等值面上的一點(diǎn)，該等值面在點(diǎn)x(1)處的法向量▽f(x(1))

=

A(x(1)

-

x*)。又設(shè)d(1)是這個等值面在d(1)處的一個切向量。記作d(2)

=

x*

-

x(1)。自然，d(1)與▽f(x(1))正交，即d(1)T▽f(x(1))

=

0，因此有d(1)TAd(2)

=

0，即等值面上一點(diǎn)處的切向量與由這一點(diǎn)指向極小點(diǎn)的向量關(guān)于A共軛。2.3共軛梯度法共軛梯度法是最著名的共軛方向法，它首先由Hestenes和Stiefel（1952）提出來作為解線性方程組的方法。由于解線性方程組等價于極小化一個正定二次函數(shù)，故1964年Fletcher和Reeves提出了無約束極小化的共軛梯度法，它是直接從Hestenes和Stiefel解線性方程組的共軛梯度法發(fā)展而來的。共軛梯度法的基本思想是把共軛性與最速下降方法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)。根據(jù)共軛方向的基本性質(zhì)，這種方法具有二次終止性。共軛梯度法就是使得最速下降方向具有共軛性，從而提高算法的有效性和可靠性。在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點(diǎn)是所需存儲量小，具有步收斂性，穩(wěn)定性高，而且不需要任何外來參數(shù)。2.4共軛梯度算法的步驟共軛梯度算法步驟如下：Step1給定迭代精度和初始點(diǎn).計(jì)算.令.Step2若,停算,輸出.Step3計(jì)算搜索方向:其中當(dāng)時,確定.Step4利用精確(或非精確)線搜索方法確定搜索步長.Step5令,并計(jì)算.Step6令,轉(zhuǎn)步Step1.3、數(shù)值實(shí)驗(yàn)3.1代碼實(shí)現(xiàn)共軛梯度法的Matlab程序如下：分別新建Conjugate_Gradient_Method.m、grad_obj.m、line_search.m、obj.m文件Conjugate_Gradient_Method.m文件如下：function[x,iter,val]=Conjugate_Gradient_Method(x,eps)k=0;x_mat(:,1)=x;%存儲每一次迭代得到的點(diǎn)xx_old=x;dy_old=grad_obj(x_old);d_old=-dy_old;whilenorm(dy_old)>epslambda=line_search(x_old,d_old);%步長x_new=x_old+lambda*d_old;dy_new=grad_obj(x_new);coef=norm(dy_new)/norm(dy_old);d_new=-dy_new+coef^2*d_old;%搜索方向k=k+1;x_old=x_new;dy_old=dy_new;d_old=d_new;x_mat(:,k)=x_new;%防止死循環(huán)ifk>100break;endendx=x_new;%目標(biāo)函數(shù)極值點(diǎn)iter=k;%迭代次數(shù)val=obj(x_new);%目標(biāo)函數(shù)在極值點(diǎn)處的函數(shù)值endline_search.m文件如下：functionlambda=line_search(xk,dk)%作線搜索，求步長%phi(lambda)=obj(xk+lambda*dk)%d_phi(lambda)=dk'*grad_obj(xk+lambda*dk)symseqnlambdaeqn=dk'*grad_obj(xk+lambda*dk);lambda=solve(eqn);%用符號計(jì)算命令solve求方程d_phi(\lambda)=0的根lambda=eval(lambda);%將符號計(jì)算的結(jié)果轉(zhuǎn)化為數(shù)值類型end3.2算法測試我們通過求解兩個無約束優(yōu)化問題來驗(yàn)證算法的穩(wěn)定性和準(zhǔn)確性。問題一：求解無約束優(yōu)化問題，該問題的有精確解。問題二：找出如下方程的極小值點(diǎn)：其中初始點(diǎn)為obj.m文件functiony=obj(x)%目標(biāo)函數(shù)y=3*x(1).^2/2+x(2).^2/2-x(1).*x(2)-2*x(1);%問題一目標(biāo)函數(shù)%y=x(1).^2-2*x(1).*x(2)+4*x(2).^2+x(1)-3*x(2);%問題二目標(biāo)函數(shù)endgrad_obj.m文件如下functiondy=grad_obj(x)%目標(biāo)函數(shù)的梯度dy=[3*x(1)-x(2)-2;x(2)-x(1)];%問題一目標(biāo)函數(shù)的梯度%dy=[2*x(1)-2*x(2)+1;-2*x(1)+8*x(2)-3];%問題二目標(biāo)函數(shù)的梯度end結(jié)果如下：問題一：問題二:3.3結(jié)果分析共軛梯度法是一種很有效求解無約束優(yōu)化的方法，共軛梯度法是根據(jù)共軛方向去搜索，可以由較快的收斂速度找到最優(yōu)解求得極小值，并且計(jì)算結(jié)果比較穩(wěn)定，誤差在忽略范圍內(nèi)。4、算法比較4.1最速下降法的描述4.1.1最速下降方向函數(shù)f(x)在點(diǎn)x處沿方向d的變化率可用方向?qū)?shù)來表示。對于可微函數(shù)，方向?qū)?shù)等于梯度與方向的內(nèi)積，即：Df(x;d)

=

▽f(x)Td,因此，求函數(shù)f(x)在點(diǎn)x處的下降最快的方向，可歸結(jié)為求解下列非線性規(guī)劃：min

▽f(x)Tds.t.

||d||

≤

1當(dāng)

d

=

-▽f(x)

/

||▽f(x)||

時等號成立。因此，在點(diǎn)x處沿上式所定義的方向變化率最小，即負(fù)梯度方向?yàn)樽钏傧陆捣较颉?.1.2最速下降法最速下降法又稱為梯度法，是1847年由著名數(shù)學(xué)家Cauchy給出的，它是解析法中最古老的一種，其他解析方法或是它的變形，或是受它的啟發(fā)而得到的，因此它是最優(yōu)化方法的基礎(chǔ)。作為一種基本的算法，他在最優(yōu)化方法中占有重要地位。其優(yōu)點(diǎn)是工作量少，存儲變量較少，初始點(diǎn)要求不高；缺點(diǎn)是收斂慢，效率不高，有時達(dá)不到最優(yōu)解。非線性規(guī)劃研究的對象是非線性函數(shù)的數(shù)值最優(yōu)化問題。它的理論和方法滲透到許多方面，特別是在軍事、經(jīng)濟(jì)、管理、生產(chǎn)過程自動化、工程設(shè)計(jì)和產(chǎn)品優(yōu)化設(shè)計(jì)等方面都有著重要的應(yīng)用。而最速下降法正是n元函數(shù)的無約束非線性規(guī)劃問題minf(x)的一種重要解析法，研究最速下降法原理及其算法實(shí)現(xiàn)對我們有著極其重要的意義。4.2最速下降法的步驟最速下降法的迭代公式是x(k+1)

=

x(k)

+

λkd(k)

,其中d(k)是從x(k)出發(fā)的搜索方向，這里取在x(k)處的最速下降方向，即d

=

-▽f(x(k)).λk是從x(k)出發(fā)沿方向d(k)進(jìn)行一維搜索的步長，即λk滿足f(x(k)

+

λkd(k))

=

min

f(x(k)+λd(k))

(λ≥0).算法步驟如下：Step1:：給出初始點(diǎn)，和精度；Step2：計(jì)算，如果，則停止迭代，輸出結(jié)果；否則轉(zhuǎn)step3；Step3：令下降方向，計(jì)算步長因子使得，令，轉(zhuǎn)step2。4.3最少下降法實(shí)現(xiàn)最速下降法的Matlab程序如下：新建Steepest_Descent_Method.m文件，并復(fù)用grad_obj.m、line_search.m、obj.m文件Steepest_Descent_Method.m文件如下：4.4最速下降法算法測試使用此最速下降法算法求解此前的問題一和問題二，取不同的起始點(diǎn)的數(shù)值結(jié)果分別如下：問題一：問題二:4.5共軛梯度法與最速下降法比較通過分別用兩種算法求解問題一和問題二所得的結(jié)果可以看出，共軛梯度法的收斂速度是比較最速下降快，在相同初始點(diǎn)處開始求解，使用共軛梯度法所需要的迭代次數(shù)比最速下降法的迭代次數(shù)的少得很多，并且也比最速下降法穩(wěn)定得多。雖然在算法設(shè)計(jì)上比較相似，但是微小的改進(jìn)，使得共軛梯度法無論是準(zhǔn)確性上還是效率上都優(yōu)于牛頓法。5、總結(jié)5.1總結(jié)概括最優(yōu)化理論研究在如今的研究領(lǐng)域發(fā)展得如火如荼，共軛梯度法是一種很有效求解無約束優(yōu)化的方法，共軛梯度法是根據(jù)共軛方向搜索，可以由較快的收斂速度找到最優(yōu)解。該算法最早是由Hesternes和Stiefle(1952)提出來的，用于解正定系數(shù)矩陣的線性方程組，在這個基礎(chǔ)上，F(xiàn)letcher和Reeves(1964)首先提出了解非線性最優(yōu)化問題的共軛梯度法。當(dāng)然該算法發(fā)展到現(xiàn)在已經(jīng)發(fā)展出了FR,PR,HS,CD,DY等算法，在搜索方法上有