第 15b 章 动态规划（下）：量化交易中的动态规划

上篇讲了动态规划的方法论和四个经典问题。本篇把同一套方法用到交易问题上：最多 \(k\) 次买卖的最大收益、带交易成本的最优交易路径、最优执行的离散化动态规划，以及隐马尔可夫模型的 Viterbi 解码。它们的共同点是：决策随时间展开，今天的决策会改变明天的状态（持仓、剩余仓位），而目标是整条路径上的总收益或总成本。这正是动态规划的主场。本篇的模型与代码是为说明方法而设计的程式化版本，不是原书内容；原书中对应的思考题会在相应位置注明。

学习目标

1. 能把一个多期交易问题写成"阶段、状态、决策、转移、阶段收益"五要素，并写出 Bellman 递归式。
2. 掌握"最多 \(k\) 次买卖"问题的 \(O(nk)\) 状态机 DP，理解交易费用和次数上限如何进入状态。
3. 理解交易成本使最优策略出现无交易区间，并会用带马尔可夫信号的随机 DP 求出最优调仓策略。
4. 会把最优执行问题离散化为"剩余仓位 × 时段"的 DP，验证它与 Almgren–Chriss 型闭式解一致，并处理闭式解无法处理的成交量形态、参与率上限、非线性冲击。
5. 会用 Viterbi 算法从收益序列中解码市场状态。
6. 能判断什么时候 DP 会失效（共享资源约束、状态维数爆炸），以及常见的补救方式。

读前导读

这一章在解决什么问题。 很多交易决策不是一次性的，而是一连串：今天调了仓，明天就要从新的持仓出发；上午卖得多，下午要卖的就少。这类问题的难点在于"今天的最优"不一定是"整条路径的最优"。动态规划（DP）的做法是：从最后一期往回算，每一期都问"如果我站在这个状态上，从这里到结束最好能做到多少"，把答案记在一张表里，前一期直接查表。你在 CFA 里用二叉树给美式期权定价时，从到期日往回推、在每个结点比较"继续持有"和"立即行权"，就已经在做动态规划了；本章把同一个思路用到择时上界、带成本调仓、最优执行和市场状态识别四个问题上。

本章的核心句子只有一个：值函数 = 本期收益 + 下一期值函数（的期望），在所有可选决策里取最好。 这就是 Bellman 方程。后面每一节只是换了"状态是什么、决策是什么、本期收益怎么算"。

需要先想起来的数学。

• max/argmax 与递归记号。 \(\max_u\{\cdots\}\) 是"在所有可选的 \(u\) 里取花括号内的最大值"，\(\arg\max\) 是"取到最大值的那个 \(u\) 本身"。\(V_t(x)\) 读作"第 \(t\) 期、处在状态 \(x\) 时，从现在到结束能拿到的最优总收益"。例：明天两个选项收益分别为 3 和 5，则 \(\max=5\)，\(\arg\max\) 是第二个选项。
• 条件期望与马尔可夫链。 \(E[V_{t+1}]\) 是"按下一期各种可能状态的概率加权平均"。若信号明天以 0.7 概率保持"强"、0.3 概率变"弱"，两种状态下的未来价值分别是 10 和 4，则期望价值 \(=0.7\times10+0.3\times4=8.2\)。转移矩阵 \(P\) 的第 \(s\) 行就是"今天在状态 \(s\) 时，明天去各个状态的概率"，每行加起来等于 1。见 第 00 册第 07 章 概率中的分析工具。
• 对一个变量求导令其为零。 最优执行的闭式解来自"对每个 \(x_k\) 求偏导数、令其为零"，这与你求最小方差组合时对权重求导是同一个动作。见 第 00 册第 02 章 导数与泰勒展开 和 第 00 册第 05 章 多元微积分与优化。
• 指数、对数与双曲函数。 \(\sinh x=(e^x-e^{-x})/2\)，\(\cosh x=(e^x+e^{-x})/2\)，只是两个由指数函数拼成的函数；\(x\) 很小时 \(\sinh x\approx x\)、\(\cosh x\approx1+x^2/2\)。Viterbi 中取对数，是因为很多小概率连乘会小到计算机存不下，而 \(\log(ab)=\log a+\log b\) 把乘法变成加法。见 第 00 册第 04 章 级数与收敛。
• 大 O 记号。 \(O(nk)\) 表示"运算次数大致与 \(n\times k\) 成正比"，常数倍不计较。见第 07 章同一册。

怎么读这一章。 15b.1 是必读，五要素表格要能用自己的话复述。15b.2 是最干净的 DP 例子，建议用纸笔把 \(p=[3,2,6,5,0,3]\) 的前几天手算一遍。15b.3 和 15b.4 是与实务最相关的两节，第一次读可以先看"读结果"再回头看模型；15b.4 中的差分方程和 \(\sinh\) 闭式解可以只记结论（"风险厌恶越强，卖得越前置"）。15b.5 Viterbi 只需理解"格子图上的最长路径"和最后一段关于前视偏差的提醒。代码块第一次可以跳过，只读输出和"读结果"。

15b.1 从原书到交易：五要素与 Bellman 方程

原书第 15 章的问题都可以抽象成：在一系列阶段上做选择，每个选择带来一个直接代价，并把问题带到一个更小的子问题。交易问题的子问题天然按时间排列：

最优值函数满足 Bellman 方程（有限期、可能带随机性）：

白话解释：把 Bellman 方程逐项读一遍。\(V_t(x)\)：站在第 \(t\) 期、手里状态是 \(x\)，从现在到结束最多能赚多少。\(g_t(x,u)\)：今天选 \(u\) 立刻拿到的收益（可以是负的，比如交易成本）。\(f(x,u,\xi_t)\)：今天选了 \(u\) 之后明天的状态，\(\xi_t\) 是今天无法控制的随机因素（比如信号明天怎么变）。\(E[\cdot]\)：对这个随机因素取平均。整句话是："今天的最优价值 = 在所有选择里，挑'今天到手的 + 明天起最优价值的期望'最大的那个。" 为什么要从 \(T\) 往回算？因为算 \(V_t\) 必须先知道 \(V_{t+1}\)，而最后一期 \(V_T\) 是题目直接给定的（例如"收盘前必须卖完"）。这与债券定价从到期日现金流往回贴现、二叉树期权从到期支付往回推完全一样。

状态设计是建模的核心。 状态必须包含"做后续决策所需的全部历史信息"（马尔可夫性），否则最优子结构不成立；但状态又不能太大，否则子问题数爆炸。上篇 15.4.2 节讲的"共享资源破坏最优子结构"，在交易中的标准解法就是把资源放进状态：交易次数上限 → 状态里记已用次数；执行剩余量 → 状态里记剩余仓位。原书思考题 15-11（库存规划）的状态"月份 × 月末库存"与最优执行的"时段 × 剩余仓位"是同一个结构；思考题 15-10（投资策略规划）的状态"第 \(j\) 年持有投资 \(i\)"则与下文的带成本交易路径同构。

15b.2 最多 \(k\) 次买卖的最大收益

15b.2.1 问题与状态设计

给定一段价格 \(p_1,\dots,p_n\)（假设事后已知），只做多、任一时刻最多持有一份，最多完成 \(k\) 次"买入—卖出"，每次卖出支付费用 \(f\)。求最大总收益。

它有两个用途。其一是择时能力的上帝视角上界：任何择时策略在这段行情上的收益都不可能超过它，用它可以衡量一个策略"吃到了多少可得收益"。其二是方法示范：次数上限是一种共享资源，必须放进状态。

状态：第 \(t\) 天结束时，已经发生了 \(j\) 次买入，当前持仓或空仓。定义

• \(H_t[j]\)：至第 \(t\) 天、已买入 \(j\) 次且当前持仓时的最大收益（买入价已计为负现金流）；
• \(C_t[j]\)：至第 \(t\) 天、已完成 \(j\) 次交易且当前空仓时的最大收益。

转移（第 \(t\) 天的决策只有"不动/买入/卖出"）：

推导拆解：用 \(p=[3,2,6]\)、\(k=1\)、\(f=0\) 手算一遍。 第 1 天（\(p=3\)）：\(H_1[1]=\max(-\infty,\ C_0[0]-3)=-3\)（买入，现金 \(-3\)）；\(C_1[0]=0\)（什么都不做）。 第 2 天（\(p=2\)）：\(H_2[1]=\max(-3,\ 0-2)=-2\)，说明"今天买比昨天买更好"；\(C_2[1]=\max(-\infty,\ H_1[1]+2)=-1\)（昨天买今天卖，亏 1）。 第 3 天（\(p=6\)）：\(C_3[1]=\max(-1,\ H_2[1]+6)=4\)。答案 \(\max_jC_3[j]=4\)，即第 2 天以 2 买、第 3 天以 6 卖。 每一格只看"昨天的两种状态 + 今天的价格"，这就是"每个状态 \(O(1)\) 次比较"的意思。初值设为 \(-\infty\) 是记账技巧：表示"这个状态还不可能到达"，任何真实的数都比它大，所以不会被 \(\max\) 选中。

最优子结构（剪切—粘贴）：若某条最优路径在第 \(t\) 天处于状态 \((j,\text{持仓})\)，则它前 \(t\) 天的部分必须是到达这个状态的最优路径；否则换成更好的前缀，后半段不受影响（后半段只依赖状态），整体更优，矛盾。之所以"后半段不受影响"，正是因为状态里已经记录了剩余的交易次数——这就是把共享资源放进状态的作用。

复杂度：\(n\) 天 × \((k+1)\) 个 \(j\) × 2 种持仓状态，每个状态 \(O(1)\) 次比较，共 \(O(nk)\) 时间。若只要最优值，只需保留上一天的两个长度为 \(k+1\) 的数组，空间 \(O(k)\)；要回溯买卖点，就像钢条切割的 \(s\) 表一样记录每天每个状态的选择。

与贪心的联系：当 \(k\ge n/2\) 且 \(f=0\) 时次数约束不起作用，最优收益就是所有上涨段之和 \(\sum_t\max(p_{t+1}-p_t,0)\)——此时贪心就够了。这是下一章"贪心何时足够"的一个具体例子；一旦有了次数上限或费用，局部最优（抓住每一段上涨）就不再是全局最优。

15b.2.2 代码

import numpy as np
from itertools import combinations

def max_profit_k(p, k, fee=0.0):
    """至多 k 次（买入→卖出）交易的最大收益。状态：已完成 j 次买入后 持仓/空仓 的最优值。O(nk)。"""
    NEG = -np.inf
    hold = np.full(k + 1, NEG)            # hold[j]：已买入 j 次、当前持仓
    cash = np.full(k + 1, NEG); cash[0] = 0.0   # cash[j]：已完成 j 次交易、当前空仓
    choice = []                           # 记录每天的最优决策，用于回溯
    for t, x in enumerate(p):
        buy  = np.r_[NEG, cash[:-1] - x]         # 第 j 次买入：从 cash[j-1] 转来
        sell = hold + x - fee                    # 卖出：hold[j] → cash[j]
        new_hold = np.maximum(hold, buy); new_cash = np.maximum(cash, sell)
        choice.append((buy > hold, sell > cash))
        hold, cash = new_hold, new_cash
    j = int(np.argmax(cash)); best = float(cash[j])
    trades, state = [], "cash"                   # 回溯：从最后一天往前找决策点
    for t in range(len(p) - 1, -1, -1):
        bmask, smask = choice[t]
        if state == "cash" and smask[j]: trades.append(("卖", t)); state = "hold"
        elif state == "hold" and bmask[j]: trades.append(("买", t)); state = "cash"; j -= 1
    return best, trades[::-1]

def brute(p, k, fee=0.0):                        # 枚举所有 i1<i2<...<i2j 的买卖点
    best = 0.0
    for j in range(1, k + 1):
        for idx in combinations(range(len(p)), 2 * j):
            v = sum(p[idx[2*i+1]] - p[idx[2*i]] - fee for i in range(j))
            best = max(best, v)
    return best

rng = np.random.default_rng(3)
ok = True
for trial in range(200):
    p = np.round(10 + np.cumsum(rng.normal(0, 0.3, 12)), 2)
    k, fee = int(rng.integers(1, 4)), float(rng.choice([0, 0.05, 0.2]))
    ok &= abs(max_profit_k(p, k, fee)[0] - brute(p, k, fee)) < 1e-9
print("200 个随机小样本与暴力枚举一致:", ok)

p = np.array([3, 2, 6, 5, 0, 3], float)
print("示例 p=[3,2,6,5,0,3], k=2:", max_profit_k(p, 2))

# 一年的日线：可实现收益的"上帝视角"上界随 k 和费用的变化
p = 100 * np.exp(np.cumsum(rng.normal(0.0003, 0.015, 250)))
greedy = np.sum(np.maximum(np.diff(p), 0))       # k ≥ n/2 且无费用时 = 所有上涨段之和
print(f"\n无费用、不限次数的上界(贪心) = {greedy:.2f}")
for fee in [0.0, 0.3]:
    row = []
    for k in [1, 2, 5, 20, 125]:
        v, tr = max_profit_k(p, k, fee); row.append(f"k={k}:{v:7.2f}({len(tr)//2}笔)")
    print(f"每笔费用 {fee}: " + "  ".join(row))

运行输出：

200 个随机小样本与暴力枚举一致: True
示例 p=[3,2,6,5,0,3], k=2: (7.0, [('买', 1), ('卖', 2), ('买', 4), ('卖', 5)])

无费用、不限次数的上界(贪心) = 148.89
每笔费用 0.0: k=1:  17.16(1笔)  k=2:  28.30(2笔)  k=5:  51.51(5笔)  k=20: 106.14(20笔)  k=125: 148.89(67笔)
每笔费用 0.3: k=1:  16.86(1笔)  k=2:  27.70(2笔)  k=5:  50.01(5笔)  k=20: 100.14(20笔)  k=125: 130.27(57笔)

读结果。 小样本上 DP 与暴力枚举完全一致。示例中第 1 天买（价格 2）、第 2 天卖（6）、第 4 天买（0）、第 5 天卖（3），共赚 7。在一年 250 个交易日上，不限次数、无费用的上界是 148.89，需要 67 笔交易，正好等于贪心算出的"所有上涨段之和"；只允许 1 笔时上界只有 17.16。加上每笔 0.3 的费用后，最优方案主动放弃了 10 笔"上涨幅度不够覆盖费用"的交易（67 笔→57 笔）。

这张表可以这样用：若一个择时策略在这段行情上赚了 20，而它一年交易约 20 次，那么它只拿到了同交易次数下上帝视角收益（约 100）的五分之一。当然，上帝视角上界只是标尺，不是可达目标。

15b.3 带交易成本的最优交易路径

15b.3.1 模型

现在换成更现实的设定：每天有一个预期收益信号 \(\mu_t\)（来自因子模型或时间序列模型），它随时间演化；仓位 \(q_t\) 可以做多做空，取值于网格 \(\{-10,\dots,10\}\) 手；每次调仓支付比例成本 \(c|q_t-q_{t-1}|\)；持仓有风险惩罚 \(\gamma q_t^2\)（均值—方差的二次惩罚）。目标是最大化

如果没有交易成本，每期可以单独优化，\(q_t^*=\mu_t/(2\gamma)\)——"信号多强就持多少仓"。有了交易成本，今天的仓位会影响明天要付的成本，各期就耦合起来了。

推导拆解：无成本时每期目标是 \(q\mu-\gamma q^2\)，这是一个开口向下的抛物线。对 \(q\) 求导：\(\mu-2\gamma q=0\)，得 \(q^*=\mu/(2\gamma)\)。这和均值—方差效用 \(E[r]-\tfrac{\lambda}{2}\sigma^2\) 下"最优风险资产权重 \(=\) 超额收益 \(/(\lambda\sigma^2)\)"是同一个结构：收益线性、风险二次，最优点就是两者边际相等处。 加入 \(c|q_t-q_{t-1}|\) 后，第 \(t\) 期的目标里出现了 \(q_{t-1}\)，第 \(t+1\) 期的目标里又出现了 \(q_t\)，各期像链条一样扣在一起，不能再各算各的，这正是需要 DP 的原因。

信号的状态化。 设 \(\mu_t\) 服从 AR(1)：\(\mu_{t+1}=\phi\mu_t+\varepsilon_t\)。把它离散化为 \(S\) 个状态的马尔可夫链（Tauchen 方法：转移概率按正态分布在网格区间上的积分计算），转移矩阵为 \(P\)。于是状态是 (上期仓位 \(q\), 信号状态 \(s\))，决策是新仓位 \(q'\)：

白话解释：AR(1) 的意思是"明天的信号 = \(\phi\) 倍的今天信号 + 一个新冲击"，\(\phi=0.9\) 表示信号很持久。计算机处理不了连续取值，于是把信号可能的取值切成 15 档（\(s=1,\dots,15\)），再算出"今天在第 \(i\) 档、明天落到第 \(j\) 档"的概率 \(P(s_i,s_j)\)，这就是 Tauchen 方法：用正态分布在每一档区间上的概率面积来填转移矩阵。 状态为什么是 (上期仓位, 信号档位) 两样？因为要决定今天的新仓位，你必须知道"从哪里调过来"（决定交易成本）和"信号现在多强"（决定预期收益），缺一样都做不了决策；而更早的历史对未来没有额外影响——这就是"状态包含全部必要信息"的具体含义。 \(\sum_{s'}P(s,s')V_{t+1}(q',s')\) 是"明天信号落在各档的概率 × 那一档的未来价值"再加总，也就是明天的期望价值。

这里的求和就是 Bellman 方程中的期望。子问题数为 \(T\times|Q|\times S\)，每个子问题有 \(|Q|\) 种选择、期望计算 \(O(S)\)，总时间 \(O(T|Q|^2S+T|Q|S^2)\)，在 numpy 中把整个时间切片向量化即可。

（若信号路径事先完全已知，问题退化为一张"时间 × 仓位"格子图上的最长路径，就是原书思考题 15-1 的 DAG 最长路径，也和 Viterbi 算法同构。）

15b.3.2 代码：DP 策略与两种短视策略的对比

import numpy as np
from scipy.stats import norm

# 信号：下一期预期收益 μ_t 服从 AR(1)，离散化为 S 个状态的马尔可夫链
phi, sig_mu, S = 0.9, 0.0005, 15
sd = sig_mu / np.sqrt(1 - phi**2)
grid = np.linspace(-3 * sd, 3 * sd, S); h = grid[1] - grid[0]
P = np.empty((S, S))                                  # 简单的 Tauchen 离散化
for i in range(S):
    cdf = norm.cdf((grid + h / 2 - phi * grid[i]) / sig_mu)
    P[i] = np.diff(np.r_[0, cdf[:-1], 1])

Q = np.arange(-10, 11)                                # 仓位网格：-10..10 手
gamma, c, T = 1.25e-4, 0.001, 250                     # 风险惩罚 γq²、单位换仓成本 c|Δq|

def solve_policy(c):
    """逆向归纳：V_t(q, s) = max_{q'} [ q'μ(s) − γq'² − c|q'−q| + Σ P(s,s') V_{t+1}(q', s') ]"""
    V = np.zeros((len(Q), S)); pol = np.empty((T, len(Q), S), dtype=int)
    stage = np.outer(Q, grid) - gamma * Q[:, None]**2            # 选定 q' 后本期的期望收益 (q', s)
    cost = c * np.abs(Q[None, :] - Q[:, None])                   # (q, q')
    for t in range(T - 1, -1, -1):
        cont = stage + V @ P.T                                    # (q', s)：本期 + 下期期望价值
        tot = cont[None, :, :] - cost[:, :, None]                 # (q, q', s)
        pol[t] = np.argmax(tot, axis=1); V = np.max(tot, axis=1)
    return pol

pol = solve_policy(c)
myopic_nc = np.argmax(np.outer(Q, grid) - gamma * Q[:, None]**2, axis=0)   # 忽略成本：q* = μ/(2γ)
def myopic_c(qi, s):                                   # 只看一期的"含成本"短视策略
    return int(np.argmax(Q * grid[s] - gamma * Q**2 - c * np.abs(Q - Q[qi])))

def simulate(rule, n_path=1000, seed=0):
    rng = np.random.default_rng(seed)                     # 各策略用同一组随机数（公共随机数），便于比较
    res = []
    for _ in range(n_path):
        s, qi, pnl, turn, pen = S // 2, 10, 0.0, 0, 0.0
        for t in range(T):
            nq = rule(t, qi, s)
            turn += abs(Q[nq] - Q[qi]); pnl -= c * abs(Q[nq] - Q[qi])
            r = grid[s] + rng.normal(0, 0.01)                    # 实现收益 = 预期 + 噪声
            pnl += Q[nq] * r; pen += gamma * Q[nq]**2; qi = nq
            s = rng.choice(S, p=P[s])
        res.append((pnl - pen, pnl, turn))
    return np.array(res)

rules = {"DP 最优策略": lambda t, qi, s: pol[t, qi, s],
         "短视·忽略成本": lambda t, qi, s: myopic_nc[s],
         "短视·计入一期成本": lambda t, qi, s: myopic_c(qi, s)}
for name, rule in rules.items():
    r = simulate(rule)
    print(f"{name:<10s} 目标值(净收益−γΣq²) {r[:, 0].mean():+.3f} (标准误 {r[:, 0].std() / np.sqrt(len(r)):.3f})"
          f" | 净收益 {r[:, 1].mean():+.3f} | 年换手 {r[:, 2].mean():6.1f} 手")

# 无交易区间：t=100 时，对每个信号状态，哪些起始仓位会"按兵不动"
t = 100
for s in [4, 7, 10]:
    stay = [int(Q[qi]) for qi in range(len(Q)) if pol[t, qi, s] == qi]
    print(f"信号 μ={grid[s]*1e4:+.1f}bp: 无成本目标仓位 {int(Q[myopic_nc[s]]):+d}，DP 不交易区间 [{min(stay):+d}, {max(stay):+d}]")

运行输出：

DP 最优策略    目标值(净收益−γΣq²) +0.466 (标准误 0.021) | 净收益 +0.937 | 年换手  139.4 手
短视·忽略成本    目标值(净收益−γΣq²) +0.291 (标准误 0.025) | 净收益 +0.971 | 年换手  386.8 手
短视·计入一期成本  目标值(净收益−γΣq²) +0.394 (标准误 0.020) | 净收益 +0.870 | 年换手   72.4 手
信号 μ=-14.7bp: 无成本目标仓位 -6，DP 不交易区间 [-7, -4]
信号 μ=-0.0bp: 无成本目标仓位 +0，DP 不交易区间 [-2, +2]
信号 μ=+14.7bp: 无成本目标仓位 +6，DP 不交易区间 [+4, +7]

15b.3.3 读结果

DP 策略的目标值最高（0.466，比次优策略高出约 3.5 个标准误），这是理论上必然的：它在模型内是最优的。值得细看的是两种短视策略为什么各输一半：

• "忽略成本"的策略每天都追着信号跑，年换手 387 手，未扣风险惩罚的净收益其实最高（0.971），但它承担了更大的平均仓位和交易成本，按目标函数算最差。这提醒我们：只看扣费后收益比较策略是不完整的，风险惩罚是目标的一部分。
• "计入一期成本"的策略把每次调仓成本都算在当期收益上，相当于假设新仓位只持有一天，于是严重低估了调仓的价值——信号的持续性 \(\phi=0.9\) 意味着今天建的仓位平均会被利用约 10 天。它换手太少（72 手），错失了信号。
• DP 策略的换手（139 手）介于两者之间：它通过 \(E[V_{t+1}]\) 把"新仓位在未来能带来的收益"正确地计入了决策。

最后三行展示了比例交易成本下最优策略的标志性结构——无交易区间（no-trade region）：信号为 \(+14.7\) bp 时，无成本的目标仓位是 \(+6\)，而 DP 的策略是"只要当前仓位在 \([+4,+7]\) 之间就不动，落在区间外才调整到区间边界附近"。这与连续时间比例成本组合选择理论中的结论一致：比例成本导致一个围绕无成本最优仓位的不交易带，带宽随成本增大而变宽。若成本是二次的（如线性冲击带来的成本），最优策略则变成"每期朝目标仓位走一部分"的平滑调整，这是多资产情形下常用的近似思路。

维数的诅咒。 这里只有一个资产、21 个仓位、15 个信号状态。\(m\) 个资产时状态数是 \(21^m\times15^m\)，精确 DP 立刻不可行。实际的多资产再平衡通常采用：二次成本下的闭式或半闭式解、逐资产分解的近似 DP、或者每期求解一个带成本项的单期优化（并把成本系数放大以近似未来摊销）——最后这个办法正是上面"短视·计入一期成本"的改良版：给成本乘一个小于 1 的系数，以反映仓位会被持有多期。

15b.4 最优执行的离散化动态规划

15b.4.1 模型与闭式解

要在一天内卖出 \(X\) 手，把一天分成 \(N\) 个时段。记 \(x_k\) 为第 \(k\) 个时段结束后剩余的仓位（\(x_0=X\)，\(x_N=0\)），\(n_k=x_{k-1}-x_k\) 为第 \(k\) 个时段卖出的量。两种力量相互拉扯：

• 卖得越急，冲击成本越高。线性临时冲击下每时段成本为 \(a\,n_k^2\)（每手冲击 \(\propto n_k\)，乘以 \(n_k\) 手）；
• 卖得越慢，剩余仓位暴露在价格波动中的时间越长，风险越大。用方差惩罚 \(b\,x_k^2\) 表示（\(b=\lambda\sigma^2\tau\)，\(\lambda\) 为风险厌恶系数）。

目标是最小化 \(\sum_{k=1}^N\big(a\,n_k^2+b\,x_k^2\big)\)。这就是 Almgren–Chriss 框架的离散形式（线性永久冲击带来的成本与路径无关，这里省略）。

闭式解。 对 \(x_k\)（\(1\le k\le N-1\)）求导令其为零：

推导拆解： 第一步，找 \(x_k\) 出现在哪里。\(x_k\) 同时出现在三项里：第 \(k\) 期的卖出量 \(n_k=x_{k-1}-x_k\)、第 \(k+1\) 期的卖出量 \(n_{k+1}=x_k-x_{k+1}\)、以及风险项 \(b\,x_k^2\)。其他项与 \(x_k\) 无关，求导时为 0。 第二步，逐项求导（链式法则）。\(\frac{\partial}{\partial x_k}a(x_{k-1}-x_k)^2=-2a(x_{k-1}-x_k)\)（内层对 \(x_k\) 求导得 \(-1\)）；\(\frac{\partial}{\partial x_k}a(x_k-x_{k+1})^2=2a(x_k-x_{k+1})\)；\(\frac{\partial}{\partial x_k}bx_k^2=2bx_k\)。三者相加令其为 0，就是原文第一个等式。 第三步，整理。两边除以 \(2a\)，把 \(x_{k+1},x_k,x_{k-1}\) 归到一起即得 \(x_{k+1}-2x_k+x_{k-1}=\frac ba x_k\)。左边是"二阶差分"，可以理解为剩余仓位曲线的"弯曲程度"：\(b=0\) 时弯曲为 0，曲线是直线（匀速卖）；\(b>0\) 时曲线向下弯，前面卖得快。 第四步，解方程。猜 \(x_k=e^{\pm\kappa k}\) 代入，得 \(e^{\kappa}+e^{-\kappa}-2=b/a\)，即 \(2(\cosh\kappa-1)=b/a\)。通解是 \(e^{\kappa k}\) 与 \(e^{-\kappa k}\) 的组合；用两个边界条件 \(x_0=X\)、\(x_N=0\) 定出系数，恰好凑成 \(\sinh\) 的形式。验证：\(k=0\) 时分子分母相同，\(x_0=X\)；\(k=N\) 时 \(\sinh 0=0\)，\(x_N=0\)。 这一套与"对每个资产权重求导、令其为零"求最优组合是同一类操作，只是这里变量按时间排成一列，每个变量只和左右邻居有关。

动态规划。 状态是"时段 \(k\) 开始时的剩余仓位 \(x\)"，决策是本时段卖出量 \(n\)：

DP 的价值不在于重算闭式解，而在于闭式解依赖的假设一旦被打破——冲击系数随时段变化、冲击非线性、有参与率上限、有最小交易单位——DP 照样能算，只要把这些写进阶段代价和可行决策集合。

15b.4.2 代码

import numpy as np

def exec_dp(X, N, a, b, cap=None, alpha=2.0):
    """卖出 X 手、分 N 期。第 k 期卖 n 手：冲击成本 a_k·n^alpha，之后持有 x 手的风险惩罚 b·x²。
    V_k(x) = min_{0<=n<=min(x,cap_k)} [ a_k n^alpha + b (x-n)^2 + V_{k+1}(x-n) ],  V_N(0)=0, V_N(x>0)=∞"""
    a = np.broadcast_to(np.asarray(a, float), (N,))
    cap = np.full(N, X) if cap is None else np.asarray(cap)
    xs = np.arange(X + 1)
    V = np.where(xs == 0, 0.0, np.inf); arg = np.zeros((N, X + 1), dtype=int)
    n = xs[None, :]; x = xs[:, None]                      # 矩阵 (x, n)
    for k in range(N - 1, -1, -1):
        rem = x - n
        feas = (n <= x) & (n <= cap[k])
        tot = np.where(feas, a[k] * n.astype(float)**alpha + b * rem.astype(float)**2
                       + V[np.clip(rem, 0, X)], np.inf)
        arg[k] = np.argmin(tot, axis=1); V = tot[xs, arg[k]]
    path, x0 = [X], X                                     # 正向回放最优路径
    for k in range(N):
        x0 -= arg[k, x0]; path.append(x0)
    return V[X], np.array(path)

# ---------- 1. 线性冲击 + 方差惩罚：DP 与 Almgren–Chriss 型闭式解对照 ----------
X, N = 400, 8                     # 卖 400 手（4 万股），一天 8 个半小时时段
eta, lam, sigma, tau = 2.5e-3, 1e-3, 0.6, 1.0        # 单位均为"每手"的抽象量纲
a, b = eta / tau, lam * sigma**2 * tau                # 每期成本 a n² + b x²
cost, path = exec_dp(X, N, a, b)
kappa = np.arccosh(1 + b / (2 * a))                   # 2(cosh κ − 1) = b/a
closed = X * np.sinh(kappa * (N - np.arange(N + 1))) / np.sinh(kappa * N)
print("DP 最优剩余仓位:", path.tolist())
print("闭式解 x_k     :", np.round(closed, 1).tolist())
print(f"κ = {kappa:.3f}；DP 目标值 {cost:.3f}；均匀卖出(TWAP)目标值 "
      f"{sum(a*50**2 + b*(X-50*(k+1))**2 for k in range(N)):.3f}")

# ---------- 2. 闭式解失效的情形：成交量 U 形 + 参与率上限 + 平方根冲击 ----------
vol = np.array([1.6, 1.1, 0.8, 0.7, 0.7, 0.8, 1.0, 1.3]); vol = vol / vol.mean() * 600   # 各时段市场成交量（手）
cap = np.floor(0.15 * vol).astype(int)                 # 参与率不超过 15%
a_k = 0.0016 / np.sqrt(vol)                             # 平方根律：每手冲击 ∝ sqrt(n / V_k)
print("\n各时段成交量:", np.round(vol).astype(int).tolist(), " 上限:", cap.tolist())
for b2 in [0.0, 3e-7]:                                   # 无风险厌恶 vs 适度风险厌恶
    cost2, path2 = exec_dp(X, N, a_k, b2, cap=cap, alpha=1.5)  # 总冲击成本 = n × 每手冲击 ∝ n^1.5 / sqrt(V_k)
    sell = -np.diff(path2)
    print(f"b={b2:g}: 各时段卖出 {sell.tolist()}  参与率 {np.round(sell / vol, 3).tolist()}")

运行输出：

DP 最优剩余仓位: [400, 273, 186, 126, 84, 54, 32, 15, 0]
闭式解 x_k     : [400.0, 273.6, 186.5, 126.3, 84.3, 54.5, 32.5, 15.1, 0.0]
κ = 0.377；DP 目标值 126.440；均匀卖出(TWAP)目标值 176.000

各时段成交量: [960, 660, 480, 420, 420, 480, 600, 780]  上限: [144, 99, 72, 63, 63, 72, 90, 117]
b=0: 各时段卖出 [80, 55, 40, 35, 35, 40, 50, 65]  参与率 [0.083, 0.083, 0.083, 0.083, 0.083, 0.083, 0.083, 0.083]
b=3e-07: 各时段卖出 [144, 79, 43, 30, 24, 23, 26, 31]  参与率 [0.15, 0.12, 0.09, 0.071, 0.057, 0.048, 0.043, 0.04]

15b.4.3 读结果

第一部分：DP 求出的整数路径与闭式解逐点相差不到 1 手（差异来自"手"的整数约束），验证了 DP 实现正确；\(\kappa=0.377\) 时第一个时段就卖出近三分之一，比匀速卖出前置得多，目标值比 TWAP 低约 28%。

第二部分展示了闭式解处理不了的情形：A 股日内成交量呈 U 形（开盘、收盘放量），冲击服从平方根律（每手冲击 \(\propto\sqrt{n_k/V_k}\)），并且有 15% 的参与率上限。

• 不厌恶风险（\(b=0\)）时，最优解恰好是 VWAP：每个时段的参与率都是 8.3%。这可以从一阶条件看出来：总冲击成本 \(c\,n_k^{3/2}/\sqrt{V_k}\) 的边际成本为 \(\tfrac32c\sqrt{n_k/V_k}\)，最优时各时段边际成本相等，于是 \(n_k/V_k\) 为常数。这给了"按成交量比例下单"一个清楚的最优性解释：在平方根冲击、无风险厌恶、无约束的假设下，VWAP 就是成本最低的执行方式。

推导拆解：为什么"最优时各时段边际成本相等"？这是总量固定下分配问题的通用结论。假如时段 1 多卖 1 手的边际成本是 0.05、时段 2 是 0.03，那么从时段 1 挪 1 手到时段 2，总卖出量不变，总成本下降 0.02。只要边际成本不等，就还能这样挪着省钱；挪不动了，就说明各时段边际成本相等。（严格写法是拉格朗日乘子，见 第 00 册第 05 章；乘子就是那个共同的边际成本。） 边际成本的求法：\(\frac{d}{dn}\big(c\,n^{3/2}V^{-1/2}\big)=\tfrac32c\,n^{1/2}V^{-1/2}=\tfrac32c\sqrt{n/V}\)。各时段相等，就是 \(\sqrt{n_k/V_k}\) 相等，平方后 \(n_k/V_k\) 相等，即参与率相同。 金融直觉：这与组合优化里"最优组合中每个资产的边际风险贡献与预期收益之比相等"是同一种逻辑。

• 适度厌恶风险时，执行向前倾斜，但仍随成交量起伏（收盘前参与率略有回升），第一个时段顶到了 15% 的上限。约束是否起作用、在哪里起作用，正是闭式解给不出、而 DP 自然处理的。

实务中的执行算法还要考虑价格的随机演化、盘口状态、限价单的成交概率等，状态会变成"剩余仓位 × 价差状态 × 队列位置 × ……"，DP 的状态空间迅速膨胀，常需近似 DP 或强化学习。冲击成本模型和执行算法的市场背景见第 07 册，综合实战见第 11 册。

15b.5 Viterbi 算法与市场状态识别

原书思考题 15-7 的 Viterbi 算法是隐马尔可夫模型（HMM）中求"最可能的隐藏状态路径"的动态规划。在量化里，隐藏状态常被解释为市场体制（regime）：平静/动荡、趋势/震荡。

设隐藏状态 \(z_t\in\{1,\dots,S\}\) 为马尔可夫链，转移概率 \(A_{ij}\)；观测 \(r_t\) 在状态 \(j\) 下的密度为 \(f_j(r_t)\)。定义 \(\delta_t(j)\) 为"在时刻 \(t\) 处于状态 \(j\) 的所有路径中，联合概率的最大对数值"，则

白话解释：一条状态路径（例如"平静、平静、动荡、动荡……"）的概率，是每一步"转移概率 × 在该状态下看到当天收益的可能性"连乘起来。Viterbi 想找出连乘结果最大的那条路径。路径总数是 \(S^T\)（两个状态、1500 天就是 \(2^{1500}\) 条），不可能一条条比。 关键观察：到第 \(t\) 天停在"动荡"的所有路径里，只有最好的那一条值得往后延伸，其余都可以扔掉——因为明天之后发生什么只取决于今天在哪个状态，不取决于怎么来的。于是每天只需为每个状态保留一个"冠军路径"的得分 \(\delta_t(j)\)，以及它的前一天是谁（用于最后回溯）。 取对数后连乘变连加，"概率最大"变成"对数和最大"，也就是格子图上的最长路径。举个数量级：1500 个 0.6 连乘约为 \(10^{-333}\)，已经低于双精度浮点能表示的最小正数（约 \(10^{-308}\) 到 \(10^{-324}\)），计算机会直接记成 0；取对数后只是 \(1500\times\ln0.6\approx-766\)，完全没有问题。

最优子结构在这里非常直观：到达 \((t,j)\) 的最优路径，其前缀一定是到达 \((t-1,i^*)\) 的最优路径——马尔可夫性保证了未来只依赖当前状态，不依赖怎么到达的。

import numpy as np
from scipy.stats import norm
rng = np.random.default_rng(5)

# 两状态市场：0=平静（低波动、正漂移），1=动荡（高波动、负漂移）
A = np.array([[0.98, 0.02], [0.05, 0.95]])           # 状态转移概率
mu, sd, pi0 = np.array([0.0005, -0.001]), np.array([0.008, 0.025]), np.array([0.5, 0.5])
T = 1500; z = np.empty(T, int); z[0] = 0
for t in range(1, T): z[t] = rng.choice(2, p=A[z[t-1]])
r = rng.normal(mu[z], sd[z])

def viterbi(r, A, mu, sd, pi0):
    """δ_t(j) = max_i [δ_{t-1}(i) + log A_ij] + log f_j(r_t)；对数空间避免下溢。O(T·S²)"""
    logA, logB = np.log(A), norm.logpdf(r[:, None], mu, sd)   # logB: (T, S)
    delta = np.log(pi0) + logB[0]; back = np.zeros((len(r), len(pi0)), int)
    for t in range(1, len(r)):
        cand = delta[:, None] + logA                   # (i, j)
        back[t] = np.argmax(cand, axis=0); delta = cand[back[t], range(len(pi0))] + logB[t]
    path = np.empty(len(r), int); path[-1] = int(np.argmax(delta))
    for t in range(len(r) - 1, 0, -1): path[t-1] = back[t, path[t]]
    return path

zh = viterbi(r, A, mu, sd, pi0)
roll = np.array([r[max(0, t-19):t+1].std() for t in range(T)])
naive = (roll > (sd[0] + sd[1]) / 2).astype(int)     # 对照：20 日滚动波动率超过阈值就判为动荡
print(f"Viterbi 状态识别准确率 {np.mean(zh == z):.3f}，状态切换次数 {np.sum(np.diff(zh) != 0)}（真实 {np.sum(np.diff(z) != 0)}）")
print(f"滚动波动率阈值法准确率 {np.mean(naive == z):.3f}，状态切换次数 {np.sum(np.diff(naive) != 0)}")

运行输出：

Viterbi 状态识别准确率 0.944，状态切换次数 35（真实 47）
滚动波动率阈值法准确率 0.779，状态切换次数 39

Viterbi 的准确率（94.4%）明显高于"20 日滚动波动率超过阈值"的直观做法（77.9%）。原因有二：Viterbi 同时利用了每个观测的似然和状态的持续性（转移矩阵的对角元很大），而滚动窗口天然滞后约半个窗口长度。它识别出的切换次数少于真实值，说明一些很短的状态片段被"平滑"掉了——这是最大化整条路径概率的代价，也往往正是实务中想要的（避免信号频繁翻转）。

需要注意两点。第一，这里假定模型参数已知；实际中参数要用 Baum–Welch（EM）算法估计，马尔可夫区制转换模型的估计见第 06 册。第二，Viterbi 用了整段样本（包括未来的观测）来决定每个时刻的状态，属于"平滑"而非"滤波"；回测中若用 Viterbi 路径作为交易信号，就引入了前视偏差。实时使用时应改用前向算法给出的滤波概率 \(P(z_t\mid r_1,\dots,r_t)\)。

金融直觉："平滑"与"滤波"的区别，类似于"用全年报表回头判断某季度是否处于衰退"与"季度末当时能做出的判断"。前者更准，但在当时拿不到。\(P(z_t\mid r_1,\dots,r_t)\) 中竖线右边只有到 \(t\) 为止的数据，读作"已知截至今天的收益，今天处于状态 \(z_t\) 的概率"，这才是回测里允许使用的信息集。

15b.6 动态规划何时失效，以及其他应用

共享资源破坏最优子结构。 原书给了三个例子：钢条数量有上限（习题 15.3-5）、兑换佣金随次数变化（习题 15.3-6）、单一投资金额有上限（思考题 15-10(d)）。交易中的对应物是：组合层面的总换手约束、行业暴露约束、杠杆上限。补救办法有两种：把资源放进状态（如本篇的交易次数 \(j\)、剩余仓位 \(x\)），代价是状态数乘上资源的取值个数；或者放弃 DP，改用数学规划（第 04 册）。

维数的诅咒。 状态是多维时，状态数呈指数增长。常见对策：利用结构得到闭式解（线性—二次问题）；对状态做粗粒度离散；近似值函数（近似动态规划、强化学习）；只在少数关键维度上做 DP。

其他常见的量化 DP：

• 美式期权的二叉树定价：在每个结点取"继续持有的价值"与"立即行权的价值"的较大者，从到期日往回推——典型的自底向上 DP，见第 08 册。
• 最优分段与变点检测：把一段序列切成若干段，使"段内代价之和 + 每段惩罚"最小，递归式为 \(F(t)=\min_{s<t}\{F(s)+\text{cost}(s+1..t)+\beta\}\)，与原书整齐打印（思考题 15-4）同构，\(O(n^2)\)。
• 货币兑换与三角套利：取对数后变成图上的最短路径，套利机会就是负权环（本册第 24 章）。
• 形态匹配：编辑距离、DTW 的二维表 DP（原书思考题 15-5）。

本章小结

量化交易里的很多决策问题都可以写成"阶段—状态—决策—转移—阶段收益"的动态规划。状态设计是关键：它必须包含后续决策所需的全部信息，共享资源（交易次数、剩余仓位）要放进状态才能保住最优子结构；状态维数又决定了计算是否可行。最多 \(k\) 次买卖是 \(O(nk)\) 的状态机 DP，给出择时收益的上帝视角上界；带比例交易成本的最优交易路径会出现无交易区间，DP 策略在模型内严格优于两种短视策略；最优执行的离散 DP 在线性—二次情形下复现 Almgren–Chriss 型的 \(\sinh\) 闭式解，并能处理成交量形态、平方根冲击和参与率上限——在平方根冲击且不厌恶风险时，最优解恰为 VWAP；Viterbi 算法是格子图上的最长路径，可用于市场体制识别，但用于回测时要警惕前视偏差。

练习

基础

1. 手算 \(p=[3,3,5,0,0,3,1,4]\) 在 \(k=2\)、无费用时的最大收益和买卖点。（答案：6，最优方案不唯一。按 0 起下标，可以第 3 天以 0 买、第 5 天以 3 卖，再第 6 天以 1 买、第 7 天以 4 卖；也可以第 0 天以 3 买、第 2 天以 5 卖，再第 3 天以 0 买、第 7 天以 4 卖。）
2. 证明：当 \(k\ge\lfloor n/2\rfloor\) 且 \(f=0\) 时，最多 \(k\) 次买卖的最大收益等于 \(\sum_t\max(p_{t+1}-p_t,0)\)。
3. 修改 max_profit_k，允许做空（同样最多 \(k\) 次开平仓）。状态需要怎样扩充？
4. 在最优执行模型中令 \(b\to0\)，证明闭式解退化为匀速卖出。
5. 在 Viterbi 的代码中把转移矩阵改为 \(\begin{pmatrix}0.8&0.2\\0.2&0.8\end{pmatrix}\)（状态持续性变弱），准确率会怎样变化？为什么？

进阶

6. 在带成本交易路径的代码中，把成本 \(c\) 依次取 0、0.0005、0.001、0.002，画出信号为 \(+14.7\) bp 时的不交易区间宽度与 \(c\) 的关系。
7. 把交易成本从比例成本 \(c|\Delta q|\) 换成二次成本 \(c(\Delta q)^2\)，重新运行 DP。最优策略的形态有什么变化？（提示：不再有严格的不交易区间，而是向目标仓位"部分调整"。）
8. 在最优执行 DP 中加入"每个时段最少成交 1 手或不成交"的最小交易单位约束和"必须在第 6 个时段前完成 80%"的进度约束，各需要怎样改动？
9. 推导：平方根冲击、无风险厌恶、无约束时，最优执行的参与率在各时段相等。若冲击是线性的（每手冲击 \(\propto n_k/V_k\)），最优的 \(n_k\) 与 \(V_k\) 是什么关系？
10. 原书思考题 15-10：写出投资策略规划的 DP，说明为什么加入"单一投资不超过 15000 美元"的约束后最优子结构不再成立；再试着把"当前持有金额"离散化后放进状态，恢复 DP。
11. 用最优分段 DP（\(F(t)=\min_{s<t}\{F(s)+\text{cost}(s+1..t)+\beta\}\)，段内代价取负对数似然）在 Viterbi 例子的模拟数据上识别波动率变点，与 Viterbi 的结果比较。

原书推荐习题：15.1-3、15.3-5、15.3-6，思考题 15-1、15-4、15-7、15-10、15-11、15-12。

原书对照

本篇的模型与代码是编写者为量化场景设计的程式化示例，依托的原书内容如下：