Penalty methods for the numerical solution of amer

PenaltymethodsforthenumerialsolutionofAmerianmulti-assetoptionproblems.BjrnFredrikNielsen,OlaSkavhaugzandAslakTveitozAugust24,2000Keywords:Amerianoption,multi-asset,penaltymethod,freebound-ary,nitedierene.AbstratWederiveandanalyseapenaltymethodforsolvingAmerianmulti-assetoptionproblems.Asmall,non-linearpenaltytermisaddedtotheBlak-Sholesequation.Thisapproahgivesaxedsolutiondo-main,removingthefreeandmovingboundaryimposedbytheearlyexerisefeatureoftheontrat.Expliit,impliitandsemi-impliitnitediereneshemesarederived,andintheaseofindependentassets,weprovethattheapproximateoptionpriessatisfysomebasipropertiesoftheAmerianoptionproblem.Severalnumerialexper-imentsarearriedoutinordertoinvestigatetheperformaneoftheshemes.Wegiveexamplesindiatingthatourresultsaresharp.Fi-nally,experimentsindiatethatintheaseoforrelatedunderlyingassets,thesamepropertiesarevalidasintheindependentase.1IntrodutionAmerianderivativesarepopulartradinginstrumentsintodaysnanialmarkets.WeonsiderAmerianputoptionswherethepayodependsonTheNorwegianComputingCenter,P.O.Box114Blindern,N-0314Oslo,Norway.E-mail:Bjorn.Fredrik.Nielsennr.no.zDepartmentofInformatis,P.O.Box1080Blindern,UniversityofOslo,N-0316Oslo,Norway.E-mail:skavhaugi.uio.no,aslaki.uio.no.1morethanoneunderlying.SuhoptionpriesanbemodelledbyhigherdimensionalgeneralisationsoftheoriginalBlak-Sholesequation[2℄.Thepurposeofthispaperistoextendthepenaltymethoddisussedin[11℄tomulti-assetAmerianputoptionproblems.Variousnumerialtehniquesanbeappliedtopriemulti-variatederiva-tives.Higherdimensionalgeneralisationsoflattiebinomialmethodsanbeused,.f.[3℄,whereEuropeanoptionsbasedonthreeunderlyingoptionsaresolvednumerially.Anotherwayofpriingmulti-assetderivativesisbyMonte-Carlosimulationtehniques,.f.[1℄.Inawiderangeofsien-tields,niteelementandnitevolumemethods(FEMandFDM)arepopular.ForstudiesofFEMandFDMfornumerialvaluationofnanialderivatives,.f.[17,8,5℄.FinitedierenemethodsarealsoommonlyusedforsolvingtheBlak-Sholesequationinhigherdimensions,.f.[15℄forastudyofthesingularity-separatingmethodfortwofatormodels,utilisinganitediereneapproah.Theideabehindthepenaltymethodformulti-assetoptionmodelsissimilartothemethoddesribedin[11℄.Amerianputoptionsanbeexer-isedatanytimebeforeexpiry.Thisintroduesafreeandmovingboundaryproblem.ByaddingaertainpenaltytermtotheBlak-Sholesequation,weextendthesolutiontoaxeddomain.Asthesolutionapproahesthepayofuntionatexpiry,thepenaltytermforesthesolutiontostayaboveit.Whenthesolutionisfarfromthebarrier,thetermissmallandthustheBlak-Sholesequationisapproximativelysatisedinthisregion.AsimilarapproahwasintroduedbyForsythandVetzalin[16℄forAmerianoptionswithstohastivolatility.Intheirworktheyaddasouretermtothedisreteequations.Ourmethodrepresentsarenementoftheirworkinthesensethatthepenaltytermisaddedtotheontinuousequation.Forindependentunderlyingassets,thisleadstorestritionsregardingthemagnitudeofthepenaltytermaswellasonditionsforthedisretizationparameters.Also,byhoosingasemi-impliitnitedierenedisretiza-2tion,weavoidsolvingnonlinearalgebraiequationsandtherebyenhanetheoverallomputationaleÆieny.Wepresentnumerialexperimentsillustratingthepropertiesoftheshemes.Intheaseoforrelatedunderlyingassets,wehavebeenunabletoderiveproperboundsonthenumerialsolutions.However,numerialexperimentsindiatethatsimilarpropertiesarepresentinsuhases.Thispaperisorganisedasfollows:InSetion2wedesribethemulti-assetBlak-Sholesequation,togetherwiththepenaltyformulationoftheproblem.TheboundaryonditionsorrespondingtozerovaluesoftheunderlyingassetsareobtainedbysolvinglowerdimensionalBlak-Sholesequations.InSetion4,numerialshemesforthetwo-fatormodelprob-lemarederived,startingbyspeifyingthetwo-fatormodelproblem.First,anexpliitshemeispresented,andthenbothasemi-impliitandafullyimpliitshemearedened.AnalysisoftheseshemesarearriedoutinSetion4,undertheassumptionthattheunderlyingassetsareindepen-dent.Restritionsregardingthetimestepsizeandthepenaltytermarethenprovidedforallthreeshemes.Inthelastsetionofthispaper,wepresentaseriesofnumerialexperiments,startingbyomparingthefullyimpliitandthesemi-impliitshemewithrespettoomputationaleÆ-ieny.InSetion5,weshowthatnumerialexperimentsindiatethatforourmodeldata,therestritionsderivedinSetion4forindependentassetsarevalidalsowhentheunderlyingassetsareorrelated.Finally,wemakesomeonlusiveremarksinSetion6.2Amerianmulti-assetoptionproblemsThemulti-dimensionalversionoftheBlak-SholesequationtakestheformPt+12nXi=1nXj=1i;jijSiSj2PSiSj+nXi=1(rDi)SiPSirP=0;3seee.g.[7℄,[10℄or[13℄.Here,Pisthevalueoftheontrat,Siisthevalueoftheithunderlyingasset,nisthenumberofunderlyingassets,i;jistheorrelationbetweenassetiandassetj,ristheriskfreeinterestrateandDiisthedividendyieldpaidbytheithasset.Foramajorityofmulti-assetoptionmodelsthepayofuntionatexpiryanbewrittenontheform(S1;:::;Sn)=maxEnXi=1iSi;0!;(1)whereEand1;:::;naregivenonstants,see[10℄.Wewillinthispaperonsiderputoptions,i.e.E;1;:::;n0:NotiethattheAmerianearlyexerisefeatureoftheontratimposestheonstraintP(S1;:::;Sn;t)(S1;:::;Sn)onthe