Pre Link

a pratical guide to robust optimization(1)

Choosing the uncertainty set

本节主要分析不同的不确定集合以及它们的优势和劣势.

Often one wants to make a trade-off between robustness against each physical realization of the uncertain parameter and the size of the uncertainty set.

盒状约束(box constraint)包含了对向量 ζ \pmb{\zeta} ζ​ζ​​ζ所有成分的约束，是最为鲁棒的选择，但是所有不确定参数都处于最坏情况这种概率是很低的.

A box uncertainty set that contains the full range of realizations for each component of ζ \pmb{\zeta} ζ​ζ​​ζ is the most robust choice and guarantees that the constraint is never violated, but on the other hand there is only a small chance that all uncertain parameters take their worst case values. This has led to the development of smaller uncertainty sets that still guarantee that the constraint is 'almost never' violated.

所以，发展出了机会约束(chance constraint)理论，即约束在一定概率下成立，但是一般情况下约束成立的概率分布是未知的，需要使用分布式鲁棒优化(distributionally robust solution)算法求解.

One application of RO is to provide a tractable safe approximation of the chance constraint in such cases.

即如果 x \mathbf{x} x满足
a ( ζ ) T x ≤ d ∀ ζ ∈ U ε \mathbf{a}(\pmb{\zeta})^T\mathbf{x}\leq d\quad \forall \pmb{\zeta}\in\mathcal{U}_\varepsilon a(ζ​ζ​​ζ)Tx≤d∀ζ​ζ​​ζ∈Uε​
那么等价的
P ( a ( ζ ) T x ≤ d ) ≥ 1 − ε (9) \mathbb{P}(\mathbf{a}(\pmb{\zeta})^T\mathbf{x}\leq d)\geq 1-\varepsilon\tag{9} P(a(ζ​ζ​​ζ)Tx≤d)≥1−ε(9)
当 ε = 0 \varepsilon=0 ε=0时，机会约束就转为了一般鲁棒性约束.

假设关于 ζ \pmb{\zeta} ζ​ζ​​ζ的信息仅有 ∥ ζ ∥ ∞ ≤ 1 \lVert\pmb{\zeta}\rVert_\infty\leq 1 ∥ζ​ζ​​ζ∥∞​≤1. 盒装约束就是机会约束 ε = 0 \varepsilon=0 ε=0的情况，当可以提供更多的信息时，如均值，方差以及概率分布为对称性或者单峰的，这样约束范围可以减小.

We mention the uncertainty sets that are used in practice in partice when box uncertainty is found to be too pessimistic.

考虑椭球约束(ellipsoid)和盒装约束重叠的情况
U ε = { ζ : ∥ ζ ∥ 2 ≤ Ω , ∥ ζ ∥ ∞ ≤ 1 } (10) \mathcal{U}_\varepsilon=\{\pmb{\zeta}: \lVert\pmb{\zeta}\rVert_2\leq \Omega, \lVert\pmb{\zeta}\rVert_\infty\leq 1\}\tag{10} Uε​={ζ​ζ​​ζ:∥ζ​ζ​​ζ∥2​≤Ω,∥ζ​ζ​​ζ∥∞​≤1}(10)
其中 ε = exp ⁡ ( − Ω 2 / 2 ) \varepsilon=\exp(-\Omega^2/2) ε=exp(−Ω2/2).
第二种是多面体(polyhedral)集合，也被成为预算约束¹(budget uncertainty set)
U ε = { ζ : ∥ ζ ∥ 1 ≤ Γ , ∥ ζ ∥ ∞ ≤ 1 } (11) \mathcal{U}_\varepsilon=\{\pmb{\zeta}:\lVert\pmb{\zeta}\rVert_1\leq \Gamma, \lVert\pmb{\zeta}\rVert_\infty\leq 1\}\tag{11} Uε​={ζ​ζ​​ζ:∥ζ​ζ​​ζ∥1​≤Γ,∥ζ​ζ​​ζ∥∞​≤1}(11)
其中 ζ ∈ R L \pmb{\zeta}\in\mathbb{R}^L ζ​ζ​​ζ∈RL并且 ε = exp ⁡ ( − Γ 2 / ( 2 L ) ) \varepsilon=\exp(-\Gamma^2/(2L)) ε=exp(−Γ2/(2L)).

This set has the interpretation that (integer) Γ \Gamma Γ controls the number of elements of ζ \pmb{\zeta} ζ​ζ​​ζ that may deviation from their nominal values. Eq ( 10 ) (10) (10) leads to better objective values for a fixed ε \varepsilon ε compared to ( 10 ) (10) (10), but gives rise to a CQP for an uncertain LP while ( 11 ) (11) (11) results in an LP and is therefore more tractable from a computational point of view.(方程 ( 10 ) (10) (10)的目标值优于 ( 11 ) (11) (11)，但是从计算复杂度的角度来讲，方程 ( 10 ) (10) (10)需要求解一个CQP问题，而 ( 11 ) (11) (11)求解的是LP问题)

Bandi和Bertsimas²提出了基于*极限定理（central limit theorem）的不确定集合，当 ζ ∈ R L \pmb{\zeta}\in\mathbb{R}^L ζ​ζ​​ζ∈RL中的分量为独立同分布并且均值为 μ \mu μ方差为 σ 2 \sigma^2 σ2.
U ε = { ζ : ∣ ∑ i = 1 L ζ i − L μ ∣ ≤ ρ n σ } \mathcal{U}_\varepsilon=\bigg\{\pmb{\zeta}:\bigg|\sum_{i=1}^L\zeta_i-L\mu\bigg|\leq \rho\sqrt{n}\sigma\bigg\} Uε​={ζ​ζ​​ζ:∣∣∣∣​i=1∑L​ζi​−Lμ∣∣∣∣​≤ρn ​σ}
其中 ρ \rho ρ控制约束冲突(constraint violation)的概率为 1 − ε 1-\varepsilon 1−ε. Bandi和Bertsimas也给出了 U ε \mathcal{U}_\varepsilon Uε​加入相关性(correlations)，厚尾(heavy tails)或者其他分布信息时的变形.

In order to avoid infeasibility, it is necessary to define separate uncertainty sets for each constraint, where the summation runs only over the elements of ζ \pmb{\zeta} ζ​ζ​​ζ that appear in that constraint. Alternatively, it may help to take the intersection of U ε \mathcal{U}_\varepsilon Uε​ with a box.

Bertsimas等说明了如何基于历史数据和统计检测构建不确定集合³，和前文提到的方法相比，该方法需要较少的假设，如对 ζ \zeta ζ的分量独立性假设是不需要的.

Bertsimas和Brown说明了基于历史不确定数据和一致性风险度量构建不确定集合并刻画决策者的偏好的方法⁴.

For a specific class of risk measures, this gives rise to polyhedral uncertainty sets.

考虑不确定概率向量，如
U ⊂ Δ L − 1 = { p ∈ R L : p ≥ 0 , ∑ i = 1 L p i = 1 } \mathcal{U}\subset\Delta^{L-1}=\{\mathbf{p}\in\mathbb{R}^L:\mathbf{p}\geq \mathbf{0}, \sum_{i=1}^L p_i=1\} U⊂ΔL−1={p∈RL:p≥0,i=1∑L​pi​=1}
Ben-Tal等价于 ϕ − \phi- ϕ−divergence构建了不确定集合，其中对于向量 p \mathbf{p} p和向量 q \mathbf{q} q的 ϕ − \phi- ϕ−divergence的定义为
I ϕ ( p , q ) = ∑ i = 1 L q i ϕ ( p i q i ) I_\phi(\mathbf{p}, \mathbf{q})=\sum_{i=1}^L q_i\phi(\frac{p_i}{q_i}) Iϕ​(p,q)=i=1∑L​qi​ϕ(qi​pi​​)
其中 ϕ \phi ϕ是凸函数.

let p \mathbf{p} p denote a probability vector and let q \mathbf{q} q be the vector with observed frequencies when N N N items are sampled according to p \mathbf{p} p. Under certain regularity conditions

2 N ϕ ′ ′ ( 1 ) I ϕ ( p , q ) ⟶ d χ L − 1 2 a s N → ∞ \frac{2N}{\phi^{''}(1)}I_\phi(\mathbf{p}, \mathbf{q})\stackrel{d}{\longrightarrow}\chi^2_{L-1} \quad as N\to\infty ϕ′′(1)2N​Iϕ​(p,q)⟶d​χL−12​asN→∞
可以使用如下不确定集合
U ε = { p : p ≥ 0 , e T p = 1 , 2 N ϕ ′ ′ ( 1 ) I ϕ ( p , p ^ ) ≤ χ L − 1 ; 1 − ε 2 } \mathcal{U}_\varepsilon=\bigg\{ \mathbf{p}: \mathbf{p}\geq \mathbf{0}, \mathbf{e}^T\mathbf{p}=1, \frac{2N}{\phi^{''}(1)}I_\phi(\mathbf{p}, \mathbf{\hat{p}})\leq\chi^2_{L-1;1-\varepsilon} \bigg\} Uε​={p:p≥0,eTp=1,ϕ′′(1)2N​Iϕ​(p,p^​)≤χL−1;1−ε2​}
其中， p ^ \hat{\mathbf{p}} p^​是对 p \mathbf{p} p的估计.

对于多阶段问题，Goh和Sim⁵说明了如何基于方差-协方差矩阵或者期望值的界构建不确定集合.

关于 U ε \mathcal{U}_\varepsilon Uε​的构建说明如下

Linearly adjustable robust counterpart: linear in what?

AARC作为一种计算方法由Ben-Tal提出，该方法可以处理adjustable variables. 在如下约束中
( a + P ζ ) T x + b T y ≤ d ∀ ζ ∈ Z (\mathbf{a}+\mathbf{P}\pmb{\zeta})^T\mathbf{x}+\mathbf{b}^T\mathbf{y}\leq d\quad \forall \pmb{\zeta}\in\mathcal{Z} (a+Pζ​ζ​​ζ)Tx+bTy≤d∀ζ​ζ​​ζ∈Z
其中， y \mathbf{y} y是可调变量， b \mathbf{b} b为不依赖 ζ \pmb{\zeta} ζ​ζ​​ζ的固定量，有两种不同的AARCs

---

1. the price of robustness ↩︎

2. tractable stochastic analysis in high dimensions via robust optimization ↩︎

3. Data-driven robust optimization ↩︎

4. Constructing uncertain sets for robust linear optimization ↩︎

5. distributionally robust optimization and its tractable approximations ↩︎