Robust Optimization (鲁棒优化)

Definition. Robust Optimization (RO) is a modelling framework in which the decision-maker minimises the worst-case cost over an uncertainty set \mathcal U of the uncertain parameters' possible realisations. RO assumes only the support of the uncertainty is known, not its distribution — the most pessimistic assumption short of admitting adversarial perturbations.

The canonical RO problem

For a cost function h(x,\xi) linear (or convex) in \xi, the RO problem is

\min_{x\in X}\ \sup_{\xi\in\mathcal U}\ h(x,\xi).

If h is convex in x and \mathcal U is a compact convex set, the supremum is a finite convex problem. If h is affine in \xi and \mathcal U is a polytope or ellipsoid, the supremum is a linear or second-order-cone program (LP / SOCP), making RO directly solvable by off-the-shelf solvers (Gurobi, Mosek, CPLEX).

History and canonical references

Soyster (1973) — the first RO formulation (linear programming with column-wise uncertainty, solved as a single LP).
Ben-Tal & Nemirovski (1998, 1999) — robust conic optimisation; SOCP and SDP reformulations of ellipsoidal uncertainty.
El Ghaoui & Lebret (1997) — robust least squares; SDP reformulation.
Bertsimas & Sim (2004) — the \Gamma-robustness framework: control conservatism via a budget on the number of parameters that can simultaneously deviate.
Bertsimas, Brown & Caramanis (2011) — theory and algorithms survey.

These references are the canon for RO; Rahimian & Mehrotra 2022 §3.2 places DRO in this lineage by showing when DRO reduces to (or is equivalent to) RO.

Uncertainty set families

Family	Shape	Tractability	Conservatism
Box \prod[\xi_k^L,\xi_k^U]	hyper-rectangle	LP	very high — assumes all \xi_k co-deviate
Budgeted (Bertsimas-Sim)	\sum_k \lvert\xi_k-\xi_k^0\rvert/\hat\xi_k \le \Gamma	LP, exact via dual reformulation	tunable via \Gamma
Ellipsoid \sum_k (\xi_k-\xi_k^0)^2/\sigma_k^2\le 1	ellipsoid	SOCP	smooth; intermediate
Polyhedral \mathcal U=\{A\xi\le b\}	polytope	LP	depends on the polyhedron
Cardinality / discrete	\xi\in\{\xi^{(1)},\dots,\xi^{(K)}\}	MILP if integer x, else LP	exact discrete RO

The Bertsimas-Sim \Gamma-robust formulation is the most-used in portfolio and OR contexts because the budget \Gamma has a probabilistic interpretation: under independent symmetric uncertainty, the chance that more than \Gamma of d parameters simultaneously deviate is at most \exp(-\Gamma^2/2d) — the conservation comes with a confidence guarantee.

不确定集的类型与规模

不确定集的具体形态决定的不只是保守程度，还决定鲁棒问题是否还能高效求解。可解性取决于「名义问题结构 × 不确定集类别」的组合，而不是单看其一（鲁棒优化的不确定集分类一页有完整对照表）。核心几条：

椭球不确定集在线性约束下化为 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

The conceptual relationship (Rahimian & Mehrotra §3.2):

RO assumes \xi\in\mathcal U — a set of realisations.
DRO assumes P\in\mathcal P — a set of distributions. The DRO inner \sup_{P\in\mathcal P}\mathbb E_P[h(x,\tilde\xi)] is a strictly weaker problem than RO \sup_{\xi\in\mathcal U}h(x,\xi) whenever \mathcal P does not contain all delta distributions on \mathcal U.
When the two are equivalent: if \mathcal P contains all distributions on the support \Xi (the "no info" case), DRO and RO coincide. With finite \Xi, DRO with a Wasserstein ball can be reformulated as a RO problem over a scaled-up uncertainty set (Mohajerin Esfahani & Kuhn 2018).

In practice: RO is the right tool when you have support information (e.g. min/max of an asset return) and no distributional information; DRO is the right tool when you have some distributional information (samples, moments) and want to use it without overcommitting.

Quant-finance applications

Problem	RO formulation	Reference
Index tracking	\min_{w}\ \max_{r\in\mathcal U}\ \lvert r^{\text{idx}} - w^\top r^{\text{basket}}\rvert_1	Mutapcic & Boyd 2009
Portfolio with bounded regret	\min_{w}\ \max_{r\in\mathcal U}\ -w^\top r	Goldfarb & Iyengar 2003
Asset allocation with factor model	\min_w\ \max_{\beta,f\in\mathcal U}\ \lvert w-(\alpha+\beta f)\rvert_2	Broadie 2007
Transaction-cost aware execution	\min_{x_t}\ \max_{\Delta S\in\mathcal U}\ \sum_t \lambda(x_t)(\Delta S - \bar S)	Bertsimas & Lo 1998
Multi-stage production / inventory	\min_{x_1,\dots,x_T}\ \max_{\xi_1,\dots,\xi_T\in\mathcal U}\ \sum_t c_t^\top x_t	Ben-Tal et al. 2004

Strengths and weaknesses

Strengths:

Solvable as a single LP / SOCP / SDP — no Monte Carlo, no scenario sampling, no tuning of \epsilon or sample size.
Guarantees hold for every \xi\in\mathcal U — no distributional assumption.
The \Gamma-robust formulation has a clean probabilistic interpretation (chance-constraint guarantee under independence).

Weaknesses:

Often too conservative — worst-case over a support that includes 10\sigma events dominates the objective.
For non-convex h (combinatorial, integer), RO is much harder; the supremum is not a convex problem.
Does not use the distribution of the uncertainty; treats all realisations as equally likely.
The size / shape of \mathcal U is itself a modelling choice; the result is highly sensitive to it (a phenomenon known as the "price of robustness" by Bertsimas & Sim).

Cross-references

concepts/Distributionally Robust Optimization — DRO generalises RO by allowing partial distributional information
concepts/Wasserstein Ambiguity Set — the data-driven bridge between RO and DRO
concepts/Coherent Risk Measures — DRO over a convex compact \mathcal P = coherent risk; RO is the limit \mathcal P = all distributions on the support
concepts/Risk Parity — risk-budget view is consistent with the worst-case formulation
鲁棒优化的不确定集分类 — 不确定集形态、规模参数与计算复杂度的完整对照