最優(yōu)化理論與方法上機報告

1、最優(yōu)化理論與方法上機報告班級:姓名:學(xué)號:1黃金分割法黃金分割法乂稱0.618法，其基本思想是試探點函數(shù)值的比較，使包含極小 點的搜索區(qū)間不斷縮小.該方法僅需計算函數(shù)值，適用范圍廣，使用方便由于該 方法思想簡單，在此不給出具體算法流程，僅介紹思想和matlab實現(xiàn)的程序. 1.1 思想在搜索區(qū)間a, b內(nèi)插入點xl,x2 ,其中xj =a+0.382(/?-a) x2 =a+0.618(方-a)把a, b區(qū)間分為了三段,比較f(xl)與f(x2)的大小，f(xl)>f(x2),則 x* gxl ,b,去掉a,xl ;若 f(xl)<f(x2),則 x* ?ga, x2 ,去掉x2

2、, b, 然后在余下的區(qū)間上根據(jù)對稱原則再計算一個對稱點的函數(shù)值，再重復(fù)上述操 作，直到滿足精度.1.2實現(xiàn)及結(jié)果采用matlab 2011a實現(xiàn)，命名為golden,具體程序見附錄golden.m文件. 下而給岀程序運行結(jié)果，其屮目標(biāo)函數(shù)為：f(x)=x"2xl +6 ,精度采用默 認(rèn):10a-6» golden(dfunc, 0 1):0.49340.49840.50150.50650.49840.50150- 50340.5065wot enough input arguments1use default:epsilon=10 -6 10.49840. 50030.5

3、0150. 5034極小點：0.49840. 49960.50030. 50150.50000.49960. 50030.50080. 50150.49960. 50010.50030. 5008極小點對應(yīng)函教值：0.49960.49990. 50010.50035.75000.49990. 50010.50020. 50030.49990. 50000.50010. 5002迭代次數(shù):0.49990.50000.50000. 5001310.50000. 50000.50000. 50010.50000. 50000.50000. 5000迭代區(qū)間：0.50000.50000.50000.5

4、000axlm2b0.50000. 50000.50000. 500000.38200.61801.00000.50000. 50000.50000. 500000. 23610.38200.61800.50000. 50000.50000. 50000. 23610.38200.47210.61800.50000. 50000.50000. 50000.38200.47210. 52780.61800.50000. 50000.50000. 50000.47210.52780.56230.61800.50000. 50000.50000. 50000. 47210. 50650. 52780

5、. 56230.50000. 50000.50000. 50000.47210. 49340. 50650. 52780.50000. 50000.50000. 50000. 49340. 50650.51470. 52780.50000.50000.50000.50000.49340. 50150.50650.51470. 49340. 49840.50150. 5065迭代終止時的區(qū)間長度：0. 49840.50150.50340.50656.2292-00；由f(x) =xla2-xl+6,求導(dǎo)得f(x)=2xl-l,易知xl=0.5為其極小點,可 見程序正確。2牛頓法牛頓法也是一種經(jīng)典

6、的無約束優(yōu)化方法，并且其收斂速度快，具有口適應(yīng) 的特點，至今仍受到人們的青睞.21思想牛頓法的基木思想是用迭代點xk處的一階導(dǎo)數(shù)（梯度）和二階導(dǎo)數(shù)（hesse 陣）對目標(biāo)函數(shù)進行二次函數(shù)近似，然后把二次模型的極小點作為新的迭代點， 并不斷重復(fù)這一過程，直至達到精度.2.2算法牛頓法的算法如下：stepl取初始點xo c rn ,容許誤差0<6彳,令k:=0；step2 計算 gk = v f （ xk ）.step3若|gk|< 0，則停止迭代,取x* =xk ,否則，轉(zhuǎn)下一步.step4 計算 hk=a2f（xk）,并由 hkd=-gk,求得 dk=hkgk step5 令 xk

7、 +=xk + q dk, k :=k+l ,轉(zhuǎn) step2.2.3實現(xiàn)及結(jié)果采用matlab 2011a實現(xiàn)，具體程序見附錄newton.m文件.下而以上機題第 一題為例介紹具體使用方法：上機題1的優(yōu)化目標(biāo)函數(shù)為/（x）=（x + 10兀2）+5（兀3 尤4）+（*2 2兀3） +10（兀x4）,» newt on <f unc, x0, 0. 001); 極小點：0.00730.00070.01580.0158極小點對應(yīng)函數(shù)備：3.7616e-006送代次效:12,仍然使用最速卜降法中建立的func.m文件，在命令窗口中輸入（加粗部分）： x0=l 2 3 4j ;newt

8、on（ftinc,xo）;即可按默認(rèn)的精度10a-6計算，若想改變精度, 如10f 則輸入：newton（func,x0,0.001）;對應(yīng)的結(jié)果分別如下圖的（a）、（b）所 示：» nevt onffunc x0):not enough input arguments! epsilon=10 -6 極小點：-0.00060. 00010.00140.0014極小點對應(yīng)函數(shù)值：2. 2345110迭代次數(shù):18（：!）采用默認(rèn)精度(b)精度為0. 001牛頓法收斂速度快，正如上圖（a）所示，達到10a-6精度只需18步，而 最速下降法卻需要366304步，兩者的收斂速度曲此可見一-斑

9、，可謂冇天壤之別! 2.4體會由于牛頓法收斂速度快，但人工求目標(biāo)函數(shù)的梯度、hesse矩陣，冇時較為 繁雜，故算法實現(xiàn)時，實現(xiàn)了自動求梯度和hesse矩陣，這樣便在程序的易用 性和吋間復(fù)雜度兩者間得到了很好的折中.3外點法外點法適合求解如下約束優(yōu)化問題:min /(x)5xern,v s.t. h. (x) = 0,ze£ = l,|5jp,g (x) > 05疋?=訓(xùn),加但木次實驗僅需求解如下約朿優(yōu)化問題:sz g； (x) > 0?xern,zez = 1|e而且，等式約束也可以轉(zhuǎn)化為不等式約束！記可行域為d = x 6 r n | gi ( x) > o(ig

10、l).31思想方法構(gòu)造罰函數(shù)m和增廣fl標(biāo)函數(shù)尸=工min0, gj (x) i=lt(x5a/) = /(x)+jwp(x)5其中m>0為懲罰因子，不難發(fā)現(xiàn)當(dāng)xcd時，即x為可行點 吋,t(x,m)=f(x),此吋口標(biāo)函數(shù)沒有受到懲罰；當(dāng)x 吋，t(x,m)>f (x),目標(biāo)函數(shù)受到懲罰，m越大，受到的懲罰越重，當(dāng)m足夠犬吋，要使f(x) 取得極小，罰函數(shù)p( x)應(yīng)充分小，從而t ( x, m )的極小點充分逼近可行域 d,這樣求解一般約束優(yōu)化問題就化為求解一系列無約束的優(yōu)化問題min t ( x, m ).3.2算法外點法的算法如下：stepl取初始點xo cr n ,容許誤

11、差0< 0<1,懲罰因了 m 1 >0 , r>l,令 k:=l.step2以xk-1為初始點求解子問題聖丁(血胚)=/(兀)+胚恥)，, 設(shè)其極小點n為xk.step3 若 j (1 <j <m),使gj(xk)>c?則令 m k+l= rm k , k =k +1,轉(zhuǎn) step2,否則 停止迭代，取x* =xk .33實現(xiàn)及結(jié)果采用matlab 2011a實現(xiàn)，無約束優(yōu)化采用牛頓法，即直接調(diào)用第一篇屮的 newton函數(shù)，具體程序見附錄 epm.m 文件.程序中的 min=newton(augf,xk,epsilon);是無約束優(yōu)化函數(shù)的調(diào)用，參數(shù)

12、augf為增廣冃 標(biāo)函數(shù)文件名，augf.m屮還涉及到(調(diào)用)了兩個函數(shù)：func.m和constrains.m, 前者為目標(biāo)函數(shù)文件，與前面的ftinc.m -樣，只是目標(biāo)函數(shù)不同而已，后者為 約束函數(shù)。4附錄：源程序.golden.mfunction func=golden(f>a,b,e)k=0;a l=b-0.618*(b-a);%插入點的值a2=a+0.618*(b-a);while b-a>e%循環(huán)條件yl=subs(f,al);y2=subs(f,a2);ifyl>y2%比較插入點的函數(shù)值的大小a=al;%進行換名al=a2; yl=y2;a2=a+0.618*

13、(ba);elseb=a2;a2=a 1;y2=yl；al=b-0.618*(b-a);endk=k+1;end%迭代到滿足條件為止就停止迭代func=(a+b)/2; fniin=subs(f,xmin) fprintfckw); disp(k);.newton.m%輸岀函數(shù)的最優(yōu)值%輸出迭代次數(shù)function x=nanewton(fhame,dfhame,xo,e,n) ifnargin<5,n=500;endif nargin<4,e=le-4; end x=xo;x0=x+2*e;k=0;while abs(xo-x)>e&k<n,k=k+l;xo=

14、x;x=xo ffeval(fhame,xo)/ffeval(dfhame,xo); disp(x);endifk=n,waming(,已達到迭代次數(shù)上限')；end.epm.mfunction y=flin(xl,x2j)y=-x 1 *x2+r* (x 1 a2+x2a2-1 )a2+(x 1 +x2)a2;%定義 fun 函數(shù)r=zeros( 1,50);a=zeros(l ,50);b=zeros(l ,50);f0=zeros(l ,50);fl =zeros( 1,50);f2=zeros(l, 50); %主要是想將rabfdfl f2都定義為數(shù)組syms d xl x2

15、;r(l)=l;c=10;a(l)=l;b(l)=l;fork=l:100%外點法r迭代循環(huán)f=fun(xl,x2,r(k)；fx udigx r);fx2=diff(f；x2'); x l=a(k);x2=b(k);for n=l:100 %梯度法最優(yōu)化f0(k)=subs(f);fl(k)=subs(fxl);f2(k)=subs(fx2);if(double(sqrt(fl(k)a2+f2(k)a2)<=0.002)a(k)=vpa(x 1,4);b(k)=vpa(x2,4);f0(k)=vpa(f0(k),4)elsexl=xl -d*f 1 (k);x2=x2-d*£2(k);d=fun(x 1 ,x2,r(k);dd=diff