基于CVaR投資組合優化問題的非光滑優化方法

張清葉，高 巖

(1.上海理工大學管理學院，上海 200093; 2.河南工學院，河南 新鄉 453003)

基于CVaR投資組合優化問題的非光滑優化方法

張清葉1,2，高 巖1

(1.上海理工大學管理學院，上海 200093; 2.河南工學院，河南 新鄉 453003)

對選定的風險資產進行組合投資，以條件風險價值(CVaR)作為度量風險的工具，建立單期投資組合優化問題的CVaR模型。目標函數中含有多重積分與極大值函數，首先利用蒙特卡洛模擬產生情景矩陣將多重積分計算轉化成求和運算，之后目標函數為分片光滑(非光滑)函數，設計相應的非光滑優化方法并給出其收斂性分析。初步的數值試驗表明了本文算法的有效性。

投資組合；條件風險價值；非光滑優化；束方法

1 引言

1952年，美國經濟學家Markowitz發表了題為《投資組合選擇》的文章[1]，首次提出投資組合的均值-方差(MV)模型，標志著現代投資組合理論的開端，從此數量化的方法開始進入金融投資領域。然而，一方面，MV模型是在證券收益率服從正態分布的假設下建立的，而對大量歷史數據的實證分析表明實際的資產收益率較正態分布具有明顯的尖峰后尾特性；另一方面，方差描述的是收益的偏離程度，沒有描述偏離方向，而實際中關心的是負偏離，即損失。作為對MV模型的改進，下半方差[2]、平均絕對偏差[3]、下偏矩[4]、風險價值[5]等風險測度被提出，其中風險價值(Value-at-Risk,VaR)作為一種金融風險評價工具，指在給定的概率水平下，證券組合在未來特定時期內的最大可能損失。由于其概念簡單，表達直觀且描述的是負偏離，一經提出便被國際金融界廣泛接受。隨著對其進一步的研究，發現其存在一些內在的缺陷，首先VaR不滿足次可加性，這與組合投資分散風險的基本原則相悖；其次，VaR僅關注某一概率水平下的最大預計損失，而當損失超過VaR時的情形被完全忽略，無法預測小概率事件發生的巨額損失情形。針對VaR的缺陷，Artzber[6]等提出了條件風險價值(Conditional VaR，CVaR)的概念并證明CVaR是一致風險度量工具，滿足正齊次、次可加、單調及平移不變性。根據定義，CVaR是指損失超過VaR的條件均值，代表超額損失的平均水平。由于在CVaR的表達式中含有VaR，除非VaR已知，否則無法計算CVaR。 Rockafellar 和Uryasev針對CVaR的計算問題，在文獻[7]中引入了同時計算VaR和CVaR的功能函數，并注意到功能函數中多重積分計算的困難性，提出了基于歷史數據的情景分析法和根據概率密度函數進行隨機抽樣的蒙特卡洛模擬方法，使得計算CVaR成為可能。于是，CVaR成為目前度量金融風險的主流工具[8-9]。

理性投資者在對風險資產進行投資時總是希望收益大且風險小，相應的優化模型可分為三種：某一期望收益水平下的風險最小化模型，某一風險水平下的收益最大化模型及效用函數最大化模型。Palmquist[10]等證明了三個模型的等價性，指出它們具有相同的有效前沿。故本文僅考慮基于CVaR最小化的投資組合優化問題。注意到在計算CVaR的功能函數里含有極大值函數，故實際上計算CVaR是一個非光滑優化問題。目前計算CVaR的方法大致可分為四類：松弛線性規劃方法[11-12]，光滑化方法[13-14]，非光滑優化算法[15-18]及啟發式算法[19-20]。其中松弛線性規劃方法也可用來處理基于絕對偏差、最大偏差等的投資組合優化問題；非光滑優化算法大都基于割平面算法或次梯度算法，如Lim等[15]提出了最小化CVaR的兩階段算法，在階段Ⅰ，利用傳統的可微優化技術迭代KI步，在此期間，如遇到不可微點，則給一擾動，此階段的目的是加快算法收斂，在階段Ⅱ，以階段Ⅰ的解為初始點，利用次梯度投影算法進行迭代。Takano等[16]提出了帶CVaR的加速割平面算法，首先求解原問題不含CVaR約束的松弛問題，若所得解滿足CVaR約束，則停止，否則逐次增加約束。相比松弛線性規劃方法，這些算法在CPU時間上都取得了絕對的優勢。束方法是目前公認的求解非光滑優化問題最有效和最有前景的算法[21]，然而到目前為止利用束方法來求解含CVaR的投資組合優化問題的文獻極少[15,18]。Lim等[15]旨在說明兩階段算法的有效性，束方法僅在附錄中被提及，Pang Liping等[18]旨在說明樣本平均逼近方法(SAA)的合理性，束方法僅作為一種計算方法被提及，本文旨在剖析問題的結構特征后提出求解基于CVaR最小化的投資組合問題的束方法并給出其收斂性分析。

下面首先給出投資組合優化問題的CVaR模型及一些預備知識，然后給出求解CVaR問題的束方法及其收斂性分析，最后為驗證本文所給算法的有效性，進行數值實驗。

2 單期投資組合優化問題的CVaR模型

s.t. -xTm≤-R

(2.1)

注意到在(2.1)中，目標函數是關于(x,α)∈Rn+1的凸函數，可行域為閉凸集，從而(2.1)為一凸規劃，其全局最優解與局部最優解相同。進一步，由于目標函數中含有極大值函數，從而為非光滑凸規劃問題。

3 預備知識

定義3.1[22]設f(x)為Rn上的凸函數，f(x)在x點的次微分?f(x)定義如下：

?f(x)={ξ∈Rn|f(y)≥f(x)+ξT(y-x),?y∈Rn}，

向量ξ∈?f(x)稱為次微分中元素，簡稱次微分或次梯度，相應的不等式稱為次梯度不等式。

定義3.2[22]設S?Rn非空，集合S在點x∈S處的法錐NS(x)定義為：

NS(x)={d∈Rn|dT(y-x)≤0,?y∈S}，

其中d∈NS(x)稱為法方向。

?f(x)=co{fi(x)|i∈I(x)}，

其中，co表示凸包，I(x)={i∈I|fi(x)=f(x)}。

(3.1)

引理3.2[24]設f(x)為Rn上的凸函數，則對于給定的ε>0，集值映射x→?εf(x)是Hausdorff連續的。

命題3.1說明當投資期末收益率y服從正態分布時，可先求解二次規劃問題(P3)，并由(P3)的解求得相應的VaR和CVaR，給出了離散化多重積分計算CVaR可行解的一個檢驗基準。

4 算法導出

首先對一般束方法進行介紹，然后給出求解問題(2.1)的束方法。

4.1一般束方法(GeneralBundleMethod，GBM)

注意到在一般束方法中求候選點xk+1實際上是在解一個二次規劃問題，而本文所考慮CVaR模型(2.1)的約束集X為一凸多面體，不妨將其直接添加到二次規劃問題中，求解難度并未增大。此外基于情景的CVaR模型，情景數往往很大，遠遠大于決策變量維數，故這里我們直接求解二次規劃問題并采用次梯度選擇策略，此外在迭代過程中對迫近參數按信賴域算法思想進行修正。下面具體給出求解CVaR模型(2.1)的迫近束方法的算法步驟。

4.2算法1——求解CVaR模型(2.1)的迫近束方法

步驟1(求下一個候選點)求解下述二次規劃問題:

0≤i≤k

-xTm≤-R

(4.1)

步驟2(停機檢測)若vk≤ε，停機；否則，轉步驟3。

步驟4(迫近參數更新)若rk≥m2，令μk+1=min{γ1μk,μmax}；若rk

步驟6(循環)令k=k+1，轉步驟1。

注2：算法1中步驟5，當割平面模型中所含超平面個數達到M時，每次去掉最前面一個，同時增加最后一個候選點處的支撐超平面，這樣做僅僅是為了計算方便。事實上，也可以采用別的更新策略，如去掉候選點列中函數值最大的點或距離當前穩定中心最遠的點等等以加快算法收斂速度。

5 收斂性分析

注意到問題(4.1)可等價的寫成：

s.t.(x,α)∈D

(5.1)

(5.2)

設(x*,α*)為問題(2.1)的任意一個最優解，則：

下面討論第二種情況，設算法1產生有限個下降步，之后均為空步。

(5.2)

綜上所述，可得如下收斂性定理。

6 數值實驗

為檢驗算法1的有效性，選擇文獻[7]中的算例進行測試。由于該算例的精確最優解已知，方便我們檢驗所求結果的正確性。考慮對三個風險資產：S&P，Gov bond和Small cap進行組合投資，投資期末收益率y服從正態分布N(m,V)，均值與協方差矩陣如表1、2所示，取R=0.011。首先求解MV模型得最優投資組合x*=[0.4520113,0.1155732,0.432416]，方差σ2(x*)=0.003785，此時mTx*=R，即-xTm≤-R為積極約束，根據命題3.1，可求得最優的VaR和CVaR值(即真實的VaR和CVaR值，作為檢驗其他方法所求結果正確性的標準)，如表3所示。

表1 收益率均值

表2 收益率協方差矩陣

表3 最優的VaR和CVaR

由于該算例假設未來收益率向量y服從正態分布，且表1、2分別為其均值與協方差矩陣，首先利用蒙特卡洛模擬對y進行隨機抽樣產生情景矩陣YJ×n，為使得抽樣數據能充分體現y的分布，情景數應盡可能大，有文獻曾專門進行研究并指出情景數應不小于5000。將情景矩陣YJ×n帶入問題(2.1)，可得

s.t.-xTm≤-R

(6.1)

表4 各種算法計算結果對比

圖1 三種算法計算結果對比(J-CVaR)

圖2 三種算法計算結果對比(J-CPU時間)

7 結語

本文首先建立了單期組合優化問題的CVaR模型，注意到目標函數中含有極大值函數，給出其次梯度計算公式并設計了求解CVaR模型的迫近束方法，緊接著給出算法的收斂性分析，最后進行了數值實驗，將文本算法(BM)與經典的松弛線性規劃方法(LP)，非光滑優化次梯度算法(SA)，典型智能優化算法-遺傳算法(GA)，光滑化方法(SM)進行了對比。數值實驗表明LP與SA效率極低，不宜采用；GA，SM與本文算法較有效，且本文算法效率最高，故本文算法不失為求解基于CVaR投資組合優化問題的一個有效方法。此外， 本文算法可推廣至其他約束或無約束非光滑凸規劃問題的求解上，尤其是大規模非光滑優化問題，其一方面可以豐富非線性規劃理論，另一方面給求解實際問題，如基于歷史數據的均值—平均絕對偏差問題等，提供了一種新的思路。

[1] Markowitz H M. Portfolio selection[J]. Journal of Finance, 1952, 7(1):77-91.

[2] 張鵬,張衛國,張逸菲.具有最小交易量限制的多階段均值_半方差投資組合優化[J].中國管理科學,2016,24(7):11-17.

[3] Liu Mingming, Gao Yan. An algorithm for portfolio selection in a frictional market[J]. Applied Mathematics and Computation, 2006,182(2):1629-1638.

[4] 劉彬蔚,房勇.引入股指期貨的兩階段投資組合選擇模型[J].中國管理科學,2015,23(S1):419-423.

[5] Jorion P. Value at risk: The new benchmark for controlling market risk [M]. BurrRidge.Illinois:Irwin Professional Publication,1997.

[6] Artzner P, Delbaen F, Eber J M, et al. Coherent measures of risk[J]. Mathematical Finance, 1999, 9(3): 203-228.

[7] Rockafellar R T, Uryasev S. Optimization of conditional value-at-risk [J]. Journal of risk, 2000, 2: 21-42.

[8] 許啟發，周瑩瑩，蔣翠俠.帶有范數約束的CVaR高維組合投資決策[J].中國管理科學，2017,25(2):40-49.

[9] Zhang Qingye, Gao Yan. Optimal consumption-portfolio problem with CVaR constraints[J]. Chaos, Solitons and Fractals, 2016, 91:516-521.

[10] Palmquist J, Uryasev S, Krokhmal P.Portfolio optimization with conditional value-at-risk objective and constraints [J]. Journal of risk, 2002, 4:43-68.

[11] 陳劍利,李勝宏. CVaR風險度量模型在投資組合中的運用[J].運籌與管理, 2004, 13(1):96-99.

[12] 朱文娟,高巖.考慮分段交易費用的CVaR投資組合優化[J].統計與決策,2008,(24):36-38.

[13] Tong Xiaojiao, Qi Liqun, Wu F, et al. A smoothing method for solving portfolio optimization with CVaR and applications in allocation of generation asset [J].Applied Mathematics and Computation, 2010, 216(6):1723-1740.

[14] Meng Fanwen, Sun Jie, Goh M. A smoothing sample average approximation method for stochastic optimization problems with CVaR risk measure[J].Journal of Optimization Theory and Applications, 2010, 146(2): 399-418.

[15] Lim C, Sherali H D, Uryasev S. Portfolio optimization by minimizing conditional value-at -risk via nondifferentiable optimization[J]. Computational Optimization and Applications, 2010, 46(3):391-415.

[16] Takano Y, Nanjo K, Sukegawa N, et al. Cutting plane algorithms for mean-CVaR portfolio optimization with nonconvex transaction costs[J].Computational Management Science,2015,12(2):319-340.

[17] Beliakov G, Bgirov A. Nonsmooth optimization methods for computation of the Conditional Value-at-Risk and portfolio optimization [J]. Optimization, 2006, 55(5-6):459-479.

[18] Pang Liping，Chen Shuang, Wang Jinhe. Risk management in portfolio applications of non-convex stochastic programming[J]. Applied Mathematics and Computation, 2015, 258:565-575.

[19] 李國成,肖慶憲. CVaR投資組合問題求解的一種混合元啟發式搜索算法[J].運籌與管理,2014,23(6):229-235.

[20] Qin Quande, Li Li, Cheng Shi. A novel hybrid algorithm for mean-CVaR portfolio selection with real-world constraints[M]//Tan Ying,Shi Yuhui,Coello CAC.Advances in swarm intelligence. Springer International Publishing, 2014.

[21] M?kel? M M. Survey of bundle method for nonsmooth optimization[J]. Optimization methods and software, 2002,17(1):1-29.

[22] 高巖.非光滑優化[M].北京:科學出版社,2008.

[23] Kiwiel K C. Method of descent for nondifferentiable optimization[M].Berlin:Springer Verlag, 1985.

[24] Belloni A. Introduction to bundle methods[J]. Lecture Notes for IAP, 2005.

ANonsmoothOptimizationMethodforPortfolioOptimizationBasedonCVaR

ZHANGQing-ye1,2,GAOYan1

(1.School of Management, University of Shanghai for Science and Technology, Shanghai 200093,China;2.Henan Institute of Techonology,Xinxiang,453003,China)

Portfolio selection is an important issue in finance. It aims to determine how to allocate one’s wealth among a given asset pool to maximize the return and minimize the risk. Different from the accepted return, there are many risk measures. Nevertheless, among all risk measures, conditional value-at-risk (CVaR) is widely accepted, and in this paper it is adopted. As there is a nonsmooth term in the expression of CVaR, an optimization problem containing CVaR cannot be solved by classical algorithms based on gradient. Though there is an extensive literature on tackling optimization problem containing CVaR, such as linear programming method, intelligent optimization algorithms and nonsmooth optimization methods, etc, literatures on solving this problem by bundle method are scarce. And the literature on this aspect in this paper is enriched. That is, a bundle method is investigated for portfolio selection problem based on CVaR. Specifically, a single-period portfolio optimization model, which takes CVaR as the objective function coupled with a prescribed minimal level of the expected return, is formulated at first. By exploring the structure of the model, a proximal bundle method is proposed. At the same time, the convergence analysis of the method is given as well. Finally, an illustrative numerical example is presented, where assets’ returns are assumed to be normally distributed and their mean and the covariance matrix known. By Monte Carlo sampling method, several scenario matrices are generated. Then, not only the bundle method, but linear programming method, subgradient algorithm, genetic algorithm and smoothing method are adopted to solve the model as well. By comparing the results of the different methods, conclusions are drawn: linear programming method and subgradient algorithm are inefficient, genetic algorithm, smoothing method and bundle method are feasible. Further, among three feasible algorithms, bundle method takes the least amount of CPU time. So, the proximal bundle method is efficient and can be regarded as a new solution method for not only portfolio optimization problem but other problems containing CVaR.

1003-207(2017)10-0011-09

10.16381/j.cnki.issn1003-207x.2017.10.002

F830;O221

A

2015-06-10；

2017-01-04

國家自然科學基金資助項目(11171221)；高等學校博士學科點專項科研基金項目(20123120110004)；上海市一流學科項目(XTKX2012)

張清葉(1978-)，女(漢族)，河南新鄉人，河南工學院講師，博士，研究方向：投資組合優化、非光滑優化，E-mail:zhangqingye123@163.com.

Keywords： portfolio；Conditional Valu-at-Risk (CVaR)；nonsmooth optimization；bundle method