Bertsimas, Brown & Caramanis (2024) — Theory and Applications of Robust Optimization

论文信息

• 标题: Theory and Applications of Robust Optimization
• 作者: Dimitris Bertsimas (MIT Sloan School of Management + Operations Research Center) · David B. Brown (Duke University Fuqua School of Business) · Constantine Caramanis (UT Austin, Department of Electrical and Computer Engineering)
• venue: 综述。初版 2008-09-05，本次归档为 2024-11-26 修订版（arXiv:1010.5445, math.OC）。正式发表版为 SIAM Review 53(3), 2011
• 本地归档: raw/papers/202411-theory-and-applications-robust-optimization/ (paper.pdf 640 KB, 50 页 + extracted.md)
• 篇幅结构: §1 引言与第一个例子（组合选择）→ §2 结构与可解性结果（鲁棒 LP / QCQP / SDP / 离散优化）→ §3 不确定集的选择（概率保证、分布歧义）→ §4 鲁棒可调优化（仿射可调、有限可调、网络设计）→ §5 应用（组合、统计学习与估计、供应链、工程）→ §6 未来方向

一句话

50 页的鲁棒优化综述：不确定集的四种基本形态（box / 椭球 / 基数约束 / 范数）各自对应哪种可解结构（LP / SOCP / SDP，或 NP-hard），每类都带一个可解释的规模参数，参数直接给出违反概率上界（如基数约束的 e^{-\Gamma^2/(2|J|)}），并把「保守性代价」「RO 与统计学习的正则化等价」一并梳理清楚。

结构

• §1 引言 + A First Example：以投资者在 n 个风险资产与现金之间配置、且不许卖空不许借款为例，比较「分布已知」与「分布只是近似已知」两种情形；概率约束在离散分布下已是 NP-hard，RO 用确定性约束替换它。三类不确定集：椭球 \mathcal R_Q(\gamma)、D-范数 \mathcal R_D(\Gamma)、尾部（凸包）\mathcal R_T(k)。
• §2 结构与可解性结果（本文最硬的部分）
  • §2.2 鲁棒线性优化：椭球 → SOCP（Ben-Tal & Nemirovski 定理 1）；多面体 → LP；基数约束（Bertsimas & Sim）→ 松弛精确、等价 LP；范数型（Bertsimas 等定理 2）→ 对偶范数约束，l_1/l_\infty 给 LP、l_2 给 SOCP
  • §2.3 鲁棒二次优化：单一椭球 → SDP（S-引理，砖砌定理 3）；多面体或椭球交 → NP-hard
  • §2.4 鲁棒 SDP：椭球下一般 NP-hard；无结构范数有界不确定是例外
  • §2.5 鲁棒离散优化：Kouvelis & Yu 的 NP-hard 结果 vs Bertsimas & Sim 的「最多解 n+1 个名义问题」
• §3 选择不确定集
  • §3.1 概率保证：椭球半径 \Omega 给 1-e^{-\Omega^2/2}；基数约束 \Gamma 给 e^{-\Gamma^2/(2|J|)}（定理 4）；范数型（已知均值协方差）给 1/(1+\Delta^2)
  • §3.2 分布歧义：Huber 的对偶把「分布族 \mathcal Q」接到一致风险测度上；CVaR 的生成族给出多面体不确定集；Delage & Ye 的矩不确定集；Ben-Tal 等的软鲁棒 (soft robust optimization)
• §4 鲁棒可调优化：静态解 vs 完全可调解；两阶段确定性不确定下 NP-hard；仿射可调 AARC（定理 5–7，固定追索下 LP、椭球交下 SDP 近似与紧性界）；有限可调（分成两块已 NP-hard）；网络设计的可行性刻画与分离问题 NP-hard（定理 8–9）
• §5 应用：§5.1 组合优化（三类不确定模型 + 六个实证研究）；§5.2 统计学习与估计（\ell_2 正则化 / Lasso / SVM 都是鲁棒问题的解；Fisher 判别、MPC 的最坏情形最大似然、线性估计器的最坏情形 MSE）；§5.3 供应链；§5.4 工程
• §6 未来方向：可调 RO 的可解性、鲁棒性代价的理论刻画、数据驱动的 RO

关键数字

• 违反概率上界：椭球 \Rightarrow 1-e^{-\Omega^2/2}；基数约束 \Rightarrow e^{-\Gamma^2/(2|J|)}；范数型 \Rightarrow 1/(1+\Delta^2)
• CVaR 生成族 \mathcal Q=\{q\in\Delta_N: q_i\le p_i/\alpha\} 在 p_i=1/N、\alpha=j/N 时就是所有 j 点平均的凸包
• Bertsimas & Sim 基数模型：鲁棒组合问题最多解 n+1 个名义问题；网络流只需对数个
• 鲁棒 SDP 内近似：\rho(\text{AR}:\mathcal U)\le \pi\sqrt{\mu}/2，\mu 为描述 \mathcal U 的矩阵最大秩
• 静态鲁棒解在对称条件下可逼近完全可调解至因子 2（Bertsimas & Goyal）

与已有页面的关系

• Robust Optimization — 本篇是该页的权威出处之一；该页的「Uncertainty set families」表与「RO vs DRO」两节直接对应本篇 §2 与 §3.2
• 鲁棒优化的不确定集分类 — 本篇 §2 与 §3 抽出的概念页，专注不确定集形态与规模参数
• Coherent Risk Measures — §3.2 的一致风险测度对偶，是把「分布歧义」写进 RO 框架的那条缝
• Distributionally Robust Optimization — Rahimian & Mehrotra 综述与本篇是互补的两本：前者统一四个范式，后者给出不确定集的可解性细节
• entities/Dimitris Bertsimas · entities/David B Brown · entities/Constantine Caramanis — 作者页

标准文献

Bertsimas, D., Brown, D.B. & Caramanis, C. (2024, 修订版 2024-11-26). Theory and Applications of Robust Optimization. arXiv:1010.5445. 初版 2008-09-05；正式版 SIAM Review 53(3), 2011.