【文章內(nèi)容簡(jiǎn)介】 ) ( ) ( )0m in ( ) ( )k k k k kff? ??? ? ? ?X S X S 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 11 以此最優(yōu)步長(zhǎng)作為由 ()kX 點(diǎn)出發(fā)沿該點(diǎn)的負(fù)梯度方向探索的步長(zhǎng) ()k? . 這種方法的迭代計(jì)算的收斂性，可用以下三式中的任一式或二式作為準(zhǔn)則來(lái)進(jìn)行判斷： ? ?? ? ? ?? ?()1( ) ( 1 )2()( ) ( 1 )3kkkkkkffff?????? ???? ?? ????????XXXXXX 最速下降法算法步驟 用最速下降法求無(wú)約束多維極值問題 m in ( ), nf ?XX 的算法步驟如下： （ 1） 取初 始點(diǎn) ??0X ，精度 0?? ， 令 0k? （ 2） 計(jì)算搜索方向 ( ) ( )()kkf? ??VX，其中 ()()kf? X 表示函數(shù) ()f X 在點(diǎn) ()kX處的梯度； （ 3） 若 ()k ??V ，則停止計(jì)算；否則，從 ()kX 出發(fā)，沿 ()kV 進(jìn)行一維搜索，即求 k? ，使得 ( ) ( ) ( ) ( )0( ) m in )k k k kkff ????? ? ?X V ( X V.此處的一維搜索可以用黃金分割法等算法 （ 4） 令 ( 1 ) ( ) ( ) ,1k k kk kk?? ? ? ? ?X X V，轉(zhuǎn)步驟（ 2） . 例 試用最速下降法求目標(biāo)函數(shù) 2212( ) 4f x x??X 的極小值，設(shè)初始點(diǎn) (0) [2 2]T?X ；收斂要求 21 10? ?? . 解：原函數(shù)的梯度 ? ?1212( ) ( [ 2 8 ]T Tfff x xxx????? ? ???????X X )X，在 (0)X 點(diǎn)的梯度為 ? ?( 0 ) [4 16 ]Tf??X . 梯度的模為 ? ? 22( 0 ) ( 0 )( 0 ) 2 212( ) ( ) 4 16 xx? ? ? ???? ? ? ? ? ?? ? ? ???? ? ? ?XXX 梯度的負(fù)方向?yàn)?( 0 ) 1 [ 4 1 6 ] [ 0 . 2 4 3 0 . 9 7 0 ]1 6 . 4 9 2 TT? ? ? ?S 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 12 ( 1 )1( 1 ) ( 0 ) ( 0 )( 1 )22 0 . 2 4 3 2 0 . 2 4 32 0 . 9 7 0 2 0 . 9 7 0 xx??? ? ???? ? ? ? ? ?? ? ? ? ? ? ??? ? ? ? ? ??? ? ? ? ? ? ??X X S ? ?( 0 ) ( 0 ) 2 2( 2 0 .2 4 3 ) 4 ( 2 0 .9 7 0 )f ? ? ?? ? ? ? ?XS ? ?( 0 ) ( 0 ) 2 ( 2 0 .2 4 3 ) ( 0 .2 4 3 ) 8 ( 2 0 .9 7 0 ) ( 0 .9 7 0 )7 .6 4 5 1 6 .4 9 2dfd? ????? ? ? ? ? ? ???XS 令 ? ?( 0 ) ( 0 ) 0df d ??? ?XS，求出 * ? ? ，算得 ? ?( 1 ) ( 1 )[ 1 .4 7 6 0 .0 9 2 3 ] , [ 2 .9 5 2 0 .7 3 8 ]TTf? ? ? ? ?XX 梯度的模為 ? ? ? ? ? ?22( 1 ) 2 . 9 5 2 0 . 7 3 8 3 . 0 4 3f? ? ? ? ?X 根據(jù)收斂準(zhǔn)則， ? ?( 1 ) 213. 04 3 10f ? ?? ? ? ?X，故未達(dá)到要求，應(yīng)繼續(xù)探索 .下一步探索放向?yàn)? ( 1 ) 1 [ 2 . 9 5 2 0 . 7 3 8 ] [ 0 . 9 7 0 0 . 2 4 3 ]3 . 0 4 3 TT? ? ? ? ? ?S ( 2 )1( 2 ) ( 1 ) ( 1 )( 2 )21 . 4 7 6 0 . 9 7 0 1 . 4 7 6 0 . 9 7 00 . 0 9 2 3 0 . 2 4 3 0 . 0 9 2 3 0 . 2 4 3 xx??? ? ???? ? ? ? ? ?? ? ? ? ? ? ??? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ??X X S ? ?( 1 ) ( 1 ) 2 2( 1 .4 7 6 0 .9 7 0 ) 4 ( 0 .0 9 2 3 0 .2 4 3 )f ? ? ?? ? ? ? ? ?XS ? ?( 1 ) ( 1 ) 2 . 3 5 4 3 . 0 4 3 0df d ? ??? ? ? ?XS ，得到 * ? ? ? ?( 2 ) ( 2 )[ 0 .2 2 2 0 .2 2 2 ] , [ 0 .4 4 4 1 .7 7 6 ]TTf? ? ?XX ? ?( 2 ) 211. 83 1 10f ? ?? ? ? ?X 未達(dá)到收斂要求，所以還應(yīng)繼續(xù)探索，下一步探索方向?yàn)? ( 2 ) 1 [ 0 . 4 4 4 1 . 7 7 6 ] [ 0 . 2 4 2 0 . 9 7 0 ]1 . 8 3 1 TT? ? ? ?S ( 3 )1( 3 ) ( 2 ) ( 2 )( 3 )20 . 2 2 2 0 . 2 4 20 . 2 2 2 0 . 9 7 0 xx?? ? ?????? ? ? ? ??????? ??X X S ? ?? ?( 2 ) ( 2 ) 2 2( 1 ) ( 1 )( 0 .2 2 2 0 .2 4 2 ) 4 ( 0 .2 2 2 0 .9 7 0 )7 .6 4 4 1 .8 3 0 0fdfd? ? ?? ??? ? ? ? ?? ? ? ?XSXS 得到： * ? ? 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 13 ? ?( 3 ) ( 3 )[ 0 .1 6 4 0 .0 0 9 8 ] , [ 0 .3 2 8 0 .0 7 8 4 ]TTf? ? ? ? ?xx ? ?( 3 ) 210. 33 7 10f ? ?? ? ? ?x 繼 續(xù) 探 索 ， 當(dāng) 探 索 到 點(diǎn) ( 7 ) [ 16 009 6] T??x 時(shí)，? ?( 7 ) 210 . 0 0 3 2 1 0f ? ?? ? ? ?x ，達(dá)到預(yù)定的收斂要求，因而可認(rèn)為 * (7)?xx為最優(yōu)點(diǎn)，而 ? ?* 2 2 6( 0 .0 0 1 6 ) 4 ( 0 .0 0 0 0 9 6 ) 2 .5 9 6 1 0 0f ?? ? ? ? ? ?x 為極小值 . 最速下降法的 matlab實(shí)現(xiàn) 首先建立 M文件： function [x,val,k]=grad(fun,gfun,x0) %功能：用最速下降法求解無(wú)約束問題： minf（ x） %輸入： x0是初始點(diǎn)， fun， gfun分別是目標(biāo)函數(shù)和梯度 %輸出： x,val分別是近似最優(yōu)點(diǎn)和最優(yōu)值， k是迭代次數(shù) . maxk=5000。 %最大迭代次數(shù) rho=。 sigma=。 k=0。 eps=1e7。 while(kmaxk) g=feval(gfun,x0)。%計(jì)算梯度 d=g。 %計(jì)算搜索方向 if(norm(d)eps),break。end m=0。mk=0。 while(m20) %Armijo搜索 if(feval(fun,x0+rho^m*d)feval(fun,x0)+sigma*rho^m*g39。*d) mk=m。break。 end m=m+1。 end x0=x0+rho^mk*d。 k=k+1。 end x=x0。 val=feval(fun,x0)。 然后建立 fun， gfun的 m文件 function f=fun(x) f=x(1)^2+4*x(2)^2。 function g=gfun(x) g=[2*x(1),8*x(2)]39。 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 14 求解結(jié)果為 x = 0 0 val = 0 k = 2 最速下降法的鋸齒現(xiàn)象 最速下降法對(duì)初始點(diǎn)的選擇要求不高，每一輪迭代工作量較少，它可以很快的從初始點(diǎn)達(dá)到極小點(diǎn)附近 .但在接近極小點(diǎn)時(shí)，最速下降法卻會(huì)出現(xiàn)鋸齒現(xiàn)象，收斂速度很慢，因?yàn)閷?duì)一般二元函數(shù)，在極小點(diǎn)附近可用極小點(diǎn)的二階泰勒多項(xiàng)式來(lái)近似，而后者為凸函數(shù)時(shí)，他的等值線是一族共心橢圓，特別是當(dāng)橢圓比較扁平時(shí)，最速下降法的收斂速度越慢 . 至于最速下降法出現(xiàn)鋸齒現(xiàn)象的原因，可以作如下粗略解釋： 由 ? ?f X 在??kX 的泰勒展式： ? ? ? ? ? ?? ?? ? ? ? ? ?? ?==k k kf f f? ? ? ?? ? ?kX X X P ? ? ? ?? ?=kkf??PX 為了出從 ??kX 出發(fā)沿方向 ??kP 的極小點(diǎn)，令 ? ? ? ? ? ?? ? ? ?= 0 ,Tk k kkf? ? ?? ? ?X P P’ 則有 ? ?? ? ? ?? ?1 0kkff??? ? ?XX. 即方向 ? ? ? ?? ?11kkf??? ??PX與方向 ? ? ? ?? ?=kkf??PX正交 .這表明迭代產(chǎn)生的點(diǎn)列??? ?kX 所循路徑是“之”字行的 .當(dāng) ??kX 接近極小點(diǎn) *X 時(shí)，每次迭代移動(dòng)的步長(zhǎng)很小，這樣就呈現(xiàn)出鋸齒現(xiàn)象，影響了收斂速度 .因此常常將梯度法與其他方法安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 15 結(jié)合起來(lái)使用 . 最速下降法的說明 最速下降法的優(yōu)點(diǎn)是算法簡(jiǎn)單 ,每次迭代 計(jì)算量小 ,占用內(nèi)存量小 ,即使從一個(gè)不好的初始點(diǎn)出發(fā) ,往往也能收斂到局部極小點(diǎn) .但它有一個(gè)嚴(yán)重缺點(diǎn)就是收斂速度慢 .沿負(fù)梯度方向函數(shù)下降很快的說法 ,容易使人們產(chǎn)生一種錯(cuò)覺 ,認(rèn)為這一定是最理想的搜索方向 ,沿該方向搜索時(shí)收斂速度