无约束最优化方法.ppt
5.8 5.8 单纯形法单纯形法目录一、单纯形法基本原理 二、单纯形法迭代步骤二、单纯形法迭代步骤 三、单纯形法有关说明三、单纯形法有关说明 四、习题四、习题单纯形法是利用比较简单几何图形各顶点的目标函数值,在连续改变几何图形的过程中,逐步以目标函数值较小的顶点取代目标函数值最大的顶点,而求优点的方法,属于直接法。一、单纯形法基本原理 现以求二元函数的极小点为例现以求二元函数的极小点为例,说明单纯形法形成原理。说明单纯形法形成原理。设设二二元元函函数数f f(X X )=)=f f(x x1 1,x x2 2)在在x x1 1x x2 2平平面面上上取取不不共共线线的的三三个个点点X X1 1,X X2 2,X X3 3，以以此此为为顶顶点点构构一一单单纯纯形形三三角角形形.算算出出各各顶顶点点的的函函数数值值f f(X X1 1),),f f(X X2 2),),f f(X X3 3),比比较较其其大大小小,现现设设有有f f(X X1 1)f f(X X2 2)f f(X X3 3)。这这说说明明X X1 1最最差差,X X3 3最最好好,X X2 2次次差差.为为了了寻寻找找极极小小点点,一一般般来来说说应应向向最最差差点点的的反反对对称称方方向向进进行行搜搜索索.以以X X4 4记记为为X X2 2 X X3 3的的中中点点在在X X1 1 X X4 4的的延延长长线上取点线上取点X X5 5,使使 称为称为X X5 5为为X X1 1关于关于X X4 4的反射点的反射点.如图如图5.155.15。图 5.15算出算出X5 5 的函数值的函数值f(X5 5),可能有下列情形可能有下列情形:f(X5)f(X3).搜索方向正确,可进一步扩张,继续沿X X1X X5向前搜索(扩张).,其中为扩张因子扩张因子,可取如f(X X6)f(X X5),则扩张不利,舍去X X6,以X X5代替X X1构新单纯形X X2,X X3,X X5.几种情形的讨论几种情形的讨论 (4)若 方向上所有点的函数值 都大于 ,则不能沿此方向搜索.这时,可以以 为中心进行缩边,若使顶点 和 向 移近一半距离(如图图5.16所示),得新单纯形 .以此单纯形为基础再进行寻优.这时取 f f(X X X X3 3)f f(X X X X5 5)f f(X X X X2 2).).这这说说明明搜搜索索方方向向正正确确,无无须须扩扩张张,以以X X X X5 5代代替替 X X X X1 1构构成成新新的的单单纯形纯形 X X X X2 2,X X X X3 3,X X X X5 5.f f(X X X X2 2)f f(X X X X5 5)f f(X X1 1).).这时应更多压缩,将新点压缩至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维维情情况况下下,一一个个单单纯纯形形含含有有n n +1+1个个顶顶点点,计计算算工作量较大工作量较大,但原理和上述二维情况相同但原理和上述二维情况相同.二、单纯形法迭代步骤二、单纯形法迭代步骤 已知设已知设X X为为n n维变量维变量,目标函数为目标函数为f f(X X),),终止限为终止限为 构造初始单纯形构造初始单纯形 在在n n维维空空间间中中选选初初始始点点X X0 0(离离最最优优点点越越近近越越好好),),从从X X0 0出出发发,沿沿各各坐坐标标方方向向以以步步长长t t移移动动得得n n个个顶顶点点 ,这这样样选选择择顶顶点点可可保保证证向向量量组组 线线性性无无关关,否否则则,就就会会使使搜搜索索范范围围局局限限在在较较低低维维的的空空间间内内,可可能能找找不不到极小点到极小点.当然当然,在各坐标方向可以走不同的距离在各坐标方向可以走不同的距离.步步长长t t的的范范围围可可取取0.515.0,0.515.0,开开始始时时常常取取t t=1.52.0,=1.52.0,接接近近最最优点时要减小优点时要减小,例如取例如取0.51.0.0.51.0.计算各顶点的函数值计算各顶点的函数值 比较各函数值的大小,确定最好点XL、最差点XH及次差点 XG,即计算计算X XH H之外各点的之外各点的“重心重心”求出反射点求出反射点扩张扩张 当当f f(X Xn n+2+2)f f(X XL L),),需扩张需扩张,令令 如如f f(X Xn n+3+3)f f(X Xn n+2+2),),则以则以X Xn n+3+3代替代替X XH H形成一新单纯形形成一新单纯形;否则否则,以以代代X Xn n+2+2替替X XH H构成新单纯形构成新单纯形.转转(8).(8).无扩缩无扩缩当当f f(X XL L)f f(X Xn n+2+2)f f(X XG G),),以代以代X Xn n+2+2替替X XH H构成新单纯形构成新单纯形.转转(8).(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).收敛性检验收敛性检验每每次次得得新新单单纯纯形形后后,即即应应进进行行收收敛敛性性检检验验,如如满满足足收收敛敛指指标标,则则迭迭代代停停止止,X XL L即即为为所所求求的的近近似似解解.否否则则,继继续续进进行行迭迭代代计计算算.常用的收敛准则是常用的收敛准则是或或1 1和和2 2为预先给定的允许误差为预先给定的允许误差.单单纯纯形形法法的的流流程程如如图图试用单纯形法求试用单纯形法求 的极小值的极小值.解解 选X0=(8,9)T,并取 X1=(10,11)T和X2=(8,11)T.这三点不共线,它们作为初始单纯形的顶点(如图所示).然后计算各顶点的函数值:，可知X1为最差点,X0为最好点.以X3表示 X0和 X2的重心,则 例例5.65.6(P(P118118)续解例续解例续解例续解例5.65.65.65.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)减小到110-6.在图中给出了前几次迭代的情形.续解例续解例5.65.6三、单纯形法有关说明三、单纯形法有关说明 本算法上机占用内存很少本算法上机占用内存很少,对变量不多且精度要求不高的对变量不多且精度要求不高的问题此法很方便问题此法很方便,但当变量个数多于但当变量个数多于1010以上以上,此法就显得此法就显得不十分有效不十分有效.四.习题习题五习题五习题五习题五 （P119P119P119P119）T8T8 用单纯形法求解用单纯形法求解用单纯形法求解用单纯形法求解min f(x).min f(x).min f(x).min f(x).题解程序参见题解程序参见 谢谢！
