求解一類投資組合模型的混合算法

郭文秀，張崇濤

（韶關(guān)學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 韶關(guān) 512005）

Markowitz投資組合模型由Markowitz在1952年提出，該模型首次將統(tǒng)計(jì)方法應(yīng)用到投資組合選擇的研究中，使收益與風(fēng)險(xiǎn)的多目標(biāo)優(yōu)化達(dá)到最佳的平衡效果. Markowitz投資組合模型是著名的風(fēng)險(xiǎn)投資模型，在實(shí)際中有著廣泛的應(yīng)用，其建模過(guò)程以及求解方法一直都是學(xué)者們研究的熱點(diǎn)［1-3］.

按照Markowitz投資組合模型的觀點(diǎn)，在收益和風(fēng)險(xiǎn)的權(quán)衡中，投資者要么在期望收益相同的條件下選擇風(fēng)險(xiǎn)最小的投資策略，要么在風(fēng)險(xiǎn)相同的條件下選擇期望收益最大的投資策略. 以第一個(gè)策略為例，Markowitz投資組合模型本質(zhì)上是一個(gè)含有非負(fù)約束的二次規(guī)劃問(wèn)題，經(jīng)過(guò)模系變換，其KKT條件［4］可以轉(zhuǎn)化為一個(gè)絕對(duì)值方程的求解［5］，這是筆者的研究對(duì)象.

絕對(duì)值方程在科學(xué)計(jì)算、工程等領(lǐng)域有著廣泛的應(yīng)用［6］.對(duì)絕對(duì)值方程的數(shù)值算法設(shè)計(jì)是近年來(lái)學(xué)者們的研究熱點(diǎn).文獻(xiàn)［7］通過(guò)利用光滑函數(shù)逼近模項(xiàng)構(gòu)建了全局平方收斂的Newton法；文獻(xiàn)［8］給出了一類廣義的Gauss-Seidel迭代法；文獻(xiàn)［9］利用一類特殊的線性搜索過(guò)程構(gòu)建了Levenberg-Marquardt方法；文獻(xiàn)［10］通過(guò)求解線性方程組和線性規(guī)劃混合的方式建立了混合算法.

盡管絕對(duì)值方程本質(zhì)上是線性的，但由于模項(xiàng)|x|的存在，求解常規(guī)線性方程組的一些高效算法并不能使用，如Krylov子空間迭代法.另一方面，如果能知道絕對(duì)值方程的解的分量符號(hào)信息，絕對(duì)值方程本質(zhì)上就是一個(gè)線性方程組，這樣對(duì)其應(yīng)用線性方程組的高效數(shù)值算法即可明顯提高計(jì)算效率. 本文在矩陣分裂迭代框架下提出一種聚類的技巧，用于獲取絕對(duì)值方程的解的符號(hào)信息，進(jìn)而構(gòu)建混合數(shù)值算法，用以求解一類Markowitz投資組合模型，數(shù)值試驗(yàn)結(jié)果表明，聚類技巧的引入可以明顯改善算法的收斂速度.

1 K-means聚類和矩陣分裂迭代混合算法

一般的絕對(duì)值方程數(shù)學(xué)定義如下：給定矩陣A，B∈Rn×n以及向量b∈Rn， 求向量x∈Rn，使得：

這里絕對(duì)值運(yùn)算的定義為：|x|=（|x1|，|x2|，…，|xn|）T.

為了給出本文的混合算法，先給出一個(gè)引理.

引理1設(shè)絕對(duì)值方程的真實(shí)解為x*∈Rn，記x*分量的正、負(fù)和零指標(biāo)集依次為η，ξ，ζ.那么式（2）成立：

這里Aηξ表示矩陣A分別以η，ξ為行、列指標(biāo)的子矩陣.

證容易看出，存在一個(gè)置換矩陣P，使得：

把上式代入Ax+B|x|=b，直接計(jì)算化簡(jiǎn)即可得到式（2）.

由引理1的結(jié)果可見(jiàn)，只要能提前獲取指標(biāo)集η，ξ的信息，求解絕對(duì)值方程（1）即等價(jià)于求解線性方程組（2），此時(shí)可以采用求解線性方程組的高效數(shù)值算法. 但注意到η，ξ是由絕對(duì)值方程本身所決定的，理論上并不能在求解之前提前獲取.為了克服這一困難，考慮采用全局收斂的矩陣分裂算法去獲取符號(hào)指標(biāo)的部分信息.

記x（t）表示某個(gè)全局收斂的矩陣分裂迭代法的第t步迭代近似向量，注意到：

由于迭代是全局收斂的，因此當(dāng)?shù)綌?shù)t充分大時(shí)，應(yīng)有xζ（t）≈0，則：

如果上述條件成立，有：

因此，式（3）可以看成是得到η，ξ的一個(gè)必要條件.

對(duì)于零元素的指標(biāo)集ζ，注意到xζ（t）≈0，這表明：

這里“?”的意思是遠(yuǎn)遠(yuǎn)小于. 也就是說(shuō)，條件（4）是獲取ζ的一個(gè)必要條件. 因此，由條件（3），考慮引入聚類技巧在η，ξ中去獲取ζ，這里采用K-means聚類方法把x（t）的分量指標(biāo)分成2類.

綜合上述討論，可以給出K-means聚類和矩陣分裂迭代混合算法.

算法1K-means聚類和矩陣分裂迭代混合算法

（1）輸入A，B，b，kmax，x（0）.

（2）運(yùn)行2步全局收斂的迭代算法得到近似迭代向量x（1），x（2）. 初始化t=2.

（8）如果殘量誤差是超線性收斂，取新的x（t+1）為下一步迭代向量；否則取舊的x（t+1）為下一步迭代向量.

（9）end if .

（10）如果迭代收斂，算法終止；否則t=t+1，回到（3）.

對(duì)于算法1的細(xì)節(jié)，給出以下說(shuō)明：

在第（2）步，為了充分利用絕對(duì)值方程的線性性質(zhì)，選擇基于矩陣分裂的迭代，即：

此處A=M-N表示矩陣A的一個(gè)分裂.

高職院校雖然對(duì)機(jī)制專業(yè)的改革做出了一些有益的探索，但人才培養(yǎng)模式單一，課程體系僵化，忽視了高職學(xué)生素質(zhì)參差不齊的現(xiàn)實(shí)，不利于充分挖掘高職生的求知潛能，不利于高端技能型機(jī)械制造專門(mén)人才的培養(yǎng)。

第（4）步是基于式（4）所構(gòu)建的，眾所周知，K-means聚類的計(jì)算量不超過(guò)O（n2）， 因此聚類技巧的引入不會(huì)增加整個(gè)算法的計(jì)算時(shí)間.

第（5）步中的sign表示對(duì)相應(yīng)的向量各分量求符號(hào).

第（6）~（7）步是根據(jù)式（3）所構(gòu)建的，式（3）的成立可以保證當(dāng)t充分大時(shí)第（8）步迭代向量更新策略的合理性.

如果聚類技巧不能發(fā)揮作用，算法1的最差情形也是退化為全局收斂的數(shù)值算法. 因此聚類技巧的引入不會(huì)降低原來(lái)算法的計(jì)算效率.

2 數(shù)值試驗(yàn)

本節(jié)先通過(guò)一個(gè)測(cè)試?yán)诱故旧瞎?jié)給出的聚類技巧的有效性，進(jìn)一步把本文的算法應(yīng)用到滬深股市光伏建筑一體化版塊的Markowitz投資組合模型求解中.

例1考慮以下絕對(duì)值方程，設(shè)：

其中，為了便于觀察混合算法運(yùn)行結(jié)果的準(zhǔn)確性，設(shè)定該絕對(duì)值方程的真實(shí)解為：x*=（-1，1，0，0）T.

在式（5）中使用Gauss-Seidel 迭代，即M=D-L，N=U.這里D，L和U。分別表示矩陣A的對(duì)角部分、嚴(yán)格下三角部分和嚴(yán)格上三角部分.令迭代初始向量x（0）=（1，1，1，1）T，停機(jī)準(zhǔn)則設(shè)置為殘量誤差不大于10-5.

算法1的數(shù)值結(jié)果見(jiàn)表1.

表1 例1的逐步迭代向量

Gauss-Seidel迭代在第7步達(dá)到了誤差精度，通過(guò)觀察迭代向量x（t）的各分量，可看出條件在第2步就已經(jīng)滿足了，這表明可以干預(yù)迭代過(guò)程使得該迭代提早終止（見(jiàn)表1）.

表2 對(duì)yi（t）進(jìn)行K-means聚類后例1的結(jié)果

應(yīng)用聚類技巧以后，條件sign（x（t））=sign（x*）在迭代的第2步就已經(jīng)滿足了（見(jiàn)表2）.另一方面， 隨著迭代步數(shù)的增加，兩個(gè)類的中心之間的距離越來(lái)越大，這表明聚類技巧發(fā)揮了作用.

例2考慮一類特殊的Markowitz投資組合模型，選取滬深股市光伏建筑一體化版塊的37支股票在2019年6月-2021年5月期間的交易數(shù)據(jù)，通過(guò)計(jì)算個(gè)股的價(jià)格振幅并歸一化得到37階的協(xié)方差矩陣，進(jìn)而可建立以下Markowitz投資組合模型：minwTQw，s.t eTw=1，rTw=ρ，w≥0.其中Q∈R37×37表示協(xié)方差矩陣，w∈R37表示對(duì)版塊個(gè)股的投資權(quán)重向量，r∈R37表示個(gè)股的收益率期望，ρ∈R表示總收益，e∈R37是分量全為1的向量. 通過(guò)模系變換得到形如式（1）的絕對(duì)值方程，其中兩個(gè)系統(tǒng)矩陣的結(jié)構(gòu)為：

設(shè)置算法1的殘量誤差為10-5. 跟Gauss-Seidel迭代對(duì)比，例2的數(shù)值結(jié)果見(jiàn)表3.

表3 例2的結(jié)果

由表3可見(jiàn)，算法1比Gauss-Seidel迭代收斂更快， 這再次表明了聚類技巧的有效性.

3 結(jié)語(yǔ)

通過(guò)分析迭代向量的分量符號(hào)信息，應(yīng)用K-means聚類分析技巧對(duì)求解絕對(duì)值方程的矩陣分裂迭代過(guò)程進(jìn)行了加速，構(gòu)建了混合算法. 在數(shù)值測(cè)試試驗(yàn)中，聚類技巧的應(yīng)用是有效的，同時(shí)，筆者構(gòu)建的算法還用于求解一類Markowitz投資組合模型，數(shù)值結(jié)果展現(xiàn)了混合算法的優(yōu)越性.