机械优化设计——鲍威尔法

1、机械优化设计鲍 威 尔 法 班级：0841001 成员：张波2010213217张建2010213214潘阳瑞20102132272013年6月鲍威尔法鲍威尔（Powell）法是直接利用函数值来构造共轭方向的一种方法。基本思想：在不用导数的前提下，在迭代中逐次构造G 的共轭方向。一基本算法：（二维情况描述鲍威尔的基本算法）1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=1,0T和e2=0,1T作为初始搜索方向。 2）从x0出发，顺次沿、作一维搜索，得 、 点，两点连线得一新方向 用 代替e1，形成两个线性无关向量,e1，作为下一轮迭代的搜索方向。再从出发，沿作一维搜索得点，

2、作为下一轮迭代的初始点。 3）从出发，顺次沿、作一维搜索，得到点、 ，两点连线得一新方向: 。沿作一维搜索得点，即是二维问题的极小点。把二维情况的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。 图1

3、.二维情况下的鲍威尔法 二改进算法在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。为此，要解决两个关键问题：（1）是否较好？是否应该进入新的方向组？即方向组是否进行更新？（2）如果应该更新方向组，不一定替换方向，而是有选择地替换某一方向。改进算法的具体步骤： （1）给定初始点（记作），选取初始方向组，它由n个线性无关的向量，,.,所组成

4、，置。 （2）从出发，顺次沿，.，作一维搜索得，.，。接着以为起点，沿方向 移动一个的距离，得到 、分别称为一轮迭代的始点、终点和反射点。始点、终点和反射点所对应的函数值分别为：同时计算各中间点的函数值，并记为：（i=1,2,.,n)因此有，计算n个函数值之差，.，。记作： （i=1,2,.,n)其中最大者记作： (3)根据是否满足判断条件和，来确定是否要对原方向组进行替换。若不满足判别条件，则下轮迭代仍使用原方向组，并以、中函数值小者作为下轮迭代的始点。若满足上述判别条件，则下轮迭代应对原方向组进行替换，将补充到原方向组的最后位置，而除掉。即新方向组为作为下轮迭代的搜索方向。下轮迭代的始点取

5、为沿方向进行一维搜索的极小点。（4） 判断是否满足收敛准则。若满足则取为极小点，否则应置，返回2，继续进行下一轮迭代。 这样重复迭代的结果，后面加进去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于二次函数，最多n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里“n”表示设计空间的维数）。 图2.鲍威尔法的程序框图 题目：用改进的鲍威尔法求目标函数的最优解。已知初始点1,1T，迭代精度。解：初始点，初始搜索方向，。初始点处的函数值。第一轮迭代：1）沿方向进行一维搜索，得 ： 为一维搜索最佳步长，应满足极值必要条件：所以算出一维搜索最佳步长 得 从

6、而算出点处的函数值及沿走步后函数值的增量2） 再沿方向进行一维搜索，得为一维搜索最佳步长，应满足极值必要条件：所以算出一维搜索最佳步长 得 从而算出第一轮终点处的函数值及沿走步后函数值的增量取沿，走步后函数值增量中最大者终点的反射点及其函数值为3）为确定下一轮迭代的搜索方向和起始点，需检查判别条件和是否满足。由于满足Powell条件，则淘汰函数值下降量最大的方向，下一轮的基本方向组为 。构成新的方向 此点为补充到原方程组的点，沿方向一维搜索得极小点和极小值： 此点为下一轮迭代初始点，按点距准则检验终止条件 需进行第二轮迭代机算。第二轮迭代：此轮基本方向组为， ，分别相当于， ，起始点为 。1）

7、沿方向进行一维搜索得，过程同上，得：2）以为起点，沿 方向一维搜索得：确定此轮中函数值最大下降量及其相应方向，取沿，走步后函数值增量中最大者终点的反射点及其函数值为检验Powell条件，淘汰函数值下降量最大的方向，下一轮的基本方向组应为 ， 。构成新的方向 此点为补充到原方程组的点，沿方向一维搜索得极小点和极小值： 此点为下一轮迭代初始点，按点距准则检验终止条件 需进行第三轮迭代机算。第三轮迭代：此轮基本方向组为， ，起始点为 ，先后沿， ，方向，进行一维搜索，得， 检验终止条件：故最优解： 实际上，前两轮迭代的， 为共轭方向，由于本例目标函数是二次函数，按共轭方向的二次收敛性，故前两轮的结果

8、就是问题的最优解，但每一轮迭代都需要进行n+1次迭代。 图3.迭代过程图附录：#include <stdio.h>#include <math.h>#include <stdlib.h>#define m 5 /*数组长度m >= 维数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);/*目标函数(n维)*/*入口参数： x ：n维数组，自变量 */*返回值 ：函数值 */float f(float x) float result; result=x0*x0+2*x1*x1-4*x0-2*x0*x1; return result;/*外推法子程序*/*入口参数： n ：优化模型维数 x0 ：n维数组，初始点坐标 h ：初始搜索步长 s ：n维数组，搜索方向 */*出口参数： a ：n维数组，搜索区间下限 b ：n维数组，搜索区间上限*/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+) /*计算初始两试点*/ x1i=x0i; x2i=x0i+h*si; f1=f(x1); f2=f(x2); if(f2>=f1) /*判断搜索方向*/ /*搜索方向为反向，转身*/ 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; /*搜索方向为正

11、向*/ for(i=0;i<n;i+) /*计算第三试点*/ x3i=x2i+h*si; f3=f(x3); while(f3<f2) /*判断是否未完成搜索*/ /*未完成，继续搜索*/ 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+) /*输出初始搜索区间*/ if(h>0) ai=x1i; bi=x3i; else ai=x3i;

12、 bi=x1i; /*黄金分割法子程序*/*入口参数： n ：优化模型维数 a ：n维数组，搜索区间下限 b ：n维数组，搜索区间上限 flag ：迭代精度 */*出口参数： x ：n维数组，极小点坐标 */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+) /*计算初始两试点*/ 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) /*判断消去区间*/ /*消去右区间*/ 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 /*消去左区间*/ 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); /*判断是否未达到精度要求，若未达到则返回继续缩小区间*/ for(i=0;i<n;i+) xi=(float)0.5*(bi+ai); /*已达到，输出极小点*/*鲍威尔法子程序*/*入口参数： n ：优化模型维数 x0 ：n维数组，初始点坐标 h ：初始搜索步长 flag ：迭代精度 a ：n维数组，搜索区间下限 b ：n维数组，搜索区间上限*/*出口参数： x ：n维数组，极小点坐标 */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+) /*依次按每个方向搜索*/ mjtf(n,x1,h,si,a,b); /*调用外推

16、法子程序*/ gold(n,a,b,flag,x1); /*调用黄金分割法子程序*/ fni=f(x0)-f(x1); /*计算函数下降值*/ for(i=0;i<n;i+) /*计算映射点*/ x2i=2*x1i-x0i; for(i=1;i<n;i+) /*找出函数下降值中的最大值存入fn0*/ if(fn0<fni) fn0=fni; r=i; /*搜索方向累加*/ else r=0; f0=f(x0); /*计算始点、终点和映射点的函数值*/ 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; /*计算一轮中终点与始点的距离*/ for(i=0;i<n;i+) sum+=(x1i-x0i)*(x1i-x0i); if(f1<=f2) /*判断将终点还是将映射点赋给下一轮始点*/ for(i=1;i<n;i+) /*将终点赋给下一轮始点*/ x0i=x1i; else for(i=1;i<n;i+) /*将映射点赋给下一轮始点*/ x0i=x2i; else /*需要换*/ for(i=r;i<n;i+) /*去掉第r+1个方向，其它

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; /*计算一轮中终点与始点的距离*/ for(i=0;i<n;i+) sum+=(x1i-x0i)*(x1i-x0i); for(i=0;i<n;i+) /*将终点赋给下一轮始点*/ x0i=x1i; if(sqrt(sum)<=flag) /*判断是否满足精度要求*/ break; else k+=1; for(i=0;i<n;i+) /*输出极小点坐标*/ xi=x1i;/*鲍威尔法主程序*/voi