坐标轮换法及最优步长法的应用

坐标轮换法是一种不计算函数梯度，而是通过函数值本身，即可求出寻优方向，因而也称为直接寻优法。在以后提到的鲍威尔（Powell）法也属于直接寻优法。

对于坐标轮换法，我们做个比喻：如果我们在北京的老城区找一个地方，我们可以沿着经纬线去找。这个比喻为我们提供了一种思路，即可以取坐标的方向为寻优的方向，这就是坐标轮换法。它在每次搜索中，只允许一个变量的变化，其余量保持不变，即沿坐标方向轮流进行搜索的方法。该方法把多变量的优化问题轮流转化成一系列单变量的优化问题。

对于n个变量的寻优函数，若在第k轮沿第i个坐标方向S^k_i=e_i进行搜索，则迭代公式为

其中搜索方向取坐标方向，即S^k_i=e_i（i=1，2，…，n）。若‖X^k_n-X₀^k‖＜ε，则X^*←X^k_n，否则X₀^k+1←X^k_n，进行下一轮搜索，一直到满足精度要求为止。其搜索路径如图10-1所示。

图10-1 坐标轮换法搜索路径

这种方法的收敛效果与目标函数等值线形有很大关系。如果目标函数为二元二次函数，其等值线为圆或长短轴平行于坐标轴的椭圆时，此法很有效，经过两次搜索即可达到最优点，如图10-2所示。如果等值线为长短轴不平行于坐标轴的椭圆，则需多次迭代才能达到最优点，但因坐标轮换法是沿坐标方向搜索而不是沿脊线搜索，所以就终止到脊线上而不能找到最优点。

图10-2 坐标轮换法的收敛精度

从上述分析可以看出，采用坐标轮换法只能轮流沿着坐标方向搜索，尽管也能使函数值步步下降，但经过曲折迂回的路径才能到达极值点；尤其极值点附近步长很小，收敛很慢，所以坐标轮换法不是一种很好的搜索方法。但是可以构造很好的搜索策略，下面讨论的鲍威尔法就是这种情况。

例10-1 已知f（X）=x²₁+x²₂-x₁x₂-10x₁-4x₂+60，设初始点：X（0）=[0，0]^T，精度ε=0.1，用最优步长法的坐标轮换法求目标函数的最优值。

解：1.作第一轮迭代计算

1）沿x₁的单位坐标方向进行一维搜索：

2）按最优步长法确定α₁：

minf（X₁^（1））=α²₁-10α₁+60(www.xing528.com)

采用一维优化方法求出：α₁=5，即：

3）沿x₂的单位坐标方向进行一维搜索：

4）按最优步长法确定α₂：

minf（X₂^（1））=α²₂-9α₂+35

采用一维优化方法求出：α₂=4.5，即

5）检验精度要求：

不满足要求：取X₀^（2）=X₂^（1）继续迭代。

2.各轮迭代计算见下表：

经5轮迭代满足终止条件，得近似最优解：

坐标轮换法的程序框图如图10-3所示。

图10-3 坐标轮换法的程序框图