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

郭文秀，張崇濤

（韶關學院 數學與統計學院，廣東 韶關 512005）

Markowitz投資組合模型由Markowitz在1952年提出，該模型首次將統計方法應用到投資組合選擇的研究中，使收益與風險的多目標優化達到最佳的平衡效果. Markowitz投資組合模型是著名的風險投資模型，在實際中有著廣泛的應用，其建模過程以及求解方法一直都是學者們研究的熱點［1-3］.

按照Markowitz投資組合模型的觀點，在收益和風險的權衡中，投資者要么在期望收益相同的條件下選擇風險最小的投資策略，要么在風險相同的條件下選擇期望收益最大的投資策略. 以第一個策略為例，Markowitz投資組合模型本質上是一個含有非負約束的二次規劃問題，經過模系變換，其KKT條件［4］可以轉化為一個絕對值方程的求解［5］，這是筆者的研究對象.

絕對值方程在科學計算、工程等領域有著廣泛的應用［6］.對絕對值方程的數值算法設計是近年來學者們的研究熱點.文獻［7］通過利用光滑函數逼近模項構建了全局平方收斂的Newton法；文獻［8］給出了一類廣義的Gauss-Seidel迭代法；文獻［9］利用一類特殊的線性搜索過程構建了Levenberg-Marquardt方法；文獻［10］通過求解線性方程組和線性規劃混合的方式建立了混合算法.

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

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

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

這里絕對值運算的定義為：|x|=（|x1|，|x2|，…，|xn|）T.

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

引理1設絕對值方程的真實解為x*∈Rn，記x*分量的正、負和零指標集依次為η，ξ，ζ.那么式（2）成立：

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

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

把上式代入Ax+B|x|=b，直接計算化簡即可得到式（2）.

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

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

由于迭代是全局收斂的，因此當迭代步數t充分大時，應有xζ（t）≈0，則：

如果上述條件成立，有：

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

對于零元素的指標集ζ，注意到xζ（t）≈0，這表明：

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

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

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

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

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

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

（9）end if .

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

對于算法1的細節，給出以下說明：

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

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

高職院校雖然對機制專業的改革做出了一些有益的探索，但人才培養模式單一，課程體系僵化，忽視了高職學生素質參差不齊的現實，不利于充分挖掘高職生的求知潛能，不利于高端技能型機械制造專門人才的培養。

第（4）步是基于式（4）所構建的，眾所周知，K-means聚類的計算量不超過O（n2）， 因此聚類技巧的引入不會增加整個算法的計算時間.

第（5）步中的sign表示對相應的向量各分量求符號.

第（6）~（7）步是根據式（3）所構建的，式（3）的成立可以保證當t充分大時第（8）步迭代向量更新策略的合理性.

如果聚類技巧不能發揮作用，算法1的最差情形也是退化為全局收斂的數值算法. 因此聚類技巧的引入不會降低原來算法的計算效率.

2 數值試驗

本節先通過一個測試例子展示上節給出的聚類技巧的有效性，進一步把本文的算法應用到滬深股市光伏建筑一體化版塊的Markowitz投資組合模型求解中.

例1考慮以下絕對值方程，設：

其中，為了便于觀察混合算法運行結果的準確性，設定該絕對值方程的真實解為：x*=（-1，1，0，0）T.

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

算法1的數值結果見表1.

表1 例1的逐步迭代向量

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

表2 對yi（t）進行K-means聚類后例1的結果

應用聚類技巧以后，條件sign（x（t））=sign（x*）在迭代的第2步就已經滿足了（見表2）.另一方面， 隨著迭代步數的增加，兩個類的中心之間的距離越來越大，這表明聚類技巧發揮了作用.

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

設置算法1的殘量誤差為10-5. 跟Gauss-Seidel迭代對比，例2的數值結果見表3.

表3 例2的結果

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

3 結語

通過分析迭代向量的分量符號信息，應用K-means聚類分析技巧對求解絕對值方程的矩陣分裂迭代過程進行了加速，構建了混合算法. 在數值測試試驗中，聚類技巧的應用是有效的，同時，筆者構建的算法還用于求解一類Markowitz投資組合模型，數值結果展現了混合算法的優越性.