f =f(X - S )= f(-0.01,0.50)=-0.2698
f沿着-S 方向减小,f(X - S )= f(- ,0.50)=2 -2 -0.25, =0, = ,因此X = X - S = .
现在我们尽量减少f沿着S = 到X = 方向,
f =f(X )=-0.75, f =f(X + S )=f(-0.5,0.51)=-0.7599< f ,
f沿着+S 方向减小,因此
f(X + S )=f(-0.5,0.5+ )= - -0.75, =0, =
这给出了
X = X + S =
方法二:模式搜索
现在我们生成第一个模式方向
S = X - X = - =
同时最大限度减少f 沿着S 到 X 方向,因此
f =f(X )=-1.0
f =f(X + S )=f(-0.5-0.005,1+0.005)
=f(-0.505,1.005)=-1.004975
f 沿着S 正方向减小
f(X + S )=f(-0.5-0.5 ,1.0+0.5 )
=0.25 -0.50 -1.00
=0, =1,因此
X = X + S = +1.0 =
点X 可以确定为最佳点。
如果在这一阶段不承认X 为最佳点,我们继续减少f沿S = 到X 方向。这样我们将得到
f =f(X )=-1.25 f =f(X + S )> f
f =f(X - S )> f
这表明f不能沿着S 方向最小化,因此X 将是最佳点。在这个例子中,收敛在第二个周期中已经完成了。在这种情况下,f作为一个二次函数,所使用的方法即二次收敛法。
6.8 单纯形方法
定义:单纯形 在n维空间中一组n+1个点的集合所形成的几何图形,被称为单纯形。当点是等距离时,单纯形据说是常规的。因此,在二维空间中,单纯形是一个三角形,而在三维空间中则是一个四面体。
单纯形法的基本思路是比较一般单纯形在n+1个顶点的目标函数值,并在迭代过程中逐步走向最佳点。下列公式可以用来在n维空间中生成大小为a的普通单一顶点(在二维空间中的等边三角形)[6.10]:
X =X +pu + , i=1,2,…,n (6.46)
这里
p= ( +n-1) q= ( -1) (6.47)
这个单纯形法不应该与线性规划的单纯形法混为一谈,其中X 是最初的基准点,u 是沿第j个坐标轴的单位向量,这种方法最初是由Spendley,Hext先生和Himsworth先生提出来的,后来经Nelder和Mead发展起来[6.11]。单纯形法的运动是通过三种操作形成的,即反射,收缩和扩张。
6.9.1 反射
如果X 是单一顶点中与最高目标函数值相一致的顶点,我们预期反射在对面面上的点X 可以获得X 的最小值。若是这样的情况,我们可以通过拒绝单一的点X 包括新的点X 来构建一个新的单纯形法,这个过程在图6.11中阐明了。如图6.11a,点X ,X ,X 形成了原始的单形,点X ,X 和X 形成新的单纯形。同样的,如图6.11b,原始的单纯形是由X ,X ,X 和X 给出的,新的则由X ,X ,X 和X 给出。此外,我们可以通过原来的单纯形法来构建一个新的,这个新的单纯形法是通过拒绝与最高函数值相一致的顶点形成的。