機(jī)械優(yōu)化設(shè)計(jì)——鮑威爾法

1、機(jī)械優(yōu)化設(shè)計(jì)鮑 威 爾 法 班級(jí)：0841001 成員：張波2010213217張建2010213214潘陽瑞20102132272013年6月鮑威爾法鮑威爾（Powell）法是直接利用函數(shù)值來構(gòu)造共軛方向的一種方法?；舅枷耄涸诓挥脤?dǎo)數(shù)的前提下，在迭代中逐次構(gòu)造G 的共軛方向。一基本算法：（二維情況描述鮑威爾的基本算法）1）任選一初始點(diǎn)x0，再選兩個(gè)線性無關(guān)的向量，如坐標(biāo)軸單位向量e1=1,0T和e2=0,1T作為初始搜索方向。 2）從x0出發(fā)，順次沿、作一維搜索，得 、 點(diǎn)，兩點(diǎn)連線得一新方向 用 代替e1，形成兩個(gè)線性無關(guān)向量,e1，作為下一輪迭代的搜索方向。再從出發(fā)，沿作一維搜索得點(diǎn)，

2、作為下一輪迭代的初始點(diǎn)。 3）從出發(fā)，順次沿、作一維搜索，得到點(diǎn)、 ，兩點(diǎn)連線得一新方向: 。沿作一維搜索得點(diǎn)，即是二維問題的極小點(diǎn)。把二維情況的基本算法擴(kuò)展到n維，則鮑威爾基本算法的要點(diǎn)是：在每一輪迭代中總有一個(gè)始點(diǎn)（第一輪的始點(diǎn)是任選的初始點(diǎn)）和n個(gè)線性獨(dú)立的搜索方向。從始點(diǎn)出發(fā)順次沿n個(gè)方向作一維搜索得一終點(diǎn)，由始點(diǎn)和終點(diǎn)決定了一個(gè)新的搜索方向。用這個(gè)方向替換原來n個(gè)方向中的一個(gè)，于是形成新的搜索方向組。替換的原則是去掉原方向組的第一個(gè)方向而將新方向排在原方向的最后。此外規(guī)定，從這一輪的搜索終點(diǎn)出發(fā)沿新的搜索方向作一維搜索而得到的極小點(diǎn)，作為下一輪迭代的始點(diǎn)。這樣就形成算法的循環(huán)。 圖1

3、.二維情況下的鮑威爾法 二改進(jìn)算法在鮑威爾基本算法中，每一輪迭代都用連結(jié)始點(diǎn)和終點(diǎn)所產(chǎn)生出的搜索方向去替換原向量組中的第一個(gè)向量，而不管它的“好壞”，這是產(chǎn)生向量組線性相關(guān)的原因所在。在改進(jìn)的算法中首先判斷原向量組是否需要替換。如果需要替換，還要進(jìn)一步判斷原向量組中哪個(gè)向量最壞，然后再用新產(chǎn)生的向量替換這個(gè)最壞的向量，以保證逐次生成共軛方向。為此，要解決兩個(gè)關(guān)鍵問題：（1）是否較好？是否應(yīng)該進(jìn)入新的方向組？即方向組是否進(jìn)行更新？（2）如果應(yīng)該更新方向組，不一定替換方向，而是有選擇地替換某一方向。改進(jìn)算法的具體步驟： （1）給定初始點(diǎn)（記作），選取初始方向組，它由n個(gè)線性無關(guān)的向量，,.,所組成

4、，置。 （2）從出發(fā)，順次沿，.，作一維搜索得，.，。接著以為起點(diǎn)，沿方向 移動(dòng)一個(gè)的距離，得到 、分別稱為一輪迭代的始點(diǎn)、終點(diǎn)和反射點(diǎn)。始點(diǎn)、終點(diǎn)和反射點(diǎn)所對(duì)應(yīng)的函數(shù)值分別為：同時(shí)計(jì)算各中間點(diǎn)的函數(shù)值，并記為：（i=1,2,.,n)因此有，計(jì)算n個(gè)函數(shù)值之差，.，。記作： （i=1,2,.,n)其中最大者記作： (3)根據(jù)是否滿足判斷條件和，來確定是否要對(duì)原方向組進(jìn)行替換。若不滿足判別條件，則下輪迭代仍使用原方向組，并以、中函數(shù)值小者作為下輪迭代的始點(diǎn)。若滿足上述判別條件，則下輪迭代應(yīng)對(duì)原方向組進(jìn)行替換，將補(bǔ)充到原方向組的最后位置，而除掉。即新方向組為作為下輪迭代的搜索方向。下輪迭代的始點(diǎn)取

5、為沿方向進(jìn)行一維搜索的極小點(diǎn)。（4） 判斷是否滿足收斂準(zhǔn)則。若滿足則取為極小點(diǎn)，否則應(yīng)置，返回2，繼續(xù)進(jìn)行下一輪迭代。 這樣重復(fù)迭代的結(jié)果，后面加進(jìn)去的向量都彼此對(duì)G共軛，經(jīng)n輪迭代即可得到一個(gè)由n個(gè)共軛方向所組成的方向組。對(duì)于二次函數(shù)，最多n次就可找到極小點(diǎn)，而對(duì)一般函數(shù)，往往要超過n次才能找到極小點(diǎn)（這里“n”表示設(shè)計(jì)空間的維數(shù)）。 圖2.鮑威爾法的程序框圖 題目：用改進(jìn)的鮑威爾法求目標(biāo)函數(shù)的最優(yōu)解。已知初始點(diǎn)1,1T，迭代精度。解：初始點(diǎn)，初始搜索方向，。初始點(diǎn)處的函數(shù)值。第一輪迭代：1）沿方向進(jìn)行一維搜索，得 ： 為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件：所以算出一維搜索最佳步長(zhǎng) 得 從

6、而算出點(diǎn)處的函數(shù)值及沿走步后函數(shù)值的增量2） 再沿方向進(jìn)行一維搜索，得為一維搜索最佳步長(zhǎng)，應(yīng)滿足極值必要條件：所以算出一維搜索最佳步長(zhǎng) 得 從而算出第一輪終點(diǎn)處的函數(shù)值及沿走步后函數(shù)值的增量取沿，走步后函數(shù)值增量中最大者終點(diǎn)的反射點(diǎn)及其函數(shù)值為3）為確定下一輪迭代的搜索方向和起始點(diǎn)，需檢查判別條件和是否滿足。由于滿足Powell條件，則淘汰函數(shù)值下降量最大的方向，下一輪的基本方向組為 。構(gòu)成新的方向 此點(diǎn)為補(bǔ)充到原方程組的點(diǎn)，沿方向一維搜索得極小點(diǎn)和極小值： 此點(diǎn)為下一輪迭代初始點(diǎn)，按點(diǎn)距準(zhǔn)則檢驗(yàn)終止條件 需進(jìn)行第二輪迭代機(jī)算。第二輪迭代：此輪基本方向組為， ，分別相當(dāng)于， ，起始點(diǎn)為 。1）

7、沿方向進(jìn)行一維搜索得，過程同上，得：2）以為起點(diǎn)，沿 方向一維搜索得：確定此輪中函數(shù)值最大下降量及其相應(yīng)方向，取沿，走步后函數(shù)值增量中最大者終點(diǎn)的反射點(diǎn)及其函數(shù)值為檢驗(yàn)Powell條件，淘汰函數(shù)值下降量最大的方向，下一輪的基本方向組應(yīng)為 ， 。構(gòu)成新的方向 此點(diǎn)為補(bǔ)充到原方程組的點(diǎn)，沿方向一維搜索得極小點(diǎn)和極小值： 此點(diǎn)為下一輪迭代初始點(diǎn)，按點(diǎn)距準(zhǔn)則檢驗(yàn)終止條件 需進(jìn)行第三輪迭代機(jī)算。第三輪迭代：此輪基本方向組為， ，起始點(diǎn)為 ，先后沿， ，方向，進(jìn)行一維搜索，得， 檢驗(yàn)終止條件：故最優(yōu)解： 實(shí)際上，前兩輪迭代的， 為共軛方向，由于本例目標(biāo)函數(shù)是二次函數(shù)，按共軛方向的二次收斂性，故前兩輪的結(jié)果

8、就是問題的最優(yōu)解，但每一輪迭代都需要進(jìn)行n+1次迭代。 圖3.迭代過程圖附錄：#include <stdio.h>#include <math.h>#include <stdlib.h>#define m 5 /*數(shù)組長(zhǎng)度m >= 維數(shù)n */float f(float x);void mjtf(int n,float x0,float h,float s,float a,float b);void gold(int n,float a,float b,float flag,float x);void mbwef(int n,float x0,floa

9、t h,float flag,float a,float b,float x);/*目標(biāo)函數(shù)(n維)*/*入口參數(shù)： x ：n維數(shù)組，自變量 */*返回值 ：函數(shù)值 */float f(float x) float result; result=x0*x0+2*x1*x1-4*x0-2*x0*x1; return result;/*外推法子程序*/*入口參數(shù)： n ：優(yōu)化模型維數(shù) x0 ：n維數(shù)組，初始點(diǎn)坐標(biāo) h ：初始搜索步長(zhǎng) s ：n維數(shù)組，搜索方向 */*出口參數(shù)： a ：n維數(shù)組，搜索區(qū)間下限 b ：n維數(shù)組，搜索區(qū)間上限*/void mjtf(int n,float x0,float

10、 h,float s,float a,float b) int i; float x1m,x2m,x3m,f1,f2,f3; for(i=0;i<n;i+) /*計(jì)算初始兩試點(diǎn)*/ x1i=x0i; x2i=x0i+h*si; f1=f(x1); f2=f(x2); if(f2>=f1) /*判斷搜索方向*/ /*搜索方向?yàn)榉聪颍D(zhuǎn)身*/ h=(-1)*h; for(i=0;i<n;i+) x3i=x1i; f3=f1; for(i=0;i<n;i+) x1i=x2i; f1=f2; for(i=0;i<n;i+) x2i=x3i; f2=f3; /*搜索方向?yàn)檎?/p>

11、向*/ for(i=0;i<n;i+) /*計(jì)算第三試點(diǎn)*/ x3i=x2i+h*si; f3=f(x3); while(f3<f2) /*判斷是否未完成搜索*/ /*未完成，繼續(xù)搜索*/ h=2*h; for(i=0;i<n;i+) x1i=x2i; f1=f2; for(i=0;i<n;i+) x2i=x3i; f2=f3; for(i=0;i<n;i+) x3i=x2i+h*si; f3=f(x3); /*已完成*/ for(i=0;i<n;i+) /*輸出初始搜索區(qū)間*/ if(h>0) ai=x1i; bi=x3i; else ai=x3i;

12、 bi=x1i; /*黃金分割法子程序*/*入口參數(shù)： n ：優(yōu)化模型維數(shù) a ：n維數(shù)組，搜索區(qū)間下限 b ：n維數(shù)組，搜索區(qū)間上限 flag ：迭代精度 */*出口參數(shù)： x ：n維數(shù)組，極小點(diǎn)坐標(biāo) */void gold(int n,float a,float b,float flag,float x) int i; float x1m,x2m,f1,f2,sum; for(i=0;i<n;i+) /*計(jì)算初始兩試點(diǎn)*/ x1i=bi-(float)0.618*(bi-ai); f1=f(x1); for(i=0;i<n;i+) x2i=ai+(float)0.618*(bi

13、-ai); f2=f(x2); do if(f1<=f2) /*判斷消去區(qū)間*/ /*消去右區(qū)間*/ for(i=0;i<n;i+) bi=x2i; for(i=0;i<n;i+) x2i=x1i; f2=f1; for(i=0;i<n;i+) x1i=bi-(float)0.618*(bi-ai); f1=f(x1); else /*消去左區(qū)間*/ for(i=0;i<n;i+) ai=x1i; for(i=0;i<n;i+) x1i=x2i; f1=f2; for(i=0;i<n;i+) x2i=ai+(float)0.618*(bi-ai); f

14、2=f(x2); sum=0; for(i=0;i<n;i+) sum+=(bi-ai)*(bi-ai); while(sqrt(sum)>flag*0.1); /*判斷是否未達(dá)到精度要求，若未達(dá)到則返回繼續(xù)縮小區(qū)間*/ for(i=0;i<n;i+) xi=(float)0.5*(bi+ai); /*已達(dá)到，輸出極小點(diǎn)*/*鮑威爾法子程序*/*入口參數(shù)： n ：優(yōu)化模型維數(shù) x0 ：n維數(shù)組，初始點(diǎn)坐標(biāo) h ：初始搜索步長(zhǎng) flag ：迭代精度 a ：n維數(shù)組，搜索區(qū)間下限 b ：n維數(shù)組，搜索區(qū)間上限*/*出口參數(shù)： x ：n維數(shù)組，極小點(diǎn)坐標(biāo) */void mbwef(

15、int n,float x0,float h,float flag,float a,float b,float x) int i,j,k,r; float x1m,x2m,f0,f1,f2,fnm,smm,sum; for(i=0;i<n;i+) /*方向矩陣初始化*/ for(k=0;k<n;k+) /*初始搜索方向確定*/ if(i=k) sik=1; else sik=0; k=1; while(1) for(i=0;i<n;i+) x1i=x0i; for(i=0;i<n;i+) /*依次按每個(gè)方向搜索*/ mjtf(n,x1,h,si,a,b); /*調(diào)用外推

16、法子程序*/ gold(n,a,b,flag,x1); /*調(diào)用黃金分割法子程序*/ fni=f(x0)-f(x1); /*計(jì)算函數(shù)下降值*/ for(i=0;i<n;i+) /*計(jì)算映射點(diǎn)*/ x2i=2*x1i-x0i; for(i=1;i<n;i+) /*找出函數(shù)下降值中的最大值存入fn0*/ if(fn0<fni) fn0=fni; r=i; /*搜索方向累加*/ else r=0; f0=f(x0); /*計(jì)算始點(diǎn)、終點(diǎn)和映射點(diǎn)的函數(shù)值*/ f1=f(x1); f2=f(x2);if(f2>=f0|(f0-2*f1+f2)*(f0-f1-fn0)*(f0-f1

17、-fn0)>=0.5*fn0*(f0-f2)*(f0-f2) /*判斷是否需要換方向*/*不需要換*/ sum=0; /*計(jì)算一輪中終點(diǎn)與始點(diǎn)的距離*/ for(i=0;i<n;i+) sum+=(x1i-x0i)*(x1i-x0i); if(f1<=f2) /*判斷將終點(diǎn)還是將映射點(diǎn)賦給下一輪始點(diǎn)*/ for(i=1;i<n;i+) /*將終點(diǎn)賦給下一輪始點(diǎn)*/ x0i=x1i; else for(i=1;i<n;i+) /*將映射點(diǎn)賦給下一輪始點(diǎn)*/ x0i=x2i; else /*需要換*/ for(i=r;i<n;i+) /*去掉第r+1個(gè)方向，其它

18、方向前移*/ for(j=0;j<n;j+) sij=si+1j; for(i=0;i<n;i+) /*生成新方向放在最后*/ sni=x1i-x0i; mjtf(n,x1,h,sn,a,b); /*按新方向搜索一次*/ gold(n,a,b,flag,x1); sum=0; /*計(jì)算一輪中終點(diǎn)與始點(diǎn)的距離*/ for(i=0;i<n;i+) sum+=(x1i-x0i)*(x1i-x0i); for(i=0;i<n;i+) /*將終點(diǎn)賦給下一輪始點(diǎn)*/ x0i=x1i; if(sqrt(sum)<=flag) /*判斷是否滿足精度要求*/ break; else k+=1; for(i=0;i<n;i+) /*輸出極小點(diǎn)坐標(biāo)*/ xi=x1i;/*鮑威爾法主程序*/voi