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

本节讨论求目标函数

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

  (表示矢量的转置)

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

这时,称为最优解(最优点)

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

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

   

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

                            

又设                            

如果                    ,当

,当

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

                   

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

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

  

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

(1)  选取初始点.

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

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

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

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

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

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

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

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

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

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

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

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

V

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

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

并命

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

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

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

[陡度法与对角线法]

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

      

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

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

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

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

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

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

上升到的陡度,由上升到的陡度,由上升到

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

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

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

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

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

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

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

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

的长等于的陡度,且分别在的两侧;再在

垂直于的方向上取一点,使的长等于

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

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

的方向。

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

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

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

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

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

在此

    有两种情形可能产生:

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

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

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


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

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

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

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

    (3)  计算

    (4)  如果

                                      (1)

            (2)

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

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

的极小点。

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

    从点开始探索,探索方向用

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

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

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

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

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

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

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

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

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

考虑第k阶段

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

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

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

首先定义矢量

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

然后方向由下式给出

其中

特别,其中主要方向

它的各个分量为

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


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

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

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

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

式中                          

(3)           ,则将缩小为由下式定义:

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

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

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

(4)           ,则将扩大为由下式定义:

扩大的条件也可以换成

                      

如果上述条件满足,并且

那末                              

否则                              

并重复以上步骤。

上述过程一直继续到

                                

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



V 在此采用矢量记号

它代表维空间的一点.上标k表示搜索的第k个阶段,下标l表示第k个阶段搜索中的第l次循环.表示搜索中的基点序列,则当接近最优点时,有