Portfolio Optimization under Short Sale Opportunity

2002年日本オペレーションズ・リサーチ学会 秋季研究発表会 2−E−1

Portfo1ioOptimizationunderShortSaleOpportunity

01102370 中央大学 02103820 中央大学 02702020 中央大学

1．Introduction

今野浩 ⅩONNOHiroshi ＊越塚知事 ⅩOSHIZtTXATbmoyuki

山本零 YAMAMOTORei

▼l

maximi次f（u，V，y）＝∑77（叫−り）

メ＝1 T れ 一入∑扉／ア−∑吋り＋すり） t＝1 ブ＝1 n

Subjectto仇−∑み（り−り）＝0，

J＝1 f＝1，2，…，r †l †l

∑り＋7∑り＝1

メ＝1 j＝1 †l

∑α‘血−り）≧わ‘，

j＝1 宜＝1，2，…，m

O≦り≦α，0≦り≦α′

りり＝0，ゴ＝1，2，…，れ し

W占consider a portfo1io optimization problem under short sale opportunity．When we sellas− sets short we must pay deposit and commission

feetothethirdpartywholendstheaぉets，and theca5l10btainedbytheshortsaleisheldatthe party．Wbhavetouseuptoallamountoffundat thetimeofportfo1ioconstruction．Inthiscasethe investablesetisanonconvexset，SOthatthemean− variancemodelbecomesanonconvexminimization problem．ThiskindofproblemcannotbesoIved

bystandardnonlinearprogrammlngmethodology・

SoweproposeabranChandboundalgorithmex− ploitingthespecialstruCtureOfthisproblem・Itis demonstratedthatthisalgorithmcansoIvevirtu− allya11testproblemsinaverye侃cientmannCr．

2．Fbrmulation

Let there be n舶SetSち，j＝1，2，…，nin

the marketandletちbe the random variable

repr尊entingthe rate ofreturn ofち・Ako，1et Xj，j＝1，2，…，nbctheproportionoffund（ei− therp（冶itiveornegative）to beallocated toち・

Thetotalc舶houtflowis（7isapositiveco吋ant） れ ∑（l頑＋＋7lりト）＝1 メ＝1 （1） wbere Whererjt，t＝1，2，…，Taretherateofreturnof thej・thassetduringthepast t−thperiod．AIso， み＝りモーり・ TbconstruCtapraCticalalgorithm，Werelaxthe equalityconstraint（1）asfo1lows： れ ▼1

1一方≦∑り＋7∑り≦1

ブ＝1 メ＝1 （2） forsomepositiveconstant6＞0．

3・ABranchandBoundAlgoritlm

Thefirst and naturalstepfor soIving this nonconvex problemis to relax the complemen−

tarity condition ujVj＝0，j＝1，2，・・・，n and

SOIvetheresultingquadraticprogrammlngprOb− 1em・Let（u書，V■，y＋）be an optimalsolution of

thequadraticprogrammlngprOblem・Ifu；v；＝0

，j＝1，2，…，n，thenitisobviouslyanOptimalso−

1utionoftheorlglnalproblem・Ifthereexistany ／

jssuchthatviblatecomplementaritycondition，

WeuSeabranchandboundmethod．Ⅵ屯consider thefo1lowlnglinearsystem

托

汀∬ブ≧0 0therwise ifごJ≧0 0tbeⅣke l頑＋＝ I勺ト＝ Letu5introduceujandvjSuChthat り−り＝勺，り≧0，り≧0，りり＝0， J＝1，2，…，m． ThenLxjI＋＝uj，lxjト＝Vj・Weemplqythehis− torical data to represent the return structure of theasset．TherneanーVariancemodelcanberepre− sented asfo1lows：

ー238−

lOIf9＝￠thengoto70． 20chooseonesubproblem乃∈gandletg＼挿）． 30soIve（乃）．If（乃）isinfeaLSible，thengobacktolO． Otherwiselet（uZ，VZ，yZ）beitsoptimalsolution andletfzbeitsoptimalvalue． 40culculateabasicfbasiblesolution（材，均l）ofthe linearsystemQl（yl）．

50If the complementarity conditions are satis丘ed， thenleりIbeitsoptimalvalue．Otherwisegener− ateanewsolutionby（3）．Ifthesolutionsatisfies （2），thenletflbetheassociatedoptimalvalue．If fi＞／’，thenJ’：＝flandremoveallsubproblem 凡sucbtbat九≦J■． 60 Let 軋＋1＝仇∪伺max（如ま＞E）） 叱＋1＝Ⅵ∪伺max（如三＞e）） andgeneratestlbproblemsPL＋1and Et＋2．Let 伊＝ク∪（J㌔十1，J㌔＋2），andretumtolO． 70sbp・

4．ComputationalResultand

Conclusions

WもtestedtheAlgorithmforthisproblemwith

andwithoutupperboundoneashvaLriable，uSlng themonthlydataoftheTbkyoStockExchange．Wb Showcomputationalresultsinpresentation．

Theproblemwithoutupperbound（Classl）is

easiersincethesol11tiongeneratedatthefirststage

COntainsatmostonepairofⅦriableviolatingthe

COmplementaritycondition．Alltestprdblemswere

SOIvedwithoutusingbranChandboundprocedure・

Whiletheproblemwithupperbound（Claぉ2）

ismorecomplicated．However，WeShowthatonly OneOutOfsixtestproblemsrequiredbranchand boundprocedure．

Wb demonst，rated that a mean−Variance model undershortsaleopportunitycanbesoIvedvery

kLSt・Thoughnonconvex，itisusual1ynotmorediト ficultthansoIvingstandardmean−VarianCemOdel

Withoutshortsaleopportunity．AIsoevenwhen

We need to apply branch and bound pr∝edure， the numberofiterationsisnotexcessivesincethe

numberofⅦriablesviolatingthecomplementarity

COnditionisusllal1yverysmall．Wearecurrently

plannlngeXtenSivcexperimentstocomparethereト

ativeadvantageoftheMVmodelwithandwithout Shortsaleopportunityuslngthefactormodel． Reference．今野浩「理財工学Ⅰ，Ⅱ」日科技連出 版，1995，1998 Tl n

∑凍明−∑減明＝瑳，f＝1，2，…，ア

ブ＝1 ブ＝1 n Tl

∑α肋−∑町り≧あ‘，宜＝1，2，…m

メ＝1 j＝1 ▼l ▼1

1一方≦∑り＋7∑り≦1

メ＝1 ブ＝1

／ 0≦り≦α，0≦り≦α， J＝1，2，…，れ．

Obviouslythisproblemhasafeasiblesolution，SO thatithasaba5icfeasiblesolution（滋，i））． Letl左＞0，碗＞0．Iftik疾＞e，thenlet us redefine t左一塊 汀l砧≧穐 0 0therwise， O if tん＞鴫 鳴一晩 otberwi5e． uた＝ Vた＝ （3）

Thereforeifthe new solution satisfythe condi−

tion（2）thenwearedone・Otherwisewesplitthe

probleminto two subproblems byimposlng the conditionuk＝00rVk＝0． kt usde丘ne maximi2；e f（u，V，y） ▼l

subjectto駒−∑み（り−り）＝0，

ブ＝1 t＝1，2，…，r ▼1 1−∂≦∑（り＋7り）≦1 プ＝1 （月） α ＜一 ．轟ノ γ ＜一 Iれ ブ∈坑，り＝0，ブ∈Ⅵ T

∑恥（り−り）＝症，

t＝1，2，‥・，ア ブ＝1 れ ト∂≦∑（り＋γり）≦1 j＝1

／ 0≦り≦α，0≦り≦α，ブ＝1，2，…，m

り＝0，ゴ∈坊， り＝0，ブ∈Ⅵ Q血■）

Algoritlm（BranChandBoundAlgorithm）

00E＞0；［ち＝鴨＝￠；J：＝0，J●：＝−∞， グ＝（凡） 一239一 © 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.