Robust Optimization (鲁棒优化)
大白话：参数不确定时，优化时按最坏情况来：只假设不确定性的「可能范围」已知（不确定集），完全不管它的分布。这是仅次于「假设有对抗性扰动」的最悲观假设——但换来的是解一定扛得住。
定义。 鲁棒优化 (RO) 是一种建模框架：决策者在不确定参数的可能取值集合（不确定集 \mathcal U） 上最小化最坏情形成本。RO 只假设不确定性的支撑集已知，而不知道其分布—— 这是仅次于「承认存在对抗性扰动」的最悲观假设。
标准的 RO 问题
对关于 \xi 线性（或凸）的成本函数 h(x,\xi)，RO 问题为
\min_{x\in X}\ \sup_{\xi\in\mathcal U} h(x,\xi).
若 h 关于 x 凸且 \mathcal U 是紧凸集，上确界是一个有限凸问题。 若 h 关于 \xi 仿射且 \mathcal U 是多面体或椭球，上确界是一个线性规划或二阶锥规划（LP / SOCP）， 使 RO 可直接由现成求解器（Gurobi、Mosek、CPLEX）求解。
历史与经典文献
- Soyster (1973) — 最早的 RO 表述（列式不确定下的线性规划，解成单个 LP）。
- Ben-Tal & Nemirovski (1998, 1999) — 鲁棒锥优化；椭球不确定的 SOCP 与 SDP 重构。
- El Ghaoui & Lebret (1997) — 鲁棒最小二乘；SDP 重构。
- Bertsimas & Sim (2004) — \Gamma-鲁棒框架：用「可同时偏离的参数个数」预算来控制保守性。
- Bertsimas, Brown & Caramanis (2011) — 理论与算法综述。
这些文献构成 RO 的正典；Rahimian & Mehrotra 2022 §3.2 通过说明 DRO 何时退化为（或等价于）RO， 把 DRO 放进了这条脉络里。
不确定集族系
| 族系 | 形状 | 可解性 | 保守性 |
|---|---|---|---|
| 盒式 \prod[\xi_k^L,\xi_k^U] | 超矩形 | LP | 极高——假设所有 \xi_k 同时偏离 |
| 预算式（Bertsimas-Sim） | \sum_k \lvert\xi_k-\xi_k^0\rvert/\hat\xi_k \le \Gamma | LP，经对偶重构后精确 | 可调，通过 \Gamma |
| 椭球 \sum_k (\xi_k-\xi_k^0)^2/\sigma_k^2\le 1 | 椭球 | SOCP | 光滑；中等 |
| 多面体 \mathcal U=\{A\xi\le b\} | 多面体 | LP | 取决于该多面体 |
| 基数 / 离散 | \xi\in\{\xi^{(1)},\dots,\xi^{(K)}\} | x 为整数时 MILP，否则 LP | 精确离散 RO |
Bertsimas-Sim \Gamma-鲁棒表述在组合与运筹语境下最常用，因为预算 \Gamma 有概率解释： 在独立对称的不确定假设下，d 个参数中超过 \Gamma 个同时偏离的概率至多为 \exp(-\Gamma^2/2d)—— 保守性是带着置信保证来的。
不确定集的类型与规模
不确定集的具体形态决定的不只是保守程度，还决定鲁棒问题是否还能高效求解。可解性取决于「名义问题结构 × 不确定集类别」的组合，而不是单看其一（鲁棒优化的不确定集分类 一页有完整对照表）。核心几条：
- 椭球不确定集在线性约束下化为 SOCP，在二次约束下经 S-引理化为 SDP（精确），但在半定规划下是 NP-hard。
- 多面体不确定集（盒式是其特例）在线性约束下化为 LP；多面体或椭球交用在二次约束下反而 NP-hard。
- 基数约束（Bertsimas–Sim）内层的集合选择虽非凸，但自然凸松弛是紧的，因此鲁棒 LP 仍是 LP。
- 范数型不确定集给出对偶范数约束：l_1/l_\infty 归约为 LP，l_2 归约为 SOCP。
每一类不确定集都配一个可解释的规模参数——半径 \gamma、基数预算 \Gamma、范数半径 \Delta、尾部水平 \alpha——它同时是保守性旋钮与概率保证的来源。参数取值范围覆盖两端：\Gamma=|J| 退化为盒式，\Gamma\to 0 退化为名义解。
保守性与预算化
保守性代价至今没有理论刻画。Bertsimas–Brown–Caramanis 的综述 §6 把「刻画鲁棒性的代价」列为三个开放问题之一，并指出已有研究（主要是 Bertsimas & Sim、Xu & Mannor）大体上是实证性的——什么时候鲁棒便宜、什么时候昂贵，仍无界。
但有两个方向性的实证结论值得记住：
- 鲁棒解未必过度保守。尽管形式上是 max-min（最坏情形），鲁棒解在很多情形下与随机方法给出的解很接近。组合领域：Tütüncü & Koenig 用真实市场数据算鲁棒有效前沿，发现鲁棒组合在最坏情形收益上显著优于名义组合，而期望收益的损失要小得多；Delage & Ye 六年市场收益实验显示其方法显著优于基于场景的随机规划。但 Goldfarb & Iyengar 的对比更谨慎——真实市场数据上鲁棒组合并非总是优于经典 Markowitz 组合，只有当置信参数较高（不确定集更大）时才显出优势。
- 预算化 (budgeted uncertainty) 给出概率保护。在不确定系数对称独立、支撑有界的假设下：椭球半径 \Omega 给违反概率 \le 1-e^{-\Omega^2/2}；基数预算 \Gamma 给 \le \exp(-\Gamma^2/(2|J|))（|J| 为可能偏离的系数个数）；范数型在已知均值与协方差时给 \le 1/(1+\Delta^2)。因此「取多大的 \Gamma」是有定量依据的选择，而非随手调参。
另一条把 RO 与统计学习接起来的线索是鲁棒即正则化：\ell_2 正则化回归的解、Lasso 的解、范数正则化 SVM 的解，都是某个鲁棒优化问题的解——由此 Lasso 的稀疏性得到一个鲁棒解释（稀疏是鲁棒性的推论），SVM 的统计一致性也可以绕开稳定性与 VC 维论证直接证明。
flowchart LR
A["Box uncertainty"] --> B["Tractable LP, very conservative"]
C["Budgeted Bertsimas-Sim"] --> D["LP, tunable Gamma"]
E["Ellipsoid"] --> F["SOCP, smooth"]
G["Polyhedral"] --> H["LP, flexible"]
A -.drop info.-> I["Distributionally Robust"]
C -.drop info.-> I
E -.drop info.-> I
F -.Wasserstein.-> J["DRO over Wasserstein ball"]
RO vs DRO
概念上的关系（Rahimian & Mehrotra §3.2）：
- RO 假设 \xi\in\mathcal U——一个取值的集合。
- DRO 假设 P\in\mathcal P——一个分布的集合。 只要 \mathcal P 不包含支撑集 \mathcal U 上的所有 delta 分布， DRO 的内层 \sup_{P\in\mathcal P}\mathbb E_P[h(x,\tilde\xi)] 就比 RO 的 \sup_{\xi\in\mathcal U}h(x,\xi) 严格更弱。
- 两者何时等价：若 \mathcal P 包含支撑集 \Xi 上的所有分布（「无信息」情形），DRO 与 RO 重合。 在有限的 \Xi 上，取 Wasserstein 球的 DRO 可以重构成一个作用于放大后不确定集的 RO 问题 （Mohajerin Esfahani & Kuhn 2018）。
实践中的选择：RO 适用于你手上有支撑信息（如某资产收益的最小/最大值）但没有分布信息的情形； DRO 适用于你有一些分布信息（样本、矩）且想在不过度承诺的前提下用上它的情形。
量化金融应用
| 问题 | RO 表述 | 出处 |
|---|---|---|
| 指数跟踪 | \min_{w}\ \max_{r\in\mathcal U}\ \lvert r^{\text{idx}} - w^\top r^{\text{basket}}\rvert_1 | Mutapcic & Boyd 2009 |
| 有界遗憾的组合 | \min_{w}\ \max_{r\in\mathcal U}\ -w^\top r | Goldfarb & Iyengar 2003 |
| 带因子模型的资产配置 | \min_w\ \max_{\beta,f\in\mathcal U}\ \lvert w-(\alpha+\beta f)\rvert_2 | Broadie 2007 |
| 考虑交易成本的执行 | \min_{x_t}\ \max_{\Delta S\in\mathcal U}\ \sum_t \lambda(x_t)(\Delta S - \bar S) | Bertsimas & Lo 1998 |
| 多阶段生产 / 库存 | \min_{x_1,\dots,x_T}\ \max_{\xi_1,\dots,\xi_T\in\mathcal U}\ \sum_t c_t^\top x_t | Ben-Tal 等 2004 |
优点与缺点
优点：
- 可解成单个 LP / SOCP / SDP——无需蒙特卡洛，无需情景抽样，无需调 \epsilon 或样本量。
- 保证对每一个 \xi\in\mathcal U 都成立——不做分布假设。
- \Gamma-鲁棒表述有干净的概率解释（独立假设下的机会约束保证）。
缺点：
- 往往过于保守——在包含 10\sigma 事件的支撑集上取最坏情形，会主导整个目标函数。
- 当 h 非凸（组合、整数）时 RO 难得多；上确界不再是凸问题。
- 不使用不确定性的分布；把所有取值视为等可能。
- \mathcal U 的规模 / 形状本身是一个建模选择，结果对它极为敏感 （Bertsimas & Sim 称之为「鲁棒性的代价」）。
交叉引用
- concepts/models-theory/Distributionally Robust Optimization — DRO 通过允许部分分布信息来推广 RO
- concepts/models-theory/Wasserstein Ambiguity Set — RO 与 DRO 之间的数据驱动桥梁
- concepts/risk-portfolio/Coherent Risk Measures — 凸紧 \mathcal P 上的 DRO = 一致风险；RO 是 \mathcal P = 支撑集上全部分布的极限
- concepts/risk-portfolio/Risk Parity — 风险预算视角与最坏情形表述一致
- 鲁棒优化的不确定集分类 — 不确定集形态、规模参数与计算复杂度的完整对照
参考文献
- Ben-Tal, A., El Ghaoui, L. & Nemirovski, A. (2009) Robust Optimization — Princeton University Press.
- Bertsimas, D., Brown, D.B. & Caramanis, C. (2011) "Theory and applications of robust optimization" SIAM Review 53(3)；2024-11-26 修订版 arXiv:1010.5445（本地归档
raw/papers/202411-theory-and-applications-robust-optimization/） - Soyster, A.L. (1973) "Convex programming with set-inclusive constraints" Operations Research 21.
- Bertsimas, D. & Sim, M. (2004) "The price of robustness" Operations Research 52(1).