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

§5.8单纯形法编辑课件目录一、单纯形法根本原理二、单纯形法迭代步骤三、单纯形法有关说明四、习题编辑课件 单纯形法是利用比较简单几何图形各顶点的目标函数值,在连续改变几何图形的过程中,逐步以目标函数值较小的顶点取代目标函数值最大的顶点,而求优点的方法,属于直接法。编辑课件一、单纯形法根本原理

现以求二元函数的极小点为例,说明单纯形法形成原理。设二元函数f(X)=f(x1,x2)在x1x2平面上取不共线的三个点X1,X2,X3，以此为顶点构一单纯形——三角形.算出各顶点的函数值f(X1),f(X2),f(X3),比较其大小,现设有f(X1)>f(X2)>f(X3)。这说明X1最差,X3最好,X2次差.为了寻找极小点,一般来说应向最差点的反对称方向进行搜索.以X4记为X2X3的中点在X1X4的延长线上取点X5,使称为X5为X1关于X4的反射点.如图5.15。编辑课件图5.15编辑课件算出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)假设方向上所有点的函数值都大于,那么不能沿此方向搜索.这时,可以以为中心进行缩边,假设使顶点和向移近一半距离(如图5.16所示),得新单纯形.以此单纯形为根底再进行寻优.这时取编辑课件⑵f(X3)<f(X5)<f(X2).这说明搜索方向正确,无须扩张,以X5代替X1构成新的单纯形{X2,X3,X5}.⑶f(X2)<f(X5)<f(X1).这表示X5走得太远,应缩回一些.假设以β表示压缩因子,那么有常取β为0.5,以X7代替X1构成新的单纯形{X2,X3,X7}.编辑课件⑷

f(X5)>f(X1).这时应更多压缩,将新点压缩至X1X4之间,有注意,上两式只是X1和X5的差异.如f(X8)<f(X1),那么以X8代替X1构成新的单纯形{X2,X3,X8}.否那么可以认为X1X4方向上所有点的函数值f(X)都大于f(X1)不能沿此方向搜索．这时,可以以X3为中心进行缩边,使顶点X1和X2向X3移近一半距离如右图所示,以此单纯形为根底再进行寻优.得新单纯形{X3,X9,X10}.编辑课件可见,不管如何,都可得到一新的单纯形,其中至少有一顶点的函数值比原单纯形为小.如此继续,直至满足终止准那么.在n维情况下,一个单纯形含有n+1个顶点,计算工作量较大,但原理和上述二维情况相同.编辑课件二、单纯形法迭代步骤

设X为n维变量,目标函数为f(X),终止限为⑴构造初始单纯形在n维空间中选初始点X0(离最优点越近越好),从X0出发,沿各坐标方向以步长t移动得n个顶点,这样选择顶点可保证向量组线性无关,否那么,就会使搜索范围局限在较低维的空间内,可能找不到极小点.当然,在各坐标方向可以走不同的距离.步长t的范围可取0.5~15.0,开始时常取t=1.5~2.0,接近最优点时要减小,例如取0.5~1.0.编辑课件⑵计算各顶点的函数值比较各函数值的大小,确定最好点XL、最差点XH及次差点XG,即编辑课件⑶计算XH之外各点的“重心〞求出反射点⑷扩张当f(Xn+2)<f(XL),需扩张,令

如f(Xn+3)<f(Xn+2),那么以Xn+3代替XH形成一新单纯形;否那么,以代Xn+2替XH构成新单纯形.转(8).⑸无扩缩当f(XL)≤f(Xn+2)<f(XG),以代Xn+2替XH构成新单纯形.转(8).编辑课件⑹收缩.当f(XG)≤f(Xn+2)<f(XH)时,那么需收缩,令以代Xn+4替XH构成新单纯形.并转(8).⑺缩边.当f(XH)≤f(Xn+2),令,如果f(XH)≤f(Xn+5),那么将单纯形缩边,可将向量Xi-XL的长度缩小一半,即这样可得一新单纯形.否那么,以Xn+5代替XH形成一新单纯形.转(8).编辑课件⑻收敛性检验每次得新单纯形后,即应进行收敛性检验,如满足收敛指标,那么迭代停止,XL即为所求的近似解.否那么,继续进行迭代计算.常用的收敛准那么是或ε1和ε2为预先给定的允许误差.编辑课件单纯形法的流程如图编辑课件试用单纯形法求的极小值.解选X0=(8,9)T,并取X1=(10,11)T和X2=(8,11)T.这三点不共线,它们作为初始单纯形的顶点(如以下图).然后计算各顶点的函数值:，可知X1为最差点,X0为最好点.以X3表示X0和X2的重心,那么例5.6

(P118)编辑课件续解例5.6反射点由于f(X4)<f(X0),故需扩张.取α=2,那么编辑课件因为f(X5)<f(X4),故以X5代替X1,由X5,X0和X2构成新单纯形,然后进行下一个循环.该问题的最优解为X*=(5,6)T,f(X

*)=0.经32次循环,可把目标函数f(X)减小到1

10-6.在图中给出了前几次迭代的情形.续解例5.6编辑课件三、单纯形法有关说明

本算法上机占用