二维鲍威尔基本算法的优化及问题防范

现针对二维的情况，描述鲍威尔的基本算法，如图10-5所示。

图10-5 二维情况的鲍威尔法

1）任选一初始点X⁰，再选两个无关向量，如坐标轴单位向量e₁=[1 0]^T和e₂=[0 1]^T作为初始搜索方向。

2）从X₀出发，顺次沿e₁、e₂作一维搜索得到点X¹₁和X₂¹，两点连线得新方向，S^（1）=X₀^（1）-X₂^（1）并沿S¹进行一维寻优，得到下一轮的搜索起点X²₀。用S¹代替e₁形成两个线性无关向量e₂、S¹，作为下一轮迭代的搜索方向。(www.xing528.com)

3）从X₀^（2）出发，顺此沿e₂、S¹作一维搜索，得到点X²₁、X²₂，两点连线得新方向，S（2）=X₀^（2）-X₂^（2）沿S²进行一维寻优，对于二次函数，即可得到其最优解。

按照与上面分析相同的方法，可以把二维情况下的基本算法扩展到n维，则鲍威尔基本算法的要点是：在每一轮迭代总有一个起始点（第一轮的起始点是任选的初始点）和n个线性独立的搜索方向。从始发点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向，而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。因为这种方法在迭代中逐次生成共轭方向，而共轭方向是较好的搜索方向，所以鲍威尔法又称为方向加速法。

应该指出的是，如果图10-5中的计算起点X₀充分靠近X¹₁，则新生成的收敛方向S₁与保留的方向e₂就有可能线性相关，从而导致方向置换的退化，为此必须对上述鲍威尔法进行改进，防止方向的退化。