混合整数二次规划投资组合优化：基于问题 -凯发k8网页登录

此示例说明如何使用基于问题的方法来求解混合整数二次规划 (miqp) 投资组合优化问题。其思想是迭代求解一系列局部逼近 miqp 问题的混合整数线性规划 (milp) 问题。有关基于求解器的方法，请参阅。

问题概要

根据 markowitz 所述 ("portfolio selection," j. finance volume 7, issue 1, pp. 77-91, march 1952)，您可以将许多投资组合优化问题表达为二次规划问题。假设您有包含 n 项的一组资产并希望选择一个投资组合，其中 $x (i)$ 是您在 $i$ 资产中的投资比例。如果您知道每项资产平均回报的向量 $r$ ，以及回报的协方差矩阵 $q$ ，则对于给定的风险厌恶水平 λ $λ$ ，您需要最大化风险调整后的预期回报：

$\max_{x} (r^{t} x - λ x^{t} q x) .$

quadprog 求解器用于求解此二次规划问题。但是，除了简单的二次规划问题之外，您还可能希望以多种方式限制投资组合，例如：

投资组合中资产不超过 m 种，其中 m <= n。
投资组合中至少有 m 种资产，其中 0 < m <= m。
具有半连续约束，意味着对某些固定比例 $f m i n > 0$ 和 $f m a x \geq f m i n$ ， $x (i) = 0$ 或 $f m i n \leq x (i) \leq f m a x$ 。

您无法在 quadprog 中包含这些约束。困难在于约束的离散性。此外，虽然混合整数线性规划求解器处理离散约束，但它不处理二次目标函数。

此示例构造一系列满足约束的 milp 问题，这些问题越来越逼近二次目标函数。虽然这种方法适用于此示例，但它可能不适用于不同问题或约束类型。

首先对约束进行建模。

对离散约束建模

$x$ 是资产配置比例的向量，对于每个 $i$ ， $0 \leq x (i) \leq 1$ 。要对投资组合中的资产数量进行建模，您需要指示变量 $v$ ，满足当 $x (i) = 0$ 时 $v (i) = 0$ ，当 $x (i) > 0$ 时 $v (i) = 1$ 。要获得满足此约束的变量，请将 $v$ 向量设置为二元变量，并施加线性约束

$v (i) f m i n \leq x (i) \leq v (i) f m a x .$

这些不等式强制在任何完全相同的时间 $x (i)$ 和 $v (i)$ 都为零，并且只要 $x (i) > 0$ ，它们还强制 $f m i n \leq x (i) \leq f m a x$ 。

此外，要对投资组合中的资产数量强制进行约束，请施加线性约束

$m \leq \sum_{i} v (i) \leq m .$

目标和连续线性逼近

对于最初表示的问题，您需要尝试最大化目标函数。然而，optimization toolbox™ 中的所有求解器都执行最小化计算。因此，需要将问题表示为最小化目标的负值：

$\min_{x} λ x^{t} q x - r^{t} x .$

此目标函数是非线性的。milp 求解器需要线性目标函数。有一种标准方法可以将此问题重新表示为具有线性目标和非线性约束的问题。引入松弛变量 $z$ 来表示二次项。

$\min_{x, z} λ z - r^{t} x such that x^{t} q x - z \leq 0, z \geq 0 .$

在迭代求解 milp 逼近时，您包含新线性约束，其中每个约束都在当前点附近局部逼近非线性约束。特别是，对于 $x = x_{0} δ$ ，其中 $x_{0}$ 是常量向量且 $δ$ 是变量向量，约束的一阶泰勒逼近为

$x^{t} q x - z = x_{0}^{t} q x_{0} 2 x_{0}^{t} q δ - z o (| δ |^{2}) .$

用 $x - x_{0}$ 取代 $δ$ 得出

$x^{t} q x - z = - x_{0}^{t} q x_{0} 2 x_{0}^{t} q x - z o (| x - x_{0} |^{2}) .$

对于每个中间解 $x_{k}$ ，您在 $x$ 和 $z$ 中引入一个新线性约束，作为上述表达式的线性部分：

$- x_{k}^{t} q x_{k} 2 x_{k}^{t} q x - z \leq 0 .$

其形式为 $a x \leq b$ ，其中 $a = 2 x_{k}^{t} q$ ，对于 $z$ 项有 $- 1$ 乘数，且 $b = x_{k}^{t} q x_{k}$ 。

这种给问题添加新线性约束的方法称为割平面法。有关详细信息，请参阅 j. e. kelley, jr."the cutting-plane method for solving convex programs."j. soc.indust.appl.math.vol. 8, no. 4, pp. 703-712, december, 1960.

matlab® 问题表示

要表达优化问题，请执行以下各项：

决定您的变量表示什么
表示这些变量中的下界和上界
给出线性等式和不等式表达式

加载问题的数据。此数据有以向量 r 形式表示的 225 个预期回报，以及以 225×225 矩阵 q 形式表示的回报协方差。数据与在投资组合优化问题中使用二次规划的示例中使用的数据相同。

load port5
r = mean_return;
q = correlation .* (stddev_return * stddev_return');

将资产数量设置为 n。

n = length(r);

创建问题变量、约束和目标

创建表示资产分配比例的连续变量 xvars，表示相关联的 xvars 是为零还是严格为正的二元变量 vvars，以及表示 $z$ 变量的 zvar（正标量）。

xvars = optimvar('xvars',n,1,'lowerbound',0,'upperbound',1);
vvars = optimvar('vvars',n,1,'type','integer','lowerbound',0,'upperbound',1);
zvar = optimvar('zvar',1,'lowerbound',0);

问题中所有 2n 1 变量的下界为零。xvars 和 yvars 变量的上界为 1，zvar 没有上界。

将解中的资产数量设置为 100 和 150 之间。将此约束纳入问题的形式中，即

$m \leq \sum_{i} v (i) \leq m,$

为此需要编写两个线性约束：

$\sum_{i} v (i) \leq m$

$\sum_{i} v (i) \geq m .$

m = 150;
m = 100;
qpprob = optimproblem('objectivesense','maximize');
qpprob.constraints.mconstr = sum(vvars) <= m;
qpprob.constraints.mconstr2 = sum(vvars) >= m;

包含半连续约束。对于每种资产类型，取资产的非零最小小数为 0.001，最大小数为 0.05。

fmin = 0.001;
fmax = 0.05;

包含不等式 $x (i) \leq f m a x (i) * v (i)$ 和 $f m i n (i) * v (i) \leq x (i)$ 。

qpprob.constraints.fmaxconstr = xvars <= fmax*vvars;
qpprob.constraints.fminconstr = fmin*vvars <= xvars;

包含投资组合为 100% 投资的约束，即 $\sum x_{i} = 1$ 。

qpprob.constraints.allin = sum(xvars) == 1;

将风险厌恶系数 $λ$ 设置为 100。

lambda = 100;

定义目标函数 $r^{t} x - λ z$ ，并将其包含在问题中。

qpprob.objective = r'*xvars - lambda*zvar;

求解问题

要以迭代方式求解问题，请首先用当前约束求解问题，这些约束尚未反映任何线性化。

options = optimoptions(@intlinprog,'display','off'); % suppress iterative display
[xlinint,fval,exitflagint,output] = solve(qpprob,'options',options);

为迭代准备停止条件：当松弛变量 $z$ 在真实二次值的 0.01% 以内时停止。

thediff = 1e-4;
iter = 1; % iteration counter
assets = xlinint.xvars;
truequadratic = assets'*q*assets;
zslack = xlinint.zvar;

保留计算出的真实二次变量和松弛变量的历史记录，以便绘图。设置比默认值更严格的容差，以帮助迭代收敛于正确的解。

history = [truequadratic,zslack];
options = optimoptions(options,'lpoptimalitytolerance',1e-10,'relativegaptolerance',1e-8,...
                      'constrainttolerance',1e-9,'integertolerance',1e-6);

计算二次值和松弛值。如果它们不同，则添加另一个线性约束并再次求解。

每个新线性约束 $a x \leq b$ 来自线性逼近

$- x_{k}^{t} q x_{k} 2 x_{k}^{t} q x - z \leq 0 .$

找到新解后，在新解和旧解的中间使用线性约束。这种包含线性约束的启发式方法可能比直接采用新解更快。要使用解而不是半启发式方法，请对下面的“midway”行进行注释，并取消注释其后的一行。

while abs((zslack - truequadratic)/truequadratic) > thediff % relative error
    constr = 2*assets'*q*xvars - zvar <= assets'*q*assets;
    newname = ['iteration',num2str(iter)];
    qpprob.constraints.(newname) = constr;
    % solve the problem with the new constraints
    [xlinint,fval,exitflagint,output] = solve(qpprob,'options',options);
    assets = (assets xlinint.xvars)/2; % midway from the previous to the current
%     assets = xlinint(xvars); % use the previous line or this one
    truequadratic = xlinint.xvars'*q*xlinint.xvars;
    zslack = xlinint.zvar;
    history = [history;truequadratic,zslack];
    iter = iter   1;
end

检查解和收敛速度

绘制松弛变量和目标函数二次部分的历史记录，看看它们是如何收敛的。

plot(history)
legend('quadratic','slack')
xlabel('iteration number')
title('quadratic and linear approximation (slack)')

figure contains an axes object. the axes object with title quadratic and linear approximation (slack) contains 2 objects of type line. these objects represent quadratic, slack.

milp 解的质量如何？output 结构体包含该信息。检查在解处目标的内部计算边界之间的绝对差距。

disp(output.absolutegap)

绝对差距为零，表明 milp 解准确。

对最佳分配绘图。使用 xlinint.xvars 而不是 assets，因为 assets 在使用中间的更新时可能不满足约束。

bar(xlinint.xvars)
grid on
xlabel('asset index')
ylabel('proportion of investment')
title('optimal asset allocation')

figure contains an axes object. the axes object with title optimal asset allocation contains an object of type bar.

很容易看出，所有非零资产分配都在半连续边界 $f m i n = 0.001$ 和 $f m a x = 0.05$ 之间。

有多少非零资产？约束是非零资产数在 100 和 150 之间。

sum(xlinint.vvars)

ans = 100

这种分配的预期回报是多少，风险调整后的回报值是多少？

fprintf('the expected return is %g, and the risk-adjusted return is %g.\n',...
    r'*xlinint.xvars,fval)

the expected return is 0.000595107, and the risk-adjusted return is -0.0360382.

通过使用 financial toolbox® 中专为投资组合优化而设计的功能，可以进行更详细的分析。有关说明如何使用 portfolio 类直接处理半连续和基数约束的示例，请参阅 (financial toolbox)。