【備忘】A Distributional Interpretation of Robust Optimization

論文の概要

 本論文は、決定変数と不確実性を表す分布の台が同じ空間に属するとき、ある条件の下Robust Optimization(RO)の最適解がDistributionally Robust Stochastic Programming(DRSP)の最適解と漸近的に一致することを示したものである。
 詳細な問題設定としては、最適化対象の関数$f(\cdot, \cdot) : \mathbb{R}^{n} \times \mathbb{R}^{m} \mapsto \mathbb{R} \cup \lbrace -\infty \rbrace$は可測関数であり、データ$\lbrace x_n \rbrace$は確率分布$h^{*}$からiidで観測されたとする。また$f$は有限でかつ同程度連続であるとする、つまり$\max_{x, v} | f(v,x) | \le Const$、かつ$d(\epsilon) := \max_{x, v, | \delta |_{\infty} \le \epsilon} | f(v, x + \delta) - f(v,x) | \rightarrow 0$である。
 このとき、次のROの最適解$v_{(n)}$はDRSPの解となる。
つまり、$v_{(n)} := \arg\max_v \frac{1}{n} \sum_{i=1}^{n} \inf_{|\delta_i|_\infty \le \epsilon(n)} f(v, x_i + \delta_i)$に対して、


\begin{aligned}
\lim_{n} \int_{\mathbb{R}^{m}} f(v(n), x) h^{*} dx = \inf_{v} \int_{\mathbb{R}^{m}} f(v, x) h^{*} dx.
\end{aligned}

が成立する。

不明点

 詳細は割愛するが、本論文のTheorem1、2の証明において不明な箇所があった。
-(Theorem1):$f( \hat{x}_{i} )$の定義において、$\inf$ではなく$\max$が使用されている点
-(Theorem1):$\sum_{k=1}^{n} \alpha_k f( \hat{x}_{k} ) \ge \sum_{k=1}^{n} c_k f( \hat{x}_{k} )$が成立する理由
-(Theorem2):$\frac{| S |}{n}$が導出できる箇所。($2^{m}$や$\epsilon(n)^{m}$などが消去できた理由)
-(Theorem2):最後、$\lim_n \int_{\mathbb{R}^{m}} f(v_{(n)},\mathbf{x}) h^{*} (\mathbf{x}) d\mathbf{x} = \lim_n \inf_{\tilde{\mu} \in \mathcal{P}_n} \int_{\mathbb{R}^{m}} f(v_{(n)}, \mathbf{x}) d\tilde{\mu}$より、Theorem2の式を導出できる理由

参考文献

Xu, Huan, Constantine Caramanis, and Shie Mannor. "A distributional interpretation of robust optimization." Mathematics of Operations Research 37.1 (2012): 95-110.