Portfolio Optimization with Stochastic Dominance

Constraints

DarinkaDentcheva∗

AndrzejRuszczy´nski†

May12,2003

Abstract

Weconsidertheproblemofconstructingaportfoliooffinitelymanyassetswhose

returnsaredescribedbyadiscretejointdistribution.Weproposeanewportfoliooptimizationmodelinvolvingstochasticdominanceconstraintsontheportfolioreturn.Wedevelopoptimalityanddualitytheoryforthesemodels.Weconstructequivalentoptimizationmodelswithutilityfunctions.Numericalillustrationisprovided.

Keywords:Portfoliooptimization,stochasticdominance,risk,utilityfunctions.

1Introduction

Theproblemofoptimizingaportfoliooffinitelymanyassetsisaclassicalprobleminthe-oreticalandcomputationalfinance.SincetheseminalworkofMarkowitz[19,20,21]itisgenerallyagreedthatportfolioperformanceshouldbemeasuredintwodistinctdimensions:themeandescribingtheexpectedreturn,andtheriskwhichmeasurestheuncertaintyofthereturn.Inthemean–riskapproach,weselectfromtheuniverseofallpossibleportfoliosthosethatareefficient:foragivenvalueofthemeantheyminimizetheriskor,equivalently,foragivenvalueofrisktheymaximizethemean.Thisapproachallowsonetoformulate

StevensInstituteofTechnology,DepartmentofMathematics,Hoboken,NJ,e-mail:ddentche@stevens-tech.edu†

RutgersUniversity,DepartmentofManagementScienceandInformationSystems,Piscataway,NJ08854,USA,e:mail:rusz@rutcor.rutgers.edu

∗

1

PortfolioOptimizationwithStochasticDominanceConstraints2

theproblemasaparametricoptimizationproblem,anditfacilitatesthetrade-offanalysisbetweenmeanandrisk.

Anothertheoreticalapproachtotheportfolioselectionproblemisthatofstochasticdom-inance(see[23,35,17]).Theconceptofstochasticdominanceisrelatedtomodelsofrisk-aversepreferences[7].Itoriginatedfromthetheoryofmajorization[11,22]forthediscretecase,waslaterextendedtogeneraldistributions[27,9,10,30],andisnowwidelyusedineconomicsandfinance[17].

Theusual(firstorder)definitionofstochasticdominancegivesapartialorderinthespaceofrealrandomvariables.Moreimportantfromtheportfoliopointofviewisthenotionofsecond-orderdominance,whichisalsodefinedasapartialorder.Itisequivalenttothis

󰀂󰀃󰀂󰀃

statement:arandomvariableRdominatestherandomvariableYifEu(R)≥Eu(Y)forallnondecreasingconcavefunctionsu(·)forwhichtheseexpectedvaluesarefinite.Thus,norisk-aversedecisionmakerwillpreferaportfoliowithreturnYoveraportfoliowithreturnR.Inourearlierpublications[2,3,4,5]wehaveintroducedanewstochasticoptimizationmodelwithstochasticdominanceconstraints.Inthispaperweshowhowthistheorycanbeusedforrisk-averseportfoliooptimization.Weaddtotheportfolioproblemthecondi-tionthattheportfolioreturnstochasticallydominatesareferencereturn,forexample,thereturnofanindex.Weidentifyconcavenondecreasingutilityfunctionswhichcorrespondtodominanceconstraints.Maximizingtheexpectedreturnmodifiedbytheseutilityfunctions,guaranteesthattheoptimalportfolioreturnwilldominatethegivenreferencereturn.

2Theportfolioproblem

󰀂󰀃

LetR1,R2,...,Rnberandomreturnsofassets1,2,...,n.WeassumethatE|Rj|<∞forallj=1,...,n.

Ouraimistoinvestourcapitalintheseassetsinordertoobtainsomedesirablechar-acteristicsofthetotalreturnontheinvestment.Denotingbyx1,x2,...,xnthefractionsoftheinitialcapitalinvestedinassets1,2,...,nwecaneasilyderivetheformulaforthetotal

PortfolioOptimizationwithStochasticDominanceConstraintsreturn:

R(x)=R1x1+R2x2+···+Rnxn.

Clearly,thesetofpossibleassetallocationscanbedefinedasfollows:

X={x∈Rn:x1+x2+···+xn=1,xj≥0,j=1,2,...,n}.

3

(1)

Insomeapplicationsonemayintroducethepossibilityofshortpositions,i.e.,allowsomexj’stobecomenegative.Otherrestrictionsmaylimittheexposuretoparticularassetsortheirgroups,byimposingupperboundsonthexj’sorontheirpartialsums.Onecanalsolimittheabsolutedifferencesbetweenthexj’sandsomereferenceinvestmentsx¯j,whichmayrepresenttheexistingportfolio,etc.Ouranalysiswillnotdependonthedetailedwaythissetisdefined;weshallonlyusethefactthatitisaconvexpolyhedron.Allmodificationsdiscussedabovedefinesomeconvexpolyhedralfeasiblesets,andare,therefore,coveredbyourapproach.

Themaindifficultyinformulatingameaningfulportfoliooptimizationproblemisthedefinitionofthepreferencestructureamongfeasibleportfolios.Ifweuseonlythemeanreturn

󰀂󰀃

µ(x)=ER(x),

thentheresultingoptimizationproblemhasatrivialandmeaninglesssolution:investev-erythinginassetsthathavethemaximumexpectedreturn.Forthesereasonsthepracticeofportfoliooptimizationresortsusuallytotwoapproaches.

Inthefirstapproachweassociatewithportfolioxsomeriskmeasureρ(x)representingthevariabilityofthereturnR(x).IntheclassicalMarkowitzmodelρ(x)isthevarianceofthereturn,

󰀂󰀃

ρ(x)=VarR(x),

butmanyothermeasuresarepossiblehereaswell.

Themean–riskportfoliooptimizationproblemisformulatedasfollows:

maxµ(x)−λρ(x).

x∈X

(2)

PortfolioOptimizationwithStochasticDominanceConstraints4

Here,λisanonnegativeparameterrepresentingourdesirableexchangerateofmeanforrisk.Ifλ=0,theriskhasnovalueandtheproblemreducestotheproblemofmaximizingthemean.Ifλ>0welookforacompromisebetweenthemeanandtherisk.Thegeneralquestionofconstructingmean–riskmodelswhichareinharmonywiththestochasticdom-inancerelationshasbeenthesubjectoftheanalysisoftherecentpapers[24,25,26,32].Wehaveidentifiedthereseveralprimalriskmeasures,mostnotablycentralsemideviations,anddualriskmeasures,basedontheLorenzcurve,whichareconsistentwiththestochasticdominancerelations.

Thesecondapproachistoselectacertainutilityfunctionu:R→Randtoformulatethefollowingoptimizationproblem

󰀃

maxEu(R(x)).

x∈X

󰀂

(3)

Itisusuallyrequiredthatthefunctionu(·)isconcaveandnondecreasing,thusrepresentingpreferencesofarisk-aversedecisionmaker[7,8].Thechallengehereistoselecttheappro-priateutilityfunctionthatrepresentswellourpreferencesandwhoseapplicationleadstonon-trivialandmeaningfulsolutionsof(3).

Anotherwaytoincorporaterisk-aversionintothemodelistheuseofValueatRisk(VaR)constraints[6]andConditionalValueatRisk(CVaR)constraints[29].

Inthispaperweproposeanalternativeapproach,byintroducingacomparisontoareferencereturnintoouroptimizationproblem.Thecomparisonisbasedonthestochas-ticdominancerelation.Morespecifically,weshallconsideronlyportfolioswhosereturnstochasticallydominatesacertainreferencereturn.

3Stochasticdominance

Inthestochasticdominanceapproach,randomreturnsarecomparedbyapoint-wisecom-parisonofsomeperformancefunctionsconstructedfromtheirdistributionfunctions.ForarealrandomvariableV,itsfirstperformancefunctionisdefinedastheright-continuous

PortfolioOptimizationwithStochasticDominanceConstraintscumulativedistributionfunctionofV:

F(V;η)=P{V≤η}forη∈R.

5

ArandomreturnVissaid[16,27]tostochasticallydominateanotherrandomreturnStothefirstorder,denotedV󰀆FSDS,if

F(V;η)≤F(S;η)forallη∈R.

ThesecondperformancefunctionF2isgivenbyareasbelowthedistributionfunctionF,

󰀇η

F2(V;η)=F(V;ξ)dξforη∈R,

−∞

anddefinestheweakrelationofthesecond-orderstochasticdominance(SSD).Thatis,randomreturnVstochasticallydominatesStothesecondorder,denotedV󰀆SSDS,if

F2(V;η)≤F2(S;η)forallη∈R.

(see[9,10,30]).Thecorrespondingstrictdominancerelations󰀇FSDand󰀇SSDaredefinedintheusualway:V󰀇SifandonlyifV󰀆S,S󰀆V.

BychangingtheorderofintegrationwecanexpressthefunctionF2(V;·)astheexpectedshortfall[24]:foreachtargetvalueηwehave

󰀂󰀃

F2(V;η)=E(η−V)+,

(4)

where(η−V)+=max(η−V,0).ThefunctionF(2)(V;·)iscontinuous,convex,nonnegativeandnondecreasing.ItiswelldefinedforallrandomvariablesVwithfiniteexpectedvalue.Inthecontextofportfoliooptimization,weshallconsiderstochasticdominancerelationsbetweenrandomreturnsdefinedby(1).Thus,wesaythatportfolioxdominatesportfolioyundertheFSDrules,if

F(R(x);η)≤F(R(y);η)forallη∈R,

PortfolioOptimizationwithStochasticDominanceConstraints6

whereatleastonestrictinequalityholds.Similarly,wesaythatxdominatesyundertheSSDrules(R(x)󰀇SSDR(y)),if

F2(R(x);η)≤F2(R(y);η)forallη∈R,

withatleastoneinequalitystrict.RecallthattheindividualreturnsRjhavefiniteexpectedvaluesandthusthefunctionF2(R(x);·)iswelldefined.

Stochasticdominancerelationsareofcrucialimportancefordecisiontheory.ItisknownthatR(x)󰀆FSDR(y)ifandonlyif

󰀂󰀃󰀂󰀃Eu(R(x))≥Eu(R(y))

(5)

foranynondecreasingfunctionu(·)forwhichtheseexpectedvaluesarefinite.Furthermore,R(x)󰀆SSDR(y)ifandonlyif(5)holdstrueforeverynondecreasingandconcaveu(·)forwhichtheseexpectedvaluesarefinite(see,e.g.,[17]).

AportfolioxiscalledSSD-efficient(orFSD-efficient)inasetofportfoliosXifthereisnoy∈XsuchthatR(y)󰀇SSDR(x)(orR(y)󰀇FSDR(x)).

WeshallfocusourattentionontheSSDrelation,becauseofitsconsistencywithrisk-aversepreferences:ifR(x)󰀇SSDR(y),thenportfolioxispreferredtoybyallrisk-aversedecisionmakers.

4Thedominance-constrainedportfolioproblem

ThestartingpointforourmodelistheassumptionthatareferencerandomreturnYhavingafiniteexpectedvalueisavailable.ItmayhavetheformY=R(¯z),forsomereferenceportfolioz¯.Itmaybeanindexorourcurrentportfolio.Ourintentionistohavethereturnofthenewportfolio,R(x),preferableoverY.Therefore,weintroducethefollowing

PortfolioOptimizationwithStochasticDominanceConstraintsoptimizationproblem:

maxf(x)subjecttoR(x)󰀆(2)Y,

x∈X.

Heref:X→Risaconcavecontinuousfunction.Inparticular,wemayuse

󰀃

f(x)=ER(x)

󰀂

7

(6)(7)(8)

andthiswillstillleadtonontrivialsolutions,duetothepresenceofthedominancecon-straint(7).

TherearefundamentalrelationsbetweentheconceptsofVaRandCVaRandthestochas-ticdominanceconstraints.TheVaRconstraintintheportfoliocontextisformulatedasfollows.Wespecifythemaximumfractionωoftheinitialcapitalallowedforriskexposureatrisklevelα∈(0,1),andwerequirethat

󰀂󰀃

PR(x)≥−ω≥1−α.

Denotingbyξα(V)therightα-quantileofarandomvariableV,wecanequivalentlyformulatetheVaRconstraintas

ξα(R(x))≥−ω.

TheCVaRatlevelα,roughlyspeaking,hastheform

󰀃

CVaRα(R(x))=ER(x)|R(x)≤ξα(R(x)).

Thisformulaispreciseifξα(R(x))isnotanatomofthedistributionofR(x).AmoreprecisedescriptionusesextremalpropertiesofquantilesandequivalentlyrepresentsCVaRasfollows(see[29]):

󰀃󰀋1󰀂

CVaRα(R(x))=supη−E(η−R(x))+.

αη

󰀊󰀂

(9)

PortfolioOptimizationwithStochasticDominanceConstraints

TheCVaRconstraintfortheportfolioproblemcanbeformulatedasfollows:

CVaRα(R(x))≥−ω.

Itisthefinancialcounterpartoftheintegratedchanceconstraintintroducedin[14].

8

(10)

Theorem1Thesecondorderstochasticdominanceconstraint(7)isequivalenttothecon-tinuumofCVaRconstraints:

CVaRα(R(x))≥CVaRα(Y)forallα∈(0,1].

Proof.LetusconsiderforarealrandomvariableVthefunction

G(α,V)=αCVaRα(V),

α∈(0,1].

(11)

Forα=0wesetG(0,V)=0.ThefunctionG(·,V)isfrequentlyreferredtoastheabsoluteLorenzcurve(see[18,26]).Itfollowsfrom(9)and(4)that

󰀊

G(α,R(x))=supαη−E(η−R(x))+

η

󰀊󰀋=supαη−F2(R(x);η).

η

󰀂

󰀃󰀋

ThereforeG(·,R(x))istheFenchelconjugateofthefunctionF2(R(x);·)(see[28]forthetheoryofconjugateduality).Thesecondorderdominancerelation(7)isequivalentto

F2(R(x);η)≤F2(Y;η)forallη∈R,

whichimpliesthat

G(α,R(x))≥G(α,Y)forallα∈(0,1].

(12)

SinceF2(R(x);·)iscontinuous,byconjugatedualityweconcludethat(7)isequivalentto(12).ThisisthesameasthepostulatedcontinuumofCVaRconstraints.

󰀁

PortfolioOptimizationwithStochasticDominanceConstraints9

InthestochasticdominanceconstraintthefractionωαoftheinitialcapitalallowedforriskexposureatlevelαisgivenbytherandomreferenceoutcomeY:

ωα=−CVaRα(Y),

α∈(0,1].

WhenthereferenceoutcomeYisdiscretethecontinuumofstochasticdominanceconstraintscanbereplacedbyfinitelymanyinequalities[4].

Proposition1AssumethatYhasadiscretedistributionwithrealizationsyi,i=1,...,m.Thenrelation(7)isequivalentto

󰀂󰀃󰀂󰀃E(yi−R(x))+≤E(yi−Y)+,

i=1,...,m.

(13)

ThisresultdoesnotimplythatthecontinuumofCVaRconstraints(11)canbereplacedbyfinitelymanyconstraintsofform

CVaRαi(R(x))≥CVaRαi(Y)i=1,...,m,

withsomefixedprobabilitiesαi,i=1,...,m.

Letusassumenowthatthereturnshaveadiscretejointdistributionwithrealizationsrjt,t=1,...,T,j=1,...,n,attainedwithprobabilitiespt,t=1,2,...,T.Thentheformulationofthestochasticdominancerelation(7)resp.(13)simplifiesevenfurther.In-troducingvariablessitrepresentingshortfallofR(x)belowyiinrealizationt,i=1,...,m,t=1,...,T,wecanformulatetheproblem

maxf(x)

n󰀆

subjecttoxjrjt+sit≥yi,

j=1T󰀆t=1

(14)

i=1,...,m,i=1,...,m,t=1,...,T.

t=1,...,T,

(15)(16)(17)(18)

ptsit≤F2(Y;yi),

i=1,...,m,

sit≥0,x∈X.

PortfolioOptimizationwithStochasticDominanceConstraintsForeveryfeasiblepointxof(6)–(8),setting

󰀄

sit=max0,yi−

n󰀆j=1

10

󰀅xjrjt,

i=1,...,m,

t=1,...,T,

weobtainafeasiblepair(x,s)for(15)–(18).Conversely,foranyfeasiblepair(x,s)for(15)–(18),inequalities(15)and(17)implythat

󰀄

sit≥max0,yi−

n󰀆j=1

󰀅xjrjt,

i=1,...,m,t=1,...,T.

Takingtheexpectedvalueofbothsidesandusing(16)weobtain

F2(R(x);yi)≤F2(Y;yi),

i=1,...,m.

Proposition1impliesthatxisfeasibleforproblem(6)–(8).Therefore,wehavethefollowingresult(see[4]).

Proposition2AssumethatRj,j=1,...,n,andYhavediscretedistributions.Thenproblem(6)–(8)isequivalenttoproblem14)–(18).

SimilarlytotheremarkfollowingTheorem1,itshouldbestressedthatnosimplificationin(11)canbemadeevenfordiscretejointdistributions.AmodelinvolvingfinitelymanyCVaRconstraintswillconstitutearelaxationofthemodelwiththestochasticdominanceconstraint.

5OptimalityandDuality

FromnowonweshallassumethattheprobabilitydistributionsofthereturnsandofthereferenceoutcomeYarediscretewithfinitelymanyrealizations.WealsoassumethattherealizationsofYareordered:y1PortfolioOptimizationwithStochasticDominanceConstraints

WedefinethesetUoffunctionsu:R→Rsatisfyingthefollowingconditions:

u(·)isconcaveandnondecreasing;

u(·)ispiecewiselinearwithbreakpointsyi,i=1,...,m;u(t)=0forallt≥ym.

ItisevidentthatUisaconvexcone.

LetusdefinetheLagrangianof(6)–(8),L:Rn×U→R,asfollows

󰀂󰀃󰀂󰀃

L(x,u)=f(x)+Eu(R(x))−Eu(Y).

n

11

(19)󰀂

󰀃

Itiswelldefined,becauseforeveryu∈Uandeveryx∈RtheexpectedvalueEu(R(x))existsandisfinite.

Thefollowingtheoremhasbeenprovedinamoregeneralversionin[4],underanaddi-tionalconstraintqualificationcondition.Hereweprovideadirectproofforthespecialcaseofportfoliooptimizationwithjointdiscretedistributions.

Theorem2Ifxˆisanoptimalsolutionof(6)–(8)thenthereexistsafunctionuˆ∈Usuchthat

L(ˆx,uˆ)=maxL(x,uˆ)

x∈X

(20)

and

󰀃󰀂󰀃

Euˆ(R(ˆx))=Euˆ(Y).󰀂

(21)

Conversely,ifforsomefunctionuˆ∈Uanoptimalsolutionxˆof(20)satisfies(7)and(21),thenxˆisanoptimalsolutionof(6)–(8).

Proof.ByProposition2problem(6)–(8)isequivalenttoproblem(14)–(18).WeassociateLagrangemultipliersµ∈Rmwithconstraints(16)andweformulatetheLagrangianΛ:Rn×RmT×Rm→Rasfollows:

Λ(x,s,µ)=f(x)+

m󰀆i=1

󰀄

µiF2(Y;yi)−

T󰀆t=1

󰀅ptsit.

PortfolioOptimizationwithStochasticDominanceConstraintsLetusdefinetheset

Z=(x,s)∈X×RmT+:

󰀊

n󰀆j=1

12

󰀋

xjrjt+sit≥yi,i=1,...,m,t=1,...,T.

SinceZisaconvexclosedpolyhedralset,theconstraints(16)arelinear,andtheobjectivefunctionisconcave,ifthepoint(ˆx,sˆ)isanoptimalsolutionofproblem(6)–(8),thenthefollowingKarush-Kuhn-Tuckeroptimalityconditionsholdtrue.Thereexistsavectorofmultipliersµˆ≥0suchthat:

Λ(ˆx,sˆ,µˆ)=maxΛ(x,s,µˆ)

(x,s)∈Z

(22)

and

󰀄

µˆiF2(Y;yi)−

T󰀆t=1

󰀅ptsˆit=0,

i=1,...,m.

(23)

WecantransformtheLagrangianΛasfollows:

Λ(x,s,µ)=f(x)+

=f(x)+

m󰀆i=1

m󰀆i=1

µiF2(Y;yi)−µiF2(Y;yi)−

m󰀆T󰀆

µiptsitµisit.

i=1t=1

Tm󰀆󰀆

pt

t=1i=1

Foranyfixedxthemaximizationwithrespecttossuchthat(x,s)∈Zyields

n󰀄󰀅󰀆󰀌󰀁

sit=max0,yi−xjrjt=max0,yi−[R(x)]t,

j=1

i=1,...,m,t=1,...,T,

where[R(x)]tisthet-threalizationoftheportfolioreturn.Definethefunctionsui:R→R,i=1,...,mby

ui(η)=−max(0,yi−η),

andlet

uµ(η)=

m󰀆i=1

µiui(η).

PortfolioOptimizationwithStochasticDominanceConstraints13

Letusobservethatuµ∈U.WecanrewritetheresultofmaximizationoftheLagrangianΛwithrespecttosasfollows:

maxΛ(x,s,µ)=f(x)+

s

m󰀆i=1m󰀆i=1

µiF2(Y;yi)+µiF2(Y;yi)+

T󰀆t=1

T󰀆t=1

pt

m󰀆i=1

µiui[R(x)]t

󰀌󰀁

(24)

=f(x)+

󰀁ptuµ[R(x)]t.

󰀌

Furthermore,wecanobtainasimilarexpressionforthesuminvolvingY:

m󰀆i=1

µiF2(Y;yi)=

=

m󰀆i=1

m󰀆k=1

µiπk

m󰀆k=1

m󰀆i=1

πkmax(0,yi−yk)µimax(0,yi−yk)=−

m󰀆k=1

πkuµ(yk).

Substitutinginto(24),weobtain

󰀃󰀂󰀃

maxΛ(x,s,µ)=f(x)+Euµ(R(x))−Euµ(Y)=L(x,uµ).

s

󰀂

(25)

Settinguˆ:=uµˆweconcludethattheconditions(22)imply(20),asrequired.Further-more,addingthecomplementarityconditions(23)overi=1,...,m,andusingthesametransformationweget(21).

Toprovetheconverse,letusobservethatforeveryuˆ∈Uwecandefine

µˆi=uˆ󰀈−(yi)−uˆ󰀈+(yi),

i=1,...,m,

withuˆ󰀈−anduˆ󰀈+denotingtheleftandrightderivativesofuˆ:

uˆ󰀈−(η)=lim

t↑η

uˆ(η)−uˆ(t)

,

η−t

uˆ󰀈+(η)=lim

t↓η

uˆ(t)−uˆ(η)

.

t−η

Sinceuˆisconcave,µˆ≥0.Usingtheelementaryfunctionsui(η)=−max(0,yi−η)wecanrepresentuˆasfollows:

uˆ(η)=

m󰀆i=1

µˆiui(η).

PortfolioOptimizationwithStochasticDominanceConstraints14

Consequently,correspondence(25)holdstrueforµˆanduˆ.Therefore,ifxˆisthemaximizerof(20),thenthepair(ˆx,sˆ),with

󰀄

sˆit=max0,yi−

n󰀆j=1

󰀅xˆjrjt,

i=1,...,m,

t=1,...,T,

isthemaximizerofΛ(x,s,µˆ),over(x,s)∈Z.Ourresultfollowsthenfromstandardsufficientconditionsforproblem(14)–(18)(see,e.g.,[28,Thm.28.1]).

󰀁

Wecanalsodevelopdualityrelationsforourproblem.WiththeLagrangian(19)wecanassociatethedualfunction

D(u)=maxL(x,u).

x∈X

Weareallowedtowritethemaximizationoperationhere,becausethesetXiscompactandL(·,u)iscontinuous.

Thedualproblemhastheform

minD(u).

u∈U

(26)

ThesetUisaclosedconvexconeandD(·)isaconvexfunction,so(26)isaconvexopti-mizationproblem.

Theorem3Assumethat(6)–(8)hasanoptimalsolution.Thenproblem(26)hasanoptimalsolutionandtheoptimalvaluesofbothproblemscoincide.Furthermore,thesetofoptimalsolutionsof(26)isthesetoffunctionsuˆ∈Usatisfying(20)–(21)foranoptimalsolutionxˆof(6)–(8).

Proof.ThetheoremisaneasyconsequenceofTheorem2andgeneraldualityrelationsinconvexnonlinearprogramming(see[1,Thm.2.165]).Notethatallconstraintsofourprob-lemarelinearorconvexpolyhedral,andthereforewedonotneedanyconstraintqualificationconditionshere.

PortfolioOptimizationwithStochasticDominanceConstraints15

6Splitting

Letusnowconsiderthespecialformofproblem(6)–(8),with

f(x)=E[R(x)].

RecallthattherandomreturnsRj,j=1,...,n,havediscretedistributionswithrealizationsrjt,t=1,...,T,attainedwithprobabilitiespt.

Inordertofacilitatenumericalsolutionofproblem(6)–(8),itisconvenienttoconsideritssplit-variableform:

maxE[R(x)]subjecttoR(x)≥V,

V󰀆(2)Y,x∈X.

a.s.,

(27)(28)(29)(30)

Intheaboveproblem,Visarandomvariablehavingrealizationsvtattainedwithprobabil-itiespt,t=1,...,T,andrelation(28)isunderstoodalmostsurely.Inthecaseoffinitelymanyrealizationsitsimplymeansthat

n󰀆j=1

rjtxj≥vt,t=1,...,T.(31)

WeshallconsidertwogroupsofLagrangemultipliers:autilityfunctionu∈U,andavectorθ∈RT,θ≥0.Theutilityfunctionu(·)willcorrespondtothedominanceconstraint(29),asintheprecedingsection.Themultipliersptθt,t=1,...,T,willcorrespondtotheinequalities(31).TheLagrangiantakesontheform

L(x,V,u,θ)=

T󰀆t=1

pt

n󰀆j=1

rjtxj+

T󰀆t=1

n󰀆

ptθt(rjtxj−vt)

j=1

+

T󰀆t=1

ptu(vt)−

m󰀆k=1

(32)

πku(yk).

Theoptimalityconditionscanbeformulatedasfollows.

PortfolioOptimizationwithStochasticDominanceConstraints16

ˆ)isanoptimalsolutionof(27)–(30),thenthereexistuTheorem4If(ˆx,Vˆ∈Uandaˆ∈RT,suchthatnonnegativevectorθ

ˆ)=ˆ,uL(ˆx,Vˆ,θ

T󰀆t=1

(x,V)∈X×RT

m󰀆k=1

max

ˆ),L(x,V,uˆ,θ

(33)(34)(35)

ptuˆ(ˆvt)−

n󰀆j=1

πkuˆ(yk)=0,

t=1,...,T.

ˆt(ˆθvt−

rjtxˆj)=0,

ˆ∈RT,anoptimalsolutionConversely,ifforsomefunctionuˆ∈Uandnonnegativevectorθˆ)of(33)satisfies(28)–(29)and(34)–(35),then(ˆˆ)isanoptimalsolutionof(27)–(ˆx,Vx,V(30).

Proof.ByProposition1,thedominanceconstraint(29)isequivalenttofinitelymanyinequalities

󰀂

󰀃

󰀂

󰀃

E(yi−R(x))+≤E(yi−Y)+,

Problem(27)–(30)takesontheform:

maxE[R(x)]

n󰀆

subjecttorjtxj≥vt,

j=1

i=1,...,m.

t=1,...,T,󰀃

󰀂

󰀃

i=1,...,m,

E(yi−R(x))+≤E(yi−Y)+,x∈X.

󰀂

LetusintroduceLagrangemultipliersµi,i=1,...,m,associatedwiththedominanceconstraints.ThestandardLagrangiantakesontheform:

Λ(x,V,µ,θ)=

T󰀆t=1

pt

n󰀆j=1

rjtxj+

T󰀆t=1

ptθt(

n󰀆j=1

rjtxj−vt)

m󰀆i=1

−

m󰀆i=1

µi

T󰀆t=1

pt[yi−

n󰀆j=1

rjtxj]++µi

m󰀆k=1

πk[yi−yk]+.

PortfolioOptimizationwithStochasticDominanceConstraints17

Rearrangingthelasttwosums,exactlyasintheproofofTheorem2,weobtainthefollowingkeyrelation.Foreveryµ≥0,setting

uµ(η)=−

wehave

Λ(x,V,µ,θ)=L(x,V,uµ,θ).

TheremainingpartoftheproofisthesameastheproofofTheorem2.Thedualfunctionassociatedwiththesplit-variableproblemhastheform

D(u,θ)=

andthedualproblemis,asusual,

u∈U,θ≥0m󰀆i=1

µimax(0,yi−η),

sup

x∈X,V

∈RT

L(x,V,u,θ).

minD(u,θ).(36)

ThecorrespondingdualitytheoremisanimmediateconsequenceofTheorem4andstandarddualityrelationsinconvexprogramming.Notethatallconstraintsofourproblem(27)–(30)arelinearorconvexpolyhedral,andthereforewedonotneedadditionalconstraintqualificationconditionshere.

Theorem5Assumethat(27)–(30)hasanoptimalsolution.Thenthedualproblem(36)hasanoptimalsolutionandtheoptimalvaluesofbothproblemscoincide.Furthermore,theˆ≥0satisfyingsetofoptimalsolutionsof(36)isthesetoffunctionsuˆ∈Uandvectorsθˆ)of(27)–(30).(33)–(35)foranoptimalsolution(ˆx,V

Letusanalyzeinmoredetailthestructureofthedualfunction:D(u,θ)=

sup

x∈X,V

∈RT

T󰀊󰀆t=1

pt

n󰀆j=1

rjtxj+

T󰀆t=1

Tmn󰀋󰀆󰀆󰀆

rjtxj−vt)+ptu(vt)−πku(yk)ptθt(

j=1

t=1

k=1

=max

x∈X

n󰀆T󰀆j=1t=1T󰀆t=1

mT󰀆󰀃󰀆󰀂

πku(yk)pt(1+θt)rjtxj+supptu(vt)−θtvt−

V

t=1

k=1

T󰀆t=1

=max

1≤j≤n

pt(1+θt)rjt+ptsupu(vt)−θtvt−

vt

󰀂󰀃

m󰀆k=1

πku(yk).

PortfolioOptimizationwithStochasticDominanceConstraints18

InthelastequationwehaveusedthefactthatXisasimplexandthereforethemaximumofalinearformisattainedatoneofitsvertices.Itfollowsthatthedualfunctioncanbeexpressedasthesum

D(u,θ)=D0(θ)+

with

D0(θ)=max

󰀂

1≤j≤n

T󰀆t=1

ptDt(u,θt)+DT+1(u),(37)

T󰀆t=1

pt(1+θt)rjt,󰀃

t=1,...,T,

(38)(39)

Dt(u,θt)=supu(vt)−θtvt,

vt

and

DT+1(u)=−

m󰀆k=1

πku(yk).(40)

IfthesetXisageneralconvexpolyhedron,thecalculationofD0involvesalinearprogram-mingproblemwithnvariables.

Todeterminethedomainofthedualfunction,observethatifu󰀈−(y1)<θtthen

vt→∞

limu(vt)−θtvt=+∞,

󰀂󰀃

andthusthesupremumin(39)isequalto+∞.Ontheotherhand,ifu󰀈−(y1)≥θt,thenthefunctionu(vt)−θtvthasanonnegativeslopeforvt≤y1andnonpositiveslope−θtforvt≥ym.Itispiecewiselinearanditachievesitsmaximumatoneofthebreakpoints.Therefore

domDt={(u,θt)∈U×R+:u󰀈−(y1)≥θt}.

Atanypointofthedomain,

󰀃󰀂

Dt(u,θt)=maxu(yk)−θtyk.

1≤k≤m

(41)

ThedomainofD0istheentirespaceRT.

PortfolioOptimizationwithStochasticDominanceConstraints19

7Decomposition

ItfollowsfromouranalysisthatthedualfunctioncanbeexpressedasaweightedsumofT+2functions(38)–(40).

Inordertoanalyzetheirpropertiesandtodevelopanumericalmethodweneedtofindaproperrepresentationoftheutilityfunctionu.Werepresentthefunctionubyitsslopesbetweenbreakpoints.Letusdenotethevaluesofuatitsbreakpointsby

uk=u(yk),

Weintroducetheslopevariables

βk=u󰀈−(yk),

k=1,...,m.k=1,...,m.

Thevectorβ=(β1,...,βm)isnonnegative,becauseuisnondecreasing.Asuisconcave,βk≥βk+1,k=1,...,m−1.Wecanrepresentthevaluesofuatbreakpointsasfollows

uk=−

󰀆

󰀌>k

β󰀌(y󰀌−y󰀌−1),k=1,...,m.

Thefunction(41)takesontheform

Dt(u,θt)=maxuk−θtyk=max

1≤k≤m

󰀂󰀃

󰀈

1≤k≤m

−

󰀆

󰀌>k

󰀉

β󰀌(y󰀌−y󰀌−1)−θtyk.

InthiswaywehaveexpressedDt(u,θt)asafunctionoftheslopevectorβ∈Rmandofθt∈R+.Wedenote

󰀈

Bt(β,θt)=max

1≤k≤m

−

󰀆

󰀌>k

󰀉

β󰀌(y󰀌−y󰀌−1)−θtyk.

(42)

ObservethatBtisthemaximumoffinitelymanylinearfunctionsinitsdomain.Thedomainisaconvexpolyhedrondefinedby

0≤θt≤β1.

Consequently,Btisaconvexpolyhedralfunction.Thereforeitssubgradientatapoint(β,θt)ofthedomaincanbecalculatedasthegradientofthelinearfunctionatwhichthemaximum

PortfolioOptimizationwithStochasticDominanceConstraints20

in(42)isattained.Letk∗betheindexofthislinearfunction.Denotingbyδ󰀌the󰀞thunitvectorinRmweobtainthefollowingsubgradientofBt(β,θt):

󰀄−󰀆

󰀌>k∗

󰀅

δ󰀌(y󰀌−y󰀌−1),−yk∗.

Similarly,function(40)canberepresentedasafunctionBT+1oftheslopevectorβ:

BT+1(β)=

m󰀆k=1

πk

󰀆

󰀌>k

β󰀌(y󰀌−y󰀌−1).

Itislinearinβanditsgradienthastheform

n󰀆󰀌=1

δ󰀌

󰀆

k<󰀌

πk(y󰀌−y󰀌−1).

Finally,denotingbyj∗theindexatwhichthemaximumin(38)isattained,weseethatthevectorwithcoordinates

ptrj∗t,

isasubgradientofD0.

Summingup,withourrepresentationoftheutilityfunctionbyitsslopes,thedualfunc-tionisasumofT+2convexpolyhedralfunctionswithknowndomains.Moreover,theirsubgradientsarereadilyavailable.Thereforethedualproblemcanbesolvedbynonsmoothoptimizationmethods(see[13,12]).Wehavedevelopedaspecializedversionoftheregular-izeddecompositionmethoddescribedin[31].Thisapproachisparticularlysuitable,becausethedualfunctionisasumofverymanypolyhedralfunctions.

ˆθˆ),butAfterthedualproblemissolved,weobtainnotonlytheoptimaldualsolution(β,alsoacollectionofactivecuttingplanesforeachcomponentofthedualfunction.

LetusdenotebyJ0thecollectionofactivecutsforD0.EachcuttingplaneforD0providesasubgradient(43)attheoptimaldualsolution.AconvexcombinationofthesesubgradientsprovidesthesubgradientofD0thatenterstheoptimalityconditionsforthedualproblem.Thecoefficientsofthisconvexcombinationarealsoidentifiedbytheregularized

t=1,...,T,

(43)

PortfolioOptimizationwithStochasticDominanceConstraints21

decompositionmethod.Letg0denotethissubgradientandletνj,j∈J0thecorrespondingcoefficients.Then

g0=

where

νj≥0,

T󰀆t=1

δt

󰀆

j∈J0

ptrjtνj,

󰀆

j∈J0

νj=1.

ForeachtthesubgradientofBtwithrespecttoθtenteringtheoptimalityconditionsis

vˆt∈conv{yk∗:k∗isamaximizerin(42)}.

Therefore

g0−

T󰀆t=1

ptvˆt=0.

Usingtheserelationswecanverifythatvˆisthevectorofoptimalportfolioreturnsinscenariost=1,...,T.Thustheoptimalportfoliohastheweightsxˆj=νjforj∈J0,andxˆj=0forj∈J0.

8NumericalIllustration

Wehavetestedourapproachonabasketof719real-worldassets,using616possiblereal-izationsoftheirjointreturns[32].Historicaldataonweeklyreturnsinthe12yearsfromSpring1990toSpring2002wereusedasequallylikelyrealizations.

WehaveusedfourreferencereturnsY.Eachofthemwasconstructedasreturnofacertainindexcomposedofourassets.Sinceweactuallyknowthepastreturns,forthepurposeofcomparisonwehaveselectedequallyweightedindexescomposedoftheNassetshavingthehighestaveragereturninthisperiod.ReferencePortfolio1correspondstoN=26,ReferencePortfolio2correspondstoN=54,ReferencePortfolio3correspondstoN=82,andReferencePortfolio4correspondstoN=200.Ourproblemwastomaximizetheexpectedreturn,undertheconditionthatthereturnofthereferenceportfolioisdominated.

PortfolioOptimizationwithStochasticDominanceConstraints

Return

22

-0.03-0.025-0.02-0.015-0.01-0.00500.005

0.01

0

-0.005

Reference Portfolio 1Reference Portfolio 2Reference Portfolio 3Reference Portfolio 4Utility-0.01

Figure1:Utilityfunctionscorrespondingtodominanceconstraintsforfourreferenceport-folios.Sincethereferencepointwasareturnofaportfoliocomposedfromthesamebasket,wehavem=T=616inthiscase.Thedualproblemofminimizing(37)has1335decisionvariables:theutilityfunctionu,representedbythevectorofslopesβ∈R616,andthemultiplierθ∈R616.Thenumberoffunctionsin(37)equals618.Ourmethodperformedverywellandconvergedtotheoptimalsolutionin100–200iter-ations,dependingonthecase,inca.20minCPUtimeona1.6GHzPCcomputer.Theutilityfunctions,whichplaytheroleoftheLagrangemultipliersforthedominanceconstraintareillustratedinFigure1.WeseethatforReferencePortfolio1,whichcontains

PortfolioOptimizationwithStochasticDominanceConstraints23

onlyasmallnumberoffastgrowingassets,theutilityfunctioniszeroonalmosttheentirerangeofreturns.Onlyverynegativereturnsarepenalized.

Ifthereferenceportfoliocontainsmoreassets,andisthereforemorediversifiedandlessrisky,inordertodominateit,wehavetouseautilityfunctionwhichintroducespenaltyforabroaderrangeofreturnsandissteeper.ForthebroadlybasedindexinReferencePortfolio4,theoptimalutilityfunctionismoresmoothandcoversevenpositivereturns.Itisworthmentioningthatalltheseutilityfunctions,althoughnondecreasingandcon-cave,haverathercomplicatedshapes.Itwouldbeaveryhardtasktoguesstheutilityfunctionthatshouldbeusedtoobtainasolutionwhichdominatesourreferenceportfolio.

References

[1]J.F.BonnansandA.Shapiro,PerturbationAnalysisofOptimizationProblems,

Springer-Verlag,NewYork,2000.

´ski,Optimizationunderlinearstochasticdomi-[2]D.DentchevaandA.Ruszczyn

nance,ComptesRendusdel’AcademieBulgaredesSciences56(2003),No.6,pp.6–11.´ski,Optimizationundernonlinearstochasticdomi-[3]D.DentchevaandA.Ruszczyn

nance,ComptesRendusdel’AcademieBulgaredesSciences56(2003),No.7,pp.19–25.´ski,Optimizationwithstochasticdominancecon-[4]D.DentchevaandA.Ruszczyn

straints,SIAMJournalonOptimization14(2003),pp.548–566..

´ski,Optimalityanddualitytheoryforstochastic[5]D.DentchevaandA.Ruszczyn

optimizationproblemswithnonlineardominanceconstraints,MathematicalProgram-ming,acceptedforpublication.

[6]K.Dowd,BeyondValueatRisk.TheScienceofRiskManagement,Wiley,NewYork,

1997.

[7]P.C.Fishburn,DecisionandValueTheory,JohnWiley&Sons,NewYork,19.

PortfolioOptimizationwithStochasticDominanceConstraints

[8]P.C.Fishburn,UtilityTheoryforDecisionMaking,Wiley,NewYork,1970.

24

[9]J.HadarandW.Russell,Rulesfororderinguncertainprospects,TheAmaerican

EconomicReview59(1969),pp.25–34.

[10]G.HanochandH.Levy,Theefficiencyanalysisofchoicesinvolvingrisk,Reviewof

EconomicStudies36(1969),pp.335–346.

´lya,Inequalities,CambridgeUniversity[11]G.H.Hardy,J.E.LittlewoodandG.Po

Press,Cambridge,MA,1934.

´chal,ConvexAnalysisandMinimization[12]J.-B.Hiriart-UrrutyandC.Lemare

Algorithms,Springer-Verlag,Berlin,1993.

[13]K.C.Kiwiel,MethodsofDescentforNondifferentiableOptimization,LectureNotes

inMathematics1133,Springer-Verlag,Berlin,1985.

[14]W.K.KleinHaneveld,DualityinStochasticLinearandDynamicProgramming,

LectureNotesinEconomicsandMathematicalSystems274,Springer-Verlag,NewYork,1986.

[15]H.KonnoandH.Yamazaki,Mean–absolutedeviationportfoliooptimizationmodel

anditsapplicationtoTokyostockmarket,ManagementScience37(1991),pp.519–531.[16]E.Lehmann,Orderedfamiliesofdistributions,AnnalsofMathematicalStatistics26

(1955),pp.399–419.

[17]H.Levy,Stochasticdominanceandexpectedutility:surveyandanalysis,Management

Science38(1992),pp.555–593.

[18]M.O.Lorenz,Methodsofmeasuringconcentrationofwealth,JournaloftheAmerican

StatisticalAssociation9(1905),pp.209–219.

[19]H.M.Markowitz,Portfolioselection,JournalofFinance7(1952),pp.77–91.

PortfolioOptimizationwithStochasticDominanceConstraints

[20]H.M.Markowitz,PortfolioSelection,JohnWiley&Sons,NewYork,1959.

25

[21]H.M.Markowitz,Mean–VarianceAnalysisinPortfolioChoiceandCapitalMarkets,

Blackwell,Oxford,1987.

[22]A.W.MarshallandI.Olkin,Inequalities:TheoryofMajorizationandItsAppli-cations,AcademicPress,SanDiego,1979.

[23]K.MoslerandM.Scarsini(Eds.),StochasticOrdersandDecisionUnderRisk,

InstituteofMathematicalStatistics,Hayward,California,1991.

´ski,Fromstochasticdominancetomean–riskmod-[24]W.OgryczakandA.Ruszczyn

els:semideviationsasriskmeasures,EuropeanJournalofOperationalResearch116(1999),pp.33–50.

´ski,Onconsistencyofstochasticdominanceand[25]W.OgryczakandA.Ruszczyn

mean–semideviationmodels,MathematicalProgramming(2001),pp.217–232.´ski,Dualstochasticdominanceandrelatedmean–[26]W.OgryczakandA.Ruszczyn

riskmodels,SIAMJournalonOptimization13(2002),pp.60–78.

[27]J.PQuirkandR.Saposnik,Admissibilityandmeasurableutilityfunctions,Review

ofEconomicStudies29(1962),pp.140–146.

[28]R.T.Rockafellar,ConvexAnalysis,PrincetonUniv.Press,Princeton,NJ,1970.[29]R.T.RockafellarandS.Uryasev,Optimizationofconditionalvalue-at-risk,

JournalofRisk2(2000),pp.21–41.

[30]M.RothschildandJ.E.Stiglitz,Increasingrisk:I.Adefinition,Journalof

EconomicTheory2(1969),pp.225–243.

´ski,Aregularizeddecompositionmethodforminimizingasumofpoly-[31]A.Ruszczyn

hedralfunctions,MathematicalProgramming35(1986)309-333.

PortfolioOptimizationwithStochasticDominanceConstraints26

´skiandR.J.Vanderbei,Frontiersofstochasticallynondominated[32]A.Ruszczyn

portfolios,Econometrica71(2003),pp.1287-1297.

[33]W.F.Sharpe,Alinearprogrammingapproximationforthegeneralportfolioanalysis

problem,JournalofFinancialandQuantitativeAnalysis6(1971),pp.1263–1275.[34]R.J.Vanderbei,LinearProgramming:FoundationsandExtensions.KluwerAca-demicPublishers,2ndedition,2001.

[35]G.A.WhitmoreandM.C.Findlay,eds.,StochasticDominance:AnApproach

toDecision–MakingUnderRisk,D.C.Heath,Lexington,MA,1978.