Powell算法总

这是一种最优化算法，可以用于求解多元方程式的解。

1. 预备知识

对于任意一个n维非线性函数，若其至少二阶连续可微，则可将其在某一点处，进行泰勒展开，保留其二阶项，写成：

略去二次以上高阶项，并将其写成如下形式：

若取，则上式变为如下一般形式：

注意，其中（表示 ，其余类似）：A为n*n矩阵，b为n*1列向量，c为常量。

…（1）

…（2）

…（3）

以上A、b在powell算法迭代过程中用于更新步长，步长计算公式为：

…（4）

其中表示搜索起始点。

2. 算法流程

例程：用powell算法求函数的最小值点，计算收敛精度。

开始：

0. 首先将函数写成一般形式：

1. 第一步，求一阶偏导数：
2. 第二步，求二阶偏导数：
3. 得到,

1. 第一轮迭代，

1. 取初始点，上标（k）表示迭代次数，下标表示第几个解，计算出初始点对应的函数值；
2. 选取n个（n为未知数的个数）搜索方向，搜索方向为一组线性不相关（不共线）的向量即可，此处选择；
3. 计算第一步搜索的最优步长，首先将初始点位置代入步长计算公式（4），则第一步的最优步长为；根据第一步的最优步长和初始点，计算得到的第一步的解：；
4. 计算第二步搜索的最优步长，将代入步长计算公式（4），求得第二步搜索最优步长；根据第二步的最优步长和搜索起始点，得到第二步的解：；
5. 计算第3（即额外的n+1）个搜索方向，；
6. 计算方向上的反射点：；
7. 计算相邻两点函数值的下降量：
   1. 计算各个点函数值
   2. 计算下降量
   3. 找到下降最快的搜索方向，；
8. 检验二个Powell判别条件：
   1. 计算；
   2. 是否满足条件，此处满足；
   3. 是否满足，此处满足；
   4. 由于两个Powell条件都满足，因此用共轭方向替换最速下降方向，并求方向上的极小值点（先计算最优步长=22.5/45.5,然后从点出发做一维搜索，得到），将此点作为下一轮迭代的出发点 。
9. 若上述两个条件有一个不满足，则下一轮迭代的搜索方向不变，出发点为函数值最小点。

1. 第k轮迭代，重复上一步过程；
2. 每次迭代结束时，验证收敛精度是否达到要求，即两轮迭代的最小值点是否满足：或；若满足条件则停止迭代，输出最小值点，若不满足则继续迭代。