基于线性规划的“多目标投资组合优化”的ε-约束法求解示例
题目描述
考虑一个经典的投资组合优化问题，其中投资者希望在不同资产之间分配资金，以在控制风险的同时最大化收益。这里我们考虑一个多目标优化问题，包含两个目标：
- 最大化预期收益。
- 最小化投资风险（以收益的方差衡量）。
设共有 \(n\) 种资产，第 \(i\) 种资产的预期收益率为 \(r_i\)，收益的协方差矩阵为 \(\Sigma \in \mathbb{R}^{n \times n}\)。决策变量 \(x_i\) 表示投资于资产 \(i\) 的资金比例。
经典的马科维茨均值-方差模型可写为：
\[\begin{aligned} \text{maximize} \quad & \sum_{i=1}^n r_i x_i \\ \text{minimize} \quad & \sum_{i=1}^n \sum_{j=1}^n \sigma_{ij} x_i x_j \\ \text{subject to} \quad & \sum_{i=1}^n x_i = 1, \\ & x_i \ge 0, \quad i=1,\dots,n. \end{aligned} \]
这是一个双目标二次规划问题。为了将其转化为线性规划可处理的形式，通常采用以下两种方法之一：
- 将风险作为约束，最大化收益（或反之）。
- 使用ε-约束法，将其中一个目标转化为约束，从而生成一系列单目标优化问题，进而得到帕累托前沿。
本题要求：
使用ε-约束法，将风险上限设为参数 ε，将原问题转化为一系列线性规划问题，并描述如何求解得到近似帕累托前沿。
解题步骤
步骤1：问题重构为ε-约束形式
我们选择将风险最小化作为主要目标，将收益最大化转化为约束。具体地，我们引入参数 \(R_0\) 表示要求的最低预期收益，将原问题改写为：
\[\begin{aligned} \text{minimize} \quad & \sum_{i=1}^n \sum_{j=1}^n \sigma_{ij} x_i x_j \\ \text{subject to} \quad & \sum_{i=1}^n r_i x_i \ge R_0, \\ & \sum_{i=1}^n x_i = 1, \\ & x_i \ge 0, \quad i=1,\dots,n. \end{aligned} \]
此时问题是一个凸二次规划（因为协方差矩阵 \(\Sigma\) 半正定）。但我们的目标是使用线性规划求解，因此需要进一步处理风险项。
步骤2：风险度量的线性化
二次形式 \(\sum \sum \sigma_{ij} x_i x_j\) 不易直接线性化。一个常见替代方案是使用绝对偏差或下半方差等线性风险度量。这里我们采用平均绝对偏差（MAD） 作为风险度量，它可以通过引入辅助变量转化为线性约束。
设历史收益率数据有 \(T\) 个时期，资产 \(i\) 在时期 \(t\) 的收益为 \(r_{it}\)，其样本平均为 \(\bar{r}_i = \frac{1}{T} \sum_{t=1}^T r_{it}\)。则投资组合在时期 \(t\) 的收益偏差为：
\[d_t = \sum_{i=1}^n (r_{it} - \bar{r}_i) x_i. \]
MAD 定义为：
\[\text{MAD} = \frac{1}{T} \sum_{t=1}^T |d_t|. \]
优化问题可写为：
\[\begin{aligned} \text{minimize} \quad & \frac{1}{T} \sum_{t=1}^T y_t \\ \text{subject to} \quad & y_t \ge d_t, \quad t=1,\dots,T, \\ & y_t \ge -d_t, \quad t=1,\dots,T, \\ & \sum_{i=1}^n \bar{r}_i x_i \ge R_0, \\ & \sum_{i=1}^n x_i = 1, \\ & x_i \ge 0, \quad i=1,\dots,n, \\ & y_t \ge 0, \quad t=1,\dots,T. \end{aligned} \]
其中 \(y_t\) 是辅助变量，表示 \(|d_t|\)。此时目标函数和约束均为线性，问题转化为线性规划。
步骤3：ε-约束法的实施
我们希望得到收益-风险权衡的帕累托前沿。ε-约束法的步骤如下：
-
确定收益范围：
计算最大可能收益 \(R_{\max}\)（通过求解线性规划：最大化 \(\sum \bar{r}_i x_i\)，满足 \(\sum x_i = 1, x_i \ge 0\)）。
计算最小可能收益 \(R_{\min}\)（通过最小化同一目标，或取单个资产最小平均收益）。 -
生成收益约束值：
在区间 \([R_{\min}, R_{\max}]\) 内选取 \(K\) 个等间距点 \(R_0^{(k)}, k=1,\dots,K\)。每一个 \(R_0^{(k)}\) 对应一个风险约束值 ε 的设定（但此处我们将收益作为约束，风险作为目标，所以 ε 对应风险上限，而 \(R_0\) 对应收益下限）。更常见做法是固定风险上限 ε，但这里我们固定收益下限。 -
求解一系列线性规划：
对每个 \(R_0^{(k)}\)，求解如下线性规划：
\[\begin{aligned} \text{minimize} \quad & \frac{1}{T} \sum_{t=1}^T y_t \\ \text{subject to} \quad & y_t \ge \sum_{i=1}^n (r_{it} - \bar{r}_i) x_i, \quad t=1,\dots,T, \\ & y_t \ge -\sum_{i=1}^n (r_{it} - \bar{r}_i) x_i, \quad t=1,\dots,T, \\ & \sum_{i=1}^n \bar{r}_i x_i \ge R_0^{(k)}, \\ & \sum_{i=1}^n x_i = 1, \\ & x_i \ge 0, \quad i=1,\dots,n, \\ & y_t \ge 0, \quad t=1,\dots,T. \end{aligned} \]
记解得的最小风险值为 \(MAD^*(R_0^{(k)})\)。
- 绘制帕累托前沿：
以收益 \(R_0^{(k)}\) 为横坐标，风险 \(MAD^*(R_0^{(k)})\) 为纵坐标，将点 \((R_0^{(k)}, MAD^*(R_0^{(k)}))\) 连接，即得到近似的帕累托前沿。该前沿上的每个点都表示在给定收益下限下的最小可能风险。
步骤4：算法伪代码
输入：历史收益率矩阵 R ∈ ℝ^{T×n}，收益下限个数 K
输出：帕累托前沿点集 P
计算每项资产平均收益 bar_r = mean(R, axis=0)
计算最大收益 R_max = max{ bar_r^T x | sum(x)=1, x≥0 }
计算最小收益 R_min = min{ bar_r^T x | sum(x)=1, x≥0 } # 或取 min(bar_r)
初始化 P = []
for k = 1 to K do
R0 = R_min + (k-1)*(R_max - R_min)/(K-1)
构建线性规划：
决策变量：x[1..n], y[1..T]
目标：min (1/T) * sum_t y_t
约束：
for t = 1 to T:
y_t ≥ sum_i (R[t,i] - bar_r[i]) * x_i
y_t ≥ -sum_i (R[t,i] - bar_r[i]) * x_i
sum_i bar_r[i] * x_i ≥ R0
sum_i x_i = 1
x_i ≥ 0, y_t ≥ 0
调用线性规划求解器（如单纯形法）求解
得到最优解 x*, 最优目标值 MAD*
将点 (R0, MAD*) 加入 P
end for
返回 P
步骤5：实例演示（数值简化）
假设有2种资产（n=2），3个历史时期（T=3）：
收益率数据：
- 资产1: (5%, 2%, 4%)
- 资产2: (8%, 1%, 7%)
计算平均收益：
\(\bar{r}_1 = (5+2+4)/3 = 3.67\%\)，
\(\bar{r}_2 = (8+1+7)/3 = 5.33\%\)。
最大收益：全投资产2，\(R_{\max} = 5.33\%\)。
最小收益：全投资产1，\(R_{\min} = 3.67\%\)。
取 K=3，收益下限 R0 取值：3.67%, 4.5%, 5.33%。
对 R0=4.5% 构建线性规划：
变量：x1, x2, y1, y2, y3。
收益约束：3.67x1 + 5.33x2 ≥ 4.5。
预算约束：x1 + x2 = 1。
偏差计算（时期1为例）：
d1 = (5-3.67)x1 + (8-5.33)x2 = 1.33x1 + 2.67x2。
约束：y1 ≥ d1, y1 ≥ -d1。类似构造时期2、3。
目标：min (y1+y2+y3)/3。
求解得：x1≈0.5, x2≈0.5, MAD≈某个值。
重复对其他 R0 求解，得到三个点，绘制帕累托前沿。
总结
通过将风险度量线性化（如使用MAD），并将收益目标转化为约束，我们可以用ε-约束法将多目标投资组合问题转化为一系列线性规划问题。求解这些线性规划，即可得到近似帕累托前沿，帮助投资者在收益与风险之间权衡选择。该方法避免了直接处理二次目标，计算效率高，且易于实现。