第 9 章 · 02 贪婪与整数 LP

第 9 章 · 02 贪婪与整数 LP

本节摘要:DiscreteAllocation 提供两种「连续权重→整数股数」的算法,本节深入它们的内部。贪婪法(greedy)用「两轮启发式」:第一轮按权重向下取整,第二轮按权重偏差逐股补齐,简单但快。整数线性规划(lp)把问题形式化为 min r + ‖wT - x⊙p‖₁ 的混合整数规划,用 cvxpy + ECOS_BB 求解,精确但慢 100~1000 倍。本节还讲做空(short_ratio、reinvest)的处理。读完本节,你能根据规模和精度需求选择算法,并理解它们在「权重偏差」上的本质差别。

内容来源:源码 pypfopt/discrete_allocation.py、文档 docs/Postprocessing.rst,汉化并套用体系化模板。

学习目标

阅读完本节,你应当能够:

1. 说清 greedy_portfolio 两轮启发式的工作原理。
2. 写出 lp_portfolio 的整数规划目标函数。
3. 解释 reinvest 参数在做空时的作用。
4. 知道 short_ratio 与 130/30 策略的关系。
5. 根据规模选 greedy 还是 lp。

一、贪婪法:两轮启发式

greedy_portfolio 分两轮:

第一轮:按权重向下取整

源码:

self.weights.sort(key=lambda x: x[1], reverse=True)   # 按权重降序

available_funds = self.total_portfolio_value
shares_bought = []
buy_prices = []
for ticker, weight in self.weights:
    price = self.latest_prices[ticker]
    n_shares = int(weight * self.total_portfolio_value / price)   # 向下取整
    cost = n_shares * price
    available_funds -= cost
    shares_bought.append(n_shares)
    buy_prices.append(price)
​

第一轮结束后,因为统一向下取整,必有大量剩余资金。

第二轮:按偏差逐股补

while available_funds > 0:
    current_weights = np.array(buy_prices) * np.array(shares_bought)
    current_weights /= current_weights.sum()
    ideal_weights = np.array([i[1] for i in self.weights])
    deficit = ideal_weights - current_weights    # 偏差
    idx = np.argmax(deficit)                     # 偏差最大的资产
    ticker, weight = self.weights[idx]
    price = self.latest_prices[ticker]
    # 买不起就找下一个偏差大的
    while price > available_funds:
        deficit[idx] = 0
        idx = np.argmax(deficit)
        # ... 防御性跳出
    shares_bought[idx] += 1
    available_funds -= price
​

核心策略:每轮挑「实际权重与目标偏差最大的」资产,补 1 股。这样能保证「补的方向永远是当前最缺的」。

💡 贪婪法的优雅:不追求全局最优,但通过「优先补最大缺口」的局部贪心,在大多数场景下能让剩余资金极少。官方示例 $10,000 组合,剩余常在 $10 量级。

二、整数 LP:精确的混合整数规划

lp_portfolio 把问题写成正式的混合整数线性规划:

变量: x ∈ ℤⁿ (每个资产的整股数), r ∈ ℝ (剩余), u ∈ ℝⁿ (辅助)

目标:  min  r + Σ u_i
约束:  η_i = w_i·T - x_i·p_i            (每个资产的偏差)
       u_i ≥ η_i, u_i ≥ -η_i            (u 是 |η| 的上界)
       x_i ≥ 0
       r = T - pᵀx ≥ 0                   (不超预算)
​

源码:

p = self.latest_prices.values
n = len(p)
w = np.fromiter([i[1] for i in self.weights], dtype=float)

x = cp.Variable(n, integer=True)
r = self.total_portfolio_value - p.T @ x

eta = w * self.total_portfolio_value - cp.multiply(x, p)
u = cp.Variable(n)
constraints = [eta <= u, eta >= -u, x >= 0, r >= 0]
objective = cp.sum(u) + r

opt = cp.Problem(cp.Minimize(objective), constraints)
opt.solve(solver=solver)
​

数学解读:

• η = wT - x⊙p 是「目标 USD 价值 - 实际 USD 价值」
• u = |η| 是绝对偏差
• 目标 Σu + r = 总偏差 + 剩余资金,最小化它意味着「权重尽量准 + 钱尽量花完」
• 求解器搜遍所有整数组合找最小,精确但慢

⚠️ ECOS_BB 的已知问题:lp_portfolio 默认用 ECOS_BB 求解器,但官方警告它有正确性问题。备选方案是 GLPK_MI(随 cvxopt 发布)。用法:da.lp_portfolio(solver="GLPK_MI")。1.7.0 版起默认 solver 会改为 None(cvxpy 自动选)。

三、greedy vs lp 的精度与速度

文档里的实测对比(同一组合):

greedy:  Funds remaining: $12.15, RMSE: 0.038
lp:      Funds remaining: $0.42,  RMSE: 0.018
​

💡 选择策略:数据探索、回测、大规模组合 → greedy;最终下单、小额组合、需要严格对账 → lp。

四、做空处理:short_ratio 与 reinvest

当 weights 里有负值(做空),DiscreteAllocation 自动把组合拆成多头和空头两部分,分别做离散分配:

if self.weights[-1][1] < 0:
    longs = {t: w for t, w in self.weights if w >= 0}
    shorts = {t: -w for t, w in self.weights if w < 0}
    # 各自归一化
    longs = {t: w / sum(longs.values()) for t, w in longs.items()}
    shorts = {t: w / sum(shorts.values()) for t, w in shorts.items()}

    short_val = self.total_portfolio_value * self.short_ratio
    long_val = self.total_portfolio_value
    if reinvest:
        long_val += short_val

    # 分别 greedy/lp
    da1 = DiscreteAllocation(longs, ..., total_portfolio_value=long_val)
    da2 = DiscreteAllocation(shorts, ..., total_portfolio_value=short_val)
    long_alloc, long_leftover = da1.greedy_portfolio()
    short_alloc, short_leftover = da2.greedy_portfolio()
    short_alloc = {t: -w for t, w in short_alloc.items()}
    # 合并返回
​

两个关键参数:

short_ratio:做空比例

默认 None 时自动等于「负权重绝对值之和」;手动设 short_ratio=0.3 对应经典的 130/30 策略——做多 $1.3、做空 $0.3,净敞口 $1。

💡 130/30 的金融含义:总风险敞口 = 多头 130% + 空头 30% = 160%,但净持仓 = 多 - 空 = 100%。这是对冲基金常见结构,既放大收益又控制净曝光。

reinvest:是否把做空所得再投入多头

short_val = self.total_portfolio_value * self.short_ratio   # 做空借到的钱
long_val = self.total_portfolio_value
if reinvest:
    long_val += short_val    # 把空头收入加到多头
​

reinvest=False(默认)时,多头只占 total_portfolio_value,空头单独用 short_val;reinvest=True 时,空头借到的钱再加到多头,实际净持仓为多 T + 空的金额。

五、verbose 输出与 RMSE

两个算法都支持 verbose=True 打印详细分析:

allocation, leftover = da.greedy_portfolio(verbose=True)
​

输出形如:

MA: allocated 0.242, desired 0.246
FB: allocated 0.200, desired 0.199
...
AMZN: allocated 0.000, desired 0.072
Allocation has RMSE: 0.038
Funds remaining: $12.15
​

源码 _allocation_rmse_error 计算每个资产的偏差平方均值:

def _allocation_rmse_error(self, verbose=True):
    portfolio_val = sum(num * self.latest_prices[t] for ticker, num in ...)
    sse = 0
    for ticker, weight in self.weights:
        allocation_weight = (
            self.allocation[ticker] * self.latest_prices[ticker] / portfolio_val
        ) if ticker in self.allocation else 0
        sse += (weight - allocation_weight) ** 2
        if verbose:
            print(f"{ticker}: allocated {allocation_weight:.3f}, desired {weight:.3f}")
    rmse = np.sqrt(sse / len(self.weights))
    print(f"Allocation has RMSE: {rmse:.3f}")
    return rmse
​

💡 为什么用 RMSE 不用 MAE:RMSE 对大偏差更敏感(平方惩罚),能让「某个资产严重偏离」的情况被放大暴露,这是离散分配里最该警惕的失败模式。

六、完整示例对比

da_greedy = DiscreteAllocation(weights, latest_prices, total_portfolio_value=20000)
da_lp = DiscreteAllocation(weights, latest_prices, total_portfolio_value=20000)

g_alloc, g_left = da_greedy.greedy_portfolio(verbose=True)
l_alloc, l_left = da_lp.lp_portfolio(verbose=True)

print(f"Greedy: leftover ${g_left:.2f}")
print(f"LP:     leftover ${l_left:.2f}")
​

本节要点回顾

1. 贪婪法两轮:第一轮按权重向下取整买足;第二轮挑「实际权重 vs 目标偏差最大」的资产逐股补,直到买不起。
2. 整数 LP 目标:min Σ|w_i·T - x_i·p_i| + r,即「权重 USD 偏差 + 剩余」,在整数约束下精确求解。
3. ECOS_BB 警告:默认 solver 有正确性问题,可手动切 GLPK_MI;1.7.0 起默认改为 None。
4. 做空拆分:负权重自动拆多空两份,各自离散化;short_ratio=0.3 对应 130/30;reinvest=True 把空头收入加到多头。
5. 选择策略:大规模/快迭代用 greedy,小规模/严格对账用 lp;两者 RMSE 差通常 2 倍,速度差 100~1000 倍。
6. RMSE 衡量:对大偏差平方惩罚,适合暴露「单资产严重偏离」的失败模式,verbose 会逐 ticker 打印。

下一节,我们看配套的 get_latest_prices 工具函数,以及离散分配的最终输出怎么用。