混合整数二次规划组合优化:基于求解器
这个例子展示了如何解决一个混合整数二次规划(MIQP)组合优化问题使用intlinprog
混合整数线性规划(MILP)求解器。其思想是迭代地解决一系列局部近似MIQP问题的MILP问题。有关基于问题的方法,请参见混合整数二次规划组合优化:基于问题.
问题概述
正如Markowitz所展示的(“投资组合选择”,J. Finance卷7,第1期,第77-91页,1952年3月),你可以用二次规划问题来表达许多投资组合优化问题。假设你有一组N
资产和想要选择的组合,有
资产是你投资的一部分
.如果你知道这个向量
每种资产的平均收益,和协方差矩阵
在一定的风险规避水平下
使风险调整后的预期收益最大化:
的quadprog
求解器解决了这个二次规划问题。然而,除了简单的二次规划问题之外,你可能还想以多种方式限制投资组合,例如:
不超过
米
在资产组合中,其中M <= n
.至少有
米
在资产组合中,其中0 < m <= m
.有断断续续的约束,意思是 ,或 对于某些固定分数 而且 .
您不能将这些约束包含在quadprog
.困难在于约束的离散性。此外,混合整数线性规划求解器intlinprog
处理离散约束,不处理二次目标函数。
本例构造了一系列满足约束条件的MILP问题,并且越来越接近二次目标函数。虽然这种技术适用于本例,但它可能不适用于不同的问题或约束类型。
首先对约束进行建模。
离散约束建模
资产配置的矢量是分数,用的 为每一个 .要对投资组合中的资产数量建模,您需要指标变量 这样 当 , 当 .要获得满足此限制的变量,请设置 向量为二进制变量,并施加线性约束
这些不等式都是强制的 而且 同时是0,它们也强制执行吗 每当 .
此外,为了加强对投资组合中资产数量的约束,可以施加线性约束
目标与连续线性逼近
正如第一个公式,你试着最大化目标函数。但是,所有优化工具箱™求解器都最小化。所以将问题表述为最小化目标的负面影响:
这个目标函数是非线性的。的intlinprog
MILP求解器需要一个线性目标函数。有一种标准的技术可以将这个问题重新表述为一个具有线性目标和非线性约束的问题。引入松弛变量
表示二次项。
当你迭代地求解MILP近似时,你包含了新的线性约束,每个约束都在当前点附近局部逼近非线性约束。特别地,对于 在哪里 是常数向量和吗 是一个变量向量,约束的一阶泰勒近似是
替换 通过 给了
对于每个中间溶液 引入一个新的线性约束 而且 如上面表达式的线性部分:
这是表格 ,在那里 ,有一个 的乘数 项, .
这种向问题中添加新的线性约束的方法被称为切割平面法。详情见小J. E.凯利。求解凸程序的切平面法j . Soc。工业上。达成。数学。第8卷第4期,703-712页,1960年12月。
MATLAB®问题公式
表达问题为intlinprog
求解器,你需要做以下工作:
决定你的变量代表什么
用这些变量表示下界和上界
给出线性等式和不等式矩阵
有第一个 变量表示 向量,下一个 变量表示二进制 向量,最后一个变量表示 松弛变量。有 问题中的变量。
加载问题的数据。该数据在向量中有225个预期收益r
225 × 225矩阵中收益的协方差问
.数据与在投资组合优化问题上使用二次规划示例中的数据相同。
负载port5R = mean_return;Q =相关性。* (stdDev_return * stdDev_return');
设置资产数为N
.
N =长度(r);
为变量设置索引
xvars = 1:N;vvars = N+1:2*N;zvar = 2*N+1;
所有的下界2 n + 1
问题中的变量为零。第一个的上界2 n
变量是一个,最后一个变量没有上界。
lb = 0 (2*N+1,1);ub = ones(2*N+1,1);ub(zvar) = Inf;
将解决方案中的资产数量设置为100到150之间。将这个约束条件合并到表单中的问题中,即
通过写出两个线性约束的形式 :
M = 150;M = 100;A = 0 (1,2*N+1);分配一个矩阵A(vars) = 1;% A*x表示v(i)A = [A; -a];B = 0 (2,1);分配b向量b(1) = M;B (2) = -m;
包括半连续约束。取资产的最小非零部分为0.001
对于每种资产类型,以及所要的最大分数0.05
.
Fmin = 0.001;Fmax = 0.05;
包括不平等 而且 线性不等式。
Atemp =眼睛(N);Amax = horzcat(Atemp,-Atemp*fmax, 0 (N,1));A = [A;Amax];b = [b; 0 (N,1)];Amin = horzcat(-Atemp,Atemp*fmin, 0 (N,1));A = [A;阿明];b = [b; 0 (N,1)];
包括投资组合是100%投资的约束,这意味着 .
Aeq = 0 (1,2*N+1);分配Aeq矩阵Aeq(xvars) = 1;Beq = 1;
设置风险规避系数
来One hundred.
.
Lambda = 100;
定义目标函数 作为一个向量。的乘数包含零 变量。
f = [-r; 0 (N,1);lambda];
解决问题
要迭代地解决问题,首先要用当前的约束来解决问题,这些约束还没有反映任何线性化。整数约束在vvars
向量。
选项= optimoptions(@intlinprog,“显示”,“关闭”);抑制迭代显示[xLinInt,fval,exitFlagInt,output] = intlinprog(f,vvars,A,b,Aeq,beq,lb,ub,options);
为迭代准备一个停止条件:当松弛变量时停止 在真实二次值的0.01%之内。设置比默认值更严格的容差,以帮助确保问题在约束累积时仍然严格可行。
Thediff = 1e-4;Iter = 1;%迭代计数器assets = xLinInt(xvars);% x变量truequadatic =资产的*Q*资产;zslack = xLinInt(zvar);松弛变量值选项= optimoptions(选项,“LPOptimalityTolerance”1平台以及“RelativeGapTolerance”1 e-8...“ConstraintTolerance”1 e-9“IntegerTolerance”1 e-6);
保存计算出的真实二次变量和松弛变量的历史,以便绘图。
History = [truequadratic,zslack];
计算二次和松弛值。如果它们不同,则添加另一个线性约束并再次求解。
在工具箱语法中,每个新的线性约束 来自于线性逼近
你可以看到这一行 新元素加入 ,与 中的-1系数表示的项 .
找到新解后,在新旧解之间使用一个线性约束。金宝搏官方网站这种包含线性约束的启发式方法比简单地采用新的解决方案更快。要使用该解决方案而不是中途启发式,请注释下面的“中途”行,并取消下面的注释。
而Abs ((zslack - truequadatic)/ truequadatic) > thediff%相对误差newArow = horzcat(2*资产'*Q,零(1,N),-1);线性化约束rhs =资产的*Q*资产;%线性化约束的右边A = [A;newArow];B = [B;rhs];用新的约束条件解决问题。[xLinInt,fval,exitFlagInt,output] = intlinprog(f,vvars,A,b,Aeq,beq,lb,ub,options);assets = (assets+xLinInt(xvars))/2;从以前到现在的中途% assets = xLinInt(xvars);使用前一行或这一行truequadratic = xLinInt(xvars)'*Q* xLinInt(xvars);zslack = xLinInt(zvar);历史=[历史;truequadratic,zslack];Iter = Iter + 1;结束
检验解和收敛速度
绘制松弛变量的历史和目标函数的二次部分,看看它们是如何收敛的。
情节(历史)传说(“二次”,“松弛”)包含(的迭代次数)标题(二次和线性逼近(松弛))
MILP解决方案的质量如何?的输出
结构包含该信息。在解处检查内部计算的目标边界之间的绝对差距。
disp (output.absolutegap)
0
绝对差为零,说明MILP解是准确的。
画出最优分配图。使用xLinInt (xvars)
,而不是资产
,因为资产
可能无法满足使用中途更新时的约束。
栏(xLinInt (xvars))网格在包含(“资产指数”) ylabel (“投资比例”)标题(“最优资产配置”)
你可以很容易地看到,所有非零资产配置都在半连续边界之间 而且 .
有多少非零资产?限制条件是有100到150个非零资产。
sum (xLinInt (vvars))
Ans = 100
这种配置的预期回报是多少?风险调整后的回报值是多少?
流(“预期收益为%g,风险调整收益为%g。\n”,...r * xLinInt (xvars)、-fval)
预期收益为0.000595107,风险调整收益为-0.0360382。
通过使用Financial Toolbox™中专门为投资组合优化设计的功能,可以进行更详细的分析。有关展示如何使用Portfolio类直接处理半连续约束和基数约束的示例,请参见基于半连续和基数约束的投资组合优化(金融工具箱).