【導(dǎo)讀】關(guān)于無(wú)約束最優(yōu)化問(wèn)題求解的基本研究。無(wú)約束最優(yōu)化計(jì)算方法是數(shù)值計(jì)算領(lǐng)域中十分活躍的研究課題之一，快速。的求解無(wú)約束最優(yōu)化問(wèn)題，除了自身的重要性以外，還體現(xiàn)在它也構(gòu)成一些約束。法，并且討論了這些方法的優(yōu)缺點(diǎn)以及每種方法的適用范圍.同事論文分別對(duì)每。種方法給出了具體實(shí)例，并對(duì)例子進(jìn)行了matlab軟件實(shí)現(xiàn)。安徽工業(yè)大學(xué)本科畢業(yè)設(shè)計(jì)(論文)

　　

【正文】 ?X ，停止，極小點(diǎn)為 ()kX ，否則轉(zhuǎn)步驟（ 3）； （ 3） 計(jì)算 12 ( )()kf ??????X ，令 1( ) ( ) ( )( ) ( )k k kHf???? ? ???S X X； 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 20 （ 4） 用一維搜索法求 ? ，使得 ( ) ( ) ( ) ( )0( ) m in (k k k kkff ????? ? ?X S X S，令( 1 ) ( ) ( )k k kk?? ??X X S， 1kk??，轉(zhuǎn)步驟（ 2） . 例 用修正牛頓法求解下列問(wèn)題： ? ? 221 2 1 1 2 2m in 2 2f x x x x x x? ? ? ? ?X ， 初始點(diǎn) ? ?0 00???????X ， 610? ?? . 解 計(jì)算 ? ?f? X 及 ? ?2f? X . ? ? 12121 4 21 2 2xxf xx?????? ??? ? ???X , ? ?2 4222f ????????X , 故有 ? ?? ?0 11f ?????????X ， ? ?? ?02 4222f ????????X ， ? ?? ? 10211221 12f ?????????????????X 因而牛頓方向?yàn)? ? ? ? ?? ? ? ?? ?10 0 0211 11223111 22ff???? ? ? ????? ?? ???? ?? ??? ? ??? ????????????S X X 從 ??0X 出發(fā)，沿牛頓方向 ??0S 作一維搜索，令步長(zhǎng)變量為 ? ，記最優(yōu)步長(zhǎng)為 0? ，則有 ? ? ? ?00 10 330 22??? ???? ? ? ??? ? ? ? ?? ? ? ??? ? ? ? ???? ? ? ?XS ， 故 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 21 ? ? ? ?? ? ? ? ? ?220023 3 3222 2 25542f ? ? ? ? ? ? ???? ? ? ?? ? ? ? ? ? ? ? ?? ? ? ?? ? ? ???XS 令 ? ? ? ?? ?00 55 022f? ??? ? ? ? ?XS 則有 0 1?? ， 故 ? ? ? ? ? ?1 0 001101 33022???? ? ? ??? ? ? ? ?? ? ? ? ? ??? ? ? ? ???? ? ? ?X X S 計(jì)算 ? ?? ?1f? X ： ? ?? ?? ?? ?131 4 1 202301 2 1 22f??? ? ? ? ?????? ? ? ????? ? ? ? ? ???X ， 故有 ? ?? ?1f ???X ，停止計(jì)算，輸出 ??1X ， ? ?1* 132???????????XX 即為極小點(diǎn) . 修正你頓法的 matlab 實(shí)現(xiàn) 首先建立 m文件： function [x,val,k]=revisenm(fun,gfun,Hess,x0) %功能：用修正牛頓法求解無(wú)約束問(wèn)題： minf(x) %輸入： x0是初始點(diǎn)， fun,gfun,Hess分別是求 % 目標(biāo)函數(shù)值，梯 度， Hesse矩陣的函數(shù) %輸出： x,val分別是近似最優(yōu)點(diǎn)和最優(yōu)值， k是迭代次數(shù) . n=length(x0)。maxk=150。 rho=。sigma=。tau=。 k=0。 epsilion=1e5。 while(kmaxk) gk=feval(gfun,x0)。 %功能：計(jì)算梯度 muk=norm(gk)39。^(1+tau)。 Gk=feval(Hess,x0)。 %功能：計(jì)算 Hess矩陣 Ak=Gk+muk*eye(n)。 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 22 dk=Ak\gk。%解方程組 Gk*dk=gk,計(jì)算搜索方向 if(norm(gk)epsilion),break。end %檢驗(yàn)終止準(zhǔn)則 m=0。mk=0。 while(m20) %用 Armijo搜索步長(zhǎng) if(feval(fun,x0+rho^m*dk)feval(fun,x0)+sigma*rho^m*gk39。*dk) mk=m。break。 End 然后建立 fun， gfun和 Hess矩陣的 m文件如下： function f=fun(x) f=x(1)x(2)+2*x(1)^2+2*x(1)*x(2)+x(2)^2。 function g=gfun(x) g=[1+4*x(1)+2*x(2),1+2*x(1)+2*x(2)]39。 function He=Hess(x) n=length(x)。 He=zeros(n,n)。 He=[4,2。2,2]39。 然后在工作窗口輸入： x0=[0,0]39。 [x,val,k]=revisenm(39。fun39。,39。gfun39。,39。Hess39。,x0) 所得結(jié)果如下 x = val = k = 6 修正牛頓法的說(shuō)明 修正 Newton 法克服了 Newton 法的缺點(diǎn) .特別是 ,當(dāng)?shù)c(diǎn)接近于最優(yōu)解時(shí) ,此法具有收斂速度快的優(yōu)點(diǎn) ,對(duì)初始點(diǎn)的選擇要求不嚴(yán) .但是 ,修正 Newton 法仍需要計(jì)算目標(biāo)函數(shù)的 Hesse 矩陣和逆矩陣 ,所以求解的計(jì)算量和存貯量均很大 .另外 ,當(dāng)目標(biāo)函數(shù)的 Hesse 矩陣在某點(diǎn)處出現(xiàn)奇異時(shí) ,迭代將無(wú)法進(jìn)行 .因此修正安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 23 Newton 法仍有相當(dāng)?shù)木窒扌? 共軛梯度法 首先介紹共軛方向 的概念： 定義 設(shè) ,xy是 n 維歐式空間中的兩個(gè)向量，即 , n?xy ，若有 0T ?xy （即? ?,0?xy ），就稱(chēng) x 與 y 是兩個(gè)正交的向量，又設(shè) A 是一個(gè) n 階對(duì)稱(chēng)正定矩陣，若有0T ?x Ay ，則稱(chēng)向量 x 與 y 關(guān)于 A 共軛正交，簡(jiǎn)稱(chēng)關(guān)于 A 共軛 定義 設(shè)一組非零向量 ? ? ? ? ? ?12, , , n n?p p p ， A 為 階對(duì)稱(chēng)正定陣，若下試成立： ? ?? ? ? ? ? ?0 , , 1 , 2 , ,Tij i j i j n? ? ?p A p .稱(chēng)向量組 ? ? ? ? ? ?12, , , np p p 關(guān)于 A 共軛 .也稱(chēng)它們?yōu)橐唤M A 共軛方向（或稱(chēng)為 A 的 n 個(gè)共軛方向） . 共軛梯度法最早是由 Hestenes 和 Stiefle（ 1952）提出來(lái)的，用于解 正定系數(shù)矩陣 的 線性方程組 ，在這個(gè)基礎(chǔ)上， Fletcher 和 Reeves （ 1964）首先提出了解非線性最優(yōu)化問(wèn)題的共軛梯度法 .由于共軛梯度法不需要 矩陣 存儲(chǔ)，且有較快的收斂速度和二次終止性等優(yōu)點(diǎn)，現(xiàn)在共軛梯度法已經(jīng)廣泛地應(yīng)用于實(shí)際問(wèn)題中 .共軛梯度法是一個(gè)典型的 共軛方向 法，它的每一個(gè)搜索方向是互相共軛的，而這些搜索方向 d 僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合，因此，存儲(chǔ)量少，計(jì)算方便 共軛梯度法的基本思想與原理 ? ? T1m in 2 Tf b C? ? ?X X A X X 其中 A 為 n 階對(duì)稱(chēng)正定陣， ,nnxb??， C 是常數(shù) 由上 ? ?f X 是正定二次函數(shù) ? ?fb? ? ?X AX ， 安徽工業(yè)大學(xué) 本科畢業(yè)設(shè)計(jì) (論文 ) ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 裝 ┊ ┊ ┊ ┊ ┊ 訂 ┊ ┊ ┊ ┊ ┊ 線 ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ ┊ 24 故有 ? ?? ? ? ?? ? ? ?1k k kkff ?? ? ? ?X X A P 0,1, , 1kn??. 又設(shè)以 kX 迭代點(diǎn)沿搜索方向 kP 進(jìn)行一維搜索時(shí)采用最佳一維搜索求步長(zhǎng)因子k? ，即 ? ? ? ?10m i nk k kkk k k kkff??????????????? ? ???X X PX P X P 進(jìn)行多次迭代，檢驗(yàn)若 ? ? 0kf??X ，則 kX 就是最優(yōu)解 .否則就繼續(xù)進(jìn)行迭代 . 共軛梯度法的迭代步驟 已知目標(biāo)函數(shù) ? ?f? X ,終止限 0?? （ 1） 選取初始點(diǎn) 0X ,給定終止限 0?? （ 2） 求初始梯度 .計(jì)算 ? ?0f? X ,若 ? ?0f ??X 停止迭代輸出 0X 。 否則轉(zhuǎn)（ 3） （ 3） 構(gòu)造初始搜索方向 .取 ? ?00Pf??? X ,令 0k? ,轉(zhuǎn) (4). （ 4） 進(jìn) 行 一 維 搜 索 . 求 kt 使得 ? ? ? ?0m ink k k k Ktf t f t?? ? ?X P X P, 令 1k K k kt? ??X X P，轉(zhuǎn)（ 5） （ 5） 求梯度向量 .計(jì)算 ? ?1kf ?? X ，若 ? ?1kfX ?? ? ，停止迭代輸出 1k?X ；否則轉(zhuǎn) （ 6） （ 6） 檢驗(yàn)迭代次數(shù) .若 1kn?? ，令 0= kXX，轉(zhuǎn)（ 3）；否則轉(zhuǎn)（ 7） （ 7） 構(gòu)造共軛方向 .取 ? ?? ?212kkkff?????XX ? ?11k k k kf ???? ?? ?P X P，令 1kk??， 轉(zhuǎn)（ 4） 例： 用共軛梯度法求 ? ? 2212m in 25f x x??X ，其中 ? ? ? ?