1、任課教師簽字： 課程作業(yè)學(xué)年學(xué)期： 20172018 學(xué)年第二學(xué)期課程名稱：優(yōu)化理論作業(yè)名稱：作業(yè)三學(xué)生姓名：學(xué) 號： 提 交 時 間：一、問題重述形如的min f(x),x w Rn問題稱為無約束優(yōu)化問題，常用下降算法來解決這 類問題。下降算法的關(guān)鍵在于步長和搜索方向的選取。步長的求取可以借助前 面作業(yè)中提到的一維搜索等方法求取，而搜索方向算法可以分為兩大類，解析 法和直接法。解析法借助了目標(biāo)函數(shù)的導(dǎo)數(shù)進行搜索，這類算法搜索速度快、效率高， 但是對目標(biāo)函數(shù)的要求更為嚴(yán)格。常用的方法有最速下降法、Newton法、共腕梯度法、擬Newton法等。直接法不使用導(dǎo)數(shù)，也不需要得到目標(biāo)函數(shù)的明確解析式

2、，只需要能夠得 到某些函數(shù)上的點即可。因此直接法的適用范圍更廣，但相應(yīng)的收斂速度會較 慢，計算量也會隨著問題維數(shù)的增加而迅速增大。常用的方法有單純形法、 Powell方向加速法以及 Powell改進算法。本作業(yè)以直接法的Powell法為例，解決具體的無約束優(yōu)化問題，并對將 Powell方向加速法和Powell改進算法解決結(jié)果進行對比。二、算法原理對于n維正定二次函數(shù)f (x) =0.5xTGx + bTx + c,設(shè)p0, p1,pk(k < n)關(guān)于 G共腕，x0與x1為任意不同點。分別從x0與x1出發(fā)，依次沿Po, R,Pk作一維 搜索。如果最后找到兩個互不相同的極小點 xa與xb,

3、則xb-xa與p0, p1,pk關(guān) 于G共腕。Powell方向加速法正是基于這一原理，每次迭代過程作n+1次一維搜索。第一次沿給定的n個線性無關(guān)的方向p0,p1,.pn依次作一維搜索，之后沿由這 一階段的起點到第n次搜索所得到的點的方向P再做一次一維搜索，并把這次 所得點作為下一階段的起點，下一階段的 n個搜索方向為p0,p1,.pn,p。以此 直到找到最優(yōu)解。此算法是在迭代中逐次生成共腕方向，而共腕方向又是較好的搜索方向， 所以稱之為方向加速法。但是，此算法產(chǎn)生的n個向量可能線性或近似線性相關(guān)，這時張不成n維空間，可能得不到真正的極小點。因此，Powell原始算法 存在一定的缺陷。Powel

4、l改進算法雖然不再具有二次終止性，但克服了搜索方向的線性相關(guān) 的不利情形，是解決無約束優(yōu)化問題較有效的直接法之一。本次作業(yè)一維搜索的過程是利用函數(shù)求導(dǎo)，求得最小值。經(jīng)過試驗發(fā)現(xiàn)， a是允許為負(fù)數(shù)的。否則最終尋優(yōu)得到的極值點與實際結(jié)果存在很大的偏差，而且尋優(yōu)的效率特別低下三、算法流程Powell算法流程圖:NXo=Xn+lPn=PPi=P+i i=0,1，n-1圖1 Powell算法流程圖Powell改進算法流程圖:圖2 Powell改進算法流程圖Xo=Xn+iF0=F(X n)設(shè)初始搜索方向Pi =ei ,i=1,.n初始目標(biāo)值F0=f(x0)Xn+1=Xn四、實驗驗證1、設(shè)目標(biāo)函數(shù)f(x)

5、=X14 + X1+X2+(1+X2)2 ,收斂精度為 0.001 ,初始點 (-2,2 )。利用Matlab自帶的函數(shù)求二元函數(shù)極值點函數(shù) fminsearch，求得極值點為 (-0.630,-1.500),最小值為-1.722。以此為標(biāo)準(zhǔn)，檢驗 Powell方向加速法和 Powell改進算法的尋優(yōu)結(jié)果。Powell方向加速法經(jīng)過2次迭代，求得極值點(-0.630,-1.500 ),對應(yīng)的 最小值-1.722 ; Powell改進方向加速法經(jīng)過2次迭代，求得極值點 (-0.630,-1.500 ),對應(yīng)的最小值 1.722。2、設(shè)目標(biāo)函數(shù)f(x) =x14 + x1+x2+(1+x2)2+x

6、x2 ,收斂精度為0.001 ,初始 點(-2,2 )。利用Matlab自帶的函數(shù)求二元函數(shù)極值點函數(shù) fminsearch，求得極值點為 (0.5827,-1.7913),最小值為-1.5109。以此為標(biāo)準(zhǔn)，檢驗 Powell方向加速法 和Powell改進算法的尋優(yōu)結(jié)果。Powell方向加速法經(jīng)過4次迭代，求得極值點(0.5827,-1.7912 ),對應(yīng) 的最小值-1.5109 ; Powell改進方向加速法經(jīng)過2次迭代，求得極值點(-0.630,-1.500 ),對應(yīng)的最小值1.722。兩種方法對應(yīng)的尋優(yōu)過程如下圖所 示。x11圖3 Powell直接與改進法尋優(yōu)過程四、算法程序1、Pow

7、ell方向加速關(guān)鍵部分算法：error=0.001; x_process =-2,2; dimensions=2;P=eye(dimensions);zeros(1,dimensions);% 初始搜索方向syms aerfa; while(1) x_zero=x_process;for i=1:dimensions%&著 P(i,:)方向進行一維搜索f=F_Object(x_process+aerfa*P(i,:);aerfa_process_all=double(real(solve(diff(f); F_process_j=; for j=1:length(aerfa_proce

8、ss_all) aerfa_process=aerfa_process_all(j); x_process_j=x_process+aerfa_process*P(i,:); F_process_j=F_process_j F_Object(x_process_j);end ,j=min(F_process_j); aerfa_process=aerfa_process_all(j); x_process=x_process+aerfa_process*P(i,:); endif norm(x_process-x_zero)<=error break;%可以避免之后分母中的(x_proc

9、ess-x_zero)過小而影響算法的進行endP(dimensions+1,:)=(x_process-x_zero)/norm(x_process-x_zero); for i=1:dimensionsP(i,:尸P(i+1,:); end f=F_Object(x_process+aerfa*P(dimensions+1,:);aerfa_process_all=double(real(solve(diff(f);%一維搜索F_process_j=; for j=1:length(aerfa_process_all) aerfa_process=aerfa_process_all(j);

10、 x_process_j=x_process+aerfa_process*P(i,:); F_process_j=F_process_j F_Object(x_process_j); end ,j=min(F_process_j); aerfa_process=aerfa_process_all(j); x_process=x_process+aerfa_process*P(end,:); if norm(x_process-x_zero)<=error break; end end2、Powell改進法關(guān)鍵部分算法:error=0.001;x_process =-2,2; syms a

11、erfa;dimensions=length(x_zero); F_process=zeros(dimensions+1,1);P=eye(dimensions); 網(wǎng)始搜索方向while(1)x_zero=x_process;F_process(1)=F_Object(x_zero);for i=1:dimensions%n著 P(i,:)方向進行一維搜索f=F_Object(x_process+aerfa*P(i,:);aerfa_process_all=double(real(solve(diff(f);%一維搜索F_process_j=;for j=1:length(aerfa_pro

12、cess_all)aerfa_process=aerfa_process_all(j);x_process_j=x_process+aerfa_process*P(i,:);F_process_j=F_process_j F_Object(x_process_j);end,j=min(F_process_j);aerfa_process=aerfa_process_all(j);x_process=x_process+aerfa_process*P(i,:);F_process(i+1)=F_Object(x_process);endif norm(x_process-x_zero)<=

13、errorbreak; endF_Object_data,m=max(F_process(1:dimensions)-F_process(2:dimensions+1);F_Object_xing=F_Object(2*x_process-x_zero);if ( F_Object_xing>=F_process)|(F_process(1)2*F_process(dimensions+1)+F_Object_xing)*(F_proc ess-F_process(dimensions+1)-F_Object_data)A2>0.5*(F_process-F_Object_xing

14、)A2*F_Object_data)x_zero=x_process;elsefor i=m:dimensions-1P(i,:)=P(i+1,:);endP(dimensions,:)=(x_process-x_zero)/norm(x_process-x_zero);f=F_Object(x_process+aerfa*P(dimensions,:);aerfa_process_all=double(real(solve(diff(f);獷維搜索F_process_j=; for j=1:length(aerfa_process_all) aerfa_process=aerfa_process_all(j);