基于整数线性规划和混合整数线性规划的投资组合优化-第1篇

1、 基于整数线性规划和混合整数线性规划的投资组合优化 【摘 要】论文主要内容是使用2个整数线性规划模型进行投资组合优化。第一个整数线性规划模型应用分支剪界算法（使用CPLEX软件）、动态规划算法和贪心算法（使用Java软件）筛选最有价值的股票。第二个模型是混合整数线性规划模型，以回报为约束条件，确定投资所选定股票的确切数额，并最小化风险。【Abstract】The main content of this paper is to optimize investment portfolio by using two integer linear programming models. The fi

2、rst 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 t

3、he constraint condition to determine the exact amount of investment in the selected stock and minimize the risk.【關键词】整数规划;投资组合优化;风险;算法【Keywords】integer programming; portfolio optimization; risk; algorithmF224;F831.5 【文献标志码】A 1673-1069（2021）09-0116-031 引言线性规划是用来寻求变量处于线性关系时的有效方法，在项目选择、投资组合优化、季节收益预测等问题

4、中有多种应用。整数规划与线性规划非常相似，但它要求所有或部分变量是整数。某些情况下，整数规划更可取，如二元变量的管理决策。部分决策变量为整数的模型，称为混合整数规划。本文将会研究整数线性规划在投资组合优化中的应用。模型A，即整数线性规划（ILP）模型可以看作NP完全问题中的0-1背包问题，通过模型A找出可选入投资组合的股票。另一个模型是混合整数线性规划（MILP），这里使用的是有限资产平均绝对偏差（LAMAD）模型的演变来确定投资所选股票的确切数量，分配最合适的权重，以达到风险最小化、回报最大化的效果。本文采用3种算法求解：分支剪界算法、动态规划算法和贪心算法。分支剪界算法用CPLEX 12.

5、6实现，动态规划算法和贪心算法在Eclipse标准4.4平台上，用Java语言实现，所采用的股票信息和数据由NASDAQ和yahoo finance网站获取。2 算法介绍以下介绍的算法都可以归属于启发法的范畴。启发法是指不以找到问题的最佳或最确切的解决方案为目标的技术，而是找到一个足够可信的解决方案的方法。直觉判断、刻板印象和常识都属于这个“范畴”。它非常适用于在计算或搜索过于详尽和不实际的情况下，通过心理捷径来加快得到满意解决方案的过程，以减轻作出决策的认知负担。它有常见的几种策略：第一种是将问题的目标状态进行切分，然后通过实现子目标逐渐实现总的目的;第二种是从最终目标状态逆向去寻找达到这个

6、状态的途径;第三种是逐步收缩初始状态和目标状态的距离的方法。元启发式是指导搜索过程的策略或上层方法论，元启发式的目标是有效地探索搜索空间，以找到最接近的最优解。启发式依赖于问题，用于确定特定问题的“足够好”的解决方案，而元启发式就像一种设计模式，可以应用于更广泛的问题。启发式方法特别适用于混合整数规划，因为混合整数规划太大而无法求解最优，而线性规划较为松弛，可以在合理的时间内求解。2.1 分支剪界算法分支剪界法是分支限界法和切割平面法2种算法的结合。最早的求解混合整数规划问题的算法是切割平面方法，但这个方法的收敛速度较慢，后来的学者提出了求解离散规划问题的分支限界法，对切割平面法进行了改进。分

7、支剪界算法在整数规划中有诸多的应用，如Mahsa在2020年发表的不完全观察下的整数优化。图1是一个用分支定界算法求解整数规划的演示例子，目标函数为：MaxZ=240 x1+160 x2。2.2 动态规划算法从数学优化的角度来看，动态规划通常是指把一个大的优化问题分解成一系列小的决策，随着时间的推移来解决，例如，将问题分成v1（.），v2（.），vn（.）等不同状态，将vi（a）定义为达到状态a的值，时间为t，t=1，T。由已决策的新状态vi（a）可以递归地运算出vi-1（a）的值（Nocedal和Wright，2006），以此来优化求解。2.3 贪心算法贪心算法同动态规划算法有相似之处，也是

8、先进行划分，把一个大的问题分成若干子问题，然后搜寻目前的最优解，再处理后续产生的子问题。有时，利用此算法求出的是局部最优解，而不是整体的。贪心算法生成的步骤似乎足够好，但不能保证对未来或所有子问题都足够好（Cormen等，1990）。3 文献综述有许多不同的模型可以为相同的或类似的目标服务。模型的选择取决于风险的性质。方差和标准偏差是表达波动性的标准概念。遵循现代投资组合理论的基本原则，本文倾向于进行有效的交易和多样化的投资，以确保对冲这类风险。多元化投资是指将资产投资于房地产、食品行业、科技行业等不同经济领域，或投资于国内市场、海外市场等不同金融市场。在现代投资组合理论中，在一个投资组合中加

9、入一定数量的适当资产可以显著降低标准差。但是，当投资组合中有一定数量的资产时，这种利益将会减弱或终止。一般来说，理想的资产数量在25个左右。剩下的无法“分散”的风险就是所谓的系统性风险。系统性风险在投资组合配置中发挥着重要作用，因为即使完全分散投资也无法消除系统风险。因此，根据Stone和其他作者在1970年共同提出的证券市场线（SML），预期收益率完全依赖于这种风险。贝塔值（）是证券、股票或投资组合相对于整个市场的系统风险。本文将贝塔值作为衡量市场风险的基准。=1意味着证券价格完全随市场变动。一些资产如国库券和黄金是贝塔值低于1的例子，因为这类资产的价格运动与市场没有高度相关。如果股票的贝塔

10、值是1.1，那么理论上，它的波动性比市场高10%。SML理论认为，同一行业的各投资工具的风险处于同一水平，而同一水平线的风险又意味着同一水平线的预期收益率。CVaR（Conditional Value at Risk）和Sortino比率（Sortino ratio）這2项主要用于衡量下行风险的指标，近来受到了投资者的广泛欢迎。根据这一趋势，许多研究者也采用了这些模型。下行风险是指随着市场环境的变化，证券价值的潜在下降。换句话说，这是投资者可能因股市下跌而承受的最大损失。它可以通过实际回报和预期回报，也就是回报的不确定性之间的差异来量化，也可以通过下行贝塔来衡量，它是当一种证券的超额回报小于平

11、均市场超额回报时的贝塔值。相反，上行风险是获利的可能性，用上行贝塔值来衡量。上行贝塔值是当一种证券的超额回报小于平均市场超额回报时的贝塔值。在进行风险度量时，这2种风险是非常重要的。在现实世界中，监管、交易成本和税收都会影响投资组合的收益，增加投资组合的风险，但这些因素在本文中没有讨论。有关投资组合优化的文章通常以非线性规划、二次规划、整数线性规划、混合整数线性规划以及线下比较流行的数据挖掘的方式进行研究，常伴随启发式方法的痕迹。本文采用整数线性规划和混合整数线性规划结合以上3种启发式方法对投资组合优化问题进行了研究。4 模型A（ILP）4.1 模型构建在国内外的金融市场上有难以计数的股票和证

12、券。因此，如果投资者想对一个投资组合进行投资，需要确定哪些资产值得包含在一个理想的投资组合中是非常关键的一步。传统的0-1背包问题的公式如下：Maxvixisubject towixiWxi0，1其中，vi是每件物品的价值，wi是每件物品的比重，W是总比重，xi的值确定选择与否。模型A选取5年数据，前100支公司股票，T=5，n=100， rjt代表第jn支股票第tT年的平均实际收益率，其公式如下：rjt=1。其中，jt是每支股票5年的平均名义收益率，jt是美国市场5年的通货膨胀率，名义收益率的公式：名义收益率=股息收益率+价格回报率。股息收益率使用的是5年平均比率，价格回报率是当前价格除以5

13、年前价格的几何回报，公式如下：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 toxj0.4。其中，ri是5年的平均预期股票回报，根据证券市场线（SML）理论，rj=rf+iE（rM）-rf

14、。E（rM）是由S&P计算器得出的平均市场投资组合M的回报率18.47%，i是系统风险率，rf是美国国债的无风险回报率1.65%。服务于判断哪些资产值得投资的模型A的完整公式如下：max xjsubject toxj0.4xi0，1需要注意的是，这里的标准偏差不随投入的资本数量而增加。因此，可以通过计算标准差与二进制变量xj的乘积之和，得到包含下行风险和上行风险的总风险水平。总风险是资产的数量乘以各自的标准差。4.2 运行结果首先用分支剪界法得出的结果：只有27只股票值得投资者投资，目标的最大值为5.03701，最小风险为0.39807。接着，再使用递归的动态规划算法验证，本文将所有，j=1，

15、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 Chemi

16、cal Co，Ford Motor Co，Fifth Third Bancorp，General Dynamics Corp，General Electric Co，Honeywell International，Intel Corp， Johnson & Johnson，Lowes Companies Inc，Microsoft Corp，Norfolk Southern Corp，Pfizer Inc，Procter & Gamble Co，Philip Morris International，Raytheon Co，Taiwan Semiconductor Manufacturing

17、Company Limited，United Parcel Service B，Walgreen Co，Wells Fargo & Company。结果表明，标准较小且具有很好收益的公司被选中居多，一些实际收益率极高的公司没被选中的原因是它们的标准差也就是风险非常大。5 模型B（LAMAD）5.1 模型构建第二个模型的建立是为了确定投资组合中每个资产的比重该如何分布。Markowitz的经典模型（1959）的目标函数是方差-协方差矩阵的二次型。为了简化算法，很多学者对此模型提出了很多替代或改进意见，Konno and Yamazaki在1991年提出绝对值形式的模型，具有較好的使用效果，但由于

18、他们使用的目标函数是非线性的，本文需将其改写为线性。同时，出于实际考虑，将投资组合中资产的数量上限设为5，并加入二进制变量dj，xj是比重，0.4是投资者期望的回报率，将5年分为20个季度，也就是T=20，通过模型A的运算后，n=27，yt代表20个季度中每期的所有资产的预期收益率和实际收益率之差乘以投资于所有资产的资本，rj是第j支股票的预期收益率，rjt是第j支股票的回报率。完整的模型B如下：minyts.t.yt（rjt-rj）xj，t=1，20yt-（rjt-rj）xj，t=1，20ujxj=0.4xi=1dj5ljdjxjujdj，j=1，27xj0， j=1，27dj0，1， j=

19、1，27yt0通常，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.0

20、2839。被选择的股票有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%。第二次测试，当本文移除所有变量的下界时，目标