A-simplex-method-for-function-minimization

AsimplexmethodforfunctionminimizationByJ.A.NelderandR.MeadfAmethodisdescribedfortheminimizationofafunctionofnvariables,whichdependsonthecomparisonoffunctionvaluesatthe(n4-1)verticesofageneralsimplex,followedbythereplacementofthevertexwiththehighestvaluebyanotherpoint.Thesimplexadaptsitselftothelocallandscape,andcontractsontothefinalminimum.Themethodisshowntobeeffectiveandcomputationallycompact.AprocedureisgivenfortheestimationoftheHessianmatrixintheneighbourhoodoftheminimum,neededinstatisticalestimationproblems.Spendleyetal.(1962)introducedaningeniousideafortrackingoptimumoperatingconditionsbyevaluatingtheoutputfromasystematasetofpointsformingasimplexinthefactor-space,andcontinuallyformingnewsimplicesbyreflectingonepointinthehyperplaneoftheremainingpoints.Thisideaisclearlyapplicabletotheproblemofminimizingamathematicalfunctionofseveralvariables,aswasrecognizedbytheseauthors.However,theyassumedthattherelativestepstobemadeinvaryingthefactorswereknown,andthismakestheirstrategyratherrigidforgeneraluse.Inthemethodtobedescribedthesimplexadaptsitselftothelocalland-scape,elongatingdownlonginclinedplanes,changingdirectiononencounteringavalleyatanangle,andcontractingintheneighbourhoodofaminimum.Thecriterionforstoppingtheprocesshasbeenchosenwithaneyetoitsuseforstatisticalproblemsinvolvingthemaximizationofalikelihoodfunction,inwhichtheunknownparametersenternon-linearly.ThemethodWeconsider,initially,theminimizationofafunctionofnvariables,withoutconstraints.Po,Pu...Pnarethe(n+1)pointsinn-dimensionalspacedefiningthecurrentsimplex.[Thesimplexwillnot,ofcourse,beregularingeneral.]WewriteytforthefunctionvalueatPhanddefinehasthesuffixsuchthatyh=max(.,)[hforhigh]and/asthesuffixsuchthatyl=min(j,)[/forlow].Furtherwedefinepasthecentroidofthepointswithi#h,andwrite[P/Pj]forthedistancefromP,toPj.AteachstageintheprocessPhisreplacedbyanewpoint;threeoperationsareused—reflection,contraction,andexpansion.Thesearedefinedasfollows:thereflectionofPhisdenotedbyP*,anditsco-ordinatesaredefinedbytherelationP*=(1+*)P-ocPhwhereaisapositiveconstant,thereflectioncoefficient.ThusP*isonthelinejoiningPhandP,onthefarsidetNationalVegetableResearchStation,Wellesbourne,Warwick.ofpfromPhwith[P*p]=oc[PhP].Ify*liesbetweenyhandyhthenPhisreplacedbyP*andwestartagainwiththenewsimplex.Ify*yhi.e.ifreflectionhasproducedanewminimum,thenweexpandP*toP**bytherelationP**=yP*+(1-y)P.Theexpansioncoefficienty,whichisgreaterthanunity,istheratioofthedistance[P**P]to[P*P].Ify**ytwereplacePhbyP**andrestarttheprocess;butify**y,thenwehaveafailedexpansion,andwereplacePhbyP*beforerestarting.IfonreflectingPtoP*wefindthaty*y,forall/^=h,i.e.thatreplacingPbyP*leavesy*themaximum,thenwedefineanewPhtobeeithertheoldPhorP*,whicheverhastheloweryvalue,andformP**=pPh+(1-ft?.Thecontractioncoefficientj8lies_between_0and1andistheratioofthedistance[P**P]to[PP].WethenacceptP**forPhandrestart,unlessy**min(yh,y*),i.e.thecontractedpointisworsethanthebetterofPhandP*.ForsuchafailedcontractionwereplacealltheP,'sby(P,+P,)/2andrestarttheprocess.Afailedexpansionmaybethoughtofasresultingfromaluckyforayintoavalley(P*)butatanangletothevalleysothatP**iswellupontheoppositeslope.Afailedcontractionismuchrarer,butcanoccurwhenavalleyiscurvedandonepointofthesimplexismuchfartherfromthevalleybottomthantheothers;con-tractionmaythencausethereflectedpointtomoveawayfromthevalleybottominsteadoftowardsit.Furthercontractionsarethenuseless.Theactionpro-posedcontractsthesimplextowardsthelowestpoint,andwilleventuallybringallpointsintothevalley.Thecoefficientsa,jS,ygivethefactorbywhichthevolumeofthesimplexischangedbytheoperationsofreflection,contractionorexpansionrespectively.ThecompletemethodisgivenasaflowdiagraminFig.1.Afinalpointconcernsthecriterionusedforhaltingtheprocedure.ThecriterionadoptedissomewhatdifferentfromthatusedbyPowell(1964)inthatitisconcernedwiththevariationintheyvaluesoverthe308FunctionminimizationINTERCalculateinitialp^amiy.iDetermineh,calculatePFormP=(i+a)P-aPhCalculatey•is'-No-isy*y1?YesFormP**=(i+yJP*-TPCalculatey•isKyyi?isy*y.,i^h?INoNo-YesReplacePhbyP**ReplaceP.byPHasminimumbeenreached?-NoFig.1.—FlowdiagramReplacePhbyP*FormP**=£Ph+(A-§)PCalculatey»*-YesNoReplaceallReplacePhbyP*-)EXITsimplexratherthanwithchangesinthex's.Theformchosenistocomparethestandarderrorofthey'sintheform*/{Y,(y,—~y)2/n}withapre-setvalue,andtostopwhenitfallsbelowthisvalue.Thesuccessofthecriteriondependsonthesimplexnotbecomingtoosmallinrelationtothecurvatureofthesurfaceuntilthefinalminimumisreached.Thereasoningbehindthecriterionisthatinstatisticalproblemswhereoneisconcernedwithfindingtheminimumofanegativelikelihoodsurface(orofasum-of-squaressurface)thecurvatureneartheminimumgivestheinformationavailableontheunknownparameters.Ifthecurvatureisslightthesamplingvarianceoftheestimateswillbelargesothereisnosenseinfindingtheco-ordinatesoftheminimumveryaccurately,whileifthecurvatureismarkedthereisjustificationforpinningdowntheminimummoreexactly.ConstraintsonthevolumetobesearchedIf,forexample,oneofthex,mustbenon-negativeinaminimizatio