A primal-dual decomposition-based interior point a

APrimal{DualDecomposition-BasedInteriorPointApproachtoTwo-StageStochasticLinearProgrammingArjanBerkelaarCeesDertyBartOldenkampzShuzhongZhangxEIReport9918/AAbstractDecisionmakingunderuncertaintyisachallengefacedbymanydecisionmakers.Stochas-ticprogrammingisamajortooldevelopedtodealwithoptimizationwithuncertaintiesthathasfoundapplicationsin,e.g.nance,suchasasset-liabilityandbond-portfoliomanage-ment.Computationallyhowever,manymodelsinstochasticprogrammingremainunsolvablebecauseofoverwhelmingdimensionality.Foramodeltobewellsolvable,itsspecialstruc-turemustbeexplored.Mostofthesolutionmethodsarebasedondecomposingthedata.Inthispaperweproposeanewdecompositionapproachfortwo-stagestochasticprogramming,basedonadirectapplicationofthepath-followingmethodcombinedwiththehomogeneousself-dualtechnique.Numericalexperimentsshowthatourdecompositionalgorithmisveryecientforsolvingstochasticprograms.Inparticular,weapplyourdecompositionmethodtoatwo-periodportfolioselectionproblemusingoptionsonastockindex.Inthismodeltheinvestorcaninvestinamoney-marketaccount,astockindex,andEuropeanoptionsonthisindexwithdierentmaturities.WeexperimentourmodelwithmarketpricesofoptionsontheS&P500.AMSClassication:49M27(DecompositionMethods),90C06(Large-ScaleProblems),90C15(StochasticProgramming).JELClassication:C61(OptimizationTechniques),G11(PortfolioChoice)CorrespondingAuthor.EconometricInstitute,ErasmusUniversityRotterdam,P.O.Box1738,3000DRRotterdam,TheNetherlands,[e-mail]-AMROAssetManagementandFreeUniversityofAmsterdam,TheNetherlands,[e-mail]-AMROAssetManagementandErasmusUniversityRotterdam,TheNetherlands,[e-mail],ErasmusUniversityRotterdam,TheNetherlands,[e-mail].12Primal{DualDecompositionforStochasticProgramming1IntroductionStochasticprogrammingplaysanincreasinglyimportantroleinmanyapplicationsofmath-ematicaloptimization,especiallyinnancialoptimizationmodelssuchasasset-liabilityandbond-portfoliomanagement(theinterestedreaderisreferredtotherecentbookonAssetLiabil-ityManagementbyMulveyandZiemba[13]).However,ecientlysolvinglarge-scalestochasticprogrammingproblemsstillremainsamajorchallenge(see[2]foranintroductiontostochasticprogramming).Asuccessfulsolutionmethodforstochasticprogrammingshouldexploitthespe-cialstructureoftheprobleminordertocutdowncomputationaltimes.Forthispurpose,mostofthesolutionmethodsintheareaarebasedonspecializeddecomposition;wereferto[8]andthereferencesthereinforasurveyalongthisdirection.Formulti-stagestochasticprogramming,theso-calledL-shapedmethodanditsvariants,basedonthesimplexmethod,areverypopu-lar.Withtherapidgrowthanddevelopmentininteriorpointmethodsinrecentyears(cf.[16]forvarioussurveyarticlesoninteriorpointmethods),thistraditionalapproachtostochasticprogrammingneedstobereconsidered.In[4]BirgeandQishowedhowdecompositioncanbeachievedbasedonKarmarkar’soriginalinteriorpointmethodfortwo-stagestochasticlinearprogramming.Afewotherinteriorpointbasedapproacheshavebeensuggestedsofarintheliterature;seee.g.[3,5,12].Zhao[20]proposedamethodinwhichalogbarrierisusedforeachrecoursesubproblem.Inthispaperweconsideranewdecompositionmethodfortwo-stagestochasticprogrammingbasedonthehomogeneousself-dualinteriorpointmethod.Thehomogeneousself-dualmethod(HSD)forlinearprogrammingwasproposedbyXu,HungandYe[18]asasimplicationoftheself-dualembeddingtechniqueofYe,ToddandMizuno[19].Thistechniqueprovestobeveryecientinsolvinglinearprograms(arenedversionoftheHSDmethodisactuallyimplementedbyAndersenandAndersen[1]inanoptimizationpackagecalledMOSEK).OneoftheadvantagesoftheHSDmethodisthatitrequiresnofeasibilityphase,allowingonetofreelyselectanyinteriorstartingpoint(possiblyinfeasible).Moreover,themethodiscapableofdetectinginfeasibilitywhichcanbeofgreatimportanceforstochasticprograms.Asageneralmeritofinteriorpointmethods,thenumberofiterationsrequiredtosolvealinearprogramistypicallylowandinsensitivetothedimensionoftheproblem.Thisisanimportantpropertyforsolvinglarge-scalestochasticprograms.Themainconcernishowtoimplementeachstepofaninteriorpointmethodeciently.Agreatdealofattentionistobepaidtothisissueinthecurrentpaper.Weobservethatitispossibletocompletelydecomposethedirection-ndingproblemintosubproblems,thereforeenablingadecomposition-basedimplementationoftheHSDtechnique.Wereportnumericalresultswhichunambiguouslyshowthespeed-upattainedwhenapplyingourdecompositionalgorithmcomparedtosolvingthedeterministicequivalentdirectlybytheHSDmethod.Asanapplicationweconsideraportfoliooptimizationproblem.Inthisproblemaninvestorwantstobuyoptionsonagivenstockindex,insuchawaythatthevalueofhisportfolioisguaranteedtobehigherthanacertainlevel,andtheprobabilityofreachinganothergivenlevelisguaranteedaswell.Moreover,theexpectedreturnattheendoftheinvestmenthorizonistobemaximized.Weassumethatthereisanintermediatedateatwhichtheinvestormayrevisehisportfolio.Thisproblemismodeledbytwo-stagestochasticlinearprogramming.Wesolvethemodelusingthedecompositionalgorithmproposedinthispaper.Berkelaar,Dert,Oldenka