搜索
鲍威尔法鲍威尔（Powell）法又称方向加速度法，它是利用共轭方向可以加快收敛速度的性质形成的一种搜索方法。该方法不用对目标函数求导，当目标函数的导数不连续时也能应用，因此，鲍威尔法是一种十分有效的直接搜索法。一共轭方向的概念与共轭向量的性质（一）共轭方向设A为n阶实对称正定矩阵，若有两个n维向量和能满足A=0则称向量与对矩阵A共轭，共轭向量的方向称为共轭方向。（二）共轭向量的性质设A为n×n阶实对称正定矩阵，（i=1,2,…n）是关于A的n个互相共轭的非零向量，对于正定二次函数f(x)的极小化寻优问题，从任何初始点出发，依次沿方向经n次一维搜索即可收敛到极小点=沿n元二次正定函数的n个共轭方向进行n次一维搜索就可达到目标函数的极小点。二鲍威尔法（一）鲍威尔法的基本原理和迭代过程（1）采用坐标轮换法顺次沿n个坐标方向进行一维搜索，然后以初始点和终点构成一个新的方向，并依此方向为搜索方向再作一维搜索得到极小点（2）取始点=，并去掉原搜索方向组中的第一个方向=，而将第一轮构成的新搜索方向作为最末一个方向，以此组成第二轮迭代的n个方向。依次进行下去，直到获得满足迭代收敛精度要求的近似极小点为止。根据这一原理构造的迭代算法称为鲍威尔基本算法。（二）鲍威尔法的缺陷鲍威尔基本算法不可能对每一个都起作用，因为在迭代过程中的n个搜索方向有时会变成线性相关的，而不能形成共轭方向，导致随后的迭代搜索在降维（退化）的空间中进行，可能求不到极小点，故而进行改进。（三）鲍威尔修正算法为了避免这种“退化”现象的发生，鲍威尔对这一算法进行了修正。即在每一轮产生新的搜索方向后，首先判断原搜索方向组是否可以直接用下一轮迭代的方向组，若可以，即用。否则，还要进一步判断原搜索方向组中哪个方向上的函数值下降量最大，然后再用新搜索方向替换这个下降量最大的搜索方向，以保证逐次生成共轭方向，即每一轮迭代的搜索方向组线性无关。其中：—第k起始点函数值—k轮方向组一维搜索终点函数值—对的映射点函数值—第k轮方向组沿诸方向一维搜索所得的各函数下降量中最大者，其对应的方向即是鲍威尔修正算法的判别条件（四）鲍威尔法的计算步骤（1）给定初始点和计算精度，即取初始方向组为n个单位坐标向量。（2）沿各方向进行一轮n次一维搜索即：minf(+a)=f(+)得到:=这一步相当于最优步长的坐标轮换法。（3）经计算求出共轭方向和映射点分别为=（4）计算k轮中相邻两点目标函数值的下降量，并求出下降量最大者及其相应的方向并求出（5）计算判断是否成立若成立，则由出发沿方向进行一维搜索，求出目标函数f(x)的极小点，并作为k+1轮的初始点，然后进行k+1轮搜索，挤掉，同时把放在方向组的最后构成新一轮的方向组。（6）若上述判断条件不成立，则k+1轮的初始点和方向组为=即此时k+1轮的n个搜索方向全部用第k轮的搜索方向。（7）每轮迭代结束，都应检验收敛条件，若能满足：则可输出最优解，迭代结束。否则进入下一轮迭代，即转步骤（2）（5）计算举例例：用鲍威尔法求目标函数的最优解（极小值）。已知，初始点，收敛精度满足进行第二次循环总结：（1）共轭方向及共轭向量（2）鲍威尔修正算法，判别条件及计算步骤。