A global optimization heuristic for portfolio choi

AGlobalOptimizationHeuristicforPortfolioChoicewithVaRandExpectedShortfallManfredGilliandEvisK¨ellezi¤Firstdraft:August2000Thisdraft:January2001¤M.Gilli:DepartmentofEconometrics,40BdduPontd’Arve,UniversityofGeneva,1211Geneva4,Switzerland,[e-mail].E.K¨ellezi:DepartmentofEconometricsandFAME,UniversityofGeneva,40BdduPontd’Arve,1211Geneva4,Switzerland,[e-mail]£tedsigni£cantlyfromconversationswithPeterWinker;wewouldliketothankhimforvaluablesuggestionsandcomments.FinancialsupportfromtheSwissNationalScienceFoundation(project12–5248.97)isgratefullyacknowledged.AbstractConstraintsondownsiderisk,measuredbyshortfallprobability,expectedshortfalletc.,leadtooptimalassetallocationswhichdifferfromthemean-varianceoptimum.Theresultingoptimizationproblemcanbecomequitecomplexasitexhibitsmultiplelocalextremaanddiscontinuities,inparticularifwealsointroduceconstraintsrestrict-ingthetradingvariablestointegers,constraintsontheholdingsizeofassetsoronthemaximumnumberofdifferentassetsintheportfolio.Insuchsituationsclassicalop-timizationmethodsfailtoworkef£cientlyandheuristicoptimizationtechniquescanbetheonlywayout.Thepapershowshowaparticularoptimizationheuristic,calledthresholdaccepting,canbesuccessfullyusedtosolvecomplexportfoliochoiceprob-lems.JELcodes:G11,C61,C63.Keywords:PortfolioOptimization,DownsideRiskMeasures,HeuristicOptimization,ThresholdAccepting.HEURISTICPORTFOLIOOPTIMIZATION31IntroductionThefundamentalgoalofaninvestoristooptimallyallocatehisinvestmentsamongdifferentassets.Thepioneeringworkof[Markowitz,1952]introducedmean-varianceoptimizationasaquantitativetoolwhichcarriesoutthisallocationbyconsideringthetrade-offbetweenrisk–measuredbythevarianceofthefutureassetreturns–andreturn.Theassumptionsofthenormalityofthereturnsorofthequadraticinvestor’spreferencesallowthesimpli£cationoftheutilityoptimizationprobleminarelativelyeasytosolvequadraticprogram.Notwithstandingitspopularity,thisapproachhasalsobeensubjecttoalotofcriticism.Alternativeapproachesattempttoconformthefundamentalassumptionstorealitybydismissingthenormalityhypothesisinordertoaccountforthefat-tailednessandtheasymmetryoftheassetreturns.Consequently,othermeasuresofrisk,suchasValueatRisk(VaR),expectedshortfall,meansemi-absolutedeviation,semi-varianceandsoonareused,leadingtoproblemsthatcannotalwaysbereducedtostandardlinearorquadraticprograms.Theresultingoptimizationproblemoftenbecomesquitecomplexasitexhibitsmultiplelocalextremaanddiscontinuities,inparticularifweintroduceconstraintsrestrictingthetradingvariablestointegers,constraintsontheholdingsizeofassets,constraintsonthemaximumnumberofdifferentassetsintheportfolio,etc.Insuchsituations,classicaloptimizationmethodsdonotworkef£cientlyandheuristicoptimizationtechniquescanbetheonlywayout.Theyarerelativelyeasytoimple-mentandcomputationallyattractive.Theuseofheuristicoptimizationtechniquestoportfolioselectionhasalreadybeensuggestedby[MansiniandSperanza,1999],[Changetal.,2000]and[Speranza,1996].Thispaperbuildsonworkby[DueckandWinker,1992]who£rstappliedaheuristicoptimizationtechnique,calledThresholdAccepting,toportfoliochoiceproblems.WeshowhowthistechniquecanbesuccessfullyemployedtosolvecomplexportfoliochoiceproblemswhereriskischaracterizedbyValueatRiskorExpectedShortfall.InSection2,weoutlinethedifferentframeworksforportfoliochoiceaswellasthemostfrequentlyusedriskmeasures.Section3givesageneralrepresentationofthethresholdacceptingheuristicweuse.Theperformanceandef£ciencyofthealgorithmisdiscussedinSection4by,£rst,comparingitwiththequadraticprogrammingso-lutionsinthemean-varianceframeworkand,second,applyingthealgorithmtotheproblemofmaximizingtheexpectedportfoliovalueunderconstraintsontheportfolioexpectedshortfallorVaR.Section5concludes.4GILLIANDK¨ELLEZI2PortfoliochoicemodelsInthissectionwedescribethemostfrequentlyusedriskmeasuresaswellasthedifferentframeworksforportfoliochoicetheygiveriseto.2.1Themean-varianceformulationMean-varianceoptimizationiscertainlythemostpopularapproachtoportfoliochoice.Inthisframework,theinvestorisfacedwithatrade-offbetweenthepro£tabilityofhisportfolio,characterizedbytheexpectedreturn,andtherisk,measuredbythevarianceoftheportfolioreturns.The£rsttwomomentsoftheportfoliofuturereturnaresuf-£cienttode£neacompleteorderingoftheinvestorspreferences.Thisstrongresultisduetothesimplistichypothesisthattheinvestors’preferencesarequadraticorthatthereturnsarenormallydistributed.Denotingbyxi,i=1;:::;nA,theamountinvestedinassetioutofaninitialcapitalv0andbyri,i=1;:::;nA,theassetslog-returnsovertheplanningperiod,theexpectedreturnontheportfoliode£nedbythevectorx=(x1;x2;:::;xnA)0isgivenas¹(x)=1v0x0E(r):Thevarianceoftheportfolioreturnis¾2(x)=x0Qx;whereQisthematrixofvariancesandcovariancesofthevectorofreturnsr.Thusthemean-varianceef£cientportfolios,de£nedashavingthehighestexpectedreturnforagivenvarianceandtheminimumvarianceforagivenexpectedreturn,areobtainedbysolvingthefollowingquadraticprogramminxx0QxPjxjrj¸½v0Pjxj=v0x`j·xj·xujj2P:(1)fordifferentvaluesof½,where½is