鲁棒优化的不确定集分类 (Uncertainty Sets in Robust Optimization)
一句话：鲁棒优化里最关键的一次建模选择不是目标函数，而是不确定集 \mathcal U 长什么样——它决定了鲁棒问题能不能高效求解、保守到什么程度、以及是否还有概率保证可言。
它是什么
鲁棒优化 (RO) 求 \min_x \sup_{\xi\in\mathcal U} h(x,\xi)。名义问题（LP/QCQP/SDP）都是可解的，但 \sup 这一层内层的结构完全由 \mathcal U 决定。综述 Bertsimas-Brown-Caramanis 2024 给出的核心判断是：可解性取决于「名义问题结构 × 不确定集类别」的组合，而不是单看其一——同一个椭球不确定集，在线性问题里给 SOCP，在二次约束问题里给 SDP，在半定规划问题里却是 NP-hard。
四类基本形态
| 形态 | 集合定义（简写） | 规模参数 | 鲁棒对应问题 | 保守性 |
|---|---|---|---|---|
| 盒式 box | 各分量 \xi_k\in[\xi_k^L,\xi_k^U] 独立 | 区间半宽 | LP | 最高：假设所有分量同时同向偏离 |
| 椭球 ellipsoidal | \{u: u=u^0+\Pi(u')\},\ \|u'\|_2\le\gamma | 半径 \gamma | SOCP | 中等；\gamma 连续可调 |
| 基数约束 cardinality | \{\bar A+\sum_{j\in J} z_j\hat a_j: \|z\|_\infty\le1,\ \sum_j \mathbf 1(z_j)\le\Gamma\} | 预算 \Gamma | LP（松弛精确） | 可调；\Gamma 越小越接近名义解 |
| 范数型 norm | \{u: \|M^{-1}(u-\bar u)\|\le1\} | 半径 \Delta | 对偶范数约束：l_1/l_\infty → LP，l_2 → SOCP | 随范数与 M 平滑变化 |
盒式是特例：多面体不确定集包含盒式，椭球包含所有多面体。「椭球 vs 盒式」的实质是用球面约束替代逐维区间约束，代价是可解结构变松（LP → SOCP）。
基数约束是「预算化」的原型：不保护「所有参数同时偏离」这一极端情形，只保护「至多 \Gamma 个参数偏离」。Bertsimas–Sim 的对偶化是精确的（内层集合选择非凸，但自然凸松弛是紧的），鲁棒 LP 仍是 LP。
规模参数与计算复杂度
| 不确定集 | 鲁棒对应问题 |
|---|---|
| 椭球 + 线性约束 | SOCP（Ben-Tal & Nemirovski 定理 1） |
| 多面体 + 线性约束 | LP |
| 基数约束 + 线性约束 | LP（等价重构，精确） |
| 范数型 + 线性约束 | 对偶范数约束（l_1/l_\infty → LP，l_2 → SOCP） |
| 单一椭球 + 二次约束 | SDP（S-引理，精确） |
| 多面体或椭球交 + 二次约束 | NP-hard |
| 椭球 + 半定规划 | NP-hard（无结构范数有界是例外） |
| 组合问题 + 基数不确定模型 | 最多解 n+1 个名义问题（网络流只要对数个） |
多阶段是另一片难区：两阶段线性鲁棒问题在确定性集合不确定下已 NP-hard。仿射可调 (AARC) 在固定追索 + 锥不确定集下化为 LP；在椭球交 + 非固定追索下只能给 SDP 近似，其紧性由描述不确定集的矩阵最大秩 \mu 控制。有限可调（分段常数后续决策）即使只分两块，求最优分区也 NP-hard。
鲁棒解与名义解的关系
保守性代价至今没有理论刻画。综述 §6 把「刻画鲁棒性的代价」列为三个开放问题之一，并说已有研究（主要是 Bertsimas & Sim、Xu & Mannor）大体上是实证性的。
但实证方向上有一个反直觉的结论：鲁棒优化形式上是 max-min（最坏情形），但它的解未必过度保守，在很多情形下与随机方法给出的解很接近。组合领域的对比：
- Tütüncü & Koenig 用真实市场数据算鲁棒有效前沿——鲁棒组合在最坏情形收益上显著优于名义组合，期望收益的损失要小得多；
- Delage & Ye 六年市场收益实验：显著优于基于场景的随机规划；
- 但 Goldfarb & Iyengar 更谨慎——真实市场数据上鲁棒组合并非总是优于经典 Markowitz 组合，只有当置信参数取值较高（不确定集更大）时才显出优势。
另一个方向的联系是鲁棒即正则化：\ell_2 正则化回归的解、Lasso 的解、范数正则化 SVM 的解，都是某个鲁棒优化问题的解。由此 Lasso 的稀疏性得到一个鲁棒解释（稀疏是鲁棒性的推论），SVM 的统计一致性也可以绕开稳定性与 VC 维论证直接证明。
预算化 (budgeted uncertainty) 如何控制保守性
每一类不确定集都要配一个可解释的规模参数，它同时是保守性旋钮和概率保证的来源：
- 椭球半径 \Omega：在不确定系数对称独立、支撑有界的假设下，鲁棒解满足约束的概率至少 1-e^{-\Omega^2/2}；
- 基数预算 \Gamma：P(\tilde a^\top x^\ast>b)\le e^{-\Gamma^2/(2|J|)}，其中 |J| 是可能偏离的系数个数；
- 范数半径 \Delta（已知均值与协方差时）：P(\tilde a^\top x^\ast>b)\le 1/(1+\Delta^2)。
于是「取多大的 \Gamma」不再是随手调参，而是有定量依据的选择：\Gamma 越大违反概率上界越小、鲁棒解越保守；\Gamma=|J| 退化为盒式，\Gamma\to0 退化为名义解。
分布层面同理：CVaR 的生成族是 \mathcal Q=\{q\in\Delta_N: q_i\le p_i/\alpha\}，给出多面体不确定集（当 p_i=1/N、\alpha=j/N 时恰是所有 j 点平均的凸包），鲁棒问题化为 LP。
与其他概念的关系
- Robust Optimization — 上位概念页：RO 的规范形式、RO vs DRO 的分工
- Distributionally Robust Optimization — 不确定集分类的另一半：那里的模糊集 \mathcal P 是分布集合，本页的 \mathcal U 是参数取值集合
- Coherent Risk Measures — 分布歧义与 RO 之间的对偶桥梁（Huber 对偶）
- Wasserstein Ambiguity Set — 数据驱动的分布歧义构造，RO 一侧的对位
局限与开放问题
- 保守性代价缺少理论界——这是综述自己列的首要开放问题。
- 多阶段 / 可调 RO 大多不可解，可解特例的条件都很强。
- 鲁棒 SDP 与鲁棒离散优化基本无精确解，只能靠内近似或特定不确定模型绕开。
- RO 与数据脱节：综述 §6 指出 RO 文献里大多数模型不直接由数据标定，数据驱动的 RO 理论仍在起步阶段——这正是 DRO 一侧在补的位置。
来源
- summaries/202411-theory-and-applications-robust-optimization/202411-theory-and-applications-robust-optimization — (2024 修订版) Bertsimas、Brown 与 Caramanis 的鲁棒优化综述；本页的四类形态、可解性表、概率保证与开放问题均出自其 §2、§3、§5.1、§6