最大化夏普比率的交替方向乘子法

劉媛媛,韋增欣,李崢嶸

(廣西大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 廣西 南寧 530004)

0 引言

夏普比率是威廉夏普[1]為研究衡量基金績(jī)效表現(xiàn)而指出的一個(gè)指標(biāo)，此指標(biāo)不僅是一個(gè)基金績(jī)效評(píng)價(jià)標(biāo)準(zhǔn)化指標(biāo)，且是一個(gè)可以同時(shí)對(duì)收益與風(fēng)險(xiǎn)加以綜合考慮的三大經(jīng)典指標(biāo)之一。由于夏普比率在多領(lǐng)域的成功應(yīng)用，威廉夏普成為了諾貝爾獎(jiǎng)獲得者，然而如何尋求最大化非凸函數(shù)夏普比率的最優(yōu)解是一個(gè)問(wèn)題。

近年來(lái),學(xué)者們使用夏普比率構(gòu)建投資組合[2]、衡量市場(chǎng)共同基金的表現(xiàn)[3]、評(píng)價(jià)信息檢索系統(tǒng)性能[4]。夏普比率有一個(gè)很好的多面體的可行域, 但是它的目標(biāo)函數(shù)比較復(fù)雜, 不易求解, 考努江斯[5]從優(yōu)化的角度對(duì)夏普比率進(jìn)行了理論分析, 然而并沒(méi)有設(shè)計(jì)優(yōu)化算法對(duì)其進(jìn)行求解以及實(shí)證分析。

ADMM(alternating direction method of multipliers)算法最早分別由GLOWINSKI等[6]以及GABBY等[7]提出, BOYD等[8]對(duì)ADMM算法進(jìn)行了相關(guān)的綜述, 闡述了ADMM算法如何通過(guò)分解問(wèn)題, 再逐一求解單個(gè)優(yōu)化問(wèn)題的基礎(chǔ)上求解問(wèn)題, 文章也證明了ADMM算法適用于大規(guī)模分布式優(yōu)化問(wèn)題, 而后證明了無(wú)松弛因子算法的收斂性。ADMM的應(yīng)用領(lǐng)域十分廣泛, 最早使用其求解單調(diào)變分不等式[9-11], 近年來(lái), ADMM算法主要應(yīng)用在電力系統(tǒng)、圖像處理等方面[12-17], 然而在金融領(lǐng)域還沒(méi)有得到廣泛應(yīng)用和重視。

筆者在考努江斯[5]證明了夏普比率可以轉(zhuǎn)化成為凸優(yōu)化問(wèn)題的基礎(chǔ)上, 使用ADMM算法對(duì)夏普比率進(jìn)行求解, 因松弛因子對(duì)算法收斂性有影響, 故考慮改進(jìn)算法找到使ADMM算法收斂最快的松弛因子, 為了驗(yàn)證其有效性, 在實(shí)證分析中將其與其他常見(jiàn)求解凸規(guī)劃的算法進(jìn)行比較。

1 使用ADMM算法改寫(xiě)夏普比率

1.1 夏普比率的等價(jià)轉(zhuǎn)化

最大化夏普比率的投資組合可以通過(guò)求解以下問(wèn)題得到

(1)

其中,μ=(μi)n,μi表示第i個(gè)資產(chǎn)的收益,x=(xi)n,xi表示第i個(gè)資產(chǎn)占總資產(chǎn)組合的比例,Σ表示投資組合的協(xié)方差。問(wèn)題(1)不是一個(gè)凸規(guī)劃問(wèn)題,可將問(wèn)題(1)進(jìn)行轉(zhuǎn)化得到等價(jià)的二次規(guī)劃問(wèn)題,以此直接獲得最優(yōu)風(fēng)險(xiǎn)投資組合。

(2)

證明假設(shè)①和假設(shè)②保證了所有的可行投資組合都是有意義的,假設(shè)③保證了投資組合的協(xié)方差矩陣為正定矩陣,若資產(chǎn)A與資產(chǎn)B的收益之間存在完全的函數(shù)關(guān)系,此時(shí)在A、B中選擇一個(gè)收益高而風(fēng)險(xiǎn)低的進(jìn)行投資即可。

對(duì)滿(mǎn)足假設(shè)②μTx>rf的可行解x以及問(wèn)題(1)中的變量做如下改變:

(3)

(4)

(5)

有

(6)

又顯然λκ1+(1-λ)κ2>0,故得證。

定理1問(wèn)題(2)的目標(biāo)函數(shù)是凸二次函數(shù),約束區(qū)域?yàn)橥埂４藛?wèn)題可以使用ADMM算法求解。

1.2 夏普比率等價(jià)問(wèn)題的ADMM形式

引理3(μ-rfe)Ty=1可改寫(xiě)成Ay=b,其中:

(7)

引理4引理3中的A可逆。

證明因?yàn)棣蘐x>rf,因此必然存在一個(gè)μk,k=1,2,…,n,使得μk≠rf,不失一般性可以假設(shè)μ1-rf≠0,那么|A|≠0,即A可逆,那么通過(guò)計(jì)算得到

(8)

得證。

引理5問(wèn)題(2)的ADMM形式可以表示為

(9)

問(wèn)題(9)的ADMM的尺度化的形式包含以下迭代:

yk+1∶=(Σ+ρI)-1[-ρ(uk-zk)],zk+1∶=yk+1+uk,uk+1∶=uk+yk+1-zk+1,

(10)

定理2添加松弛因子的ADMM算法的尺度化的形式包含以下迭代：

yk+1∶=(Σ+ρI)-1[-ρ(uk-zk)],zk+1∶=αyk+1+(1-α)zk+uk,uk+1∶=uk+α(yk+1-zk+1),

(11)

根據(jù)文獻(xiàn)[18]的實(shí)驗(yàn)可知松弛變量α∈[1.5,1.8]可以改善收斂,為了加快算法在解決本問(wèn)題時(shí)的收斂速度,這里考慮尋找一個(gè)合適的松弛因子。

1.3 改進(jìn)ADMM算法并尋找加快收斂速度的松弛因子

α和ρ的取值可能對(duì)算法的結(jié)果產(chǎn)生一定的影響,因此增加α和ρ循環(huán),根據(jù)ρ變化時(shí)不同松弛因子下的終止迭代次數(shù),找到使得迭代加快的松弛因子。以下是算法的基本流程:

Step 1:設(shè)置ρ根據(jù)步長(zhǎng)為0.1循環(huán);

Step 2:設(shè)置α根據(jù)步長(zhǎng)為0.01進(jìn)行循環(huán);

Step 3:設(shè)置迭代次數(shù)k以步長(zhǎng)為1進(jìn)行循環(huán);

Step 4:根據(jù)z0、u0使用式(11)計(jì)算yk、zk、uk;

Step 5:若此時(shí)yk、zk、uk滿(mǎn)足終止條件,輸出迭代次數(shù)k,回到step 2,直到step 2循環(huán)完畢回到step 1,step 1循環(huán)完畢跳出循環(huán),輸出矩陣ali、kit; 若此時(shí)yk、zk、uk不滿(mǎn)足終止條件,則回到step 4計(jì)算yk+1、zk+1、uk+1。

1.4 ADMM算法的收斂性證明

定理3設(shè)L0的鞍點(diǎn)為(y*,z*,h*),并定義P*=f(y*)+g(z*),Pk=f(yk)+g(zk),rk+1=yk+1-zk+1。當(dāng)α∈(0,2)時(shí),算法收斂到最優(yōu)解,即

(12)

證明f(y)是Gateaux可微的并且是一致凸函數(shù),根據(jù)Glowinski[6]可以得

(13)

因?yàn)長(zhǎng)0的鞍點(diǎn)為(y*,z*,h*),顯然,L0(y*,z*,h*)是有限的,并且(y*,z*)是原問(wèn)題的最優(yōu)解,那么就有y*-z*=0,并且f(y*)<∞,g(z*)<∞,h*是對(duì)偶問(wèn)題的最優(yōu)解。

根據(jù)L0(y*,z*,h)≤L0(y*,z*,h*)≤L0(y,z,h*)有

f(y*)+g(z*)+(h*)T(y*-z*)≤f(yk+1)+g(zk+1)+(h*)T(yk+1-zk+1),

(14)

將y*-z*=0,P*=f(y*)+g(z*),Pk=f(yk)+g(zk)代入式(14)則有

P*-Pk+1≤(h*)Trk+1,

(15)

由yk+1=argminyLρ(y,zk,hk),則有

0∈?f(yk+1)+hk+ρ(yk+1-zk),

(16)

由hk+1=hk+αρ(yk+1-zk+1),得到hk=hk+1-αρ(yk+1-zk+1)，代入式(16)有

0∈?f(yk+1)+[hk+1+ρ(αzk+1-zk)+ρ(1-α)yk+1]，

(17)

對(duì)式(17)求以y為變量的原函數(shù),則有

(18)

同理zk+1=argminzLρ(yk+1,z,hk),則有

(19)

根據(jù)式(18)、(19)有下式成立：

(20)

(21)

將式(20)、(21)相加后,再將y*-z*=0,yk+1-zk+1=rk+1代入,所得結(jié)果與式(15)聯(lián)立得到

-(h*)Trk+1≤Pk+1-P*≤-(hk+1)Trk+1-ρ(αzk+1-zk)T[rk+1+(zk+1-z*)]-

(22)

得證。

2 實(shí)證分析

針對(duì)建立的模型,給出下面的數(shù)值算例以驗(yàn)證模型有效性,同時(shí)選取可以加快收斂速度的拉格朗日乘子、松弛因子,并且將ADMM算法與常用的算法比較,驗(yàn)證ADMM算法收斂速度的快慢。這里通過(guò)同花順軟件選取5支股票,收集這5支股票在2017年的月收益率數(shù)據(jù),如表1所示。

表1 5支股票月收益率

經(jīng)過(guò)計(jì)算其協(xié)方差矩陣的特征值皆為正數(shù),因此協(xié)方差矩陣是正定的,可以使用ADMM算法求解。這里選取招商銀行2017年3月10日發(fā)售的儲(chǔ)蓄國(guó)債(憑證式)三年期票面利率3.8 %為無(wú)風(fēng)險(xiǎn)利率,即rf=3.8 %,那么:

(24)

這里先將問(wèn)題(2)轉(zhuǎn)化成無(wú)約束問(wèn)題(25)：

(25)

問(wèn)題(2)與問(wèn)題(25)等價(jià)。根據(jù)初始值,圖1給出了改進(jìn)后的ADMM算法在ρ∈(0.1,1)時(shí)不同松弛因子下的終止迭代次數(shù)。

(a) 不同拉格朗日參數(shù)的目標(biāo)函數(shù)值隨松馳因子變化圖

圖1(b)中的離散點(diǎn)組成的曲線(xiàn)從下往上表示以0.1為步長(zhǎng)ρ∈(0.1,1)的圖像,從圖1可以看出,目標(biāo)函數(shù)值都達(dá)到了最優(yōu)點(diǎn),迭代次數(shù)可用來(lái)衡量迭代速度的快慢;α在1.8附近時(shí),迭代速度相對(duì)較快,并且此時(shí)拉格朗日乘子取值對(duì)迭代速度的影響沒(méi)有太大區(qū)別。

根據(jù)上述結(jié)論,后面在進(jìn)行比較時(shí)參數(shù)取ρ=0.5,α=1.8可以加速迭代速度。此時(shí)求出問(wèn)題(2)中的解:

κ=0.000 998 881。

圖2 不同迭代次數(shù)下各個(gè)算法的目標(biāo)函數(shù)值變化情況

3 結(jié)語(yǔ)

ADMM是目前比較成熟,且比較受歡迎的約束問(wèn)題最優(yōu)化通用框架,它將許多經(jīng)典優(yōu)化思路整合、將一個(gè)問(wèn)題分成可分布式的同時(shí)對(duì)多個(gè)小問(wèn)題交替求解,使得問(wèn)題得以解決。將ADMM算法運(yùn)用于求解夏普比率,從數(shù)學(xué)的角度來(lái)求解金融問(wèn)題,并且通過(guò)數(shù)值實(shí)驗(yàn)對(duì)算法的有效性進(jìn)行了驗(yàn)證。在實(shí)證分析中考慮了維數(shù)為五的低維情況,而ADMM算法更適用于求解大規(guī)模分布式優(yōu)化問(wèn)題以及數(shù)據(jù)集較大的統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)的相關(guān)問(wèn)題,因此在下一步將考慮維數(shù)更高的情況,驗(yàn)證ADMM算法在高維環(huán)境下的可行性、有效性以及優(yōu)勢(shì)。