A Simulation-Based Approach to Two-Stage Stochasti

ASimulation-BasedApproachtoTwo-StageStochasticProgrammingwithRecourseAlexanderShapiroandTitoHomem-de-MelloRevisedOctober8,1996SchoolofIndustrialandSystemsEngineering,GeorgiaInstituteofTechnology,Atlanta,Georgia30332-0205,USAAbstractInthispaperweconsiderstochasticprogrammingproblemswheretheobjectivefunctionisgivenasanexpectedvaluefunction.WediscussMonteCarlosimulationbasedapproachestoanumericalsolutionofsuchproblems.Inparticular,wediscussindetailandpresentnumericalresultsfortwo-stagestochasticprogrammingwithre-coursewheretherandomdatahaveacontinuous(multivariatenormal)distribution.Wethinkthatthenoveltyofthenumericalapproachdevelopedinthispaperistwofold.First,variousvariancereductiontechniquesareappliedinordertoenhancetherateofconvergence.Successfulapplicationofthosetechniquesthatiswhatmakesthewholeapproachnumericallyfeasible.Second,astatisticalinferenceisdevelopedandappliedtoestimationoftheerror,validationofoptimalityofacalculatedsolutionandstatisticallybasedstoppingcriteriaforaniterativealgorithm.Keywords:Two-stagestochasticprogrammingwithrecourse,MonteCarlosimulation,likelihoodratios,variancereductiontechniques,condenceintervals,hypothesestesting,validationanalysis,nonlinearprogramming.SupportedbyCNPq(ConselhoNacionaldeDesenvolvimentoCientcoeTecnologico),Braslia,Brazil,throughaDoctoralFellowshipundergrant200595/93-8.1IntroductionInmanypracticalsituationsoneisrequiredtosolveoptimizationproblemswhicharesubjecttouncertainty.Therearevariouswaystomodelanuncertainty(incompleteinformation,datavariability,randomness,etc.)whichleadtodierentformulationsoftheassociatedoptimizationproblems.Inthispaperwefocusonaparticularapproachtosuchproblems,whichisbasedonsimulation(MonteCarlo)techniques,andapplyittoaspecicclassofproblems.Considertheoptimizationproblemminx2SIEff(x;)g(1.1)ofminimizationoftheexpectedvaluefunctionIEff(x;)goverasetSIRm.WeassumethatthesetSisdeterministicandisgivenexplicitlybylinearornonlinearconstraintsandthatisarandomvectorwhosedistributionisknown.Inrealisticapplications,andespeciallywhentherandomvectorhasalargedimensionality,itistypicallyimpossibletocalculatetheexpectedvalueIEff(x;)ginaclosedformandhencenumericalapproxi-mationsarerequired.ThebasicideaofanapproachthatwediscussinthispaperisbasedonMonteCarlotechniquesandisquitesimple.ArandomsampleZ1;:::;ZNofindepen-dentreplicationsoftherandomvectorisgeneratedandconsequentlytheexpectedvaluefunctionisapproximatedbytheaveragefunction^fN(x)=N1NXi=1f(x;Zi):(1.2)Theideaofgenerationofarandomsampleandconsequentapproximationoftheexpec-tationbythecorrespondingaverageisnotnew,ofcourse,andistheheartoftheMonteCarlomethod.SomewhatrecentlyMonteCarlosimulationbasednumericaltechniquesstartedtoattractattentioninstochasticprogrammingcommunity.Wecanmentioninthatrespectthestochasticsubgradient(stochasticquasigradient)methods([5],[6]),andapproachesdevelopedin[9]and[11].Inthispaperweconsidersituationswhen,forageneratedsampleZ1;:::;ZN,thevalue,rstandpossiblysecondorderderivativesoftheaveragefunction^fN(x)canbecalculatedandhencedeterministicalgorithmsofnonlinearprogrammingcanbeappliedtominimizationof^fN(x)overS(cf.[18],[28]).Wediscusstheproblemandreportanumericalexperienceforaparticularclassofstochasticprograms,namelytwo-stagestochasticprogramswithrecourse.Althoughtheideasdiscussedhereareconcentratedontwostagestochasticprogrammingwithrecourse,webelievethatsomeofthemcanbeappliedtoawiderrangeofproblems.Wethinkthatthenoveltyofnumericaltechniquesdevelopedinthispaperistwofold.First,itwaspossibletoapplyvariousvariancereductiontechniqueswhichenhancedtherateofconvergenceandinfactmadethewholeapproachnumericallyfeasible.Second,astatisticalinferencewasdevelopedandappliedtoestimationoftheerror,validationofoptimalityofacalculatedsolutionandstatisticallybasedstoppingcriteriaforaniterativealgorithm.2TwoStageRecourseProblemInthissectionwediscusssomebasicideasappliedtotwostagestochasticprogrammingwithrecourse.StochasticprogramswithrecoursewereintroducedintheftiesbyDantzig[3]and1Beale[2].Formorerecentdiscussionsofthisclassofproblemsandextendedbibliographysee,e.g.,[4,6,13,37].Considertheoptimizationproblemminx2ScTx+IEfQ(x;!)g;(2.1)whereQ(x;!)=infnqTy:Wy=h(!)T(!)x;y0o:(2.2)Hereh=h(!)isann1randomvectorandT=T(!)isannmrandommatrixdenedonaprobabilityspace(;F;P).Withafewexceptions(e.g.[9,11]),existingnumericalmethodsforsolutionof(2.1)arebasedondeterministictechniqueswhichdealwithanitenumberofrealizationsofthecorrespondingrandomvariables.This,inturn,requiresdiscretizationoftheunderlyingprobabilitymeasures(distributions)incasethesedistributionsarecontinuous.Inmanysituationsevenareasonablymoderatenumberofsuchrealizationsresultsinhugelinearprogramswhichcannotbesolvedevenbymoderncomputers.NotethatthefunctionQ(x;!)canbewrittenintheformQ(x;!)=G(h(!)T(!)x),whereG(z)=infnqTy:Wy=z;y0o:(2.3)Bydualityarguments(cf.[36])thefunctionG()canberepresentedintheformG(z)=supfTz:WTqg:(2.4)Forthesakeofsimplicityweassumethat:(i)foreveryvectorzthesystemWy=z,y0,hasasolution(therecourseiscomplete),