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

机械优化设计鲍 威 尔 法班级：0841001成员：张波 2010213217张建 2010213214潘阳瑞 20102132272013 年 6 月鲍威尔法鲍威尔（Powell）法是直接利用函数值来构造共轭方向的一种方法。基本思想：在不用导数的前提下，在迭代中逐次构造 G 的共轭方向。一基本算法：（二维情况描述鲍威尔的基本算法）1）任选一初始点 x0，再选两个线性无关的向量，如坐标轴单位向量 e1=1,0T和e2=0,1T作为初始搜索方向。 2）从 x0出发，顺次沿 、 作一维搜索，得 、 点，两点连线得一新1e201x2方向 1d0xd用 代替 e1， 形成两个线性无关向量 ,e1，作为下一轮迭代的搜索方向。再d从 出发，沿 作一维搜索得点 ，作为下一轮迭代的初始点。 02 013）从 出发，顺次沿 、 作一维搜索，得到点 、 ，两点连线得一新方向: 1x2 x12。d沿 作一维搜索得点 ，即是二维问题的极小点 。2x*把二维情况的基本算法扩展到 n 维，则鲍威尔基本算法的要点是：在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和 n 个线性独立的搜索方向。从始点出发顺次沿 n 个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来 n 个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。图 1.二维情况下的鲍威尔法 二改进算法在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏” ，这是产生向量组线性相关的原因所在。在改进的算法中首先判断原向量组是否需要替换。如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。为此，要解决两个关键问题：（1） 是否较好？是否应该进入新的方向组？即方向组是否进行更新？1kd（2）如果应该更新方向组， 不一定替换方向 ，而是有选择地替换某一方1kdkd1向 。km改进算法的具体步骤：（1）给定初始点 （记作 ） ，选取初始方向组，它由 n 个线性无关的向量 ，0x0 01d,., 所组成，置 。02d0nk（2）从 出发，顺次沿 ， ，.， 作一维搜索得 ， ，.， 。接kkd12kndkx12knx着以 为起点，沿方向 knxknx0移动一个 的距离，得到 k0 knkn001)(、 、 分别称为一轮迭代的始点、终点和反射点。始点、终点和反射点所对应k0n1的函数值分别为：)(00kxfF2n13k同时计算各中间点的函数值，并记为： （i=1,2,.,n)(kiif因此有 ，0fFnf2计算 n 个函数值之差 ， ，.， 。102fnf1记作： （i=1,2,.,n)iii其中最大者记作： minim11ax(3)根据是否满足判断条件 和03F，来确定是否要对原方向组进行230220320 )(5.)(F替换。若不满足判别条件，则下轮迭代仍使用原方向组，并以 、 中函数值小者作knx1为下轮迭代的始点。若满足上述判别条件，则下轮迭代应对原方向组进行替换，将 补充到原方向kd组的最后位置，而除掉 。即新方向组为 作为下轮迭kmd nkmkd1121 ,.,.代的搜索方向。下轮迭代的始点取为沿 方向进行一维搜索的极小点 。kn 0kx（4）判断是否满足收敛准则。若满足则取 为极小点，否则应置 ，10kx1k返回 2，继续进行下一轮迭代。这样重复迭代的结果，后面加进去的向量都彼此对 G 共轭，经n 轮迭代即可得到一个由 n 个共轭方向所组成的方向组。对于二次函数，最多 n 次就可找到极小点，而对一般函数，往往要超过 n 次才能找到极小点（这里“n”表示设计空间的维数） 。 图 2.鲍威尔法的程序框图 题目：用改进的鲍威尔法求目标函数 的最优211221214)(xxxf解。已知初始点1,1T，迭代精度 。01.解：初始点 ，初始搜索方向， 。初始点处的函数值10x012ed。3)(0fF第一轮迭代：1）沿 方向进行一维搜索，得 ： 1d11010100 为一维搜索最佳步长，应满足极值必要条件：134minin)( 201001 dxfxf)(421所以算出一维搜索最佳步长 得 310x从而算出 点处的函数值及沿 走步后函数值的增量01d7)(011f42）再沿 方向进行一维搜索，得02d3101231020102 2x为一维搜索最佳步长，应满足极值必要条件：27minin)( 2020102 dff)(42所以算出一维搜索最佳步长 5.得 3.102x从而算出第一轮终点 处的函数值及沿 走步后函数值的增量02d.7)(02f521取沿 ， 走步后函数值增量中最大者01d24,max21终点 的反射点及其函数值为02x52135.100203 7)(33fF3）为确定下一轮迭代的搜索方向和起始点，需检查判别条件和 是否满足。20220320 5.)(Fmm 03F由于满足 Powell 条件，则淘汰函数值下降量最大的方向 ，下一轮的基本方向组为1e。032,de构成新的方向 25.0135.100203 x此点 为补充到原方程组的点，沿 方向一维搜索得极小点和极小值： 03 3d97)(,18.371f此点 为下一轮迭代初始点，按点距准则检验终止条件 1x86.2210x需进行第二轮迭代机算。第二轮迭代：此轮基本方向组为 ， ，分别相当于 ， ，起始点为 。2e03d12d110x1）沿 方向进行一维搜索得，过程同上，得：298.7)(,18.391 xfx2）以 为起点，沿 方向一维搜索得：10361296.312确定此轮中函数值最大下降量及其相应方向，8.10.2取沿 ， 走步后函数值增量中最大者2e03d8.,max21终点 的反射点及其函数值为12x12.488.37196.34110213 )(33fF检验 Powell 条件，淘汰函数值下降量最大的方向 ，下一轮的基本方向组应为 2e03d， 。13d构成新的方向 16.0248.37196.34101213 x此点 为补充到原方程组的点，沿 方向一维搜索得极小点和极小值： 13 3d)(,242f此点 为下一轮迭代初始点，按点距准则检验终止条件 2x36.07.18.(220x需进行第三轮迭代机算。第三轮迭代：此轮基本方向组为 ， ，起始点为 ，先后沿 ， ，方向，进03d120x203d1行一维搜索，得， 421x42检验终止条件： 0故最优解： 8)(,*42* xf实际上，前两轮迭代的 ， 为共轭方向，由于本例目标函数是二次函数，按13d2共轭方向的二次收敛性，故前两轮的结果就是问题的最优解，但每一轮迭代都需要进行 n+1 次迭代。图 3.迭代过程图附录：#include #include #include #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,float 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 h,float s,float a,float b)int i;float x1m,x2m,x3m,f1,f2,f3;for(i=0;i=f1) /*判断搜索方向*/ /*搜索方向为反向，转身*/h=(-1)*h;for(i=0;i0)ai=x1i;bi=x3i;elseai=x3i;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;iflag*0.1); /*判断是否未达到精度要求，若未达到则返回继续缩小区间*/for(i=0;i=f0|(f0-2*f1+f2)*(f0-f1-fn0)*(f0-f1-fn0)=0.5*fn0*(f0-f2)*(f0-f2) /*判断是否需要换方向*/*不需要换*/sum=0; /*计算一轮中终点与始点的距离*/for(i=0;in“);printf(“维数: 2n“);n = 2;printf(“请输入初始点:“);for(i=0;in;i+)printf(“nx0%d=“,i);scanf(“%f“,printf(“n请输入初始步长:n“);scanf(“%f“,printf(“n请输入精度:n“);scanf(“%f“,