帯邊際風險控制的投資組合問題的半定規劃松弛

丁曉東，肖琳燦，羅和治

(1.浙江工業大學 理學院，浙江 杭州 310023；2. 浙江工業大學 經貿管理學院，浙江 杭州 310023)

帯邊際風險控制的投資組合問題的半定規劃松弛

丁曉東1，肖琳燦1，羅和治2

(1.浙江工業大學 理學院，浙江 杭州 310023；2. 浙江工業大學 經貿管理學院，浙江 杭州 310023)

邊際風險衡量單個資產對投資組合總體風險的貢獻，是投資組合和風險管理中的一個重要準則.考慮均值方差框架下帶有邊際風險控制的投資組合選擇問題，其優化模型是一個非凸二次約束二次規劃問題.通過探索模型的結構特點并結合提升方法和割不等式技術，給出了帶有邊際風險控制的均值方差投資組合選擇模型的一個緊的半定規劃松弛，分析了它與原問題的最優解和最優值之間的關系以及它與文獻中的凸二次規劃松弛所提供下界的比較關系.初步數值結果表明基于半定規劃松弛的分支定界算法能有效地找到原問題的全局解.

投資組合；邊際風險；半定規劃松弛；分支定界

投資組合理論主要研究如何在收益不確定的情況下進行資產有效配置以最大化預期收益同時最小化風險.MARKOWITZ[1]在1952年采用均值和方差度量投資組合的預期收益和風險，提出了均值方差投資組合優化模型，奠定了現代投資組合理論的基礎.LI等[2-3]分別將均值方差模型推廣到多階段投資組合和帶有破產風險控制的動態投資組合問題.PARDALOS等[3]綜述了投資組合選擇的優化模型.自均值方差模型提出后，基于不同視角的新的風險度量方法和投資組合模型被相繼提出.KNONO等[5]采用均值絕對偏差度量風險，建立均值絕對偏差投資組合模型，該模型可轉化為線性規劃來求解.YOUNG[6]采用投資組合可能出現的最壞收益作為風險度量，基于歷史數據給出了極大極小投資組合模型，并通過引入變量替換方法將該模型轉化為線性規劃來求解.PHILIPPE等[7]利用風險值(Value-at-risk, VaR)來衡量一定置信度下投資組合所面臨的最大損失.ALEXANDER[8]證明了在各資產的收益服從正態分布的假設下，帶有VaR約束的投資組合模型可轉化為等價的二階錐規劃問題.值得指出，這些風險度量方法僅考慮投資組合的總體風險，而忽略了單個資產對投資組合總體風險的貢獻.邊際風險來衡量單個資產對投資組合的總體風險的貢獻，單個資產的邊際風險定義為整個投資組合的風險與不包含該資產的投資組合的風險之差；GRINOLD等[9]將單個資產的邊際風險定義為投資組合的收益標準差關于該資產持有量的偏導數.但遺憾的是，這些定義都有一個共同缺點：所有資產的邊際風險之和不等于投資組合的總體風險.為克服這個缺點，ZHU等[10]通過分解資產收益的協方差矩陣提出了一個新的邊際風險定義，建立了帶有邊際風險控制約束的均值方差投資組合選擇模型，但該模型是一個帶非凸二次約束的二次規劃(QCQP)問題，求它的全局解是NP-難的；并給出了該模型的一個凸二次規劃松弛和基于該松弛的分支定界全局算法.

尋找非凸QCQP問題全局解的常用方法是基于線性規劃與二次凸松弛的分枝-定界方法，而分枝-定界方法的關鍵問題是如何有效地計算緊的下界.我們知道，半定規劃(簡記SDP)松弛對非凸QCQP問題可以提供更緊的下界.ZHENG等[11-12]研究了非凸QCQP的基于D.C.分解、矩陣錐分解和多胞形逼近等技術的SDP松弛方法；蔡偉榮等[13]利用矩陣分解方法研究了0-1二次規劃的SDP松弛.為此，我們針對模型的結構特點并結合提升方法和割不等式技術，給出了帶有邊際風險約束的均值方差投資組合模型的一個緊的SDP松弛，討論了它與原問題的最優解和最優值之間的性質以及它與文獻[10]中的凸二次規劃松弛所提供下界的比較關系.初步數值結果表明：基于SDP松弛的分支定界算法能在較短時間內求得模型的全局解，比文獻[10]中全局算法的求解效率更高.

1 帶邊際風險控制的投資組合模型

描述文獻[10]所提出的帶有邊際風險約束的均值方差投資組合選擇模型.假設市場上有n個風險資產，r=(r1,r2,…,rn)T表示資產收益隨機向量,其中ri表示第i個資產的收益隨機變量.給定投資組合x=(x1,x2,…,xn)T，則投資組合x的收益隨機變量可表為p(x)=rTx,其預期收益和方差可分別表為

μ(x)=E(rTx)=μTx

σ(x)=E(rTx-μ(x))2=xTQx

其中：μ∈Rn和Q=(σij)n×n∈Rn×n分別為資產收益r的均值向量和協方差矩陣.以預期收益μ(x)和方差σ(x)為雙目標的均值方差投資組合模型可表為

(PMV) minτxTQx-μTxs.t.x∈D={x∈Rn:eTx=1,l≤x≤u}其中：e=(1,1,…,1)T,τ∈(0,∞)分別為風險厭惡參數，l,u∈Rn.然而，均值方差投資組合模型的弊端是未考慮單個資產對投資組合總體風險的貢獻.為此，文獻[10]給出了如下的邊際風險的定義.

定義1 投資組合x=(x1,x2,…,xn)T的第k個資產的邊際風險記為

(1)

(PMR) minf(x)=τxTQx-μTxs.t.xTQkx≤ρkk=1,2,…,mx∈D

其中ρk(k=1,2,…,m,m≤n)為給定的第k個資產的邊際風險容忍參數.需要指出的是，由于Qk為不定矩陣，問題(PMR)是一個非凸二次約束二次規劃問題，求它的全局最優解是NP-難的.

引入如下記號：記v(·)為優化問題(·)的最優值,記Sn為n×n對稱矩陣的集合.設A,B∈Sn,AB表示A-B是為半正定矩陣,Sn中的內積定義為A·B=Tr(AB).

2 半定規劃松弛

給出模型(PMR)的一個SDP松弛及其性質，并討論它與文獻中已有的凸二次規劃松弛的比較關系.根據Qi的定義可知：Qi為秩2矩陣，用特征值分解方法將其分解為

(2)

i=1,2,…,m

(3)

i=1,2,…,m

注意到當eTx=1時E·xxT=(eTx)2=1,其中E=eeT.另外，注意到xTQx=Q·xxT且xTQix=Qi·xxT.于是，令X=xxT并將其松弛為半定約束X-xxT0，我們可以得到問題(PMR)的一個SDP松弛為

(SDPMR) minτQ·X-μTxs.t.eTx=1,E·X=1Qi·X≤ρii=1,2,…,m

X-xxT0,l≤x≤u

首先，討論問題(PMR)與其松弛(SDPMR)的最優解和最優值之間的關系.

(4)

(5)

(6)

其次，我們討論SDP松弛與文獻[10]中所提出的凸二次規劃松弛的比較關系.文獻[10]先利用式(2)將問題(PMR)中的邊際風險約束xTQix≤ρi,i=1,2,…,m改寫為

i=1,2,…,m

(7)

(QPMR) minτxTQx-μTxs.t.eTx=1,l≤x≤u

i=1,2,…,m

我們有

定理3v(SDPMR)≥v(QPMR)

i=1,2,…,m

定理3證明了問題(SDPMR)比(QPMR)提供更緊的下界.注意到從下節的數值結果看到，對所有數值例子不等式v(SDPMR)

3 數值結果

首先，給出模型(SDPMR)和(QPMR)對問題(PMR)提供下界的比較數值結果.數值測試在Matlab R2013b上實現，在PC機(3.33 GHz，8 GB，RAM)上運行，并用CVX 1.2中的SDPT3求解器來求解計算下界的SDP模型，用CPLEX 12.6中的QP求解器來求解計算下界的QP模型.

測試問題由文獻[11]給出的隨機方法生成.令ri=αi+βirM+δi,i=1,2,…,n,其中：ri為第i個資產的收益；rM市場指數的收益；δi為第i個資產收益的殘差.從而可得到μi=αiβiE(rM)，σii=Var(rM)+Var(δi)，且σij=βiβjVar(rM),其中：參數αi=0.000 001×ra,rd為用正態隨機分布生成的，i=1,2,…,m;βi為在[0.6,1.2]上用均勻分布隨機生成的，i=1,2,…,m；E(rM)=0.02，Var(rM)=0.003，且Var(δi)是在[0,0.002]上用均勻分布隨機生成的，i=1,2,…,m.再令l=(0,0,…,0)T,u=(1,1,…,1)T,τ=1.為了衡量下界的緊性,定義下界的改進率為

表1給出了對(PMR)的具有相同規模的10個測試問題的下界的平均改進率.從表1可看到：在所有的測試問題中,下界v(SDP}MR)比v(QPMR)更緊,且當ρi=0.003/n時測試問題的平均改進率提高更大.

表1 對問題(PMR)下界的平均改進率

Table 1 The average improvement ratio of lower bound for (PMR)

nmR/%Pi=0．01/nPi=0．003/n10102．839．4720203．7013．8630304．8716．6040405．3517．9550505．3117．6660605．0918．2370704．9818．8280804．7918．6190904．7918．521001004．4618．38

其次，給出求問題(PMR)全局解的基于SDP和二次凸松弛的分支定界算法的比較數值結果.

記“BB-QP”為文獻[11]中所提出的基于二次凸松弛(QPMR)的分支定界算法，而“BB-SDP”為下界由SDP松弛(SDPMR)得到的分支定界算法.表2給出了BB-SDP和BB-QP算法對5個測試問題的平均數值結果，其中“fval”，“iter”，“cpu”分別為算法對5個測試問題得到的平均最優值、平均迭代次數和平均CPU時間(單位：s).從表2可見：BB-SDP算法能有效地找到所有測試問題的全局解，而且比BB-QP算法所需時間更短.

表2 BB-SDP和BB-QP對5個測試問題的平均數值結果

Table 2 The average numerical results of BB-SDP and BB-QP for five test problems

nmBB?QPfvalitercpuBB?SDPfvalitercpu105-0．017850．43．0-0．01781．00．41010-0．0182144．47．4-0．01821．00．1205-0．018726．41．5-0．01871．00．12010-0．0191131．87．7-0．01911．00．23010-0．018949．63．2-0．01891．00．23020-0．0186376．826．8-0．01851．00．34010-0．0189103．47．2-0．01891．00．34020-0．0187349．227．2-0．01871．00．45010-0．0190129．410．9-0．01901．00．45020-0．0191149．612．4-0．01911．00．66010-0．019173．26．8-0．01911．00．66020-0．0190273．627．9-0．01901．00．87010-0．019282．08．3-0．01911．00．77020-0．0191226．025．4-0．01911．01．18010-0．019430．03．6-0．01931．00．98020-0．019356．86．1-0．01931．01．29010-0．019225．23．3-0．01921．01．19020-0．0194209．228．9-0．01921．01．810010-0．019425．43．2-0．01941．01．410020-0．0193171．623．2-0．01931．02．210050-0．01921050．0224．4-0．01921．07．0

4 結 論

考慮了帶有邊際風險控制約束的投資組合選擇問題，其優化模型是一個非凸二次約束二次規劃問題，但求它的全局解一般而言是非常困難的.利用非凸約束的特殊結構并結合提升法和添加割不等式技術，給出了該模型的一個更緊的SDP松弛及其最優解的性質，證明了它比文獻[10]中的二次凸松弛更緊.初步數值結果表明：基于SDP松弛的分支定界算法能在較短時間內求得由隨機產生的測試問題的全局解，比文獻[10]中的全局算法更有效.

[1] MARKOWITZ H M. Portfolio selection[J]. Journal of finance,1952,7:77-91.

[2] LI D, NG W L. Optimal dynamic portfolio selection: multi-period mean-variance formulation[J]. Mathematical finance,2000,10：387-406.

[3] ZHU S S, LI D, WANG S Y. Risk control over bankruptcy in dynamic portfolio selection: a generalized mean-variance formulation[J]. IEEE transactions on automatic control,2004,49:447-457.

[4] PARDALOS P, SANDTSAR M, ZOPOUNIDIS C. On the use of optimization models for portfolio selection: a review and some computational results[J]. Computational economics,1997,7:227-244.

[5] KONNO H, YAMAZAKI H. Mean-absolute deviation portfolio optimization model and its applications to Tokyo stock market[J]. Management science,1991,37:519-531.

[6] YOUNG M R. A minimax portfolio rule with linear programming solution[J]. Management science,1998,44:673-683.

[7] PHILIPPE J. Value at risk: the new benchmark for controlling market risk[M]. Chicago：Irwin Professional Publishing,1996.

[8] ALEXANDER G J, BAPTISTA A M. A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model[J]. Management science,2004,50(9):1261-1273.

[9] GRINOLD R C, KAHN R N. Active portfolio management: a quantitative approach for producing superior returns and controlling risk[M]. New York: McGraw-Hill,1999.

[10] ZHU S S, LI D, SUN X L. Portfolio selection with marginal risk control[J]. The journal of computational finance,2010,14(1):3-28.

[11] ZHENG X J, SUN X L, LI D. Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation[J]. Mathematical programming,2011,129(2):301-329.

[12] ZHENG X J, SUN X L, LI D. Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations[J]. Journal of global optimization,2011,50(4):695-712.

[13] 蔡偉榮，柳葉，羅和治.基于矩陣分解的0-1二次規劃的SDP松弛[J].浙江工業大學學報，2015,43(5):582-586.

Semidefinite programming relaxation for portfolio selection with marginal risk control

DING Xiaodong1, XIAO Lincan1, LUO Hezhi2

(1.College of Science, Zhejiang University of Technology, Hangzhou 310023, China；2.College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023, China)

Marginal risk that is used to measure the contribution of an individual assets to the overall risk of the portfolio, is an important criterion in portfolio selection and risk management. In this paper, we consider the portfolio selection problem with marginal risk control in the mean-variance framework. In this problem, the optimization model is a quadratic programming problem with nonconvex quadratic constraints. By exploiting the structural characteristics of the model and combining the lifting method with secant inequality techniques, we present a tight semidefinite programming (SDP) relaxation for this problem. We discuss the relationships between optimal solutions and optimal values of the original problem and its SDP relaxation, and compare the lower bounds provided by the SDP relaxation and quadratic convex relaxation in the literature. Preliminary numerical results show that the branch-and-bound algorithm based on the SDP relaxation can find the global optimal solution of the original problem effectively.

portfolio selection; marginal risk; semidefinite programming relaxation; branch-and-bound

(責任編輯：劉 巖)

2016-04-12

國家自然科學基金資助項目(11371324)；浙江省自然科學基金資助項目(LY17A010023)

丁曉東(1983—)，男，河南鄭州人，講師，博士，研究方向為最優化理論、算法與應用，E-mail: dxdopt@zjut.edu.cn.

O221.2

A

1006-4303(2017)01-0064-05