ProbablisticConstrainedOptimization:TheoryandApplications(S.P.Uryasev,Editor),pp.91-116c2000KluwerAcademicPublishersStatisticalinferenceofstochasticoptimizationproblemsAlexanderShapiro(ashapiro@isye.gatech.edu)GeorgiaInstituteofTechnology,Atlanta,GA30332-0205,USAAbstractWediscussinthispaperstatisticalinferenceofMonteCarlosimulationbasedapproximationsofstochasticoptimizationproblems,wherethe\trueobjec-tivefunction,andprobablysomeoftheconstraints,areestimated,typicallybyaveragingarandomsample.Theclassicalmaximumlikelihoodestimationcanbeconsideredinthatframework.Recentlystatisticalanalysisofsuchmeth-odshasbeenmotivatedbyadevelopmentofsimulationbasedoptimizationtechniques.WeinvestigateasymptoticpropertiesoftheoptimalvalueandanoptimalsolutionofthecorrespondingMonteCarlosimulationapproximationsbyemployingtheso-calledDeltamethod,anddiscusssomeexamples.1IntroductionConsidertheoptimizationproblemMinx2Sf(x);(1.1)whereSisasubsetofIRmandf:S!IR.SupposethattheaboveoptimizationproblemisapproximatedbyasequenceofproblemsMinx2S^fN(x);(1.2)where^fN(x)arerandomfunctionsconverging,asN!1,insomeprobabilisticsensetof(x).Wereferto(1.1)and(1.2)asthetrueandapproximatingproblems,91respectively.Typicallytheobjectivefunctionf(x)isgivenastheexpectedvaluefunctionf(x):=IEPfg(x;!)g=Zg(x;!)P(d!);(1.3)where(;F;P)isaprobabilityspace,andtheapproximatingfunctions^fN(x)areconstructedbyaveragingarandomsample.Letv0,^vNandx0,^xNbetheoptimalvaluesandoptimalsolutionsoftheproblems(1.1)and(1.2),respectively.Inthispaperwediscussasymptoticstatisticalinferenceof^vNand^xN,asNtendstoinnity.WealsoconsiderthecaseswherethefeasiblesetSissubjecttoperturbationsandisgivenbyrandomconstraints.Letusdiscusssomeexamples.Example1.1Ourrstexampleismotivatedbytheclassicalmaximumlikelihoodmethodofestimation.Thatis,letg(y;)beafamilyofprobabilitydensityfunctions(pdf),parameterizedbytheparametervector2IRm,andletY1;:::;YNbeani.i.d.randomsamplewithaprobabilitydistributionP.Dene^fN():=N1NXi=1lng(Yi;):BytheLawofLargeNumberswehavethat,foranyxedvalueof,^fN()convergestof():=IEPflng(Y;)g=Zlng(y;)P(dy);withprobabilityone,asN!1,providedofcoursethattheaboveexpectationexists.Thisleadstothe\trueand\approximatingoptimizationproblemsofminimizingf()and^fN(),respectively,overtheparameterset.Inparticular,supposethatthedistributionPisgivenbyapdfg(y;0),02,fromtheaboveparametricfamily,i.e.,theparametricmodeliscorrectlyspecied.Then0isanunconstrainedminimizeroff(),andhenceisanoptimalsolutionofthe\trueproblem.Indeed,byusingconcavityofthelogarithmfunction,weobtainf(0)f()=Zlng(y;)g(y;0)#g(y;0)dyZg(y;)g(y;0)1#g(y;0)dy=0:Thereisalargeliteratureonthemaximumlikelihoodmethod,andtheabovederiva-tionofoptimalityof0isknownofcourse.Wewillcomebacktothisexamplelater.Letusnoteatthispointthatthecorrespondingrandomsampleusuallyrepresentsavailabledataandtheassociatedminimizer^Nof^fN(),over,isviewedasthemax-imumlikelihoodestimatorofthe\truevalue0oftheparametervector.Therearealsovariousextensionsofthemaximumlikelihoodmethod,inparticularthemethodofM-estimatorsintroducedbyHuber[13,15].92SomewhatdierenttypeofexamplesismotivatedbyaMonteCarlosimulationapproachtonumericalsolutionsofstochasticprogrammingproblems.Agoalofasuchstochasticprogrammingproblemistosolveanoptimizationproblemoftheform(1.1)withtheobjectivefunctionf(x)givenastheexpectedvalueintheform(1.3).TheprobabilitydistributionPissupposedtobeknown,althoughmaybenotgivenexplicitly.However,thecorrespondingintegral(expectedvalue)cannotbecalculatedinaclosedformandhastobeapproximated.MonteCarlosimulationtechniquesprovidesuchanapproximationbyaveragingageneratedarandomsamplewithanappropriateprobabilitydistribution.LetusdiscussthefollowingtwoexamplesofstochasticprogrammingwithrecourseandaGI=G=1queue.Example1.2ConsidertheoptimizationproblemMinx2ScTx+IEfQ(x;h(!))g;(1.4)wherec2IRmisagivenvector,Q(x;h)istheoptimalvalueoftheoptimizationproblemMiny0qTysubjecttoWy=hAx;(1.5)andh=h(!)isarandomvectorwithaknownprobabilitydistribution.(Forthesakeofsimplicityweassumethatonlyvectorhisrandomwhileotherparametersinthelinearprogrammingproblem(1.5)aredeterministic.)Thisistheso-calledtwo-stagestochasticprogrammingproblemwithrecourse,whichoriginatedinworksofBeale[2]andDantzig[8].Iftherandomvectorhhasadiscretedistribution,thentheexpectedvaluefunctionIEfQ(x;h)gisgiveninaformofsummationandproblem(1.4)canbewrittenasalargelinearprogrammingproblem.Overtheyearsthisapproachwasdevelopedandvarioustechniquesweresuggestedinordertomakeitnumericallyecient.TheinterestedreaderisreferredtorecentbooksbyKallandWallace[16]andBirgeandLouveaux[4],andreferencestherein,foranextensivediscussionofthesemethods.However,thenumberofrealizationsofh(thenumberofdiscretizationpointsincasethedistributionofhiscontinuous)typicallygrowsexponentiallywiththedimensionalityofh.Consequently,thisnumbercanquicklybecomesolargethatevenmoderncomputerscannotcopewiththerequiredcalculations.MonteCarlosimulationtechniquessuggestanapproachtodealwiththisproblem.Thatis,arandomsampleh1;:::;hNofNindepende
本文标题:Statistical inference of stochastic optimization
链接地址:https://www.777doc.com/doc-3303093 .html