Introduction to Global Optimization

《Introduction to Global Optimization》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、IntroductiontoGlobalOptimizationLeoLibertiLIX,EcolePolytechnique,PalaiseauF-91128,France´(liberti@lix.polytechnique.fr)February15,2008AbstractAccuratemodellingofreal-worldproblemsoftenrequiresnonconvextermstobeintroducedinthemodel,eitherintheobjectivefunctionorintheconstraints.Nonconvexpr

2、ogrammingisoneofthehardestfieldsofoptimization,presentingmanychallengesinbothpracticalandtheoreticalaspects.Thepresenceofmultiplelocalminimacallsfortheapplicationofglobaloptimizationtechniques.Thispaperisamini-courseaboutglobaloptimizationtechniquesinnonconvexprogramming;itdealswithsomethe

3、oreticalaspectsofnonlinearprogrammingaswellaswithsomeofthecurrentstate-of-the-artalgorithmsinglobaloptimization.Thesyllabusisasfollows.SomeexamplesofNonlinearProgrammingProblems(NLPs).Generaldescriptionoftwo-phasealgorithms.LocaloptimizationofNLPs:derivationofKKTconditions.Shortnotesabout

4、stochasticglobalmultistartalgorithmswithaconcreteexample(SobolOpt).In-depthstudyofadeterministicspatialBranch-and-Boundalgorithm,andconvexrelaxationofanNLP.Latestadvancesinbilinearprogramming:thetheoryofreductionconstraints.Contents1Introduction21.1Scopeofthispaper........................

5、................31.2ExampleswhichrequireGlobalOptimization.........................41.3Abriefhistoryofglobaloptimization..............................62ThestructureofGlobalOptimizationAlgorithms82.1Stochasticglobalphase......................................92.2Deterministicglobalphase....

6、................................112.2.1Fathoming........................................132.3ExampleofsolutionbyBranch-and-Select...........................133LocalOptimizationofNLPs163.1Fundamentalnotionsofconvexanalysis............................163.2Necessaryandsufficientconditionsforlo

7、caloptimality....................183.3Alocaloptimizationalgorithm:SQP..............................241INTRODUCTION24TheSobolOptalgorithm255ThespatialBranch-and-Boundalgorithm275.1Boundstightening........................................285.1.1Optimization-basedbounds