【正文】 *??(3) (3)[14],[]T Tf????xx??() ?????繼續(xù)探索，當(dāng)探索到點(diǎn) 時(shí)，(7)[.]T，達(dá)到預(yù)定的收斂要求，因而可認(rèn)為 為最(7) ????x *(7)?x優(yōu)點(diǎn)，而 為極小值.??* 26(.6)4(.).510f ????? 最速下降法的 matlab 實(shí)現(xiàn)首先建立 M 文件：function [x,val,k]=grad(fun,gfun,x0)%功能：用最速下降法求解無約束問題： minf（x）%輸入： x0是初始點(diǎn)，fun，gfun分別是目標(biāo)函數(shù)和梯度%輸出： x,val分別是近似最優(yōu)點(diǎn)和最優(yōu)值，k是迭代次數(shù).maxk=5000。 eps=1e7。end m=0。break。endx=x0。求解結(jié)果為 x = 0 0val = 0k = 2 最速下降法的鋸齒現(xiàn)象 最速下降法對(duì)初始點(diǎn)的選擇要求不高，每一輪迭代工作量較少，它可以很，最速下降法卻會(huì)出現(xiàn)鋸齒現(xiàn)象，收斂速度很慢，因?yàn)閷?duì)一般二元函數(shù)，在極小點(diǎn)附近可用極小點(diǎn)的二階泰勒多項(xiàng)式來近似，而后者為凸函數(shù)時(shí)，他的等值線是一族共心橢圓，特別是當(dāng)橢圓比較扁平時(shí)，最速下降法的收斂速度越慢. 至于最速下降法出現(xiàn)鋸齒現(xiàn)象的原因，可以作如下粗略解釋：由在 的泰勒展式：??fX??k ????????==kkkfff??????XXP ??kP為了出從 出發(fā)沿方向 的極小點(diǎn)，令??k??k ??=0,Tkf??????XP’則有安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 15 .????10kkff????X即方向 與方向 正交 .這表明迭代產(chǎn)生的點(diǎn)列??1k??P??=kf??PX所循路徑是 “之” 接近極小點(diǎn) 時(shí)，每次迭代移動(dòng)的步長???X??k*很小，這樣就呈現(xiàn)出鋸齒現(xiàn)象，結(jié)合起來使用. 最速下降法的說明最速下降法的優(yōu)點(diǎn)是算法簡單,每次迭代計(jì)算量小,占用內(nèi)存量小,即使從一個(gè)不好的初始點(diǎn)出發(fā),容易使人們產(chǎn)生一種錯(cuò)覺,認(rèn)為這一定是最理想的搜索方向,沿該方向搜索時(shí)收斂速度應(yīng)該很快,然而事實(shí)證明,梯(面)有狹長深谷形狀的函數(shù),收斂速度更,在遠(yuǎn)離極小點(diǎn)的地方每次迭代可能使目標(biāo)函數(shù)有較大的下降,但是在接近極小點(diǎn)的地方,由于鋸齒現(xiàn)象,從而導(dǎo)致每次迭代行進(jìn)距離縮短,因而收斂速度不快. 牛頓法 牛頓法算法思想與原理如前面所提到的，最速下降法在最初幾步迭代中函數(shù)值下降很快外，總的說來下降的并不快，一種收斂很快的方法，其基本思路是利用二次曲線來逐點(diǎn)近似原目標(biāo)函數(shù)，以二次曲線的極小值點(diǎn)來近似原目標(biāo)函數(shù)的極小值點(diǎn)并逐漸逼近改點(diǎn).一維目標(biāo)函數(shù) 在 點(diǎn)逼近用的二次曲線（即泰勒二次多項(xiàng)式）為()fX()k()()()()()()212kkkkkff?? ??????XX此二次函數(shù)的極小點(diǎn)可由 求得.()0k?對(duì)于 維問題， 為目標(biāo)函數(shù) 在 點(diǎn)逼近用的二次曲線為：nf()k()()()()()2()()1.[][]..[]2kkk kTkkf f????????????XXXX安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 16 令式中的 ，則上式可改寫為：Hesian2()()kkfH??X()()()()()()()1.[][]..[]2kkkkkTkkff H???????????XX當(dāng) 時(shí)可求得二次曲線 的極值點(diǎn)，且當(dāng)且僅當(dāng)改點(diǎn)處的 矩陣()0?X()?esian為正定時(shí)有極小值點(diǎn).由上式得： ()()()()[]kkkfH????XX令 ，則()0???X()()()[]0kf???若 為可逆矩陣，將上式等號(hào)兩邊左乘 ，則得 ()kH1()k?????1()()()[]kknHfI???????XX整理后得 1()()()kkkf??????當(dāng)目標(biāo)函數(shù) 是二次函數(shù)時(shí)，牛頓法變得極為簡單、有效，這時(shí) 是一個(gè)()f ()kHX常數(shù)矩陣，式變成精確()()()()()()()1.[][]..[]2kkkkkTkkff????????????XXX表達(dá)式，而利用式 作一次迭代計(jì)算所得的 就是最優(yōu)點(diǎn)1()()()kkkHf?????? X.在一般情況下 不一定是二次函數(shù)，則不能一步就能求出極小值，即極小值點(diǎn)不*f在 方向上，但由于在 點(diǎn)附近函數(shù) 與 是近似的，所1()()kkH??????X()kX()?f以這個(gè)方向可以作為近似方向，可以用式 求出點(diǎn) 作為1()()()kkH???????X一個(gè)逼近點(diǎn) .這時(shí)式 可改成牛頓法的一般迭代公式：(1)k? 1()()()kkf??????1(1)()()()kkkkf??X式中 稱為牛頓方向，通過這種迭代，逐次向極小值點(diǎn) ()()kHf?????? *X安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 17 牛頓法是基于多元函數(shù)的泰勒展開而來的，它將 作為探索1()()kkHf??????X方向，因此它的迭代公式可直接寫出來： 1(1)()()()kkkkf???????X 牛頓法算法步驟（1） 給定初始點(diǎn) ，及精度 ，令 ；(0)x0??k?（2） 若 ，停止，極小點(diǎn)為 ，否則轉(zhuǎn)步驟（3） ；()kf??X()X（3） 計(jì)算 ，令 ；12()?????1()()()kkkHf??????S（4） 令 ， ，轉(zhuǎn)步驟（2）.(1)()()kk????例 試用牛頓法求目標(biāo)函數(shù) ()046fxx??X解：取 ，則??()0Tk?X112()2022kfxxf?????????????????()21()2()2221kkk XffxHfff????????????????X1(1)()()0082463kkkHf???????????????????即為最小點(diǎn) (1)86k????????X*X 牛頓法的 matlab 實(shí)現(xiàn)首先建立 M 文件 function [x,fval,iterations]=newton(fun,x0,tol)安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 18 %這是一個(gè)用Newton法求解無約束優(yōu)化問題的matlab程序%第一個(gè)參數(shù)fun是一個(gè)包含函數(shù),梯度,hessian矩陣的M文件%比如：% function [f,grad,hessian]=fun_grad_hess(x)% f=x(1)^3+(x(2)1)^2。0 2]。)。 return。while norm(grad)=tol p=inv(H)*grad。endif nargout==3 iterations=count。hessian=[2 1。maxk=150。k=0。^(1+tau)。%解方程組Gk*dk=gk,計(jì)算搜索方向 if(norm(gk)epsilion),break。*dk) mk=m。function He=Hess(x)n=length(x)。然后在工作窗口輸入：x0=[0,0]39。gfun39。 否則轉(zhuǎn)??0f??0f??X0X（3）（3） ,令 ,轉(zhuǎn)(4). 00Pf???k?（4） 使得 ,令 kt????0minkkKttft???P，轉(zhuǎn)（5）1kKkt??X（5） ，若 ，停止迭代輸出 ；否則??1kf??X??1kf???1k?X轉(zhuǎn) （6）（6） ，令 ，轉(zhuǎn)（3） ；否則轉(zhuǎn)（7）n?0=k安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 25 （7） ，令 ， ??21kkf????X??11kkkf??????PXP1k??轉(zhuǎn)（4）例： 用共軛梯度法求 ，其中??21min5fx??????6120,10TTx????X解 ?? 00010024421tf tt??????????????????????????PXP 令 ，則???22min5minttt??????? ??536dtt? f???????????????????X新的搜索方向 ??10. ????????????????1PXP有 ??21 fttt??????????????XXP下一迭代點(diǎn) 21. ????????????????P由于 ??620f????X 停止迭代輸出所求得 ??*20,T?X 共軛梯度法的 matlab 實(shí)現(xiàn)首先建立如下 m 文件：function [x,val,k]=frcg(fun,gfun,x0)%功能：用共軛梯度法求解無約束問題：minf（x）%輸入：x0是初始點(diǎn)，fun,gfun分別是目標(biāo)函數(shù)和梯度%輸出：x,val分別是近似最優(yōu)點(diǎn)和最優(yōu)值，k是迭代次數(shù).maxk=5000。 eps=1e3。 itern=itern+1。*g0)。 if(gd=) d=g。 while(m20) %Armijo搜索 if(feval(fun,x0+rho^m*d)feval(fun,x0)+sigma*rho^m*g39。 end x0=x0+rho^mk*d。 k=k+1。 [x,val,k]=frcg[39。,x0] 共軛梯度法的說明安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 27 實(shí)際上, 時(shí),就變0k??,僅僅有向量運(yùn)算,因而存儲(chǔ)量小,適,不精確的直線搜索可能導(dǎo)致迭代出來的向量不再共軛,服的辦法是,重設(shè)初始點(diǎn),即把經(jīng)過 次迭代得到的 ?1n?X計(jì)算實(shí)踐指出,用 比 ?X 變尺度法 變尺度法是在牛頓法的基礎(chǔ)上發(fā)展起來的，度法避免了 Newton 法在每次迭代都要計(jì)算目標(biāo)函數(shù)的 Hesse 矩陣和它的逆矩陣而導(dǎo)致隨問題的維數(shù)增加計(jì)算量迅速增加. 變尺度法的基本原理在 Newton 法中，基本迭代公式 1kkt??XP其中， ，1kt?，21[()]()kkkff??PX于是有 　　 （1）11,0,2kkk????XGg其中 是初始點(diǎn)， 和 分別是目標(biāo)函數(shù) 在點(diǎn) 的梯度和 Hesse ??fkX為了消除這個(gè)迭代公式中的 Hesse 逆矩陣 ，可用某種近似矩陣1k?來替換它，即構(gòu)造一個(gè)矩陣序列 去逼近 Hesse 逆矩陣序列??kk?H??H1{}?G此時(shí)上式變?yōu)? 1kkk???Xg事實(shí)上，式中 無非是確定了第 次迭代的搜索方向，為了取得更大kk??PHg安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì)(論文)┊┊┊┊┊┊┊┊┊┊┊┊┊裝┊┊┊┊┊訂┊┊┊┊┊線┊┊┊┊┊┊┊┊┊┊┊┊┊ 28 的靈活性，我們考慮更一般的的迭代公式 （ 2）1kkkt???XHg其中步長因子 通過從 出發(fā)沿 （2）是代表ktkkkP，當(dāng) （單位矩陣）時(shí)，它變?yōu)樽钏傧陆捣ǖ牡?I 確實(shí)與 近似并且有容易計(jì)算的特點(diǎn)，必須對(duì) 附加某些條kH1k?GkH件：第一， 為保證迭代公式具有下降性質(zhì)，要求 中的每一個(gè)矩陣都是??k對(duì)稱正定的