基于整數(shù)線性規(guī)劃和混合整數(shù)線性規(guī)劃的投資組合優(yōu)化

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

【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.

【關(guān)鍵詞】整數(shù)規(guī)劃;投資組合優(yōu)化;風(fēng)險;算法

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

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

1 引言

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

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

2 算法介紹

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

啟發(fā)式方法特別適用于混合整數(shù)規(guī)劃，因為混合整數(shù)規(guī)劃太大而無法求解最優(yōu)，而線性規(guī)劃較為松弛，可以在合理的時間內(nèi)求解。

2.1 分支剪界算法

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

2.2 動態(tài)規(guī)劃算法

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

2.3 貪心算法

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

3 文獻綜述

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

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

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

4 模型A（ILP）

4.1 模型構(gòu)建

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

subject towixi≤W

xi∈{0，1}

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

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

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

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

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

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

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

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

服務(wù)于判斷哪些資產(chǎn)值得投資的模型A的完整公式如下：max xj

subject toxj≤0.4

xi∈{0，1}

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

4.2 運行結(jié)果

首先用分支剪界法得出的結(jié)果：只有27只股票值得投資者投資，目標的最大值為5.03701，最小風(fēng)險為0.39807。接著，再使用遞歸的動態(tài)規(guī)劃算法驗證，本文將所有∑，j=1，…，100和∑，j=1，…，100的值乘以10萬，確保都以整數(shù)形式呈現(xiàn)，運行出的結(jié)果與第一種算法一致，目標值為503701，風(fēng)險值為39807。最后使用貪心算法，需計算Oj=，j=1，…，100，并且將Oj以降序的形式排列，顯示的選擇結(jié)果與之前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，F(xiàn)ord Motor Co，F(xiàn)ifth 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。

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

5 模型B（LAMAD）

5.1 模型構(gòu)建

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

同時，出于實際考慮，將投資組合中資產(chǎn)的數(shù)量上限設(shè)為5，并加入二進制變量dj，xj是比重，0.4是投資者期望的回報率，將5年分為20個季度，也就是T=20，通過模型A的運算后，n=27，yt代表20個季度中每期的所有資產(chǎn)的預(yù)期收益率和實際收益率之差乘以投資于所有資產(chǎn)的資本，rj是第j支股票的預(yù)期收益率，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次測試。第一次測試，根據(jù)5年實際的數(shù)據(jù)表分析，設(shè)每個xj設(shè)置上界uj=0.65，American Express Co.的lj=0.2，Walt Disney Company的lj=0.2，Dow Chemical Co.的lj=0.1。第二次測試，為了無偏優(yōu)化，本次測試去掉每個變量的下界。2次測試中，價格回報率的計算同模型A。

PRj，0=1/3-1

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

5.2 運行結(jié)果

第一次測試，目標值的最小風(fēng)險的絕對值為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，投資者應(yīng)投資2000美元到American Express Co.，2000美元到Walt Disney Company，Dow Chemical Co.，1000美元到Dow Chemical Co，5000美元到Norfolk Southern Corp。Norfolk Southern Corp的股票是一項非常有價值的資產(chǎn)，占總資本分配的50%。

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

6 結(jié)論

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

【參考文獻】

【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】金維佳.基于自更新網(wǎng)格的變異多目標粒子群算法[J].浙江工商職業(yè)技術(shù)學(xué)院學(xué)報，2017，16（04）：94-96.