【doc】无约束优化问题的再改进单纯形法

【doc】无约束优化问题的再改进单纯形法无约束优化问题的再改进单纯形法?第1l謇太原重量机械举院学摄V.1-I】Nt2-t2?~OURNJIL乙OFtJIL1YUJILNHEArYMACHINERYINST1TUtE?鲁O无约束优化问题的再改进单纯形法杨晋(基础部)提要本文对原有的单地形法进行了再改进,使其计算量减少,速度加快.关键谒单纯开;反射廷忡O引言对于无约束的优化问题,在直接法中有一种行之有效的,即单纯形法.最初的单纯形法是由SpendleyHext和Himsworth在1962年提出来的rj.那时鼠是利用正规单纯形进行反射过程来搜索,速度较慢.在l965年由Nelder和Mead改进成为变型的单纯形法r,提出了一个改进的单纯形法f".他的主要想法是:最大值的顶点xrJ沿单纯形中心方向反射后得到点xr,如果xj姓的函数值比原单纯形中的任何一个顶点处的值都小,则认为方向xfJ—xr是一个较好的下降方向,因此继续沿这一方向下降到最低点.这种方法加遗了搜索的速度.详细的计算方法可参阅.下面提出的一种单纯形法是在原改进单纯形法的基础上进行了又一处的改进.故称之为再改进单纯形法.这种方法使计葬量进一步减少,从而更加快了搜索的速度.1再改进之处再改进的地方是使原来以最大值顶点沿单纯形中心方向反射,变为以最大值顶点浩^V单纯形最小值顶点方向反射即对于一个单纯形找出最大值顶点x与最小值顶点x,则认V^为方向x—x是一个较好的反射方向,在这个方向进行反射得到新的一点x,如果点-xj处的值比点X处的值还小,则又认舫向x—x是一个较好的下降方向,因此继续梧韦妻{}日葺I:1..,.82l26太原重机学院'.-1990JF-——…一…一————:?,一…_ll一J一?.一一这一方向下降刊甚低点,如果在线段i—i上有一点处的值比点j处的值还小,?取这点为新顶点,其,钥同,因此在这代过程巾电用了反目,},7:',8fqt,收缩和压缩四种运算,这在二卸桐题上可以得到直观的几何意义,如图l所示.2计算步骤在迭代过程中我们记^f=)=iliax{,),fCx..'),…,,(f)}一.,,f=(r)=mi1"1f(.),f(.),…,f(f)):其中r.I,r,…,,是n维宅间巾单纯形的.I+1个顶点.再改进单纯形法的迭代运算由下述四种运算组成:i)反射J令…=r^J-I-yCxrJ—(J,).其中>0为给定的反射系数.,,.li)延伸J当』)<f时,令=…+aC,.z"一)...其中a>0为?给定的延伸系数,若…)<F(r…一),删改…代替I,否则以代替i<ij.iii)收缩;f"')?f时,有两种情形,a),rI)?,,b)f(r…)<^?...^,,此时将向量r一,.收缩(在b)的情形先以代缸…,,)代替,],'...^冷f?=f『j+似r'一r),其中0<<1为给定的收缩系数,当,?')<,时,呆收缩成功,以fnl1J代替).一.iv)压缩;当,(,sj?时,令,:{(+,产ilo'1,2,…,n;.下面是此单纯形法的计算步骤.…0一.-,第2期无约束优化问题的再馥进单纯形法取初始,,…,},给定参'黧n>0,0<<1)0.1.J计算f.:f?)i=0,1,2…,‰2.}按顺序找出最大值和最小值及相应的顶点,'}}?:.'?l<:f(o??n)30;检验o?ma?x{II"一一'I{?,成立取为极小点,,(),为极小值停机.否则做下而运算.…4.;取,+-J_+V一),:fr…),若?f则做9.,否则做下面运算.5.若+?}??做7.,否则取:r一+,J+a(,+=f(xr一)).6.,着+2?+】,令r川净fJ,f+lf做lO,否贝?做8..7.;若f+?,令:,,(f"j)f做,否91II做下面运算.8.,令r?,2净,做1O.^,^^V9.取r'J-茹4-卢(一),,…)=f+3,若一.?,则令}'+)净fiJ,f=0,1,2,….七做10.,否则令rJ-)r『J,.+5fj做下面运算.10.,令f+l,做2..5优点,.从上述计算步骤中可以看出,本单纯形法的主要优点是J?在每次迭代中都比躁单纯形法少算一个单纯形中心点,即:[ixr1)-x].?反射后的点的值不必与原?单纯形中每一个顶点的值进行比较.?从最大值顶点沿最小值顶点的方向进行反射.?和图2原单纯形甚在三难蘧算示意图?使得计算量在一次迭代中大为减少,?使得迭代次数减少,搜索的速度进一步加侠,如图2是原单纯形法在二维上的运算示意图,与图l相比,在同图同位置上用同一个初始单纯形进行运算暇显图l优于图2.在运算中的参数a,F,要根据具体情况进行选歌,一般可28太原童机学院】990丰选取a,口:;,r:1进行参考.4程序框图根据上述计算步骤,此单纯形的程序框图如下计鼻'7lttt?,lll:c—'')矗:,.…O=P.I刊年f..[(x?),J=D.1.2.^lIa?{l.{『lJ-f|…:lf}一,f'…x一】If.."…JJ90:丁,世一I_一一????第2期无约束优化问题的再改进单纯开J击5例子例求解minf(,z):4(一)似2—6).取初始点为r.=(8,9),为了计算方便,我们不取等边三有形,而是取直角三角形作为初始单纯形,并取r=l,:,a=1,三个顶点为Xr.一(8,9),xr一(1O,11),J=(8i11)求出相应于三点的函数值为f.=45,=125,,z=65.^A故f=111ax{,o,fl,,2}=i25=,【="f=mi1"1{f.,,【,f2)=45:f.:r.j首先试验反射运算fJ=2x—=(6,7)f3:,(j)=5由于f.<,.,故反射成功,所以下面试验延伸运算.J-j+专(;一;)=(5'6)fs=f(xc'J)=o由于f.<,.,故延伸成功,此时得出三个新的顶点及函数值为.J=(8,9),,lJ_(5,6),r.(8,11)f.=45,f1=0,=65下面开始第2次迭代,max(f口,,1,,4)=65=,:,mi11{.,f,,)=0=,,=膏f.J=r】J反射f,=2x—=(2,1),,8=f()BI由于f.>,,故反射失败.进行吸缩,由于fs<f:,所以取=(2,1),这时,5J一21(+)=(3.5,3.5),,=,()=15.25由于,<,():61,故收缩成功,取r2j=(3.5,3.5),.=15..25.现将前五次迭代列表如下;太原童机学院1990.晕迭代狄数lxi(0x2(0)fo毒J…t二—一:.0一二…i一.,sls,st,s65511.255,756.7528l28xl'){(1)fil()z(2,f2战功运算l01ll25延伸x—jx【I)收缩l0):争x(】IL5603,53.5l5.25救维x(】__,'0】5603.53,515,25收缩x'5】:争(】5604,25753.8l25收缩x'5)(0J5BoI4,25,5——————}6结束语再改进单纯形法可以象原单纯形法一样,类似地经过改造后推广到约束优化问题上,形成复合形法,电可以和别的声法混合使用,使搜索的速度更加侠,目标更加准确.这些有待于在今后的研究和实中得到进一步的完善.参考文献lM'阿佛里耳.非线析分性与方法(下册)上海科学挂术出版枉.1980.P23.2葛人溥蝙.实用非线性最优化中计算方法.西安交通大学即.1984.P1683同1.P31.4同2.P171.5席少霖,赵风自骗.最优化计算方法.上海科学技术出版枉.1984.p77.???第0期无约束优亿问题的苒改进单纯形法AReimprovedSimplexMethodforNbn~restictedOptimizationProblemYang)i11^BSTRACT31ThispapercarrieSoutreimpr0Vment0ntheorigi11alsimplOxmethod,tomakecomputationjessandfaster.KeyWordssimplex,reglection,exte11sion