An informational approach to the global optimizati

arXiv:cs/0611143v2[cs.NA]18Jul2007Aninformationalapproachtotheglobaloptimizationofexpensive-to-evaluatefunctionsJulienVillemonteix∗†‡,EmmanuelVazquez†andEricWalter∗†Supélec,DépartementSignauxetSystèmesÉlectroniques91192Gif-sur-Yvette,France∗LaboratoiredesSignauxetSystèmes,CNRS-Supélec-UnivParis-Sud‡RenaultS.A.,service6824078298Guyancourt,FranceAbstractInmanyglobaloptimizationproblemsmotivatedbyengineeringapplications,thenumberoffunctionevaluationsisseverelylimitedbytimeorcost.Toensurethateachevaluationcontributestothelocalizationofgoodcandidatesfortheroleofglobalminimizer,ase-quentialchoiceofevaluationpointsisusuallycarriedout.Inparticular,whenKrigingisusedtointerpolatepastevaluations,theuncertaintyassociatedwiththelackofinformationonthefunctioncanbeexpressedandusedtocomputeanumberofcriteriaaccountingfortheinterestofanadditionalevaluationatanygivenpoint.ThispaperintroducesminimizerentropyasanewKriging-basedcriterionforthesequentialchoiceofpointsatwhichthefunctionshouldbeevaluated.Basedonstepwiseuncertaintyreduction,itaccountsfortheinformationalgainontheminimizerexpectedfromanewevaluation.Thecriterionisap-proximatedusingconditionalsimulationsoftheGaussianprocessmodelbehindKriging,andtheninsertedintoanalgorithmsimilarinspirittotheEfficientGlobalOptimization(EGO)algorithm.Anempiricalcomparisoniscarriedoutbetweenourcriterionandex-pectedimprovement,oneofthereferencecriteriaintheliterature.ExperimentalresultsindicatemajorevaluationsavingsoverEGO.Finally,themethod,whichwecallIAGO(forInformationalApproachtoGlobalOptimization)isextendedtorobustoptimizationproblems,whereboththefactorstobetunedandthefunctionevaluationsarecorruptedbynoise.Keywords:Gaussianprocess,globaloptimization,Kriging,robustoptimization,stepwiseuncertaintyreduction1IntroductionThispaperisdevotedtoglobaloptimizationinacontextofexpensivefunctioneval-uation.TheobjectiveistofindglobalminimizersinX(thefactorspace,aboundedsubsetofRd)ofanunknownfunctionf:X→R,usingaverylimitednumberoffunctionevaluations.Notethattheglobalminimizermaynotbeunique(anyglobalminimizerwillbedenotedasx∗).Suchaproblemisfrequentlyencounteredintheindustrialworld.Forinstance,intheautomotiveindustry,optimalcrash-relatedparametersareobtainedusingcostlyrealtestsandtime-consumingcomputersim-ulations(asinglesimulationofcrash-relateddeformationsmaytakeupto24hoursondedicatedservers).Itthenbecomesessentialtofavoroptimizationmethodsthatusethedramaticallyscarceinformationasefficientlyaspossible.Tomakeupforthelackofknowledgeonthefunction,surrogate(alsocalledmetaorapproximate)modelsareusedtoobtaincheapapproximations(Jones[2001]).Theyturnouttobeconvenienttoolsforvisualizingthefunctionbehaviororsug-gestingthelocationofanadditionalpointatwhichfshouldbeevaluatedinthesearchforx∗.SurrogatemodelsbasedonGaussianprocesseshavereceivedpar-ticularattention.KnowninGeostatisticsunderthenameofKrigingsincetheearly1960s(Matheron[1963]),Gaussianprocessmodelsprovideaprobabilisticframe-worktoaccountfortheuncertaintystemmingfromthelackofinformationonthesystem.Whendealingwithanoptimizationproblem,thisframeworkallowsthesetoffunctionevaluationstobechosenefficiently(Jones[2001],Jonesetal.[1998],Huangetal.[2006]).Inthiscontext,severalstrategieshavebeenproposed,withsignificantadvantagesovertraditionaloptimizationmethodswhenconfrontedtoexpensive-to-evaluatefunctions.Mostofthemimplicitlyseekalikelyvalueforx∗,andthenassumeittobeasuitablelocationforanewevaluationoff.Yet,givenexistingevaluationresults,themostlikelylocationofaglobalminimizerisnotnecessarilyagoodeval-uationpointtoimproveourknowledgeonx∗.Asweshallshow,bymakingfulluseofKriging,itisinsteadpossibletoexplicitlyestimatetheprobabilitydistributionoftheoptimumlocation,whichallowsaninformation-basedsearchstrategy.Basedontheseobservations,thepresentpaperintroducesminimizerentropyasacriterionforthechoiceofnewevaluationpoints.Thiscriterion,directlyinspiredfromstepwiseuncertaintyreduction(GemanandJedynak[1995]),istheninsertedinanalgorithmsimilartotheEfficientGlobalOptimization(EGO)algorithm(Jonesetal.[1998]).WecalltheresultingalgorithmIAGO,forInformationalApproachtoGlobalOptimization.Section2recallstheprincipleofKriging-basedoptimization,alongwithsomegen-eralideasonGaussianprocessmodelingthatareusedinSection3tobuildanes-timateofthedistributionoftheglobalminimizers.Section4detailsthestepwiseuncertaintyreductionapproachappliedtoglobaloptimization,whileSection5de-scribesthecorrespondingalgorithmanditsextensionstonoisyproblems.Section6illustratesthebehaviorofthenewalgorithmonsomesimplebenchmarkproblems,alongwithitsperformancescomparedwiththoseoftheclassicalEGOalgorithm,chosenforitsgoodcompromisebetweenlocalandglobalsearch(Sasenaetal.2[2002]).Finally,afteraconclusionsectionandtomakethispaperself-contained,Section8presents,asanappendix,somemoreresultsonGaussianprocessmodel-ingandKriging.2Kriging-basedglobaloptimizationWhendealingwithexpensive-to-evaluatefunctions,optimizationmethodsbasedonprobabilisticsurrogatemodels(andKriginginparticular)havesignificantad-vantagesovertraditionaloptimiza