高维风险平价组合的快速算法
Théophile Griveau-Billion · Jean-Charles Richard · Thierry Roncalli — Lyxor Asset Management 量化研究部 2013 年 9 月 · 9 页 本次归档:
raw/papers/201311-fast-algorithm-high-dimensional-risk-parity/(paper.pdf 509 KB + extracted.md)
一句话核心
风险平价组合的数值求解此前依赖 SQP（Maillard 等 2010）或 Newton-Nesterov（Spinu 2013），两者在资产数上百时都很慢甚至不收敛。这篇论文把风险预算问题识别为「带对数障碍的二次函数最小化」，套用机器学习里的循环坐标下降 (CCD) 算法，得到一个实现简单、无需调步长、在 n>500 时明显更快的求解器，并用五算法对比实验量化了这一点。
问题与关键结构
RB 组合由非线性方程组定义：RC_i(\boldsymbol{x})=b_iR(\boldsymbol{x})。等价地可写成带对数障碍的极小化问题：
\min_{\boldsymbol{x}}\ \tfrac{1}{2}\boldsymbol{x}^\top\boldsymbol{\Sigma}\boldsymbol{x}-\lambda\sum_{i=1}^{n}b_i\ln x_i
（其中 \lambda 可取 1，最后再归一化 \boldsymbol{x}^\star=\boldsymbol{y}^\star/\sum_i y_i^\star）。
CCD 的思路与 Gauss-Seidel / Jacobi 解线性方程组类似：每一步只优化一个坐标，其余坐标固定，循环直到收敛。收敛性依据 Tseng (2001) 对不可微函数情形的坐标下降收敛定理。
单坐标更新。 对坐标 i 求一阶条件并令 \lambda=1，得到关于 x_i 的二次方程（论文 §2.1 的公式 (4)）。因为 \sigma_i^2>0 使该多项式为凸二次式，且两根之积为负，两个根必异号，因此取正根即为该坐标的最优解。由于 \boldsymbol{x} 的分量严格为正，迭代过程中每次更新后仍保持为正。
效率技巧。 把更新式改写成只需 (\boldsymbol{\Sigma}\boldsymbol{x})_i 和 \sigma(\boldsymbol{x}) 的形式后，\boldsymbol{\Sigma}\boldsymbol{x} 与 \sigma(\boldsymbol{x}) 的更新各只需一次向量乘法（利用 \boldsymbol{\Sigma} 的第 i 行/列），这把每次迭代的成本从矩阵级降到矩阵-向量级。
关键发现
Eurostoxx 50 ERC 回测（1989-12 至 2012-12，每月计算 ERC）。 五种算法（SQP+BFGS、Jacobi、Newton、Nesterov、CCD）：
| 算法 | 收敛频率 % | 平均每次迭代耗时 (1/100 秒) | 最大耗时 |
|---|---|---|---|
| SQP | 94.96 | 2.00 | 4.70 |
| Jacobi | 92.02 | 0.04 | 1.60 |
| Newton | 100.00 | 0.04 | 1.60 |
| Nesterov | 100.00 | 0.05 | 1.60 |
| CCD | 100.00 | 0.12 | 1.60 |
SQP 最慢且并非每次都收敛；Jacobi 在 S&P 500 的 ERC 回测中十次只收敛七次。
S&P 500 ERC 回测。 SQP 在此表被略去（不收敛）；Jacobi 收敛频率仅 69.14%，CCD 的平均耗时 4.33、最大 9.40，Newton 17.90/38.78，Nesterov 18.80/54.70。
高维表现（Davies-Higham 2000 生成的模拟相关矩阵）。 计算 ERC 的耗时：
| n | Jacobi | Newton | Nesterov | CCD |
|---|---|---|---|---|
| 500 | 不收敛 | 24 | 37 | 13 |
| 1000 | 不收敛 | 215 | 384 | 45 |
| 1500 | 不收敛 | 790 | 1575 | 110 |
分界线在 n=250 附近：资产数少于 250 时 Newton 更快，超过 250 时 CCD 更高效。
实现细节的重要性。 论文明确提醒：Newton 算法若直接算 Hessian 的逆而非用 Cholesky 分解，n=1500 的例子会从 7.90 秒变成 35.40 秒；CCD 的耗时取决于编程语言的循环效率，在 Matlab 和 R 里（循环实现差）Newton 反而更快，而在 C、Fortran、Gauss 里 CCD 更快。
与已有算法的关系。 论文指出 Spinu (2013) 的贡献是发现拉格朗日函数是自协调 (self-concordant) 的，因此可以用 Nesterov (2004) 的工具改善 Newton 法的收敛；本文的 CCD 则来自另一条线——Friedman-Hastie-Tibshirani (2010) 的坐标下降，且该算法已被用于范数约束的均值-方差优化（Yen & Yen 2013）。
重要 caveat
- 算法要求所有风险预算严格为正；论文明确指出若某些 b_i=0，算法未定义（这也强化了「RB 问题必须写成 b_i>0」的规范）。
- 数值实验用的是 Gauss 10 语言、Intel T8400 3 GHz Core 2 Duo、3.5 GB 内存，绝对耗时不具参考价值，只有相对比较有意义。
- 收敛性依赖 Tseng (2001) 的技术性假设（(B1)–(C2)），论文自陈函数 (3) 满足这些假设。
- 论文未处理交易成本、协方差估计误差等实务问题；只解决「给定 \boldsymbol{\Sigma} 如何快速求权重」。
- 高维测试用的是模拟相关矩阵（奇异值算术分布），不反映真实市场相关结构。
对 quant wiki 的意义
- 它是 Risk Parity 从论文走向工程实现的关键一环：风险平价基金要每天/月对几百只成分股做 ERC，没有 CCD 这类算法根本跑不动。
- 它把机器学习的大规模优化工具（坐标下降）引入组合优化，与 ADMM 算法 一同构成「用 ML 优化器解组合问题」的路线，后者在 Richard-Roncalli 2019 里被进一步扩展为 ADMM-CCD 混合算法。
- 与 高维风险平价算法 概念页对应。
- 它对 Risk Parity 中「ERC 解是内生的、需要数值算法」这一点的工程后果给出量化答案。
相关概念
- 高维风险平价算法 — 本论文整理出的概念页
- Risk Parity — 风险平价总入口
- 风险预算与风险平价 — RB 的定义
- ADMM 算法 — 同属大规模优化工具箱
- Griveau-Billion-Richard-Roncalli 2013 — 论文实体页