基于整數線性規劃和混合整數線性規劃的投資組合優化

【摘? 要】論文主要內容是使用2個整數線性規劃模型進行投資組合優化。第一個整數線性規劃模型應用分支剪界算法（使用CPLEX軟件）、動態規劃算法和貪心算法（使用Java軟件）篩選最有價值的股票。第二個模型是混合整數線性規劃模型，以回報為約束條件，確定投資所選定股票的確切數額，并最小化風險。

【Abstract】The main content of this paper is to optimize investment portfolio by using two integer linear programming models. The first integer linear programming model applies branch shear bound algorithms （using CPLEX software）， dynamic programming algorithms， and greedy algorithms （using Java software） to select the most valuable stocks. The second model is a mixed integer linear programming model， which takes the return as the constraint condition to determine the exact amount of investment in the selected stock and minimize the risk.

【關鍵詞】整數規劃;投資組合優化;風險;算法

【Keywords】integer programming; portfolio optimization; risk; algorithm

【中圖分類號】F224;F831.5? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號】1673-1069（2021）09-0116-03

1 引言

線性規劃是用來尋求變量處于線性關系時的有效方法，在項目選擇、投資組合優化、季節收益預測等問題中有多種應用。整數規劃與線性規劃非常相似，但它要求所有或部分變量是整數。某些情況下，整數規劃更可取，如二元變量的管理決策。部分決策變量為整數的模型，稱為混合整數規劃。

本文將會研究整數線性規劃在投資組合優化中的應用。模型A，即整數線性規劃（ILP）模型可以看作NP完全問題中的0-1背包問題，通過模型A找出可選入投資組合的股票。另一個模型是混合整數線性規劃（MILP），這里使用的是有限資產平均絕對偏差（LAMAD）模型的演變來確定投資所選股票的確切數量，分配最合適的權重，以達到風險最小化、回報最大化的效果。本文采用3種算法求解：分支剪界算法、動態規劃算法和貪心算法。分支剪界算法用CPLEX 12.6實現，動態規劃算法和貪心算法在Eclipse標準4.4平臺上，用Java語言實現，所采用的股票信息和數據由NASDAQ和yahoo finance網站獲取。

2 算法介紹

以下介紹的算法都可以歸屬于啟發法的范疇。啟發法是指不以找到問題的最佳或最確切的解決方案為目標的技術，而是找到一個足夠可信的解決方案的方法。直覺判斷、刻板印象和常識都屬于這個“范疇”。它非常適用于在計算或搜索過于詳盡和不實際的情況下，通過心理捷徑來加快得到滿意解決方案的過程，以減輕作出決策的認知負擔。它有常見的幾種策略：第一種是將問題的目標狀態進行切分，然后通過實現子目標逐漸實現總的目的;第二種是從最終目標狀態逆向去尋找達到這個狀態的途徑;第三種是逐步收縮初始狀態和目標狀態的距離的方法。元啟發式是指導搜索過程的策略或上層方法論，元啟發式的目標是有效地探索搜索空間，以找到最接近的最優解。啟發式依賴于問題，用于確定特定問題的“足夠好”的解決方案，而元啟發式就像一種設計模式，可以應用于更廣泛的問題。

啟發式方法特別適用于混合整數規劃，因為混合整數規劃太大而無法求解最優，而線性規劃較為松弛，可以在合理的時間內求解。

2.1 分支剪界算法

分支剪界法是分支限界法和切割平面法2種算法的結合。最早的求解混合整數規劃問題的算法是切割平面方法，但這個方法的收斂速度較慢，后來的學者提出了求解離散規劃問題的分支限界法，對切割平面法進行了改進。分支剪界算法在整數規劃中有諸多的應用，如Mahsa在2020年發表的不完全觀察下的整數優化。圖1是一個用分支定界算法求解整數規劃的演示例子，目標函數為：MaxZ=240x1+160x2。

2.2 動態規劃算法

從數學優化的角度來看，動態規劃通常是指把一個大的優化問題分解成一系列小的決策，隨著時間的推移來解決，例如，將問題分成v1（.），v2（.），…，vn（.）等不同狀態，將vi（a）定義為達到狀態a的值，時間為t，t=1，…，T。由已決策的新狀態vi（a）可以遞歸地運算出vi-1（a）的值（Nocedal和Wright，2006），以此來優化求解。

2.3 貪心算法

貪心算法同動態規劃算法有相似之處，也是先進行劃分，把一個大的問題分成若干子問題，然后搜尋目前的最優解，再處理后續產生的子問題。有時，利用此算法求出的是局部最優解，而不是整體的。貪心算法生成的步驟似乎足夠好，但不能保證對未來或所有子問題都足夠好（Cormen等，1990）。

3 文獻綜述

有許多不同的模型可以為相同的或類似的目標服務。模型的選擇取決于風險的性質。方差和標準偏差是表達波動性的標準概念。遵循現代投資組合理論的基本原則，本文傾向于進行有效的交易和多樣化的投資，以確保對沖這類風險。多元化投資是指將資產投資于房地產、食品行業、科技行業等不同經濟領域，或投資于國內市場、海外市場等不同金融市場。在現代投資組合理論中，在一個投資組合中加入一定數量的適當資產可以顯著降低標準差。但是，當投資組合中有一定數量的資產時，這種利益將會減弱或終止。一般來說，理想的資產數量在25個左右。剩下的無法“分散”的風險就是所謂的系統性風險。系統性風險在投資組合配置中發揮著重要作用，因為即使完全分散投資也無法消除系統風險。因此，根據Stone和其他作者在1970年共同提出的證券市場線（SML），預期收益率完全依賴于這種風險。貝塔值（β）是證券、股票或投資組合相對于整個市場的系統風險。本文將貝塔值作為衡量市場風險的基準。β=1意味著證券價格完全隨市場變動。一些資產如國庫券和黃金是貝塔值低于1的例子，因為這類資產的價格運動與市場沒有高度相關。如果股票的貝塔值是1.1，那么理論上，它的波動性比市場高10%。SML理論認為，同一行業的各投資工具的風險處于同一水平，而同一水平線的風險又意味著同一水平線的預期收益率。

CVaR（Conditional Value at Risk）和Sortino比率（Sortino ratio）這2項主要用于衡量下行風險的指標，近來受到了投資者的廣泛歡迎。根據這一趨勢，許多研究者也采用了這些模型。下行風險是指隨著市場環境的變化，證券價值的潛在下降。換句話說，這是投資者可能因股市下跌而承受的最大損失。它可以通過實際回報和預期回報，也就是回報的不確定性之間的差異來量化，也可以通過下行貝塔來衡量，它是當一種證券的超額回報小于平均市場超額回報時的貝塔值。相反，上行風險是獲利的可能性，用上行貝塔值來衡量。上行貝塔值是當一種證券的超額回報小于平均市場超額回報時的貝塔值。在進行風險度量時，這2種風險是非常重要的。

在現實世界中，監管、交易成本和稅收都會影響投資組合的收益，增加投資組合的風險，但這些因素在本文中沒有討論。有關投資組合優化的文章通常以非線性規劃、二次規劃、整數線性規劃、混合整數線性規劃以及線下比較流行的數據挖掘的方式進行研究，常伴隨啟發式方法的痕跡。本文采用整數線性規劃和混合整數線性規劃結合以上3種啟發式方法對投資組合優化問題進行了研究。

4 模型A（ILP）

4.1 模型構建

在國內外的金融市場上有難以計數的股票和證券。因此，如果投資者想對一個投資組合進行投資，需要確定哪些資產值得包含在一個理想的投資組合中是非常關鍵的一步。傳統的0-1背包問題的公式如下：Maxvixi

subject towixi≤W

xi∈{0，1}

其中，vi是每件物品的價值，wi是每件物品的比重，W是總比重，xi的值確定選擇與否。

模型A選取5年數據，前100支公司股票，T=5，n=100， rjt代表第j≤n支股票第t≤T年的平均實際收益率，其公式如下：rjt=1。

其中，αjt是每支股票5年的平均名義收益率，βjt是美國市場5年的通貨膨脹率，名義收益率的公式：名義收益率=股息收益率+價格回報率。股息收益率使用的是5年平均比率，價格回報率是當前價格除以5年前價格的幾何回報，公式如下：PRj，0=1/5-1。

其中，PRj，0是第j支股票的當前價格回報率，Pj，0是第j支股票的當前價格，Pj，5是第j支股票5年前的價格。

模型A的目標是將報酬率最大化，用rjt替代vi，目標函數改寫為：maxrjt xj。

同時，整數模型也應考慮風險，本文使用實際收益率與預期收益率之間的標準差作為衡量風險的工具，它可以代表現實和期望之間的波動性。40%作為一個理性的投資者能承受的最大風險水平是較為合理的。

用替換wi，W=0.4，限制條件如下：subject to?xj≤0.4。

其中，ri是5年的平均預期股票回報，根據證券市場線（SML）理論，rj=rf+βi[E（rM）-rf]。E（rM）是由S&P計算器得出的平均市場投資組合M的回報率18.47%，βi是系統風險率，rf是美國國債的無風險回報率1.65%。

服務于判斷哪些資產值得投資的模型A的完整公式如下：max xj

subject toxj≤0.4

xi∈{0，1}

需要注意的是，這里的標準偏差不隨投入的資本數量而增加。因此，可以通過計算標準差與二進制變量xj的乘積之和，得到包含下行風險和上行風險的總風險水平?？傦L險是資產的數量乘以各自的標準差。

4.2 運行結果

首先用分支剪界法得出的結果：只有27只股票值得投資者投資，目標的最大值為5.03701，最小風險為0.39807。接著，再使用遞歸的動態規劃算法驗證，本文將所有∑，j=1，…，100和∑，j=1，…，100的值乘以10萬，確保都以整數形式呈現，運行出的結果與第一種算法一致，目標值為503701，風險值為39807。最后使用貪心算法，需計算Oj=，j=1，…，100，并且將Oj以降序的形式排列，顯示的選擇結果與之前2種算法一致。

被3種算法選擇的27支股票，其公司名稱如下：Allstate Corporation，American Express Co，Boeing Co，Caterpillar Inc，Capital One Financial Cp，Cvs Caremark Corp，Chevron Corp，The Walt Disney Company，Dow Chemical Co，Ford Motor Co，Fifth Third Bancorp，General Dynamics Corp，General Electric Co，Honeywell International，Intel Corp， Johnson & Johnson，Lowe's Companies Inc，Microsoft Corp，Norfolk Southern Corp，Pfizer Inc，Procter & Gamble Co，Philip Morris International，Raytheon Co，Taiwan Semiconductor Manufacturing Company Limited，United Parcel Service B，Walgreen Co，Wells Fargo & Company。

結果表明，標準較小且具有很好收益的公司被選中居多，一些實際收益率極高的公司沒被選中的原因是它們的標準差也就是風險非常大。

5 模型B（LAMAD）

5.1 模型構建

第二個模型的建立是為了確定投資組合中每個資產的比重該如何分布。Markowitz的經典模型（1959）的目標函數是方差-協方差矩陣的二次型。為了簡化算法，很多學者對此模型提出了很多替代或改進意見，Konno and Yamazaki在1991年提出絕對值形式的模型，具有較好的使用效果，但由于他們使用的目標函數是非線性的，本文需將其改寫為線性。

同時，出于實際考慮，將投資組合中資產的數量上限設為5，并加入二進制變量dj，xj是比重，0.4是投資者期望的回報率，將5年分為20個季度，也就是T=20，通過模型A的運算后，n=27，yt代表20個季度中每期的所有資產的預期收益率和實際收益率之差乘以投資于所有資產的資本，rj是第j支股票的預期收益率，rjt是第j支股票的回報率。完整的模型B如下：minyt

s.t.yt≥（rjt-rj）xj，t=1，…，20

yt≥-（rjt-rj）xj，t=1，…，20

ujxj=0.4

xi=1

dj≤5

ljdj≤xj≤ujdj，j=1，…，27

xj≥0，? j=1，…，27

dj∈{0，1}，? j=1，…，27

yt≥0

通常，xj的上界（uj）和下界（lj）的范圍是從0到1，本文將分2次測試。第一次測試，根據5年實際的數據表分析，設每個xj設置上界uj=0.65，American Express Co.的lj=0.2，Walt Disney Company的lj=0.2，Dow Chemical Co.的lj=0.1。第二次測試，為了無偏優化，本次測試去掉每個變量的下界。2次測試中，價格回報率的計算同模型A。

PRj，0=1/3-1

其中，PRj，0是第j支股票的當前價格回報率，Pj，0是第股票的當前價格，Pj，3是第j股票3個月前的價格。

5.2 運行結果

第一次測試，目標值的最小風險的絕對值為0.02839。被選擇的股票有4支：American Express Co.（比重=0.2），Walt Disney Company， Dow Chemical Co.（比重=0.2），Dow Chemical Co（比重=0.1）和Norfolk Southern Corp（比重=0.5），總收益為0.34962。因此，如果總資本是10000，投資者應投資2000美元到American Express Co.，2000美元到Walt Disney Company，Dow Chemical Co.，1000美元到Dow Chemical Co，5000美元到Norfolk Southern Corp。Norfolk Southern Corp的股票是一項非常有價值的資產，占總資本分配的50%。

第二次測試，當本文移除所有變量的下界時，目標值的結果0.04335。Norfolk Southern Corp占總資本的0.65，Procter & Gamble Co占總資本的0.35。Norfolk Southern Corp股票的比重達到了上限，更加證明了它的價值。

6 結論

本文證實了分支剪界法、動態規劃算法和貪心算法在處理整數規劃問題上是非常實用的。分支剪界法的搜索和迭代，動態規劃基于步驟隨時間變化的遞歸，貪心算法的排序策略，盡管各有所長和缺陷，但都給出了相同的結果。本文建立的整數規劃模型的不足之處在于需要預處理一些數據。整數規劃在投資組合優化的應用是有實際意義的，并且可以針對不同目標進行多樣性設計。

【參考文獻】

【1】Hiroshi Konno，Hiroaki Yamazaki.Mean-Absolute Deviation Portfolio Optimization Model and Its Applications to Tokyo Stock Market[J].Management Science，1991，37（5）：519-531.

【2】Moghaddass Mahsa， Terekhov Daria. Inverse Integer Optimization with an Imperfect Observation[J]. Operations Research Letters，2020，48（6）：763-769.

【3】金維佳.基于自更新網格的變異多目標粒子群算法[J].浙江工商職業技術學院學報，2017，16（04）：94-96.