§2多变量函数极值问题解法(直接法)

本节讨论求目标函数

在定义区域上的最优解的直接方法(或试验最优化方法)，其中

  (表示矢量的转置)

表示自变量组成的列矢量，由于极小和极大只是目标函数相差一符号，因此这里只讨论求维列矢量使得

这时，称为最优解(最优点)。

[单峰函数]  如果函数在所讨论的区域上只有一个极值点(最大点或最小点)，那末称这个函数为多变量单峰函数。

多变量单峰函数也可用分析定义。例如，设函数定义在区域上，由于区域上的任一路线都可用一参数方程

表示，所以函数沿这条路线也可用参数表示为

   设                       

又设                           

如果                   ,当

,当

那末称函数在区域上从点和点的路线上是单峰的，式中

   设              

如果对区域上的任一对点和，都存在一条从经过到的路线，在其上函数是单峰的，那末称函数在区域上为单峰的.

[因素交替法]  这个方法是轮流按坐标轴方向探索最优点.设为第i个坐标轴的单位矢量，即

并且预先给定允许误差那末，迭代程序如下：

(1)  选取初始点.

(2)  由初始点出发，先沿第一个坐标轴方向进行优选(用§1的单因素方法)，得到好点，即

式中为实参数.然后以为起点沿第二个坐标轴方向进行优选，得到好点，即

如此等等，一直到个方向全部优选完毕，得到，它满足

(3)  再以为新的初始点，重复步骤(2)。

(4)  以上步骤一直进行到从某一初始点出发，经过个方向搜索后得不到新点，或与前个初始点之间的距离都小于预先给定的允许误差为止。这时即为最优点的近似解。

[平行线法]  如果处理的双因素问题中，有一个因素难于调整，而另一个因素却容易变动，这时用双因素交替法就不太方便，应改用下面的平行线法：

把难于调整的因素放在纵轴上(图18.5)，设其可调范围为[0,]，把容易变动的因素放在横轴上，设其可调范围为[0，].先把因素固定在点处，在过这点而平行于横轴的直线上对因素在[0，]上优选，好点为①；再把固定在点处，在过这点而平行于横轴的直线上对因素在[0，]上优选，好点为②；比较①与②两点的好坏，如果②比①好，就去掉直线的上半部(如果①比②好，就去掉直线的下半部)，然后把因素固定在可调范围的处，在过这点而平行于横轴的直线上对因素在[0，]上优选，好点为③；比较②与③两点的好坏，如果②比③好，就去掉直线的下半部如此继续做下去把优选范围不断缩小，就可以找到最优点的近似解。

对因素的选择也可采用分数法。

[瞎子爬山法]  迭代过程如下：

(1)          (1)      选取初始点(基点)的步长，命。

(2)          (2)      进行第k阶段的第l次方向(即轴方向)的局部探索

其中为第l个坐标轴的单位矢量，首先沿正方向探索

V

如果，则探索成功，就把这点作为下一次沿第l+1个坐标轴方向探索的起点，并命；否则就沿反方向搜索

如果，则探索成功，就把这点作为下一次沿第l+1个坐标轴方向探索的起点，并命；如果正反方向探索都失败就退回原处，即命

并命。

当沿各个坐标轴方向的局部探索都轮流进行后，这个阶段的局部探索也就完成了，这时得到第k阶段的最好点。

(3)          (3)      命，以为新基点，重复步骤(2),如果不能得到更好的点，就缩小步长再进行局部探索，直到步长缩小到规定的精度为止，这时所得最好点即为最优点的近似解。

瞎子爬山法(也称探索爬山法)虽然没有前面几个方法快，但它特别适用于因素不能大幅度调动，或是在大生产中如果出一次废品就造成很大损失的情况。

[陡度法与对角线法]

1°  陡度和陡度法  设在,两点已经做试验，其目标函数值分别为(图18.6)，而且，那末

称为从上升到的陡度.对维空间有类似的定义。

陡度大的方向目标函数显然上升得快一些.所谓陡度法，就是利用已得的试验结果，算出各点间的陡度，然后沿陡度最大的方向(有利方向)再取点做试验。

2°  联合法(瞎子爬山法与陡度法联合使用)  例如用瞎子爬山法从点出发，沿轴方向调动因素得到点,效果较好，仍沿轴方向调动因

素得到点(图18.7)，效果还是好的，然后沿轴方向

调动因素得到点，效果也好，接下去就不一定从出

发再沿纵横方向去探索了。这时可以分别算出目标函数由

上升到的陡度，由上升到的陡度，由上升到

的陡度，从中选出一个陡度最大的方向，例如，那末

下一次就可以沿的方向往上爬了，这时可以从点出

发沿线段的延长线用瞎子爬山法往上爬，也可以在

上应用单因素的方法优选，一般总可以找出一个比好的点.

3°  对角线法  以上我们通过比较，从通过点的三个方向的陡度挑出一个较陡的方向来，例如是,但并

不一定过点的最陡方向，其实只要利用过点的二个方向的陡

度就可以找出过点的更陡的方向来。

如图18.8,在过垂直于的方向上取一点，使

的长等于到的陡度，且和分别在的两侧；再在

过垂直于的方向上取一点，使的长等于到

的陡度，且和分别在的两侧，以，为边

作平行四边形，其对角线的方向就是在点的陡度最大

的方向。

    [步长加速法] 步长加速法实际上是瞎子爬山法和沿有利方向加速相结合的方法.其迭代程序如下：

(1)              (1)     选取初始点(基点)和步长，命。

(2)              (2)     瞎子爬山(程序见瞎子爬山法)。

    当沿各个坐标轴方向的局部探索都轮流进行后，这个阶段的局部探索也就完成了，下一步就可沿有利方向进行加速。

(3)              (3)     加速爬山。命。若，那末移到新的位置进行加速试探，

在此

    有两种情形可能产生：

    1°  如果的数值有改进，那末命,应用步骤(2)的方法开始新的探索。

    2°  如果的数值没有改进，那末取消这个加速，将基点放在上次发现的最好点，即。命，象步骤(2)一样开始一个新的局部探索。

    如果经过一个阶段后发现不能加速移动，那末就缩小步长重复步骤(2)。如果逐次缩小步长都不能加速移动，这点便是最优点的近似解。

   步长加速法在二维的情形如图18。9所示。

    [方向加速法(共轭方向法)]  迭代程序如下：

    (1)  从前面的最好数值位置(可以是前一次迭代最后所确定的点或用其他方法所得的好点)和一组线性独立的探索方向(可以取坐标轴的方向)出发。首先寻找过点平行于的直线上的最好点设为，再找过点平行于的直线上的最好点设为，继续这个过程直到所有n个探索方向都已试探过，最后所得点为。

    (2)  寻找特殊点，这个点使目标函数的数值同前一点相比改进最大，即点给出个移动的最大改变量，其中。此外决定矢量。

    (3)  计算

    (4)  记如果

                                      (1)

或

            (2)

那末不是探索中的好方向，则应重新开始探索，从最后一点出发并用同样的方法，即和，重复步骤(1)。如果不等式(1),(2)都不满足，那末沿方向探索直到找到极小点。将这个点定义为，而k+1阶段的新探索方向为;;又。然后从步骤(1)出发重复整个过程，直到,其中为预先给定的允许误差。

    例 应用方向加速法找出目标函数

的极小点。

    解 应用导数的方法容易求出目标函数的绝对极小点为。下面用方向加速法来求出这个极小点。

    从点开始探索，探索方向用和。

    第一阶段  从基点出发，沿方向进行一维探索，移动距离由使

到达极小，得到，因此，而目标函数值由减少到。再沿方向用同样的方法探索，得到，同时。

为决定下一阶段是否用方向，应检验不等式(1)，计算点,而,由于 ，所以下一阶段不用方向。

第二阶段  本阶段的方向和前一阶段的一样(因为不采用)。相继探索得到，而又，而。再计算点。在此，由于，不等式(1)不满足。再检验不等式(2)，计算

式中是目标函数在给定方向的最大改变量，即。不等式(2)的右端是

因此不等式(2)不满足，即下一阶段可以采用方向

，沿方向探索得到第三阶段的基点为，并且。

第三阶段  本阶段的探索方向为和。沿这两个方向探索将发现不能再前进，因为事实上前一阶段已经找到绝对极小点。当然，这是不足为奇的，因为目标函数是二次的。

[方向步长双加速法]  迭代程序如下：

考虑第k阶段

(1)    (1)           选择一初始点(基点)，一组步长和一组方向，其中，上指标表示第个阶段，下指标表示第个方向。当时，一般选择探索方向平行于坐标轴方向。

(2)    (2)           依次平行于n个方向的每一个进行相继探索，若移动是成功的，则采用新点，若移动不成功则保留基点。若在一给定方向的移动是成功的，则下一次再在这个方向上探索时，步长将增大为倍；若失败，则缩小为倍，负号表示在反方向探索。一般取。

(3)    (3)           直到在每一个方向上都至少有一次成功，一次失败，这时沿该方向的探索就告结束。依次沿平行于n个方向的探索完毕后最后一次成功的点为新的基点。下一阶段(即第阶段)的探索方向，由下列方程计算得到：

首先定义矢量

其中是在方向的所有成功移动的代数和，

然后方向由下式给出

其中

特别，其中主要方向

它的各个分量为

(4)    (4)           以上步骤一直进行到(为预先给定的允许误差)为止，所得最后的基点就近似于最优点。

方向步长双加速法在二维的情况如图18.10所示。

[单纯形调优法]  迭代程序如下：

(1)    (1)           命n维空间的单纯形的n+1个顶点为，计算函数值，比较大小，并确定

(2)    (2)           求出最坏点的对称点

式中                          

(3)    (3)           若，则将缩小为，由下式定义：

这里要求，是避免的情形发生。

如果，那末，并重复以上步骤。

如果，那末，并重新开始迭代。

(4)    (4)           若，则将扩大为，由下式定义：

扩大的条件也可以换成

或                     

如果上述条件满足，并且

那末                              

否则                              

并重复以上步骤。

上述过程一直继续到

或                               

为止，其中是预先给定的正数。