Directsearchmethods:thenandnow直接搜索法：历史和现状RobertMichaelLewis1,a,VirginiaTorezon2,*,,ba,MichaelW.Trossetac,aICASE,MailStop132C,NASALangleyResearchCenter,Hampton,VA23681-2199.USAbDepartmentofComputerScience,CollegeofWilliam&Mary,P.O.Box8795,Williamsburg,VA23187-8795,USAcDepartmentofMathematics,CollegeofWilliam&Mary,P.O.Box8795,Williamsburg,VA23187-8795,USAReceived1July1999;receivedinrevisedform23February2000Abstract摘要我们讨论无约束优化的直接搜索法。我们从现在的观点来看这类与导数无关的算法，主要集中在1960到1971年的直接搜索法发展的黄金时期。我们首先讨论在未构建目标模型的情况怎样使用直接搜索法。然后我们考虑一些经典直接搜索法并揭示那些年这类算法的进展。特别地，当原始直接搜索法开始直接利用启发式方法时，更多近来的分析表明，虽然不是全部但大部分启发式方法实际上已经足可以保证迭代序列中至少有一个子序列全局收敛到目标函数的一阶驻点。关键词：求导无关优化；直接搜索法；模式搜索法Wediscussdirectsearchmethodsforunconstrainedoptimization.Wegiveamodernperspectiveonthisclassicalfamilyofderivative-freealgorithms,focusingonthedevelopmentofdirectsearchmethodsduringtheirgoldenagefrom1960to1971.Wediscusshowdirectsearchmethodsarecharacterizedbytheabsenceoftheconstructionofamodeloftheobjective.Wethenconsideranumberoftheclassicaldirectsearchmethodsanddiscusswhatresearchintheinterveningyearshasuncoveredaboutthesealgorithms.Inparticular,whiletheoriginaldirectsearchmethodswereconsciouslybasedonstraightforwardheuristics,morerecentanalysishasshownthatinmost–butnotall–casestheseheuristicsactuallysufficetoensureglobalconvergenceofatleastonesubsequenceofthesequenceofiteratestoafirst-orderstationarypointoftheobjectivefunction.©2000ElsevierScienceB.V.Allrightsreserved.Keywords:Derivative-freeoptimization;Directsearchmethods;Patternsearchmethods1.Introduction1．引言罗伯特·胡克和T.A.捷吾斯首先在1961年的计算机械协会期刊上的一篇论文上提出“直接搜索”[12].在他们的论文的引言中这样描述直接搜索：RobertHookeandT.A.Jeevescoinedthephrase“directsearch”inapaperthatappearedin1961inthejournaloftheAssociationofComputingMachinery[12].TheyProvidedthefollowingdescriptionofdirectsearchintheintroductiontotheirpaper:*Correspondingauthor.E-mailaddressed:bucharoo@icase.edu(R.M.Lewis),va@cs.wm.edu(V.Torczon),trosset@math.wm.edu(M.W.Trosset).1ThisresearchwassupportedbytheNationalAeronauticsandSpaceAdministrationunderNASAContractNo.NAS1-97046.2ThisresearchwassupportedBytheNationalScienceFoundationunderGrantCCR-9734044andbytheNationalAeronauticsandSpaceAdministrationunderNASAContractNo.NASI-97046,whiletheauthorwasinresidenceattheInstituteforComputerApplicationsinScienceandEngineering(ICASE).0377-0427/00/$-seefrontmatter©2000ElsevierScienceB.V.Allrightsreserved.Pll:S0377-0427(00)00423-4我们用“直接搜索”术语来描述试验解的有序检查，包括每个试验解与当前“最好”解的比较和决定（作为以前结果的函数）下一个试验解的策略。该术语暗示我们的优先选择是基于经验的。对于直接搜索策略，一般的经典分析方法起不到任何作用。Weusethephrase“directsearch”todescribesequentialexaminationoftrialsolutionsinvolvingcomparisonofeachtrialsolutionwiththe“best”obtaineduptothattimetogetherwithastrategyfordetermining(asafunctionofearlierresults)whatthenexttrialsolutionwillbe.Thephraseimpliesourpreference,basedonexperience,forstraightforwardsearchstrategieswhichemploynotechniquesofclassicalanalysisexceptwherethereisademonstrableadvantageindoingso.对于现...
