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

PAGE《最優(yōu)化方法》課程設(shè)計題目：共軛梯度法算法分析與實現(xiàn)院系：數(shù)學(xué)與計算科學(xué)學(xué)院專業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)姓名：梁婷艷學(xué)號：0800730103指導(dǎo)教師：李豐兵日期：2015年12月30日摘要在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。本文主要介紹的共軛梯度法是介于最速下降法與牛頓法之間的一種無約束優(yōu)化算法，它具有超線性收斂速度,而且算法結(jié)構(gòu)簡單,容易編程實現(xiàn)。在本次實驗中,我們首先分析共軛方向法、對該算法進行分析，運用基于共軛方向的一種算法—共軛梯度法進行無約束優(yōu)化問題的求解。無約束最優(yōu)化方法的核心問題是選擇搜索方向。共軛梯度法的基本思想是把共軛性與最速下降方法相結(jié)合，利用已知點處的梯度構(gòu)造一組共軛方向，并沿這組方向進行搜索，求出目標(biāo)函數(shù)的極小點。根據(jù)共軛方向的基本性質(zhì)，這種方法具有二次終止性。再結(jié)合該算法編寫matlab程序，求解無約束優(yōu)化問題，再結(jié)合牛頓算法的理論知識，編寫matlab程序，求解相同的無約束優(yōu)化問題，進行比較分析，得出共軛梯度法和牛頓法的不同之處以及共軛梯度法的優(yōu)缺點。共軛梯度法僅需利用一階導(dǎo)數(shù)信息，避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便。關(guān)鍵詞：共軛梯度法；超線性收斂；牛頓法；無約束優(yōu)化AbstractInavarietyofoptimizationalgorithms,conjugategradientmethodisaveryimportantone.Inthispaper,theconjugategradientmethodisbetweenthesteepestdescentmethodandNewtonmethodforunconstrainedoptimizationbetweenamethod,ithassuperlinearconvergencerate,andthealgorithmissimpleandeasyprogramming.Inthisexperiment,wefirstanalyzetheconjugatedirectionmethod,thealgorithmanalysis,theuseofaconjugatedirection-basedalgorithm-conjugategradientmethodforunconstrainedoptimizationproblems.Unconstrainedoptimizationmethodistoselectthecoreissueofthesearchdirection.Conjugategradientmethodisthebasicideaoftheconjugatedescentmethodwiththemostcombinedpointsinthegradientusingtheknownstructureofasetofconjugatedirections,andsearchalongthedirectionofthisgroup,findtheminimumpointofobjectivefunction.Accordingtothebasicnatureoftheconjugatedirection,thismethodhasthequadratictermination.Combinedwiththepreparationofthisalgorithmmatlabprogramforsolvingunconstrainedoptimizationproblems,combinedwithNewton’stheoryofknowledge,writingmatlabprogramtosolvethesameproblemofunconstrainedoptimization,comparisonanalysis,theconjugategradientmethodandNewtonmethoddifferentOfficeandtheadvantagesanddisadvantagesoftheconjugategradientmethod.Conjugategradientmethodusingonlyfirstderivativeinformation,toavoidtheNewtonmethodrequiresstorageandcomputingtheinverseHessematrixandshortcomings,isnotonlytheconjugategradientmethodtosolvelargelinearsystemsoneofthemostuseful,butalsolarge-scalesolutionnonlinearoptimizationalgorithmisoneofthemosteffective.Conjugategradientmethodisatypicalconjugatedirectionmethod,eachofitssearchdirectionisconjugatetoeachother,andthesearchdirectiondisjustthenegativegradientdirectionwiththelastiterationofthesearchdirectionoftheportfolio,therefore,storagelesscomputationalcomplexity.Keywords:Conjugategradientmethod;Superlinearconvergence;NewtonmethodUnconstrainedoptimization目錄1、引言 12、共軛梯度法的描述 12.1共軛方向法 12.2共軛梯度法 2HYPERLINK3.1代碼實現(xiàn) 7HYPERLINK3.2算法測試 8HYPERLINK4、算法比較 104.1牛頓法的構(gòu)造 10HYPERLINK4.2算法實現(xiàn) 11HYPERLINK5、總結(jié) 13HYPERLINK\l"_5.1_總結(jié)概括"5.1總結(jié)概括 13HYPERLINK\l"_5.3_個人感言"5.2個人感言 14HYPERLINK\l"_6、參考文獻："6、參考文獻： 16最優(yōu)化方法課程設(shè)計PAGE181、引言在各種優(yōu)化算法中，共軛梯度法（ConjugateGradient）是非常重要的一種。其優(yōu)點是所需存儲量小，具有N步收斂性，穩(wěn)定性高，而且不需要任何外來參數(shù)。共軛梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算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、共軛梯度法的描述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步精確線性搜索終止；且每一都是在和方向所張成的線性流行中的極小點。2.2共軛梯度法共軛梯度法是最著名的共軛方向法，它首先由Hestenes和Stiefel（1952）提出來作為解線性方程組的方法。由于解線性方程組等價于極小化一個正定二次函數(shù)，故1964年Fletcher和Reeves提出了無約束極小化的共軛梯度法，它是直接從Hestenes和Stiefel解線性方程組的共軛梯度法發(fā)展而來的。共軛方向法基本定理告訴我們，共軛性和精確線性搜索產(chǎn)生二次終止性。共軛梯度法就是使得最速下降方向具有共軛性，從而提高算法的有效性和可靠性。下面針對二次函數(shù)情形討論共軛梯度法，我們先給出共軛梯度法的推導(dǎo)。設(shè)(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)因此，共軛梯度法的公式為,(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若,停算,輸出.步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. 下面用反證法證明.如果不然，即，則對于充分小，有.注意到，對任意的，有.對于，令對上式去極限得，這與(2.2.23)若在算法2.2.1中采用非精度搜索確定的補步長因子，比如Wolfe準(zhǔn)則和Armijo準(zhǔn)則，則利用一般下降類算法的全局收斂性定理，可得到非精確搜索下的共軛梯度算法的收斂性定理。定理2.2.4設(shè)是由算法2.2.1利用Wolfe準(zhǔn)則產(chǎn)生的序列，假定函數(shù)一階連續(xù)可微且有下界，其梯度函數(shù)在上Lipschitz連續(xù)，即存在常數(shù)，使得,.若選取的搜索方向與的夾角滿足條件,.那么算法2.2.1或者有限步終止，或者。證:不失一般性,不妨假設(shè)是無窮序列.由Lipschitz及連續(xù)條件和Wolfe準(zhǔn)則得,即.于是利用上式及Wolfe準(zhǔn)則可得.注意到是有下界的,由上式不難推得,這蘊含了當(dāng)時,有.證畢.2.3Armijo準(zhǔn)則Armijo準(zhǔn)則是指:給定,令步長因子.其中是滿足下列不等式的最小非負整數(shù):(2.3.1)可以證明,若是連續(xù)可微的且滿足,則Armijo準(zhǔn)則是有限終止的,即存在正數(shù),使得對于充分大的正整數(shù),(2.3.1)式成立.也就是說，目標(biāo)函數(shù)的下降要與步長和下降方向成一定的比例。為了程序?qū)崿F(xiàn)的方便,我們將Armijo準(zhǔn)則寫成下列詳細的算法步驟。算法2.3.1步0給定.令.步1若不等式成立，置，停算，否則，轉(zhuǎn)步2.步2令，轉(zhuǎn)步1.3、數(shù)值實驗3.1代碼實現(xiàn)在共軛梯度法的實際使用中，通常在迭代步或步之后，重新取負梯度方向作為搜索方向，我們稱之為再開始共軛梯度法。這是因為對于一般非二次函數(shù)而言，步迭代后共軛梯度法產(chǎn)生的搜索方向往往不再具有共軛性。而對于大規(guī)模問題，常常每(或)步就進行再開始。此外，當(dāng)搜索方向不是下降方向時，也插入負梯度方向作為搜索方向。基于Armijo非精確線性搜索的再開始FR共軛梯度法的Matlab程序如下：(分別新建frcg.M,fun.M,gfun.M三個M文件)function[x,val,k]=frcg(fun,gfun,x0)%功能:用FR共軛梯度法求解無約束問題:minf(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;elsebeta=(g'*g)/(g0'*g0);d=-g+beta*d0;gd=g'*d;if(gd>=0.0)d=-g;endendif(norm(g)<epsilon),break;end%檢驗終止條件m=0;mk=0;while(m<20)%Armijo搜索if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d)mk=m;break;endm=m+1;endx0=x0+rho^mk*d;val=feval(fun,x0);g0=g;d0=d;k=k+1;endx=x0;val=feval(fun,x);3.2算法測試我們通過求解兩個無約束優(yōu)化問題來驗證算法的穩(wěn)定性和準(zhǔn)確性。問題一：求解無約束優(yōu)化問題，該問題的有精確解。問題二：求解無約束優(yōu)化問題，該問題的有精確解。解：利用程序3.1求解以上兩個問題，終止準(zhǔn)則為，分別修改目標(biāo)函數(shù)和梯度如下：fun.M文件functionf=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文件functiongf=gfun(x)%目標(biāo)函數(shù)的梯度函數(shù)gf=[3*x(1)-x(2)-2,x(2)-x(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-0073.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)牛頓法的迭代公式.設(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(fun,gfun,x0)%功能:用最速下降法求解無約束問題:minf(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;endm=0;mk=0;while(m<20)%Armijo搜索if(feral(fun,x0+rho^m*d)<feral(fun,x0)+sigma*rho^m*g'*d)mk=m;break;endm=m+1;endx0=x0+rho^mk*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)解（）382.8220e-009281.4429e-011371.3597e-009392.1601e-009371.4698e-0094.4算法比較通過求解問題一和問題二，由上表可以看出,共軛梯度法的收斂速度是比較令人滿意的，在相同初始點處開始求解，使用牛頓法所需要的迭代次數(shù)共軛梯度法的迭代次數(shù)的兩倍。雖然在算法設(shè)計上比較相似，但是微小的改進，使得共軛梯度法無論是準(zhǔn)確性上還是效率上都優(yōu)于牛頓法。5、總結(jié)5.1總結(jié)概括求解最優(yōu)問題是一個艱難而具有挑戰(zhàn)性的