c○2005 INFORMS A Semidefinite Programming Approach

MATHEMATICSOFOPERATIONSRESEARCHVol.30,No.x,Xxxxxxx2005,pp.xxx{xxxISSN0364-765XjEISSN1526-5471j05j300xjxxxxinforms®DOI10.1287/moor.xxxx.xxxxc°2005INFORMSASemidefiniteProgrammingApproachtoOptimalMomentBoundsforConvexClassesofDistributionsIoanaPopescuDecisionSciencesAreaINSEAD,Blvd.deConstance,Fontainebleau77300,FRANCEemail:[e-mail]¯niteprogramming.Theseboundsarenotsharpiftheunderlyingdistributionspossessadditionalstructuralproperties,includingsymmetry,unimodality,convexityorsmoothness.Forconvexdistributionclassesthatareinsomesensegeneratedbyanappropriateparametricfamily,weuseconicdualitytoshowhowoptimalmomentboundscanbee±cientlycomputedassemide¯niteprograms.Inparticular,weobtaingeneralizationsofChebyshev'sinequalityforsymmetricandunimodaldistributions,andprovidenumericalcalculationstocomparetheseboundsgivenhigherordermoments.Wealsoextendtheseresultsformultivariatedistributions.Keywords:momentproblems;Chebyshevinequalities;probabilitybounds;convexoptimization;semide¯niteprogrammingMSC2000SubjectClassi¯cation:Primary:60E15;Secondary:90C22,90C25OR/MSsubjectclassi¯cation:Primary:ProbabilityDistributions;Secondary:In¯niteDimensionalProgramming,MathematicsConvexityHistory:Received:April5,2002;revised:April2,2004.1.Introduction.Ageneralizedmomentboundisaproblemofthefollowingtype:Given\momentinformation,intheformE[fi(X)]=qi;i=1;:::;n;aboutarandomvariableX,whatarethe\bestpossibleupperand/orlowerboundsontheexpectationofarelatedquantity,Á(X),thatcanbederivedfromtheavailableinformation?Wecanformulatetheproblemof¯ndingsuchoptimalupper(andsimilarlylower)boundsasanoptimizationprogram:(P)maxX2PE[Á(X)]s.t.E[fi(X)]=qi;i=0;:::;n:wheretheoptimizationistakenoverallpossibledistributionsoftherandomvariableXintheclassP.Thissetupismaderigorousinthenextsection.ThisformulationispowerfulbecauseofthevarietyofinterpretationsthatcanbegiventotherandomvariableXandtheunderlyingclassP,aswellasthegeneralityoftheobjectiveandconstraintfunctionsÁandfi.Thesearenotassumedtobecontinuousorbounded,toallowfor\momentssuchasP(X¸a)anddistributionswithunboundedsupport.Theproblem(P)providesageneralframeworkforstudyingamultitudeofmomentproblems,withapplications.Forexample,momentinequalitiesareusedtoproviderobustestimatesfor¯nancialquantities,suchasoptionandstockprices(seeLo[22],Grundy[14]orBertsimasandPopescu[3]),wealthbalanceinoptionhedging(YamadaandPrimbs[46])orvalueatrisk(ElGhaouietal.[13]).Inthedecisionsciencesliterature,Smith[36]exploresseveralareasofapplicationofmomentbounds,includingdynamicprogramming,decisionanalysiswithincompleteinformation(seealsoWillassen[43],LiCalzi[21])andBayesianstatistics.ThequestionoffeasibilityofProblem(P)givenstandardmomentconstraintsE[Xi]=qi;i=1;:::;n;istheclassicalmomentproblem.Ithasbeeninvestigatedbyprobabilistssincethenineteenthcentury,mostnotablybyChebyshev[7],Markov[24],Stieltjes[38],AkhiezerandKrein[1],KarlinandStudden[16].Forcollectedworksonmomentproblems,seealsoShohatandTamarkin[35],Tong[40],Landau[20]andreferencestherein.Giventhe¯rstandsecondmomentofaunivariaterandomvariable,Chebyshev's12Popescu:OptimalMomentBoundsforConvexClassesofDistributionsbySDPMathematicsofOperationsResearch30(x),pp.xxx{xxx,c°2005INFORMSinequality(Chebyshev[7],Markov[24])givesaboundonthedistributionfunction.AgeneralizationofthisresultisduetoBertsimasandPopescu[4]whocomputeoptimalboundsonarbitrarydistributionsgivenany¯nitenumberofgeneralizedmomentsusingsemide¯niteprogramming.Momentboundsareusedtoproviderobust,worstcaseestimatesofunknownrandomquantities.Theseestimates,however,canbeoverlypessimistic.Thereasonisthatmomentboundsareachievedbydiscretedistributions,whicharenotalwaysrealisticforpracticalapplications.Forexample,in¯nance,YamadaandPrimbs[46]observethattheirupperandlowermomentboundscanbefarapart,hencenotprovidingmuchvaluableinformation.Thisispartlyduetoignoringadditionalstructuralpropertiesoftheunderlyingstockpricedistributions.Inaninventorycontrolapplication,Scarf[33]andGallego[12]deriveworstcaseorderquantitiesgivenmean-variancedemandinformation.Theresultingboundisveryconservative,asitcorrespondstoanunrealistictwopointdistributionofdemand.Incontrasttoworstcasemomentbasedestimates,analternateapproachtakenintheliteratureisto¯ta(functional)parametricdistributiontothemomentdata.Forexample,unknown¯nancialquantitiesareusuallymodeledasnormalorlognormaldistributions.Inadecisionsciencescontext,SollandKlayman[37]providemeasuresofovercon¯dencebyestimatingmeanabsolutedispersionandotherdistributionalpropertiesgivensamplequantilesofadistributionwhichisknowntobecontinuousandunimodal.Tomaketheanalysistractable,they¯tabetadistributiontothedata.Thisapproach,akintothemethodofmomentsestimators,isubiquitousinavarietyofsettingsforstatisticalestimation.