常用无约束最优化方法 单纯形.ppt

§ 单纯形法
目录
一、单纯形法基本原理
二、单纯形法迭代步骤
三、单纯形法有关说明
四****题
单纯形法是利用比较简单几何图形各顶点的目标函数值,在连续改变几何图形的过程中,逐步以目标函数值较小的顶点取代目标函数值最大的顶点,而求优点的方法,属于直接法。
一、单纯形法基本原理
现以求二元函数的极小点为例,说明单纯形法形成原理。
设二元函数f(X )=f(x1,x2)在x1x2平面上取不共线的三个点X1, X2,X3,以此为顶点构一单纯形——(X1),f(X2),f(X3),比较其大小,现设有f(X1)>f(X2)>f(X3)。这说明X1最差, X3最好,, X3的中点在X1 X4的延长线上取点X5,使
称为X5为X1关于X4的反射点. 。
图
算出X5 的函数值f(X5 ),可能有下列情形:
⑴ f(X5)<f(X3).
搜索方向正确,可进一步扩张,继续沿X1X5向前搜索(扩张). ,
其中α为扩张因子,可取
如f(X6)<f(X5),则扩张有利,以X6代替X1构新单纯形{X2,X3,X6}.如f(X6)>f(X5),则扩张不利,舍去X6,以X5代替X1构新单纯形{X2,X3,X5}.
几种情形的讨论
(4) 若方向上所有点的函数值都大于,,可以以为中心进行缩边,若使顶点和向移近一半距离(),.
这时取
⑵ f(X3)<f(X5)<f(X2).
这说明搜索方向正确,无须扩张,以X5代替 X1构成新的单纯形{X2,X3,X5}.
⑶ f(X2)<f(X5)<f(X1).
这表示X5走得太远,,
则有
,以X7代替X1构成新的单纯形{X2,X3,X7}.
⑷ f(X5)>f(X1).
这时应更多压缩,将新点压缩至X1X4之间,有
注意,(X8)<f(X1),则以X8代替X1构成新的单纯形{X2,X3,X8}. 否则可以认为X1X4方向上所有点的函数值f(X)都大于 f(X1)不能沿
,可以以X3为中心进行
缩边,使顶点X1和X2向X3移近一半距离如
右图所示,
以此单纯形为基础再进行寻优.
得新单纯形{X3,X9,X10}.
可见,不管如何,都可得到一新的单纯形,,,一个单纯形含有n +1个顶点,计算工作量较大,但原理和上述二维情况相同.
二、单纯形法迭代步骤
已知设X为n维变量,目标函数为f(X) ,终止限为
⑴构造初始单纯形
在n维空间中选初始点X0(离最优点越近越好),从X0出发,沿各坐标方向以步长t移动得n个顶点,这样选择顶点可保证向量组线性无关,否则,就会使搜索范围局限在较低维的空间内,,在各坐标方向可以走不同的距离.
~,开始时常取t=~,接近最优点时要减小,~.