Wasserstein距離に基づく分布的ロバスト最適化の凸最適化問題への帰着

1. はじめに

この記事は、文献[2]の式変形の備忘録として残したものです。式番号は論文にあわせておりますのでご注意ください。

ルベーグ積分、関数解析、凸解析および測度論的確率論を勉強しはじめた段階なので、間違った理解をしているところがあると思います。見つけた際は、間違いをご指摘頂ければ幸いです。

2. Wasserstein距離とは

Wasserstein距離は、輸送問題に着想を得た分布間の距離尺度のことである。連続型分布$\mathbb{Q}:=\gamma (・)$と、離散型分布である経験分布$\mathbb{P}:=p$の間に限定して考える。

Wasserstein距離のイメージ図

図1のように、$\mathbb{P}$から$\mathbb{Q}$へと確率を移動する輸送問題を考え、単位輸送費用が$\parallel z-Y_i{\parallel }_p$で与えられた場合の最小費用がダイバージェンス$d(\mathbb{Q}|\mathbb{P})$を与える。

3. 分布的ロバスト最適化とは

事前には認知が難しい事後での不整合に対し、最悪ケースのずれがあったとしても最適解の実行可能性やある種の最適性を担保しようとする最適化モデリングをロバスト最適化という。

ロバスト最適化の比較を図に示す。

ロバスト最適化の比較

ロバスト最適化の中でも想定する確率分布の不確実性を考慮したものを分布的ロバスト最適化という。

分布的ロバスト最適化は、経験分布${\hat{\mathbb{P}}}_N$の不確実性を集合で表し、その集合の中で最悪ケースの期待コストの最小化を目指す。

$$\underset{x}{inf}\underset{\mathbb{Q}\in {\mathbb{B}}_{ϵ}({\hat{\mathbb{P}}}_N)}{sup}{\mathbb{E}}^{\mathbb{Q}}[l(\xi )]$$

不確実性集合${\mathbb{B}}_{ϵ}({\hat{\mathbb{P}}}_N)$は、下式で与えられる。

$$\begin{array}{}\text{(6)}& {\mathbb{B}}_{ϵ}({\hat{\mathbb{P}}}_N):=\{\mathbb{Q}\in \mathcal{M}(\mathrm{\Xi }):d_W({\hat{\mathbb{P}}}_N,\mathbb{Q})\le ϵ\}.\end{array}$$

経験分布${\hat{\mathbb{P}}}_N$を中心とした半径$ϵ$のWasserstein球とみることができる。

4. 最悪ケースの期待コスト問題の凸最適化問題への帰着

式(10)の最悪ケースの期待コスト問題が凸最適化問題に帰着することができることをみていく。

$$\begin{array}{}\text{(10)}& \underset{\mathbb{Q}\in {\mathbb{B}}_{ϵ}({\hat{\mathbb{P}}}_N)}{sup}{\mathbb{E}}^{\mathbb{Q}}[l(\xi )]\end{array}$$

4.1 定理１で使う道具の紹介

この節では、定理1の証明に入る前に、証明でつかう定義や補題を紹介する。
関数解析、凸解析および測度論的確率論はまだ勉強しはじめたばかりなので間違いがあればご指摘ください。

4.2 定理1の証明

$$\begin{array}{rl}\underset{\mathbb{Q}\in {\mathbb{B}}_{ϵ}({\hat{\mathbb{P}}}_N)}{sup}{\mathbb{E}}^{\mathbb{Q}}[l(\xi )]& =|\begin{array}{rl}\underset{{\mathbb{Q}}_{\mathbb{i}}\in \mathcal{M}(\mathrm{\Xi })}{sup}& {\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}l(\xi ){\mathbb{Q}}_i(d\xi )\\ \text{s.t.}& {\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}\parallel \xi -{\hat{\xi }}_i\parallel {\mathbb{Q}}_i(d\xi )\le ϵ\end{array}\\ & =\underset{{\mathbb{Q}}_{\mathbb{i}}\in \mathcal{M}(\mathrm{\Xi })}{sup}\underset{\lambda \ge 0}{inf}{\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}l(\xi ){\mathbb{Q}}_i(d\xi )+\lambda (ϵ-{\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}\parallel \xi -{\hat{\xi }}_i\parallel {\mathbb{Q}}_i(d\xi ))\\ & \le \underset{\lambda \ge 0}{inf}\underset{{\mathbb{Q}}_{\mathbb{i}}\in \mathcal{M}(\mathrm{\Xi })}{sup}{\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}l(\xi ){\mathbb{Q}}_i(d\xi )+\lambda (ϵ-{\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}\parallel \xi -{\hat{\xi }}_i\parallel {\mathbb{Q}}_i(d\xi ))(12a)\\ & =\underset{\lambda \ge 0}{inf}\underset{{\mathbb{Q}}_{\mathbb{i}}\in \mathcal{M}(\mathrm{\Xi })}{sup}\lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{\int }_{\mathrm{\Xi }}(l(\xi )-\lambda \parallel \xi -{\hat{\xi }}_i\parallel ){\mathbb{Q}}_i(d\xi )\\ & =\underset{\lambda \ge 0}{inf}\lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N\underset{\xi \in \mathrm{\Xi }}{sup}(l(\xi )-\lambda \parallel \xi -{\hat{\xi }}_i\parallel )(\because 補題2)\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(l(\xi )-\lambda \parallel \xi -{\hat{\xi }}_i\parallel )\le s_i,\mathrm{\forall }i\le N\\ & \lambda \ge 0\end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(l_k(\xi )-\underset{\parallel z_{ik}{\parallel }_{\ast }\le \lambda }{max}⟨z_{ik},\xi -{\hat{\xi }}_i⟩)\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \lambda \ge 0\end{array}\\ & \le |\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\parallel z_{ik}{\parallel }_{\ast }\le \lambda }{min}\underset{\xi \in \mathrm{\Xi }}{sup}(l_k(\xi )-⟨z_{ik},\xi -{\hat{\xi }}_i⟩)\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \lambda \ge 0\end{array}(12e)\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(l_k(\xi )-⟨z_{ik},\xi -{\hat{\xi }}_i⟩)\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \lambda \ge 0\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(l_k(\xi )-⟨z_{ik},\xi -{\hat{\xi }}_i⟩)\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(l_k(\xi )-⟨z_{ik},\xi ⟩)+⟨z_{ik},{\hat{\xi }}_i⟩\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(l_k(\xi )+⟨z_{ik},\xi ⟩)-⟨z_{ik},{\hat{\xi }}_i⟩\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(⟨z_{ik},\xi ⟩-(-l_k(\xi )))-⟨z_{ik},{\hat{\xi }}_i⟩\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& \underset{\xi \in \mathrm{\Xi }}{sup}(⟨z_{ik},\xi ⟩-(-l_k(\xi )+{\chi }_{\mathrm{\Xi }}(\xi )))-⟨z_{ik},{\hat{\xi }}_i⟩\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& [-l_k+{\chi }_{\mathrm{\Xi }}{]}^{\ast }(z_{ik})-⟨z_{ik},{\hat{\xi }}_i⟩\le s_i,\mathrm{\forall }i\le N,\mathrm{\forall }k\le K\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}\\ & =|\begin{array}{rl}\underset{\lambda ,s_i,z_{ik},v_{ik}}{inf}& \lambda ϵ+{\displaystyle \frac{1}{N}}\sum _{i=1}^N{s}_i\\ \text{s.t.}& {[-l_k]}^{\ast }(z_{ik}-v_{ik})+{\sigma }_{\mathrm{\Xi }}(v_{ik})-⟨z_{ik},{\hat{\xi }}_i⟩\le s_i\\ & \parallel z_{ik}{\parallel }_{\ast }\le \lambda \end{array}(\because 補題4)\end{array}$$

仮定4.1のもとで、式(12a)と式(12e)の不等号が等号になることを示す。仮定4.1のもとで、式(12a)は強双対性より等号が成立する。仮定4.1のもとで、minimax定理より式(12e)は等号が成立する。

よって、仮説4.1において、任意の$ϵ\ge 0$において、式(10)の最悪ケースの期待コスト問題は式(11)の凸最適化問題の最適値に等しい。