算法框图与4.8.2迭代过程

1.鲍威尔方法的基木算法

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

图4-16 二维情况下的鲍威尔方法

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

2）从X^（0）出发，顺次沿e₁、e₂做一维搜索得点X₁^（0）、X₂^（0），两点连线得一新方向

S^（1）=X₂^（0）-X^（0）

用S^（1）代替e₁形成两个线性无关的向量e₂、S¹，作为下一轮迭代的搜索方向。再从X₂^（0）出发，沿S^（1）做一维搜索得X₀^（1），并将其作为下一轮迭代的初始点。

3）从X₀^（1）出发，顺次沿e₂、S^（1）做一维搜索得点X₁^（1）、X₂^（1），两点连线得一新方向

S^（2）=X₂^（1）-X₀^（1）

X₀^（1）、X₂^（1）两点是从不同点X^（0）、X₁^（1）出发，分别沿S^（1）方向迸行一维搜索而得的极小点，因此X₀^（1）、X₂^（1）两点连线的方向S^（2）同S^（1）一起对G共轭。再从X₂^（1）出发，沿S^（2）做一维搜索得点X^（2）。

因为X^（2）相当于从X^（0）出发分别沿G的两个共轭方向S^（1）、S^（2）迸行两次一维搜索而得到的点，所以X^（2）点即是二维问题的极小点X^*。

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

上述基本算法仅具有理论意义，不要说对于一般函数，就是对于二次函数，这个算法也可能失效，因为在迭代中的n个搜索方向有时会变成线性相关而不能形成共轭方向。这时张不成n维空间，可能求不到极小点，所以上述基本算法有待改迸。

2.改进的鲍威尔算法

在鲍威尔基本算法中，每一轮迭代都用连接始点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的“好坏”，这是产生向量组线性相关的原因所在。因此在改迸的算法中首先判断原向量组是否需要替换。如果需要替换，还要迸一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。

改迸算法的具体步骤如下：

1）给定初始点X^（0）（记作X₀^（0））。选取初始方向组，它由n个线性无关的向量S₁^（0）、S₂^（0）、…、S_n^（0）（如n个坐标轴单位向量e₁、e₂、…、e_n）所组成，置k←0。

2）从X₀^（k）出发，顺次沿S₁^（k）、S₂^（k）、…、S_n^（k）做一维搜索得X₁^（k）、X₂^（k）、…、X_n^（k）。接着以X_n^（k）为起点，沿方向

S_n+1^（k）=X_n^（k）-X₀^（k）

移动一个X_n^（k）-X₀^（k）的距离，得到(www.xing528.com)

X_n+1^（k）=X_n^（k）+（X_n^（k）-X₀^（k））=2X_n^（k）-X₀^（k）

X₀^（k）、X_n^（k）、X_n+1^（k）分别称为一轮迭代的始点、终点和反射点。始点、终点和反射点所对应的函数值分别表示为

F₀=f（X₀^（k））

F₂=f（X_n^（k））

F₃=f（X_n+1^（k））

同时计算各中间点处的函数值，并记为

f_i=f（X_i^（k））（i=0，1，2，…，n）

因此有F₀=f₀，F₂=f_n

计算n个函数值之差f₀-f₁、f₁-f₂、…、f_n-1-f_n

记作Δ_i=f_i-1-f_i（i=1，2，…，n）

其中最大者记作

3）根据是否满足判别条件F₃＜F₀或（F₀-2F₂+F₃）（F₀-F₂-Δ_m）2＜0.5Δ_m（F₀-F₃）²来确定是否要对原方向组迸行替换。

若不满足判别条件，则下轮迭代仍用原方向组，并以X_n^（k）、X_n+1^（k）中函数值小者作为下轮迭代的始点。

若满足上述判别条件，则下轮迭代应对原方向组迸行替换，将S_n+1^（k）补充到原方向组的最后位置，而除掉S_m^（k）。即新方向组为S₁^（k）、S₂^（k）、…、S_m-1^（k）、S_m+1^（k）、…、S_n^（k）、S_n+1^（k）作为下轮迭代的搜索方向。下轮迭代的始点取为沿S_n+1^（k）方向迸行一维搜索的极小点X₀^（k+1）。

4）判断是否满足收敛准则。若满足则取X₀^（k+1）为极小点，否则应置k←k+1返回2），继续迸行下一轮迭代。

这样重复迭代的结果，后面加迸去的向量都彼此对G共轭，经n轮迭代即可得到一个由n个共轭方向所组成的方向组。对于二次函数，最多不超过n次就可找到极小点，而对一般函数，往往要超过n次才能找到极小点（这里的“n”表示设计空间的维数）。

改迸后的鲍威尔方法程序框图如图4-17所示。

鲍威尔方法是鲍威尔于1964年提出的，以后又经过他本人的改迸。该方法是一种有效的共轭方向法，它可以在有限步内找到二次函数的极小点。对于非二次函数只要具有连续二阶导数，用这种方法也是有效的。

图4-17 改迸后的鲍威尔方法的程序框图